リスト内のアイテムのドラッグアンドドロップは、最近のアプリケーションで人気のある機能であり、その存在はユーザーを喜ばせるだけです。ただし、このような機能を実装するときは、不適切な最適化のレーキを踏まないようにする必要があります。多数の要素、毎回の位置の再計算、リストに複数のセクションがある場合、セクション間でドラッグする場合は、追加のロジックを実装する必要があります。額に当たらないようにする方法、計算の数を減らす方法、およびレキソランがこれをどのように支援するか-カットの下をお読みください。
問題を定義しましょう
したがって、アプリケーションにドラッグアンドドロップ機能を追加することにしました。そのため、何らかの方法で要素をソートする必要があります。そうしないと、ドラッグアンドドロップしても意味がありません。そして、最初に頭に浮かぶのは何ですか？
ポジション
最も一般的な目立たない位置。同じ数字が1から無限大まで（実際にはありません）それらを使用するのは簡単で便利です。要素は問題なくソートされます。一見、すべてが順調です。ほとんどのアプリケーションにとって、これが必要なものです。
では、数値の位置の何が問題になっていますか？
問題は関連する操作にあります。 2番目と3番目の要素の間に要素を挿入する必要がありますか？データベースのデータを更新することを忘れないで、3番目の要素から始めて、すべてを1つ前にシフトします。このような操作を1回実行することは難しくありませんが、この操作は頻繁に実行されます。
別の問題のある操作は、サーバー上のデータの更新です。タスクを更新しました-影響を受けるすべてのタスクの更新をサーバーに送信する必要があります。サーバーは、この更新をタスクリストに「サブスクライブ」しているすべてのユーザーに送信する必要があります。ユーザーがリスト内のタスクの順序を並べ替える頻度が高いほど、サーバーに送信する必要があるデータが多くなり、サーバーがクライアントに送信する必要があるデータが多くなります。
1つのタスクをドラッグすると、多数の要素の位置が変更されるだけでなく、それらがサーバーに送信され、他のユーザーに送信されることがわかりました。
結論：より最適なものが欲しい
ソリューションオプション
社内で同様の問題が発生した場合、最初の解決策は次のアルゴリズムでした。標準的な位置にあるすべての要素を等間隔（ステップ）に配置します。したがって、最初の要素の位置は1になり、2番目の要素の位置は-1000になります。ユーザーがこれら2つの要素の間に何かをドラッグしたい場合、平均位置-（1000 + 1）/ 2 =〜500を計算します。などなど。
なぜこのオプションが悪いのか、すぐに推測したと思います。実行できる手順の数には制限があります。それら。 1から1000-500まで。1から500-250まで。その後125 ...そして最終的にはスペースがなくなります。ステップを増やしても、この問題は解決しません。
小数を使用できますか？
いいえ、小数は問題を解決しませんが、出現の瞬間を遅らせるだけです。
少し考えてグーグルで調べたところ、Jiraでのレキソランの使用方法に関するレポートが見つかりました（Lexorank、レポート）。
それらは3つのことに基づいています：
1-文字列をアルファベット順にソートするのは簡単
です2-2つの文字列の間の中央の文字列を見つけることができます（常にではなく、これはそれほど簡単ではありません）
3- 中央の文字列を見つけることができませんか？バケツを使ってみましょう（奇妙に聞こえます、はい）
。並べ替えがすべて明確になったら、ポイント番号2に直接移動します。
英語のアルファベットには、「a」と「c」の文字があり、その間に明らかに「b」があります。しかし、この「b」を数学的に見つける方法は？
文字 "c"のコードから文字 "a"のコードを引くと、2になります（ "c" = 143、 "a" = 141）。結果を半分に分割することは残ります。確かに、コード「a」に1を追加すると、文字「b」のコードが取得されます。
英語の文字の組み合わせをレクソランと呼びます
。2行の間にスペースがなく、場所もある場合、それらを解決するためにバケツを使うことはすでに書いています。
バケットは、ランクの前のラベルで、「0 | aaa」のようになります。ここで0はバケット番号です。部屋が残っていない場合、要素はバケット間で移動され、ラベルは順番に再配置されます。それはすべての魔法です！
それをどのように利用したか
2つの中間線を見つけるのがいかに簡単で痛みがないかについては、正確には言われていません（むしろ、単に見つかりませんでした）。それで私たちは緊張してこれを思いつきました。すぐに例を見てみましょう。
「aa」と「cc」の2つの行を取り、それらの間の真ん中の行を見つけます。
上記のように記号で減算すると、11になりますが、次に何をするのでしょうか。 「aa」行に結果を追加するだけでよいと思うかもしれません。ここで、文字列「bb」は実際には「aa」と「cc」の間にあることがわかりますが、アルゴリズムは正しくありません。ここで、その理由を確認します。
それがどのように見えるか考えてみましょうか？ 「Aa」、「cc」、「11」。ある種の数体系。何の上に？そして26日！どうして？英語のアルファベットには26文字あるからです。以上です。
結果の "11"を26進法から通常の10進法に変換する必要があります。
式は非常に単純である：
X = Y 0 + Y 1つの *サイズ+ Y 2 *サイズ^ 2 ... Y N *サイズ^ （N-1）
ここで、サイズがを表し、 "サイズ"数システム（この場合、サイズ= 26）の
Y N -右側のn番目の数値
この式を、たとえば式1として覚えておいてください。
数値を代入すると、2 + 2 * 26 = 54になります。これで、行「aa」と「cc」の間に何文字あるかがわかります。しかし、2つの間の平均を取る必要があります。 54を2で割ると27になります。「aa」コードに結果を正しく追加するだけです。
どうやってするの？最初に、最初の（右）文字にどれだけ追加するかを調べます。これを行うには、27を26で割った余りを取得します。結果は次のとおりです。1.「a」に1を追加します。「b」の文字が得られます。
次に、2番目の文字をシフトするための文字数を調べる方法を考える必要があります。
ここでは、次の式が役立ちます
。X = Y /サイズ^ （n-1）％サイズ
この式により、特定の場所（文字、nを使用して指定）に追加する必要がある量を見つけることができます。
そこですべてを代入すると、（n = 2）が得られます：（27/26）％26 = 1.追加。最終結果「bb」が得られます。
アルゴリズムがどのように機能するかを正確に理解している場合、プログラミング言語でアルゴリズムを実装することはそれほど難しくありません。以下に、Dartでアルゴリズムの実装を追加しました（この問題が発生したアプリケーションはFlutterで記述されています）。
「中間」行を見つけるための私たちの実装
String getRankBetween({@required String firstRank, @required String secondRank}) {
assert(firstRank.compareTo(secondRank) < 0, "First position must be lower than second. Got firstRank $firstRank and second rank $secondRank");
/// Make positions equal
while (firstRank.length != secondRank.length) {
if (firstRank.length > secondRank.length)
secondRank += "a";
else
firstRank += "a";
}
var firstPositionCodes = [];
firstPositionCodes.addAll(firstRank.codeUnits);
var secondPositionCodes = [];
secondPositionCodes.addAll(secondRank.codeUnits);
var difference = 0;
for (int index = firstPositionCodes.length - 1; index >= 0; index--) {
/// Codes of the elements of positions
var firstCode = firstPositionCodes[index];
var secondCode = secondPositionCodes[index];
/// i.e. ' a < b '
if (secondCode < firstCode) {
/// ALPHABET_SIZE = 26 for now
secondCode += ALPHABET_SIZE;
secondPositionCodes[index - 1] -= 1;
}
/// formula: x = a * size^0 + b * size^1 + c * size^2
final powRes = pow(ALPHABET_SIZE, firstRank.length - index - 1);
difference += (secondCode - firstCode) * powRes;
}
var newElement = "";
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
} else {
difference ~/= 2;
var offset = 0;
for (int index = 0; index < firstRank.length; index++) {
/// formula: x = difference / (size^place - 1) % size;
/// i.e. difference = 110, size = 10, we want place 2 (middle),
/// then x = 100 / 10^(2 - 1) % 10 = 100 / 10 % 10 = 11 % 10 = 1
final diffInSymbols = difference ~/ pow(ALPHABET_SIZE, index) % (ALPHABET_SIZE);
var newElementCode = firstRank.codeUnitAt(
secondRank.length - index - 1) + diffInSymbols + offset;
offset = 0;
/// if newElement is greater then 'z'
if (newElementCode > 'z'.codeUnits.first) {
offset++;
newElementCode -= ALPHABET_SIZE;
}
newElement += String.fromCharCode(newElementCode);
}
newElement = newElement
.split('')
.reversed
.join();
}
return newElement;
}
しかし、それだけではありません
いずれにせよ、それがすべてではありませんでした。すでにリリースされているアプリケーションにこの機能を追加したため、移行が必要でした。SQLのマイグレーションの作成は問題ありませんが、標準ランクの計算はそれほど簡単ではありません。しかし、中央の列がどのように配置されているかを知っていると、これを行うのは難しくありません。アルゴリズムは次のようになります。
- 間隔の開始と終了を設定します（ここでは、これらはそれぞれ「aaa」と「zzz」です）
- 行間の異なる文字の組み合わせの数を数えます。ここでは、式1が役立ちます
- ここで、結果をリスト内の可能な最大要素数で割ります
- したがって、ステップがあり、初期位置があります。初期位置にステップを追加し、ランクを取得してから、このランクにステップを追加し、新しいランクを取得してから、もう一度ステップを追加するなどの処理が残ります。
ダートでも同じです。forNumOfTasksパラメータは、取得するポジションの数を担当します。要素が3つしかないリストの位置を下に置くと、リスト全体の位置（50、100など）を計算しても意味がありません。
「デフォルト」ランク検索の実装
/// modify field forNumOfTasks to get certain number of positions
List‹String› getDefaultRank({int forNumOfTasks = TASK_FOR_PROJECT_LIMIT_TOTAL}) {
final startPos = START_POSITION;
final endPos = END_POSITION;
final startCode = startPos.codeUnits.first;
final endCode = endPos.codeUnits.first;
final diffInOneSymb = endCode - startCode;
/// x = a + b * size + c * size^2
final totalDiff = diffInOneSymb + diffInOneSymb * ALPHABET_SIZE + diffInOneSymb * ALPHABET_SIZE * ALPHABET_SIZE;
/// '~/' – div without remainder
final diffForOneItem = totalDiff ~/ (TASK_FOR_PROJECT_LIMIT_TOTAL + 1);
/// x = difference / size^(place - 1) % size
final List‹int› diffForSymbols = [
diffForOneItem % ALPHABET_SIZE,
diffForOneItem ~/ ALPHABET_SIZE % ALPHABET_SIZE,
diffForOneItem ~/ (pow(ALPHABET_SIZE, 2)) % ALPHABET_SIZE
];
List‹String› positions = [];
var lastAddedElement = startPos;
for (int ind = 0; ind < forNumOfTasks; ind++) {
var offset = 0;
var newElement = "";
for (int index = 0; index < 3; index++) {
final diffInSymbols = diffForSymbols[index];
var newElementCode = lastAddedElement.codeUnitAt(2 - index) + diffInSymbols;
if (offset != 0) {
newElementCode += 1;
offset = 0;
}
/// 'z' code is 122 if 'll be needed
if (newElementCode > 'z'.codeUnitAt(0)) {
offset += 1;
newElementCode -= ALPHABET_SIZE;
}
final symbol = String.fromCharCode(newElementCode);
newElement += symbol;
}
/// reverse element cuz we are calculating from the end
newElement = newElement.split('').reversed.join();
positions.add(newElement);
lastAddedElement = newElement;
}
positions.sort();
positions.forEach((p) => print(p));
return positions;
}
ふうう、疲れた？一番難しい部分は終わり、残りわずかです！
バケツのアイデアはあまり好きではありませんでした。客観的には、彼女は上手です。しかし、「リカバリー」アルゴリズムを使用するというアイデアそのものは好きではありませんでした。位置が終わったら、バケットでリカバリーしてください！つまり、バケットはありません。ただし、ランクは無限ではありません。つまり、何かを発明する必要があります。
そして
、行間にスペースが残っていない場合は、下の境界に英語のアルファベットの中央の文字（ "n"）を追加することにしました。それら。 「aa」と「ab」の間に要素を貼り付けたい場合は、「aa」、「aan」、「ab」を取得します。文字列は要素ごとに左から右に並べ替えられるため、文字列を長くしても並べ替えが損なわれることはありません。しかし、私たちには新しい要素のための場所があり、これには回復アルゴリズムがありません。
このコードは、真ん中の行を見つけるためのアルゴリズムにも含まれています。
「真ん中」の文字が追加されたコード
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
概要
Lexorangsは、データベースとサーバーでの作業を最適化する優れたインデックス作成ツールであるように見えました。タスクの順序を変更する場合、変更する必要があるタスクは1つだけ更新する必要があります。
レキソランについてのあなたの意見と、そのような問題を解決することについてのあなたの考えを共有してください。
まあ、Habrのすべての読者のために、私たちは得られた結果を評価することを提案します。また、「Habr's Authors 'Code」の有用なリストを入手してください。
ご清聴ありがとうございました！