Node.jsでデータを自由自在かつ効率的にソートする

こんにちは。データアナリティクス事業本部の松村です。

前回の投稿ではPythonでのデータソートについて調べましたが、本当にやりたかったのは比較関数を使ってスマートにソートすることでした。さらに比較関数をC#/LINQのOrderBy、ThenByのようなメソッドチェーンで作れたらカッコいいなと。

結局比較関数を使用したソートがあまりにも遅いので断念しましたが、今度はNode.jsで同じことを試してみたいと思います。
Node.jsといえばスクリプト言語らしからぬ実行速度が大きな長所ですので、比較関数の遅さに足をひっぱられるようなことはないでしょう。

やりたいこと／目指す形

C#だと、LINQを使ってこんな形で複数ソートキーによるソートを自在に行うことができます。

list
    .OrderBy(item => item.x)
    .ThenByDescending(item => item.y)
    .ThenBy(item => item.z);

ソートキーがいくつあっても、昇順／降順が入り混じっていても、全部メソッドチェーンで繋げるだけです。
OrderBy()などのメソッドは、チェーンで繋げられたソート操作のみを記憶したIOrderedEnumerableオブジェクトを返し、実際のソート処理はforeachなどによる列挙時に初めて実行されます（遅延実行と呼びます）。なので無駄がありません。

Node.jsでLINQにできるだけ近付けて書くとしたら、こんな感じになるでしょうね。

list.sort(
    orderBy(item => item.x)
    .thenByDescending(item => item.y)
    .thenBy(item => item.z)
    .comparer
);

Node.jsには遅延実行のような仕組みは少なくとも標準では存在しません。替わりにArray.prototype.sort()に渡すための比較関数をメソッドチェーンで構築することで、実際のソート処理を1回に抑える、という仕掛けです。これを作ります。

自分で作る、その前に

実は、LINQにできるだけ近く、ではなく、LINQ（正確にはLINQ to Objects）を遅延実行まで含めてそっくりそのまま忠実に再現したライブラリが存在しています。その名もlinq.js。もうそのまんまですね。

ES2015が登場するよりもずっと前から存在していて、その頃にお世話になった方も多いと思います。私もそのひとりです。
今はArrayにmap()、filter()、reduce()があるので、それである程度の事はできるようになりましたが、リッチなコレクション操作が必要な場面であれば依然強力なツールです。

が、今回はソートをしたいだけなので、こちらは紹介だけに留めて標準機能だけで何とかしてみましょう。この後すぐコードを提示しますが、ほんの数十行でできます。

動的な比較関数の構築

これがLINQ的なメソッドチェーンで動的に比較関数を構築するコードです。

function compareAscending(a, b) {
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;
    } else {
        return 0;
    }
}

function compareDescending(a, b) {
    return compareAscending(b, a);
}

function orderBy(valueGetter) {
    return orderByCore(valueGetter, compareAscending);
}

function orderByDescending(valueGetter) {
    return orderByCore(valueGetter, compareDescending);
}

function orderByCore(valueGetter, func) {
    const builder = {};
    builder.comparer = function (a, b) {
        return func(valueGetter(a), valueGetter(b));
    };

    const thenByCore = function (valueGetter, func) {
        const comparer = builder.comparer;
        builder.comparer = function (a, b) {
            return comparer(a, b) || func(valueGetter(a), valueGetter(b));
        };
        return builder;
    };

    builder.thenBy = function (valueGetter) {
        return thenByCore(valueGetter, compareAscending);
    };

    builder.thenByDescending = function (valueGetter) {
        return thenByCore(valueGetter, compareDescending);
    };

    return builder;
}

これだけです。モジュールにするならorderBy()とorderByDescending()だけ公開しておけばよいです。
では実際に使ってみましょう。

const list = [];

for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
        for (let k = 0; k < 2; k++) {
            list.push({ x: i, y: j, z: k });
        }
    }
}

list.sort(
    orderBy(item => item.z)
    .thenByDescending(item => item.y)
    .thenBy(item => item.x)
    .comparer
);

for (const item of list) {
    console.log(item);
}

zの昇順、yの降順、xの昇順でソートしています。
結果はこちら。

{ x: 0, y: 1, z: 0 }
{ x: 1, y: 1, z: 0 }
{ x: 0, y: 0, z: 0 }
{ x: 1, y: 0, z: 0 }
{ x: 0, y: 1, z: 1 }
{ x: 1, y: 1, z: 1 }
{ x: 0, y: 0, z: 1 }
{ x: 1, y: 0, z: 1 }

ちゃんと狙い通りにソートされていますね。

少しだけ解説

短いコードですし、とりたてて高度なこともしていないので、読めばだいたい仕組みは分かると思いますが、一点だけ。

    const thenByCore = function (valueGetter, func) {
        const comparer = builder.comparer;
        builder.comparer = function (a, b) {
            return comparer(a, b) || func(valueGetter(a), valueGetter(b));
        };
        return builder;
    };

これがthenBy()やthenByDescending()の本体であり、比較関数を動的に構築している箇所です。メソッドチェーンするごとに呼び出され、ソートキーを追加します。
32行目は、それまでに構築した比較関数をコールバックして、0でなければ（それまでに指定したソートキーで大小が確定すれば）その値をそのまま返し、0であれば（大小が確定しなければ）追加されたソートキーで比較を行う、という処理を1行で書いたものです。この||演算子の使い方はJavaScriptでよくあるイディオムですね。

あくまで簡略化したイメージですが、メソッドチェーンするごとに、以下のreturn 0;の部分に新しいソートキーによる比較処理を差し込んでいく、という感じでしょうか。

if (a < b) {
    return -1;
} else if (a > b) {
    return 1;
} else {
    return 0;
}

