はじめに
この記事は一休.com Advent Calendar 2023 9日目の記事です。
アプリケーション開発において、ユーザーがデータを任意の順番に並び替えたいというユースケースが発生することがよくあります。
今回は、 Fractional Indexing というアルゴリズムを使って、一つのレコードを更新するだけで順番を表現できる手法を紹介したいと思います。
一般的な手法
1. レコードにIntで順番を持たせる
素朴な方法を考えると、それぞれのデータに1〜連番を振っていき、順番を変更したら番号も振り直すという手法が取られることがあります。
以下のようにpositionで順番を表現します。
| ID | NAME | POSITION |
|---|---|---|
| 1 | A | 1 |
| 2 | B | 3 |
| 3 | C | 2 |
この実装にした場合、AとCの間に新しいレコードを追加しようとすると、 C = 3 と B = 4 というように複数のレコードに新しい順番を書き込む必要があります。
件数が多くなるほど、書き込み件数も増えていきます。
2. レコードに浮動小数点で順番を持たせる
1の方法では書き込みの回数がデータ量に応じて増加するというデメリットがあったため、それを解消する方法です。
レコード間にデータを追加する時は両隣のレコードのpositionの間の数値にします。
| ID | NAME | POSITION |
|---|---|---|
| 1 | A | 1.5 |
| 2 | B | 1 |
| 3 | C | 2 |
新しいレコードを B-A 間に追加すると、 position = 1.25 と計算できるので、対象レコードのみを書き込めばOKです。
1の方法と異なり、複数のレコードを更新する必要がなくなります。
文字列で表現する Fractional Indexing
前述の2の手法は、順番を分数で表現するということで Fractional Indexing と呼ばれます。
浮動小数点で実装する方法は非常にシンプルですが、並び替えを頻繁に行うと、だんだん少数の桁数が増えていき、浮動小数点で表現できなくなる恐れもあります。
このデメリットを解消しつつ、機能提供している fractional-indexing というライブラリがありました。
大きな違いとしては、
- 表現力の大きい62進数などの数値表現を使い、文字列としてindexを表現
- indexを辞書順にソートするだけで正しい順番を得られる
- 浮動小数点での表現に比べ、桁数が対数的に増えていくので精度が落ちることがない
となっています。
アルゴリズムの詳しい説明は、こちらの記事が参考になりましたので、興味があれば。
実際に使ってみる
javascriptでnpmライブラリ fractional-indexing が実装されているので使ってみます。
import { generateKeyBetween } from 'fractional-indexing'
/**
* generateKeyBetween(a, b)
* 二つのインデックスを与えることでその間にデータを挿入した場合のインデックスを返す関数
*/
const first = generateKeyBetween(null, null) // "a0"
// 末尾に挿入したい場合は、 generateKeyBetween（末尾のindex, null）
const second = generateKeyBetween(first, null) // "a1"
// 先頭に挿入したい場合は、 generateKeyBetween（null, 先頭のindex）
const zeroth = generateKeyBetween(null, first) // "Zz"
// 要素間に挿入したい場合
const between_first_and_second = generateKeyBetween(first, second) // "a0V"
const sorted = [first, second, zeroth, between_first_and_second].sort()
// 辞書順にソートする
console.log(sorted) // [zeroth, first, between_first_and_second, second]
所感
アルゴリズム自体の実装は複雑ですが、インターフェースが使いやすく、順番変更時に1レコードの更新だけで済むのが魅力的でした。
ただ、数値に比べて文字列のソートの方がコストが高いと思うので、そこをどう考えるかだと思います。
もしデータの順番をどのように表現するか悩んでいたら、検討してみてください。
参考記事
https://observablehq.com/@dgreensp/implementing-fractional-indexing
https://www.figma.com/ja/blog/realtime-editing-of-ordered-sequences/