まだ並び順を整数で管理してるの？

※この記事は「COUNTERWORKS Advent Calendar」の6日目の記事です。

はじめまして！株式会社カウンターワークスのエンタープライズ事業部のエンジニアのはたけです！
今回はデータの任意順並び替え時によく用いられるアルゴリズムと弊社が用いているアルゴリズムを比較しながら紹介したいと思います！

任意の順番に並び替えたい

サービスを開発する上でユーザーがドラッグアンドドロップのような操作で、データを自由に並び替えたい！という要件は珍しくないものだと思います。
弊社は現在運用しているプロダクトで文字列を用いてLexoRankと呼ばれるアルゴリズムを用いた並び順をDB上で表現していますが、その特徴とメリットを一般的に用いられるアルゴリズム2つと比較して紹介します。

方法1: 整数で保存し、並び替えの度に全データを更新

position のような整数型のカラムを持たせ、並び替える度に影響があるデータ全てに対して更新を走らせる。

この方法がパッと思いついた方は少なくないのではないでしょうか。
例えば架空の商業施設を記録する buildings テーブルがあったとしましょう。

name	position
カウワクモール新宿	0
渋谷セントラル	1
六本木タウン	2

そしてユーザーがこのデータを「六本木タウン」→「カウワクモール新宿」→「渋谷セントラル」の順番に
欠番、重複が出ないように並び替えたい場合、

name	position
六本木タウン	0
カウワクモール新宿	1
渋谷セントラル	2

「六本木タウン」を末尾に移動させたいだけで、3つのデータ全てに対して更新処理をする必要があります。このように整数で並び順を表現しようとすると、並び替え時に位置が変更されるデータ全てに対して更新が走ってしまいます。

また、並び順の重複を許可しない場合は、一時的に並び順を別の値に退避して更新をかける必要があります。

    # 並び順の最大値を取得
    max_position = Building.maximum(:position) || 0
    # 並び順を退避
    Building.update_all(['position = position + ?', max_position + 1000])
    # その後変更されるデータを更新

更新自体の計算量は $O(n)$ ですが、ユニーク制約を回避するための並び順更新も考えると計算量は $O(2n)$ であることから、データ量の増加に比例した計算時間の増加が問題となるでしょう。
また、同時操作が考えられるケースではデッドロックを誘発する可能性も高く、更新に必要なペイロードも肥大化します。

方法2: 少数で保存し、対象のデータのみ並び順を計算

Fractional indexingとも呼ばれるこの方法は、並び順(position)の取りうる値を 0 < position < 1の少数として、既存データの並び順を変更せずに柔軟にデータを挿入できるアルゴリズムです。

並び替えによる更新時は以下のルールに従って並び順を決定します。

• 前後があるデータの間に並び替える場合は、前後の position の平均値を取る
• 先頭か末尾に並び替える場合は、0か1と既存データの平均値を取る

name	position
カウワクモール新宿	0.1
渋谷セントラル	0.2
六本木タウン	0.3

ここで、「渋谷セントラル」→「カウワクモール新宿」→「六本木タウン」の順番に変更する場合

name	position
渋谷セントラル	0.2
カウワクモール新宿	0.25
六本木タウン	0.3

と「カウワクモール新宿」が前後のデータの position の平均値を取ります。

また、ここからさらに末尾のデータである「六本木タウン」を先頭に並び替える場合

name	position
六本木タウン	0.1
渋谷セントラル	0.2
カウワクモール新宿	0.25

と 0 と既存データの position との平均値を取ります。

この方法は更新時に他のデータの値を変更しないため、計算量が $O(1)$ と非常に少なく、また無限に近い細かい値まで表現することができるというメリットがあります。
ただ、何度も並び替えを繰り返すと 0.000000001 といった非常に細かい間隔に値が収束してしまうため、新たに平均値を取ることができなくなってしまう場合があるので注意が必要です。(オーバーフロー^[1])

これを解決するために定期的に設定されている並び順の値を監視し、指数部が基準値を超えていないか監視、超えている場合はリバランスを実行する必要があります。

