📑

LexoRankで任意順ソートを効率的に保存する

2021/10/03に公開約2,200字

任意順によるソート

ドラッグ&ドロップなどのUIを使ってアイテムをユーザーの任意順でソートし、データベースに保存しておきたい場合があります。
例えばToDoリストのタスク表示順などです。

この機能を実現するにはどのような実装がいいでしょうか?

方法1 Positionを使う

最初に考えつくのは、アイテムに Position のような数値を持たせることです。

item position
apple 1
orange 2
banana 3

なんの問題もないように見えますが、アイテムをソートするときはどうなるでしょうか。
banana を 1番目に並び替えたいときに appleorange も更新する必要があります。

item position
banana 1
apple 2
orange 3

アイテムが増えれば増えるほど、1つのアイテムをソートするためだけに更新しなければならないレコードが増加してしまいます。
そこで次のようなアプローチはどうでしょうか。

方法2 Positionの値を大きくする

item position
apple 100
orange 200
banana 300

このように Position の値を大きくして間隔に余裕をもたせます。
すると任意のアイテムをソートするときは、挿入先の Position を計算して1レコードを更新するだけでソートが完了します。

item position
apple 100
banana 150
orange 200

Position には100の間隔を設けているので、99アイテムを間に挿入することができます。
もっと間隔を大きくすれば良いのですが、データサイズが無駄に大きくなってしまいます。

本題 Lexorank

アトラシアンの JIRA では、 LexoRank という巧妙なアルゴリズムで上記の問題を解決しています。

  1. Position に文字列を使って並び替える
  2. 2つの文字列の間で平均値を求められる
  3. 平均値を求められない場合、バケット(後述)を使って解決する

Lexorank は上記に基づいて、効率的にソートを実現します。

item position
apple a
orange b
banana c

文字列を使って並び替えをするのは簡単です。
そして平均を求めるときは、以下のように考えればできます。

  • アルファベットには文字コードがあるので "a" は 97 で、 "c" は 99 で表されます
  • "a" と "c" の間を求めたい場合は 99 - 97 = 2 になります
  • 結果の 2 を半分にすると、 1 になります。
  • "a" に 1 を加えると "b" の文字コードが得られます

では2つの文字列の間に空きがない場合はどうすればよいか。
このためにバケットを使います。

item position
apple 0|a
banana 1|a
orange 0|b

バケットは文字列の前に置かれ、0 がバケット番号です。
文字列間に空きがないときは別のバケットを作成することによって順序を維持することができます。

Lexorank

なお上記はサンプルのため、実際はこのようになります。

item position
apple 0|100000:
orange 0|100008:
banana 0|10000g:
grape 0|10000o:
cherry 0|10000w:

いくつかの言語でライブラリもあるようなので、一度検討してみてはいかがでしょうか。

https://www.npmjs.com/package/lexorank

参考

https://medium.com/whisperarts/lexorank-what-are-they-and-how-to-use-them-for-efficient-list-sorting-a48fc4e7849f
https://stackoverflow.com/questions/9536262/best-representation-of-an-ordered-list-in-a-database/49956113

Discussion

ログインするとコメントできます