Arrastrar y soltar elementos en la lista es una característica popular en las aplicaciones modernas, cuya presencia solo hará las delicias de los usuarios. Sin embargo, al implementar dicha funcionalidad, debe intentar no pisar el rastrillo de una mala optimización: una gran cantidad de elementos, el recálculo de la posición cada vez, y si también hay varias secciones en la lista, entonces, al arrastrar entre secciones, lo más probable es que sea necesario implementar lógica adicional. Cómo no recibir un golpe en la frente, reducir la cantidad de cálculos y cómo los lexorangs nos ayudarán con esto: lea debajo del corte.
Definamos el problema
Entonces, ha decidido agregar la funcionalidad de arrastrar y soltar a su aplicación. Por lo tanto, debe ordenar los elementos de alguna manera, de lo contrario no tiene sentido arrastrar y soltar. ¿Y qué es lo primero que me viene a la mente?
Posiciones
Las posiciones comunes más comunes. Esos mismos números del 1 al infinito (no realmente). Es fácil y conveniente trabajar con ellos, los elementos se ordenan sin problemas. A primera vista, todo está bien. Tan bueno que para la mayoría de las aplicaciones, esto es lo que necesita.
¿Qué hay de malo en la posición numérica?
El problema radica en las operaciones asociadas. ¿Necesita inyectar un elemento entre el segundo y el tercer elemento? Cambiamos todo hacia adelante por uno, comenzando desde el tercer elemento, sin olvidarnos de actualizar los datos en la base de datos. Realizar una operación de este tipo una vez no parece difícil, pero esta operación se realizará con bastante frecuencia.
Otra operación problemática es la actualización de datos en el servidor. Actualizó la tarea: debe enviar una actualización de todas las tareas afectadas al servidor. El servidor, a su vez, debe enviar esta actualización a todos los que están "suscritos" a la lista de tareas. Cuanto más a menudo los usuarios cambien el orden de las tareas en la lista, más datos deben enviarse al servidor y más datos debe enviar el servidor a los clientes.
Resulta que al arrastrar una tarea, no solo cambiaremos las posiciones de una gran cantidad de elementos, sino que también los enviaremos al servidor, que luego los enviará a otros usuarios.
Conclusión: quiero algo más óptimo
Opciones de solucion
Cuando en la empresa enfrentamos un problema similar, la primera solución posible fue el siguiente algoritmo: para todos los elementos colocaremos algunas posiciones estándar a intervalos iguales (pasos). Entonces, el primer elemento tendrá una posición de 1, y el segundo - 1000. Cuando el usuario quiere arrastrar algo entre estos dos elementos, calculamos la posición promedio - (1000 + 1) / 2 = ~ 500. Y así sucesivamente y así sucesivamente.
Por qué esta opción es mala, creo que lo has adivinado de inmediato. Estamos limitados en la cantidad de pasos que se pueden tomar. Aquellos. entre 1 y 1000 - 500. Entre 1 y 500 - 250. Luego 125 ... y eventualmente no habrá espacio. Aumentar el paso no resuelve este problema.
¿Podemos usar números fraccionarios?
No, los números fraccionarios no solucionan el problema, sino que solo retrasan el momento de su aparición.
Después de pensar un poco y buscar en Google, encontramos un informe sobre cómo se usan los lexorangs en Jira (Lexorank, informe ).
Se basan en tres cosas:
1: es fácil ordenar las cadenas en orden alfabético
2: puede encontrar la cadena del medio entre dos cadenas (no siempre, y esto ya no es tan fácil)
3: ¿no puede encontrar la del medio? Usemos un cubo (suena extraño, sí) Al
ordenar todo está claro, vamos directamente al punto número 2.
Hay letras en el alfabeto inglés en "a" y "c", y entre ellas, obviamente, "b". Pero, ¿cómo encontrar esta "b" matemáticamente?
Restemos del código de la letra "c" el código de la letra "a", obtenemos 2 ("c" = 143, "a" = 141). Queda por dividir el resultado a la mitad. Obtuve 1. De hecho, si agregamos uno al código "a", obtenemos el código de la letra "b".
Una combinación de letras en inglés se llama lexorang.
Situaciones en las que no hay espacio entre dos líneas, también hay un lugar para estar, y ya escribí que se usan cubos para resolverlas.
El cubo es la etiqueta antes del rango , se ve así: "0 | aaa". Aquí 0 es el número del cubo. Cuando no queda espacio, los elementos se mueven de un cubo a otro y las etiquetas se reorganizan en orden. Esa es toda la magia!
Cómo lo aprovechamos
No se dice exactamente (más bien, simplemente no encontramos) cuán fácil e indoloro encontrar la línea media entre los dos. Entonces nos tensamos y se nos ocurrió esto. Pasemos inmediatamente a un ejemplo.
Tomemos dos líneas: "aa" y "cc" y busquemos la línea media entre ellas.
Después de la resta por símbolo, como arriba, obtenemos el número 11. ¿Pero qué hacer después? Puede pensar que solo necesita agregar el resultado a la línea "aa". Aquí la cadena "bb" realmente resultará, ubicada entre "aa" y "cc", pero el algoritmo será incorrecto, y ahora veremos por qué.
Pensemos en cómo se ve? "Aa", "cc", "11". Algún tipo de sistema numérico. ¿En que? ¡Y el 26! ¿Por qué? Porque el alfabeto inglés tiene 26 letras. Eso es todo.
Es necesario traducir el resultado, "11", del sistema de números de 26 arios al sistema de números de 10 arios habitual.
La fórmula es bastante simple:
X = y 0 + y 1 * tamaño + y 2 * tamaño ^ 2 ... y n * tamaño ^ (n-1)
Aquí el tamaño es el "tamaño" del sistema numérico (en este caso, tamaño = 26)
y n - Enésimo número a la derecha
Recordemos esta fórmula como, por ejemplo, la fórmula 1 , aún nos será útil.
Sustituimos nuestros números y esto es lo que obtenemos: 2 + 2 * 26 = 54. Ahora sabemos cuántos caracteres hay entre las líneas "aa" y "cc". Pero tenemos que tomar el promedio entre los dos. Dividimos 54 por 2, obtenemos 27. Solo queda agregar correctamente nuestro resultado a los códigos "aa".
¿Cómo hacerlo? Primero, descubrimos cuánto agregar al primer carácter (derecho). Para hacer esto, obtenemos el resto de dividir 27 entre 26. Resulta 1. Agregue 1 a "a": obtendrá la letra "b".
Ahora tenemos que pensar en cómo averiguar cuántos caracteres cambiar el segundo personaje.
Aquí la siguiente fórmula nos ayudará:
X = Y / tamaño ^ (n-1) % tamaño
Con esta fórmula, podemos averiguar cuánto se debe agregar a un lugar determinado (carácter, especificado usando n).
Sustituyendo todo allí, obtenemos (n = 2): (27/26)% 26 = 1. Suma. Obtenemos el resultado final "bb".
No es tan difícil implementar un algoritmo en cualquier lenguaje de programación cuando se sabe exactamente cómo funciona. A continuación he agregado la implementación del algoritmo en Dart (la aplicación en la que se produjo este problema está escrita en Flutter).
Nuestra implementación de encontrar la fila 'central'
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;
}
Pero eso no es todo
En cualquier caso, no fue todo para nosotros. Agregamos esta función a una aplicación ya lanzada, por lo que se necesitaba una migración. Escribir migraciones para SQL no es un problema, pero calcular los rangos estándar ya no es tan fácil. Pero, sabiendo cómo está ubicada la fila central, no es difícil hacer esto. El algoritmo será el siguiente:
- establecer el comienzo y el final del intervalo (para nosotros, estos son "aaa" y "zzz", respectivamente)
- contamos cuántas combinaciones de diferentes caracteres entre las líneas, aquí la fórmula 1 nos ayudará
- ahora dividimos el resultado por el número máximo posible de elementos en la lista
- entonces, tenemos un paso, hay una posición inicial, solo queda agregar un paso a la posición inicial, obtener un rango, luego agregar un paso a este rango, obtener un nuevo rango, luego agregar un paso nuevamente, y así sucesivamente
Es lo mismo en Dart. El parámetro forNumOfTasks es responsable de la cantidad de posiciones que obtenga. Si coloca posiciones para una lista donde solo hay tres elementos ahora, no tiene sentido calcular las posiciones para toda la lista (por 50, 100 u otra cosa)
Nuestra implementación de encontrar rangos 'predeterminados'
/// 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, ¿estás cansado? La parte más difícil ha terminado, ¡queda muy poco!
Realmente no nos gustó la idea del cubo. Objetivamente, ella es buena. Pero no nos gustó la idea de tener un algoritmo de "recuperación": si las posiciones han terminado, ¡recupere con cubos! Entonces, no hay cubos. Sin embargo, los rangos no son infinitos, lo que significa que hay que inventar algo.
Y se nos ocurrió
si no quedaba espacio entre las líneas, entonces decidimos simplemente agregar la letra del medio del alfabeto inglés ("n") al borde inferior. Aquellos. si queremos pegar un elemento entre "aa" y "ab", obtenemos "aa", "aan" y "ab". Debido al hecho de que las cadenas están ordenadas por elementos de izquierda a derecha, alargar la cadena no estropeará la clasificación. Pero tenemos un lugar para nuevos elementos, y esto es sin algoritmos de recuperación.
Este fragmento de código también se puede encontrar en el algoritmo para encontrar la línea media.
Una pieza de código con la adición de un personaje 'medio'
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
Resumen
Lexorangs nos pareció una excelente herramienta de indexación, cuyo uso optimiza el trabajo con la base de datos y el servidor: al cambiar el orden de las tareas, solo se necesita actualizar una tarea modificada.
Comparta su opinión sobre los lexorangs y qué pensamientos tiene para resolver tales problemas.
Bueno, para todos los lectores de Habr, proponemos evaluar el resultado que obtuvimos. Y también recoge una lista útil de "Código de los autores Habra" .
¡Gracias por tu atención!