Das Ziehen und Ablegen von Elementen in die Liste ist eine beliebte Funktion in modernen Anwendungen, deren Vorhandensein nur Benutzer begeistern wird. Wenn Sie eine solche FunktionalitĂ€t implementieren, mĂŒssen Sie jedoch versuchen, nicht auf den Fehler einer schlechten Optimierung zu treten: eine groĂe Anzahl von Elementen, jedes Mal eine Neuberechnung der Position, und wenn die Liste auch mehrere Abschnitte enthĂ€lt, muss beim Ziehen zwischen Abschnitten höchstwahrscheinlich zusĂ€tzliche Logik implementiert werden. Wie man sich nicht in die Stirn trifft, die Anzahl der Berechnungen reduziert und wie Lexorangs uns dabei helfen - lesen Sie unter dem Schnitt.
Definieren wir das Problem
Sie haben sich also entschlossen, Ihrer Anwendung Drag & Drop-Funktionen hinzuzufĂŒgen. Sie mĂŒssen die Elemente also irgendwie sortieren, sonst macht das Ziehen und Ablegen keinen Sinn. Und was fĂ€llt mir als Erstes ein?
Werbebuchungen
Die hĂ€ufigsten unauffĂ€lligen Positionen. Die gleichen Zahlen von 1 bis unendlich (nicht wirklich). Es ist einfach und bequem, mit ihnen zu arbeiten, die Elemente werden ohne Probleme sortiert. Auf den ersten Blick ist alles in Ordnung. So gut, dass Sie dies fĂŒr die meisten Anwendungen benötigen.
Was ist dann falsch an der numerischen Position?
Das Problem liegt in den damit verbundenen Operationen. MĂŒssen Sie ein Element zwischen dem zweiten und dritten Element einfĂŒgen? Wir verschieben alles um eins vorwĂ€rts, beginnend mit dem dritten Element, ohne zu vergessen, die Daten in der Datenbank zu aktualisieren. Eine solche Operation einmal auszufĂŒhren, sieht nicht schwierig aus, aber diese Operation wird ziemlich oft ausgefĂŒhrt.
Ein weiterer problematischer Vorgang ist das Aktualisieren von Daten auf dem Server. Die Aufgabe wurde aktualisiert. Sie mĂŒssen eine Aktualisierung aller betroffenen Aufgaben an den Server senden. Der Server sollte dieses Update wiederum an alle senden, die die Aufgabenliste âabonniertâ haben. Je öfter Benutzer die Reihenfolge der Aufgaben in der Liste Ă€ndern, desto mehr Daten mĂŒssen an den Server gesendet werden und desto mehr Daten muss der Server an Clients senden.
Es stellt sich heraus, dass wir beim Ziehen einer Aufgabe nicht nur die Positionen einer groĂen Anzahl von Elementen Ă€ndern, sondern sie auch an den Server senden, der sie dann an andere Benutzer sendet.
Fazit: Ich möchte etwas Optimaleres
Lösungsoptionen
Als wir im Unternehmen mit einem Ă€hnlichen Problem konfrontiert waren, war die erste mögliche Lösung der folgende Algorithmus: FĂŒr alle Elemente werden wir einige Standardpositionen in gleichen Intervallen (Schritten) platzieren. Das erste Element hat also eine Position von 1 und das zweite eine - 1000. Wenn der Benutzer etwas zwischen diese beiden Elemente ziehen möchte, berechnen wir die durchschnittliche Position - (1000 + 1) / 2 = ~ 500. Und so weiter und so fort.
Warum diese Option schlecht ist, haben Sie wohl sofort erraten. Die Anzahl der Schritte, die unternommen werden können, ist begrenzt. Jene. zwischen 1 und 1000 - 500. Zwischen 1 und 500 - 250. Dann 125 ... und schlieĂlich wird kein Platz mehr sein. Das Erhöhen des Schritts löst dieses Problem nicht.
Können wir Bruchzahlen verwenden?
Nein, Bruchzahlen beheben das Problem nicht, sondern verzögern nur den Moment seines Auftretens.
Nach einigem Nachdenken und Googeln stieĂen wir auf einen Bericht darĂŒber, wie Lexorangs in Jira verwendet werden (Lexorank, Bericht ).
Sie basieren auf drei Dingen:
1 - es ist einfach, die Zeichenfolgen in alphabetischer Reihenfolge zu sortieren
2 - Sie können die mittlere Zeichenfolge zwischen zwei Zeichenfolgen finden (nicht immer, und das ist nicht mehr so ââeinfach)
3 - können Sie die mittlere nicht finden? Verwenden wir einen Eimer (klingt seltsam, ja).
Wenn alles klar ist, gehen wir direkt zu Punkt 2.
Es gibt Buchstaben im englischen Alphabet in "a" und "c" und dazwischen offensichtlich "b". Aber wie findet man dieses "b" mathematisch?
Subtrahieren wir einfach vom Code des Buchstabens "c" den Code des Buchstabens "a", wir erhalten 2 ("c" = 143, "a" = 141). Es bleibt, das Ergebnis in zwei HĂ€lften zu teilen. Got 1. Wenn wir dem Code "a" einen hinzufĂŒgen, erhalten wir den Code des Buchstabens "b".
Eine Kombination englischer Buchstaben wird als Lexorang bezeichnet.
Situationen, in denen zwischen zwei Zeilen kein Leerzeichen steht, gibt es auch einen Platz, an dem man sein kann, und ich habe bereits geschrieben, dass Eimer verwendet werden, um sie zu lösen.
Der Bucket ist das Label vor dem Rang , es sieht so aus: "0 | aaa". Hier ist 0 die Bucket-Nummer. Wenn kein Platz mehr vorhanden ist, werden die Elemente von einem Eimer in einen anderen verschoben und die Beschriftungen in der richtigen Reihenfolge neu angeordnet. Das ist die ganze Magie!
Wie wir es ausgenutzt haben
Es wird nicht genau gesagt (vielmehr haben wir es einfach nicht gefunden), wie einfach und schmerzlos es ist, die Mittellinie zwischen den beiden zu finden. Also haben wir uns angespannt und uns das ausgedacht. Lassen Sie uns sofort in ein Beispiel eintauchen.
Nehmen wir zwei Zeilen: "aa" und "cc" und finden Sie die mittlere Zeile zwischen ihnen.
Nach Subtraktion durch Symbol wie oben erhalten wir die Nummer 11. Aber was tun als nĂ€chstes? Sie könnten denken, Sie mĂŒssen nur das Ergebnis zur Zeile "aa" hinzufĂŒgen. Hier wird sich die Zeichenfolge "bb" zwischen "aa" und "cc" wirklich herausstellen, aber der Algorithmus wird falsch sein, und jetzt werden wir sehen, warum.
Lassen Sie uns darĂŒber nachdenken, wie es aussieht. "Aa", "cc", "11". Eine Art Zahlensystem. Auf was? Und am 26! Warum? Weil das englische Alphabet 26 Buchstaben hat. So ist das.
Es ist notwendig, das Ergebnis "11" aus dem 26-ary-Zahlensystem in das ĂŒbliche 10-ary-Zahlensystem zu ĂŒbersetzen.
Die Formel ist recht einfach:
X = y 0 + y 1 * GröĂe + y 2 * GröĂe ^ 2 ... y n * GröĂe ^ (n-1)
Hier ist GröĂe die "GröĂe" des Zahlensystems (in diesem Fall GröĂe = 26)
y n - n-te Zahl rechts
Erinnern wir uns an diese Formel, da sie beispielsweise fĂŒr Formel 1 weiterhin nĂŒtzlich sein wird.
Wir ersetzen unsere Zahlen und dies ist, was wir erhalten: 2 + 2 * 26 = 54. Jetzt wissen wir, wie viele Zeichen zwischen den Zeilen "aa" und "cc" stehen. Aber wir mĂŒssen den Durchschnitt zwischen den beiden nehmen. Wir teilen 54 durch 2, wir erhalten 27. Es bleibt nur, unser Ergebnis korrekt zu den "aa" -Codes hinzuzufĂŒgen.
Wie kann man es machen? Zuerst finden wir heraus, wie viel dem ersten (rechten) Zeichen hinzugefĂŒgt werden muss. Dazu erhalten wir den Rest der Division von 27 durch 26. Es stellt sich heraus, 1. FĂŒgen Sie 1 zu "a" hinzu - Sie erhalten den Buchstaben "b".
Jetzt mĂŒssen wir uns ĂŒberlegen, wie wir herausfinden können, wie viele Zeichen das zweite Zeichen verschieben soll.
Hier hilft uns die folgende Formel:
X = Y / GröĂe ^ (n-1) % GröĂe
Mit dieser Formel können wir herausfinden, wie viel an einer bestimmten Stelle hinzugefĂŒgt werden muss (Zeichen, angegeben mit n).
Wenn wir dort alles ersetzen, erhalten wir (n = 2): (27/26)% 26 = 1. Add. Wir erhalten das Endergebnis "bb".
Es ist nicht so schwierig, einen Algorithmus in einer Programmiersprache zu implementieren, wenn Sie genau wissen, wie er funktioniert. Unten habe ich die Implementierung des Algorithmus in Dart hinzugefĂŒgt (die Anwendung, in der dieses Problem aufgetreten ist, ist in Flutter geschrieben).
Unsere Implementierung, die "mittlere" Reihe zu finden
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;
}
Das ist aber noch nicht alles
Auf jeden Fall war es nicht alles fĂŒr uns. Wir haben diese Funktion einer bereits veröffentlichten Anwendung hinzugefĂŒgt, sodass eine Migration erforderlich war. Das Schreiben von Migrationen fĂŒr SQL ist kein Problem, aber die Berechnung der StandardrĂ€nge ist nicht mehr so ââeinfach. Wenn Sie jedoch wissen, wie sich die mittlere Reihe befindet, wird dies nicht schwierig. Der Algorithmus lautet wie folgt:
- Stellen Sie den Anfang und das Ende des Intervalls ein (fĂŒr uns sind dies "aaa" bzw. "zzz").
- Wir zÀhlen, wie viele Kombinationen verschiedener Zeichen zwischen den Zeilen stehen. Hier hilft uns Formel 1
- Jetzt teilen wir das Ergebnis durch die maximal mögliche Anzahl von Elementen in der Liste
- Wir haben also einen Schritt, es gibt eine Anfangsposition. Es bleibt nur ein Schritt zur Anfangsposition hinzuzufĂŒgen, einen Rang zu erhalten, dann einen Schritt zu diesem Rang hinzuzufĂŒgen, einen neuen Rang zu erhalten, dann erneut einen Schritt hinzuzufĂŒgen und so weiter
Bei Dart ist es genauso. Der Parameter forNumOfTasks ist dafĂŒr verantwortlich, wie viele Positionen Sie erhalten. Wenn Sie Positionen fĂŒr eine Liste festlegen, in der es jetzt nur drei Elemente gibt, ist es nicht sinnvoll, Positionen fĂŒr die gesamte Liste zu berechnen (um 50, 100 oder etwas anderes).
Unsere Implementierung der Suche nach "Standard" -RĂ€ngen
/// 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;
}
Fuuuuh, bist du mĂŒde? Der schwierigste Teil ist vorbei, es ist nur noch sehr wenig ĂŒbrig!
Die Idee mit dem Eimer hat uns nicht wirklich gefallen. Objektiv ist sie gut. Die Idee eines "Wiederherstellungs" -Algorithmus gefiel uns jedoch nicht: Wenn Positionen vorbei sind, erholen Sie sich mit Eimern! Also keine Eimer. Die Reihen sind jedoch nicht unendlich, was bedeutet, dass etwas erfunden werden muss.
Und wir haben uns ausgedacht:
Wenn zwischen den Zeilen kein Leerzeichen mehr vorhanden ist, haben wir beschlossen, einfach den mittleren Buchstaben des englischen Alphabets ("n") am unteren Rand hinzuzufĂŒgen. Jene. Wenn wir ein Element zwischen "aa" und "ab" einfĂŒgen wollen, erhalten wir "aa", "aan" und "ab". Aufgrund der Tatsache, dass Zeichenfolgen von links nach rechts elementweise sortiert sind, wird die Sortierung durch eine VerlĂ€ngerung der Zeichenfolge nicht beeintrĂ€chtigt. Aber wir haben einen Platz fĂŒr neue Elemente, und dies ohne Wiederherstellungsalgorithmen.
Dieser Code befindet sich auch im Algorithmus zum Auffinden der Mittellinie.
Ein StĂŒck Code mit einem 'mittleren' Zeichen
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
Zusammenfassung
Lexorangs schien uns ein hervorragendes Indizierungswerkzeug zu sein, dessen Verwendung die Arbeit mit der Datenbank und dem Server optimiert: Wenn Sie die Reihenfolge der Aufgaben Àndern, muss nur eine geÀnderte Aufgabe aktualisiert werden.
Teilen Sie Ihre Meinung zu Lexorangs und Ihre Gedanken zur Lösung solcher Probleme mit.
Nun, fĂŒr alle Leser von Habr schlagen wir vor, das Ergebnis zu bewerten, das wir erhalten haben. Und holen Sie sich auch eine nĂŒtzliche Liste von "Habr's Authors 'Code" .
Vielen Dank fĂŒr Ihre Aufmerksamkeit!