https://www.figma.com/blog/realtime-editing-of-ordered-sequences/

方法3: 文字列を用いたLexoRankアルゴリズム

LexoRankアルゴリズムとはアトラシアンの製品の一つであるJIRAに実装されたものであり、以下の特徴を持っています。

1. 文字列はアルファベット順に簡単に並べ替えることができる
2. 2つの文字列間の平均値を取ることができる(取れないこともあるが)
3. 平均値を取る方法がない場合は、バケットを使用して解決できる

1については明らかなので説明は省略させていただきます。
2についてですが
みなさんは「A」と「C」の間は何が存在するかわかりますか？
もちろん答えは「B」です。

ただこれは私たちがAの次はB、Bの次はCが来るといったアルファベット順を知っているからです。
これをシステム上で自動に文字列の間にある文字を数学的に見つける方法はあるのでしょうか？

その答えは文字コード^[2]にあります。
文字コードとは文字に割り当てられた番号のことです。
文字コードの種類によって割り当てられた番号は異なりますが、ここではASCIIコードを例に説明します。

ASCIIコード上では「A」は10進数で65,「C」は10進数で67に置き換えて表すことができます。

それでは「A」と「C」の間にある文字を数学的に探して行きましょう

まず、文字コード間の差は $67 - 65 = 2$になります。

次にコード間の差を半分にします。
$2 / 2 = 1$ですね。

そして最後に「A」に先ほど求めた1を加えると $65 + 1 =66$ となり
「A」と「C」の間の文字は文字コードが66である「B」であるということがわかります。

(「A」と「E」など他のケースでも算出できるので計算してみてください！！)

さて、では「A」と「B」の間のような平均値を取れない場合はどうすればよいのでしょうか？

ここで用いられるのがバケットと呼ばれる概念です。
(イメージとしてバケツ🪣を想像してもらえるとわかりやすいかなと思います。)

以下のようなデータがあると仮定します。

name	position
カウワクモール新宿	aaa
渋谷セントラル	aab
六本木タウン	aac

ここで、「カウワクモール新宿」→「六本木タウン」→「渋谷セントラル」の順に並び替えを行いたい場合
aaaとaab間で文字列の長さを維持しながら平均値を求めることはできません。
こういった文字間に空きがない場合は別のバケットを以下のように作成することで並び順を維持しながらデータの挿入、更新を実現することができるのです！！

name	rank
カウワクモール新宿	0|aaa
渋谷セントラル	1|aaa
六本木タウン	0|aab

ここで「0|aaa」と英数字のランクからパイプで区切られた数字をバケット番号と呼び、この数字は0がデフォルトで、0=>1=>2=>0...と循環して使用され、順序を維持するのに役立ちます。

この方法は先述した方法1,2と比べ非常に可用性が高く、データロックもかからないためパフォーマンス面でもかなり優秀なアルゴリズムだと思いました。

このアルゴリズムにさらに興味がある方は、実際にJIRAでLexoRankがどのような要素で構成されているのか解説している動画があるのでご覧ください。

https://www.youtube.com/watch?v=OjQv9xMoFbg

https://medium.com/whisperarts/lexorank-what-are-they-and-how-to-use-them-for-efficient-list-sorting-a48fc4e7849f#6c95

終わりに

LexoRankは少ない計算量でオーバーフローを考慮せず並び替えを実現することができ優秀なアルゴリズムだと思います。
再インデックス時のアルゴリズム等自分で実装するには少し難易度が高いですが色々な言語でライブラリが作成されているので、ぜひ触ってみてください！

• ruby
  • https://github.com/richardboehme/lexorank
• C#
  • https://github.com/kvandake/lexorank-dotnet
• TypeScript
  • https://github.com/kvandake/lexorank-ts

最後に、株式会社カウンターワークスでは、共に運用しやすいアプリケーション作りを考えながら事業を前進させるメンバーを募集しています！
興味のある方はぜひページ下部のリンクからご応募ください！

脚注

1. https://e-words.jp/w/オーバーフロー.html

2. https://opentype.jp/charactercode.htm