【TS】バージョン比較用関数について

Zennデビュー記事です。

はじめに

Zennにユーザ登録して早速目に留まったのが、以下の記事でした。

• アルゴリズムのせいで面接に落ちた

とある大企業の採用プロセスについてと、最終的に不採用の原因となった「ソートアルゴリズム」についての記事となっています。

日本国内とはいえ、転職を考えている身として色々考えるところがあったのですが、開発者である自分が気になったのは課題として出された「バージョンの比較処理」についてです。

お題

元記事中のお題は以下の通りでした。
0.1.0や3.2.1など一般的とされているバージョンを比較して正しい順番に並べ替えるプログラムを完成させよ、というものです。

// index.js
/*
We have lots of deployment dashboards where we have drop-down UI to select an application version to deploy. We want to ensure that software version numbers delivered to our UI from the back-end API are always ordered with the newest (highest) available version at the top.

Eg:
const input = [0.1.0, 3.2.1, 2.2.3, 0.1.1];
sortVersions(input) should return [3.2.1, 2.2.3, 0.1.1, 0.1.0];
*/

const sortVersions = (unsortedVersions) => {
  // code
};

export default sortVersions;

続いて動作確認用テストファイル。

// index.test.js
import sortVersions from './index';

it('should sort correctly numbered versions', () => {
  const versions = ['0.2.0', '3.1.2', '0.1.6', '5.0.0'];
  const output = ['5.0.0', '3.1.2', '0.2.0', '0.1.6'];
  expect(sortVersions(versions)).toEqual(output);
});

// Other assertions

元記事中の回答

このお題に対して、筆者の方は以下のようなコードを書いています。

const sortVersions = (unsortedVersions) => {
  // code
  return unsortedVersions.sort().reverse();
};

実にシンプルでいいと思います。
しかしながらこのコードでは不完全で、次のテストコードでは期待する結果になりません。

// index.js

it('should sort correctly numbered versions with different lengths', () => {
  const versions = [
    '1.3.0.9',
    '0.2.0',
    '3.1.2',
    '0.1.6',
    '5.0.0',
    '3.3.3.3',
    '3.3.3.3.3',
    '3.10',
    '0.2.0',
  ];

  const output = [
    '5.0.0',
    '3.10',
    '3.3.3.3.3',
    '3.3.3.3',
    '3.1.2',
    '1.3.0.9',
    '0.2.0',
    '0.2.0',
    '0.1.6',
  ];

  expect(sortVersions(versions)).toEqual(output);
});

なぜかというと、"x.x.x.x"のような文字列型のままソートをかけると1文字ずつ文字コードでのソートが走ってしまうため、例えば"3.3"と"3.10"を比較した場合に、"3,3" > "3.10"と判定されてしまいます。

模範回答

最終的に筆者はStackOverflowのこの回答がベストだと語っています。

// Return 1 if a > b
// Return -1 if a < b
// Return 0 if a == b
function compare(a, b) {
    if (a === b) {
       return 0;
    }

    var a_components = a.split(".");
    var b_components = b.split(".");

    var len = Math.min(a_components.length, b_components.length);

    // loop while the components are equal
    for (var i = 0; i < len; i++) {
        // A bigger than B
        if (parseInt(a_components[i]) > parseInt(b_components[i])) {
            return 1;
        }

        // B bigger than A
        if (parseInt(a_components[i]) < parseInt(b_components[i])) {
            return -1;
        }
    }

    // If one's a prefix of the other, the longer one is greater.
    if (a_components.length > b_components.length) {
        return 1;
    }

    if (a_components.length < b_components.length) {
        return -1;
    }

    // Otherwise they are the same.
    return 0;
}

自分自身も確かに数字のみのバージョンならこれがベストかなと思っています。
記事中で細かい解説がされていなかったため、自分なりに分かりやすく噛み砕いた内容を解説しようと思います。
※普段Typescriptでコーディングしているので、Typescriptで記載します。

模範回答(Typescript版)

/**
 * バージョン文字列比較処理
 * @description 数値のみ、もしくは「.」区切りの数値を対象とする
 */
export const compareVersion = (a: string, b: string): number => {
    if (a === b) {
      return 0;
    }

    // バージョンを"."でユニットに切り分ける
    const aUnits = a.split(".");
    const bUnits = b.split(".");

    // ユニット数が少ない方の表記に探索幅を合わせる
    const len = Math.min(aUnits.length, bUnits.length);

    // 探索幅に従ってユニット毎に比較していく
    for (var i = 0; i < len; i++) {
        // A > B
        if (parseInt(aUnits[i]) > parseInt(bUnits[i])) return 1;
        // B > A
        if (parseInt(aUnits[i]) < parseInt(bUnits[i])) return -1;
    }
    
    // 個々のユニットが完全に一致している場合はユニット数が多い方が大きいとする
    if (aUnits.length > bUnits.length)　return 1;
    if (aUnits.length < bUnits.length) return -1;

    // 上記の処理で判定仕切れない場合は同一とみなす
    return 0;
}

