Faire glisser et déposer des éléments dans la liste est une fonctionnalité populaire dans les applications modernes, dont la présence ne fera que ravir les utilisateurs. Cependant, lors de la mise en œuvre d'une telle fonctionnalité, vous devez essayer de ne pas marcher sur le râteau d'une mauvaise optimisation: un grand nombre d'éléments, un recalcul de la position à chaque fois, et s'il y a plusieurs sections dans la liste, alors lorsque vous faites glisser entre les sections, vous devez très probablement implémenter une logique supplémentaire. Comment ne pas être touché au front, réduire le nombre de calculs et comment les lexorangs nous aideront avec cela - lisez sous la coupe.
Définissons le problème
Vous avez donc décidé d'ajouter une fonctionnalité de glisser-déposer à votre application. Donc, vous devez trier les éléments d'une manière ou d'une autre, sinon il ne sert à rien de glisser-déposer. Et quelle est la première chose qui vous vient à l'esprit?
Positions
Les positions banales les plus courantes. Ces mêmes nombres de 1 à l'infini (pas vraiment). Il est facile et pratique de travailler avec eux, les éléments sont triés sans problème. À première vue, tout va bien. Tellement bon que pour la plupart des applications, c'est ce dont vous avez besoin.
Qu'est-ce donc qui ne va pas avec la position numérique?
Le problème réside dans les opérations associées. Besoin d'injecter un élément entre les deuxième et troisième éléments? Nous décalons tout de un en avant, à partir du troisième élément, sans oublier de mettre à jour les données de la base de données. Effectuer une telle opération une fois ne semble pas difficile, mais cette opération sera effectuée assez souvent.
Une autre opération problématique est la mise à jour des données sur le serveur. Mise à jour de la tâche - vous devez envoyer une mise à jour de toutes les tâches affectées au serveur. Le serveur, à son tour, doit envoyer cette mise à jour à tous ceux qui sont «abonnés» à la liste des tâches. Plus les utilisateurs modifient souvent l'ordre des tâches dans la liste, plus il faut envoyer de données au serveur et plus le serveur doit envoyer aux clients.
Il s'avère que lorsque vous faites glisser une tâche, nous modifierons non seulement les positions d'un grand nombre d'éléments, mais nous les enverrons également au serveur, qui les enverra ensuite à d'autres utilisateurs.
Conclusion: je veux quelque chose de plus optimal
Options de solution
Lorsque nous sommes confrontés à un problème similaire dans l'entreprise, la première solution possible était l'algorithme suivant: pour tous les éléments, nous placerons des positions standard à intervalles égaux (étapes). Ainsi, le premier élément aura une position de 1, et le second - 1000. Lorsque l'utilisateur veut faire glisser quelque chose entre ces deux éléments, nous calculons la position moyenne - (1000 + 1) / 2 = ~ 500. Et ainsi de suite.
Pourquoi cette option est mauvaise, je pense que vous l'avez deviné tout de suite. Nous sommes limités dans le nombre de mesures qui peuvent être prises. Ceux. entre 1 et 1000 - 500. Entre 1 et 500 - 250. Puis 125 ... et finalement il n'y aura plus de place. Augmenter le pas ne résout pas ce problème.
Pouvons-nous utiliser des nombres fractionnaires?
Non, les nombres fractionnaires ne résolvent pas le problème, mais retardent seulement le moment de son apparition.
Après un peu de réflexion et de recherche sur Google, nous sommes tombés sur un rapport sur l'utilisation des lexorangs dans Jira (Lexorank, rapport ).
Ils sont basés sur trois choses:
1 - il est facile de trier les chaînes par ordre alphabétique
2 - vous pouvez trouver la chaîne du milieu entre deux chaînes (pas toujours, et ce n'est plus si facile)
3 - vous ne trouvez pas la chaîne du milieu? Utilisons un seau (ça semble étrange, oui)
Avec le tri, tout est clair, nous allons directement au point numéro 2.
Il y a des lettres de l'alphabet anglais dans "a" et "c", et entre elles, évidemment, "b". Mais comment trouver ce "b" mathématiquement?
Soustrayons simplement du code de la lettre "c" le code de la lettre "a", on obtient 2 ("c" = 143, "a" = 141). Il reste à diviser le résultat en deux. Got 1. En effet, si on en ajoute un au code "a", on obtient le code de la lettre "b".
Une combinaison de lettres anglaises s'appelle un lexorang.Les
situations où il n'y a pas d'espace entre deux lignes, elles ont aussi un endroit où être, et j'ai déjà écrit que des seaux sont utilisés pour les résoudre.
Le bucket est l'étiquette avant le rang , il ressemble à ceci: "0 | aaa". Ici, 0 est le numéro de compartiment. Lorsqu'il n'y a plus de place, les éléments sont déplacés d'un compartiment à un autre et les étiquettes sont réorganisées dans l'ordre. C'est toute la magie!
Comment nous en avons profité
Il n'est pas dit exactement (plutôt, nous n'avons tout simplement pas trouvé) à quel point il est facile et indolore de trouver la ligne médiane entre les deux. Nous nous sommes donc tendus et avons trouvé ça. Plongeons-nous immédiatement dans un exemple.
Prenons deux lignes: "aa" et "cc" et trouvons la ligne médiane entre elles.
Après soustraction par symbole, comme ci-dessus, on obtient le chiffre 11. Mais que faire ensuite? Vous pourriez penser que vous devez simplement ajouter le résultat à la ligne "aa". Ici, la chaîne "bb" se révélera vraiment, située entre "aa" et "cc", mais l'algorithme sera incorrect, et maintenant nous verrons pourquoi.
Pensons à quoi ça ressemble? "Aa", "cc", "11". Une sorte de système numérique. Sur quoi? Et le 26! Pourquoi? Parce que l'alphabet anglais a 26 lettres. Donc c'est tout.
Il est nécessaire de traduire le résultat, "11", du système de nombres à 26 aires dans le système de nombres à 10 aires habituel.
La formule est assez simple:
X = y 0 + y 1 * taille + y 2 * taille ^ 2 ... y n * taille ^ (n-1)
Ici, la taille est la "taille" du système numérique (dans ce cas, taille = 26)
y n - n-ième nombre à droite
Retenons cette formule comme, par exemple, la formule 1 , elle nous sera toujours utile.
Nous substituons nos nombres et voici ce que nous obtenons: 2 + 2 * 26 = 54. Nous savons maintenant combien de caractères se trouvent entre les lignes "aa" et "cc". Mais nous devons prendre la moyenne entre les deux. On divise 54 par 2, on obtient 27. Il ne reste plus qu'à ajouter correctement notre résultat aux codes «aa».
Comment faire? Tout d'abord, nous découvrons combien il faut ajouter au premier caractère (à droite). Pour ce faire, nous obtenons le reste de la division de 27 par 26. Il s'avère que 1. Ajoutez 1 à "a" - vous obtenez la lettre "b".
Maintenant, nous devons réfléchir à la façon de savoir combien de caractères pour déplacer le deuxième caractère.
Ici, la formule suivante nous aidera:
X = Y / taille ^ (n-1) % taille
Par cette formule, nous pouvons savoir combien doit être ajouté à un certain endroit (caractère, spécifié en utilisant n).
En substituant tout ce qui s'y trouve, nous obtenons (n ​​= 2): (27/26)% 26 = 1. Additionnez. Nous obtenons le résultat final "bb".
Il n'est pas si difficile d'implémenter un algorithme dans n'importe quel langage de programmation lorsque vous savez exactement comment cela fonctionne. Ci-dessous, j'ai ajouté l'implémentation de l'algorithme dans Dart (l'application dans laquelle ce problème s'est produit est écrite en Flutter).
Notre implémentation de trouver la ligne du `` milieu ''
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;
}
Mais ce n'est pas tout
En tout cas, ce n'était pas tout pour nous. Nous avons ajouté cette fonctionnalité à une application déjà publiée, une migration était donc nécessaire. Écrire des migrations pour SQL ne pose aucun problème, mais calculer les classements standard n'est plus aussi simple. Mais, sachant comment se trouve la rangée du milieu, cela ne devient pas difficile à faire. L'algorithme sera le suivant:
- définir le début et la fin de l'intervalle (pour nous, ce sont respectivement "aaa" et "zzz")
- nous comptons combien de combinaisons de caractères différents entre les lignes, ici la formule 1 nous aidera
- maintenant nous divisons le résultat par le nombre maximum possible d'éléments dans la liste
- donc, on a un pas, il y a une position initiale, il ne reste plus qu'Ă ajouter un pas Ă la position initiale, obtenir un rang, puis ajouter un pas Ă ce rang, obtenir un nouveau rang, puis rajouter un pas Ă nouveau, etc.
C'est la même chose sur Dart. le paramètre forNumOfTasks est responsable du nombre de positions que vous obtenez. Si vous mettez des positions pour une liste où il n'y a que trois éléments maintenant, cela n'a aucun sens de calculer les positions pour la liste entière (par 50, 100 ou autre chose)
Notre implémentation de la recherche de rangs 'par défaut'
/// 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, tu es fatigué? Le plus dur est terminé, il en reste très peu!
Nous n'avons pas vraiment aimé l'idée du seau. Objectivement, elle est bonne. Mais nous n’avons pas aimé l’idée même d’avoir un algorithme de «récupération»: si les positions sont terminées, récupérez avec des seaux! Donc, pas de seaux. Cependant, les rangs ne sont pas infinis, ce qui signifie qu'il faut inventer quelque chose.
Et nous avons trouvé
S'il n'y avait plus d'espace entre les lignes, nous avons décidé d'ajouter simplement la lettre du milieu de l'alphabet anglais ("n") à la bordure inférieure. Ceux. si nous voulons coller un élément entre "aa" et "ab", nous obtenons "aa", "aan" et "ab". En raison du fait que les chaînes sont triées élément par élément de gauche à droite, l'allongement de la chaîne ne gâchera pas le tri. Mais nous avons une place pour les nouveaux éléments, et cela sans aucun algorithme de récupération.
Ce morceau de code peut également être trouvé dans l'algorithme pour trouver la ligne médiane.
Un morceau de code avec l'ajout d'un caractère «central»
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
Résumé
Les Lexorangs nous ont semblé un excellent outil d'indexation, dont l'utilisation optimise le travail avec la base de données et le serveur: lors du changement de l'ordre des tâches, une seule tâche modifiée doit être mise à jour.
Partagez votre opinion sur les lexorangs et ce que vous pensez de la résolution de ces problèmes.
Eh bien, pour tous les lecteurs de Habr, nous proposons d'évaluer le résultat que nous avons obtenu. Et prenez également une liste utile de "Code des auteurs de Habr" .
Merci de votre attention!