LexoRankで任意順ソートを効率的に保存する
任意順によるソート
ドラッグ&ドロップなどのUIを使ってアイテムをユーザーの任意順でソートし、データベースに保存しておきたい場合があります。
例えばToDoリストのタスク表示順などです。
この機能を実現するにはどのような実装がいいでしょうか？
方法1 Positionを使う
最初に考えつくのは、アイテムに Position のような数値を持たせることです。
| item | position |
|---|---|
| apple | 1 |
| orange | 2 |
| banana | 3 |
なんの問題もないように見えますが、アイテムをソートするときはどうなるでしょうか。
banana を 1番目に並び替えたいときに apple と orange も更新する必要があります。
| 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 という巧妙なアルゴリズムで上記の問題を解決しています。
- Position に文字列を使って並び替える
- 2つの文字列の間で平均値を求められる
- 平均値を求められない場合、バケット(後述)を使って解決する
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: |
いくつかの言語でライブラリもあるようなので、一度検討してみてはいかがでしょうか。
参考
Discussion