関数・変数名は分かりやすいものに差し替えています。
以下、解説です。

"."でバージョンを切り分ける

まず、バージョンを"."で区切った配列にします。
メジャーバージョンから順番に数値型で比較するために前処理になります。

// バージョンを"."でユニットに切り分ける
const aUnits = a.split(".");
const bUnits = b.split(".");

表記が短い方に合わせる

続いて、分割した配列の幅を比較して短い方の値を取得します。
例えば"3.3.10"と"3.3.10.2"のように表記の長短に差があるバージョンを比較する場合に、短い方に合わせるためです。
ちなみに"3.3.3"と"3.3.3.0"というバージョンを比較した場合は"3.3.3.0"の方がバージョンが高いと判定されます。

// ユニット数が少ない方の表記に探索幅を合わせる
const len = Math.min(aUnits.length, bUnits.length);

順番にバージョンを比較

メジャーバージョンから順番に比較していきます。
上位のバージョンに差異があり、大小が定まった場合はここで処理が終了します。

// 探索幅に従ってユニット毎に比較していく
for (var i = 0; i < len; i++) {
    // A > B
    if (parseInt(aUnits[i]) > parseInt(bUnits[i])) return 1;
    // B > A
    if (parseInt(aUnits[i]) < parseInt(bUnits[i])) return -1;
}

表記の長短を比較

各バージョンを突合しても大小が決まらない場合、表記の長い方を大とします。
従って、"."で分割した配列のlengthを比較しています。

最後のreturn 0;に流れてくるパターンは例外に近いケースです。

// 個々のユニットが完全に一致している場合はユニット数が多い方が大きいとする
if (aUnits.length > bUnits.length)　return 1;
if (aUnits.length < bUnits.length) return -1;

// 上記の処理で判定仕切れない場合は同一とみなす
return 0;

感想・改めて問題を眺めてみて

順番に処理を追ってみれば特別なことはしておらず、比較的簡単な記述に終始しているように思えます。
ただ、いきなり問題を出されてこの回答ができるかどうかと聞かれたら微妙なところです。

加えて、この問題の後に追加の問題がある可能性もあります。
例えば"2.5.4.a"のように数値以外のバージョンを考えた場合などが挙げられます。
その場合、["a","b","c","d", ... "z"]のように文字列表記のバージョンの順番を定義した配列を用意しておき、その配列にindexOf()で問い合わせを行って比較する等すればいけるかと思いますが、もっとスマートな解法があるような気もします。

20201116.追記

@standard softwareさん、@rithmetyさんよりコメントをいただきました。

• 参考：Qiita | バージョン情報ソートができないと面接に落ちるので解答しとく

文字列込みのバージョンに対しても正常に動作する処理を紹介させていただきます。
localeCompareを利用した方法です。

• 参考：MDN | localeCompare

const sortVersions = (unsortedVersions: string[]) => {
  return unsortedVersions
    .slice()
    .sort((q, w) => w.localeCompare(q, [], { numeric: true }))
}

// 文字列込みのバージョン
const versions = [
    '5.0.0.',
    '1.3.0.9',
    '0.2.0',
    '3.1.2',
    '0.1.6',
    '5.0.0',
    '3.3.3.3',
    '3.3.3.3.3',
    '3.10',
    '0.2.0',
    '0.2.0a',
    '0.2.0aa',
    '0.2.0AA',
    '0.2.0Aa',
    '0.2.0aA',
    '0.2.0c',
    '0.2.0b',
    '0.2.0A',
    '0.2.0C',
    '0.2.0B',
    '0.2.0.a',
    '0.2.0.c',
    '0.2.0.b',
    '0.2.0.A',
    '0.2.0.C',
    '0.2.0.B',
    '5.0.0.',
    '5.0.0.0',
  ];

console.log(sortVersions(versions));

出力

[ '5.0.0.0',
  '5.0.0.',
  '5.0.0.',
  '5.0.0',
  '3.10',
  '3.3.3.3.3',
  '3.3.3.3',
  '3.1.2',
  '1.3.0.9',
  '0.2.0C',
  '0.2.0c',
  '0.2.0B',
  '0.2.0b',
  '0.2.0AA',
  '0.2.0Aa',
  '0.2.0aA',
  '0.2.0aa',
  '0.2.0A',
  '0.2.0a',
  '0.2.0.C',
  '0.2.0.c',
  '0.2.0.B',
  '0.2.0.b',
  '0.2.0.A',
  '0.2.0.a',
  '0.2.0',
  '0.2.0',
  '0.1.6' ]