🔃
【JavaScript】SortedSetお手軽実装

2024/08/24に公開
 はじめにJavaScriptでは、標準組み込みオブジェクトであるSetを使うことで、簡単に集合を表現することができます。しかし事前に並び替えられた集合（ソート済み集合／SortedSet）を表現するのは一筋縄ではいきません。そもそも並び替えとは適切に実装できないとパフォーマンスが悪くなりがちな処理です。要素が追加されるたびにすべての要素を並び替え直していてはダメです。それゆえに、木構造のような複雑で強力なデータ構造を活用することになります。並び替えられた状態で値を保存しておく仕組みが言語に標準で組み込まれていたら……。

 実はオブジェクトのプロパティキーは並び替えられているJavaScriptの言語仕様（ECMAScript）では、オブジェクトのプロパティキー取得時の並び替えについて次のように定義されています。
https://tc39.es/ecma262/#sec-ordinaryownpropertykeys
（雑意訳）
プロパティキーのリストを得る処理では次の手順が実行されます。
まず空のリストを作ります
配列インデックスとして解釈されるプロパティキーについて、数値として昇順にリストに追加します
文字列として解釈されるプロパティキーについて、プロパティ作成タイムスタンプで昇順にリストに追加します
シンボルとして解釈されるプロパティキーについて、プロパティ作成タイムスタンプで昇順にリストに追加します
リストを返します
どういうことかというと、こういうことです：
const obj = {};

obj[1] = "a";
obj[3] = "c";
obj[2] = "b";

console.log([...Object.entries(obj)]);
// [["1", "a"], ["2", "b"], ["3", "c"]]
この仕様を活用すれば、並び替えや要素が追加されたときの更新といった難しい部分を、JavaScriptエンジンに丸投げできます。手軽に高い効率を得られることが期待できます。

 SortedSetを実装してみる任意の型の値とそれに対応した符号なし整数で表されるスコアを与えられ、それをソートされた状態で持っておくようなクラスをTypeScriptで実装してみます。
export class SortedSet<T> {
  // 実際に値を保存しておくオブジェクト
  // 並び替えはJavaScriptエンジンがよしなにやってくれる
  private readonly data: Record<number, T> = Object.create(null);

  // 効率的な値の削除を実装するには、値とスコアの関係が保存されている必要がある
  // Mapは任意のキーで任意の値を得る操作について最適化されているため、こういった用途にはうってつけ
  private readonly index = new Map<T, number>();

  public add(value: T, score: number): void {
    this.delete(value);
    this.data[score] = value;
    this.index.set(value, score);
  }

  public delete(value: T): void {
    const score = this.index.get(value);

    if (score !== undefined) {
      delete this.data[score];
      this.index.delete(value);
    }
  }

  public *[Symbol.iterator](): Iterator<[T, number]> {
    yield* Object.entries(this.data).map<[T, number]>(([score, value]) => [
      value,
      parseInt(score),
    ]);
  }
}
この実装では、あるスコアに対して1つの値しか持てないという制約はありますが、ソート済み集合をとてもシンプルに実現できています。
もしスコアが同じ複数の値を扱えるようにしたいなら、dataプライベートプロパティをRecord<number, T[]>型などにすればいいでしょう。スコアが同じ複数の値をどう並び替えるかという問題は発生しますし、同じスコアで大量の値が追加されてしまった場合の効率を考える必要も出てきますが……。

 おわりにJavaScriptなんもわからん。
はじめに

実はオブジェクトのプロパティキーは並び替えられている

SortedSetを実装してみる

おわりに

Discussion