計測してみる

100万件での処理速度も計測してみましょう。Node.jsは実行速度が売りですから、このぐらいは軽くこなしてくれそうですが、果たしてどうでしょう。
実行環境はMacBook Pro (13-inch, 2019, Four Thunderbolt 3 ports)／第8世代クアッドコア Core i5 2.4GHz／Node.js v12.16.2です。

const { performance } = require('perf_hooks');
const list = [];

for (let i = 0; i < 100; i++) {
    for (let j = 0; j < 100; j++) {
        for (let k = 0; k < 100; k++) {
            list.push({ x: i, y: j, z: k, shuffleKey: Math.random() });
        }
    }
}
list.sort(orderBy(item => item.shuffleKey).comparer);

const start = performance.now();
list.sort(
    orderBy(item => item.z)
    .thenByDescending(item => item.y)
    .thenBy(item => item.x)
    .comparer
);
const duration = performance.now() - start;

console.log(duration / 1000);

Arrayに標準でシャッフルする機能が付いていないので、データ初期化時にシャッフル用の乱数を追加し、先にそれでソートしています。seedが指定できないので実行のたびにシャッフルした結果が変わってしまいますが、そこは目をつぶります。
3回実行した結果がこちらです。

duration: 2.0569663529992104 sec.
duration: 2.1238859220147135 sec.
duration: 2.010219173014164 sec.

うーん、ちょっと微妙、な気もしますが、なんとか許容範囲でしょうか？
こんなふうにして、複数キーによるソートを直感的に書くことができます。

LINQへのこだわりを捨てる

許容範囲、とは言いましたが、やっぱりもう一声欲しいですね。Pythonだとタプルによる複数キーでの100万件ソートが1.3秒ぐらいでしたので。
そもそもNode.jsで大量データをソートする機会がどれだけあるんだ、という話ではありますが、ちょっとした見直しで改善できるならしたいです。別に黒魔術に頼ろうというわけではなく。

ボトルネックはどこでしょう。最終的に出来上がった比較関数が、コールバック関数の入れ子になってしまっているので、そのせいでしょうか。
先程計測したコードで構築された比較関数って、じっくり考えて書き起こすと実はこんなんなんです。

function compare(a, b) {
    return function (a, b) {
        return function (a, b) {
            return compareAscending((item => item.z)(a), (item => item.z)(b));
        }(a, b) || compareDescending((item => item.y)(a), (item => item.y)(b));
    }(a, b) || compareAscending((item => item.x)(a), (item => item.x)(b));
};

見た目のインパクトが凄いですね。これじゃちょっと遅いのも無理はない気がします。何とかしたい、というかできればこんな比較関数を構築したいです。

function compare(a, b) {
    return compareAscending(a.z, a.z)
        || compareDescending(a.y, a.y)
        || compareAscending(a.x, a.x);
};

でも言うほど簡単じゃないというか、実装方法の手掛かりすらわかりません。コールバックに頼らず||を繋げるというのが超難関なんです。JavaScriptにもC#のExpressionTreeのように構文木で組み上げたコードをコンパイルできる仕組みがあれば良いのですが、そんなものもなく、もはや黒魔術が必要になってくる気がします。

あ、でもよく考えたらこれをこのまま手書きすれば良いのでは？簡潔でさえあればLINQにこだわる必要なんてないんです。

というわけで部品側を書き直したのがこちらです。

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

function asc(a, b, valueGetter) {
    return valueGetter
        ? compare(valueGetter(a), valueGetter(b))
        : compare(a, b);
}

function desc(a, b, valueGetter) {
    return valueGetter
        ? compare(valueGetter(b), valueGetter(a))
        : compare(b, a);
}

さらにコンパクトになりました。関数名もちょっとスッキリさせてみました。
動作確認結果は省略して（もちろん確認自体はしており、ちゃんと指定通りにソートされます）、計測用のコードで使い方を見てみましょう。

const { performance } = require('perf_hooks');
const list = [];

for (let i = 0; i < 100; i++) {
    for (let j = 0; j < 100; j++) {
        for (let k = 0; k < 100; k++) {
            list.push({ x: i, y: j, z: k, shuffleKey: Math.random() });
        }
    }
}
list.sort((a, b) => asc(a.shuffleKey, b.shuffleKey));

const start = performance.now();
list.sort(
    (a, b) => asc(a.z, b.z) || desc(a.y, b.y) || asc(a.x, b.x)
);
const duration = performance.now() - start;

console.log(`duration: ${duration / 1000} sec.`);

これまでと同じように、zの昇順、yの降順、xの昇順でソートしています。LINQのようなメソッドチェーンではありませんが、先入観がなければむしろこちらの方が見やすいのかもしれません。
3回実行した結果はこちら。

duration: 1.1840224100351333 sec.
duration: 1.138292612016201 sec.
duration: 1.2355729880332946 sec.

半分とまではいきませんでしたが、いい感じですね。

ちなみにascやdescはオプショナル引数でソートキー取得関数を渡せます。例えばzに文字列セットされていて、大文字小文字を同一視してソートしたい場合、こんなふうに書くことができます。

list.sort(
    (a, b) => asc(a, b, item => item.z.toUpperCase()) || desc(a.y, b.y) || asc(a.x, b.x)
);

ただし、比較関数は(n log n)回呼び出されるので、データ件数が多い場合は、ソートを行う前にソートキーを取得してプロパティに追加しておくことをお勧めします。

最後に

最初に目指したものとは違ってしまいましたが、処理速度、読みやすさともにそれなりに満足の行く形でNode.jsのソートを書くことができました。機会があれば実戦投入してバリバリ使っていこうと思います。