Arrastar e soltar itens da lista é um recurso popular nos aplicativos modernos, cuja presença só agradará os usuários. No entanto, ao implementar essa funcionalidade, você precisa tentar não adotar uma otimização ruim: um grande número de elementos, recálculo da posição todas as vezes e, se houver também várias seções na lista, ao arrastar entre as seções, provavelmente é necessário implementar lógica adicional. Como não ser atingido na testa, reduzir o número de cálculos e como os lexorangs nos ajudarão com isso - leia abaixo.
Vamos definir o problema
Então, você decidiu adicionar a funcionalidade de arrastar e soltar ao seu aplicativo. Portanto, você precisa classificar os elementos de alguma forma, caso contrário, não faz sentido arrastar e soltar. E qual é a primeira coisa que vem à mente?
Posições
As posições comuns mais comuns. Esses mesmos números de 1 ao infinito (na verdade não). É fácil e conveniente trabalhar com eles, os elementos são classificados sem problemas. À primeira vista, está tudo bem. Tão bom que, para a maioria dos aplicativos, é disso que você precisa.
O que há de errado com a posição numérica?
O problema está nas operações associadas. Precisa injetar um elemento entre o segundo e o terceiro elementos? Mudamos tudo adiante em um, começando no terceiro elemento, sem esquecer de atualizar os dados no banco de dados. Executar uma operação assim uma vez não parece difícil, mas essa operação será realizada com bastante frequência.
Outra operação problemática é a atualização de dados no servidor. Atualização da tarefa - você precisa enviar uma atualização de todas as tarefas afetadas ao servidor. O servidor, por sua vez, deve enviar esta atualização para todos os que estão "inscritos" na lista de tarefas. Quanto mais os usuários alteram a ordem das tarefas na lista, mais dados devem ser enviados ao servidor e mais dados o servidor deve enviar aos clientes.
Acontece que, ao arrastar uma tarefa, não apenas alteraremos as posições de um grande número de elementos, mas também as enviaremos ao servidor, que as enviará para outros usuários.
Conclusão: quero algo mais ideal
Opções de solução
Quando enfrentamos um problema semelhante na empresa, a primeira solução possível foi o seguinte algoritmo: para todos os elementos, colocaremos algumas posições padrão em intervalos iguais (etapas). Portanto, o primeiro elemento terá uma posição de 1 e o segundo - 1000. Quando o usuário deseja arrastar algo entre esses dois elementos, calculamos a posição média - (1000 + 1) / 2 = ~ 500. E assim por diante.
Por que essa opção é ruim, acho que você adivinhou imediatamente. Estamos limitados no número de etapas que podem ser tomadas. Essa. entre 1 e 1000 - 500. Entre 1 e 500 - 250. Então 125 ... e eventualmente não haverá espaço. Aumentar a etapa não resolve esse problema.
Podemos usar números fracionários?
Não, números fracionários não corrigem o problema, mas atrasam apenas o momento de sua aparência.
Depois de pensar um pouco e pesquisar no Google, encontramos um relatório sobre como os lexorangs são usados em Jira ( relatório do Lexorank ).
Eles são baseados em três coisas:
1 - é fácil classificar as strings em ordem alfabética
2 - você pode encontrar a string do meio entre duas strings (nem sempre, e isso não é mais tão fácil)
3 - você não consegue encontrar a strings do meio? Vamos usar um balde (soa estranho, sim). Ao
classificar tudo está claro, vamos diretamente ao ponto número 2.
Existem letras no alfabeto inglês em "a" e "c", e entre elas, obviamente, "b". Mas como encontrar esse "b" matematicamente?
Vamos apenas subtrair do código da letra "c" o código da letra "a", obtemos 2 ("c" = 143, "a" = 141). Resta dividir o resultado pela metade. Obtido 1. De fato, se adicionarmos um ao código "a", obteremos o código da letra "b".
Uma combinação de letras em inglês é chamada lexorang.Em
situações em que não há espaço entre duas linhas, elas também têm um lugar para estar, e eu já escrevi que os baldes são usados para resolvê-las.
O balde é o rótulo antes da classificação , fica assim: "0 | aaa". Aqui 0 é o número do intervalo. Quando não há espaço, os elementos são movidos de um balde para outro e os rótulos são reorganizados em ordem. Isso é toda a mágica!
Como aproveitamos isso
Não se diz exatamente (em vez disso, simplesmente não encontramos) como é fácil e indolor encontrar a linha do meio entre os dois. Então, ficamos tensos e criamos isso. Vamos mergulhar imediatamente em um exemplo.
Vamos pegar duas linhas: "aa" e "cc" e encontrar a linha do meio entre elas.
Após a subtração pelo símbolo, como acima, obtemos o número 11. Mas o que fazer a seguir? Você pode pensar que você só precisa adicionar o resultado à linha "aa". Aqui a string "bb" realmente ficará, localizada entre "aa" e "cc", mas o algoritmo estará incorreto e agora veremos o porquê.
Vamos pensar sobre o que parece? "Aa", "cc", "11". Algum tipo de sistema numérico. Em que? E no dia 26! Por quê? Porque o alfabeto Inglês tem 26 letras. Então é isso.
É necessário converter o resultado "11" do sistema numérico de 26 anos para o sistema numérico de 10 anos usual.
A fórmula é bastante simples:
X = y 0 + y 1 * tamanho + y 2 * tamanho ^ 2 ... y n * tamanho ^ (n-1)
Aqui size representa o "tamanho" do sistema numérico (neste caso, tamanho = 26)
y n - n-ésimo número à direita
Lembremo-nos desta fórmula, pois, por exemplo, a fórmula 1 , ainda será útil para nós.
Substituímos nossos números e é isso que obtemos: 2 + 2 * 26 = 54. Agora sabemos quantos caracteres existem entre as linhas "aa" e "cc". Mas precisamos calcular a média entre os dois. Dividimos 54 por 2, obtemos 27. Resta apenas adicionar corretamente nosso resultado aos códigos "aa".
Como fazer isso? Primeiro, descobrimos quanto adicionar ao primeiro caractere (direito). Para fazer isso, temos o restante da divisão 27 por 26. Acontece que 1. Adicione 1 a "a" - você recebe a letra "b".
Agora precisamos pensar em como descobrir quantos caracteres mudar o segundo caractere.
Aqui, a seguinte fórmula nos ajudará:
X = Y / size ^ (n-1) % size
Por essa fórmula, podemos descobrir quanto precisa ser adicionado a um determinado local (caractere, especificado usando n).
Substituindo tudo, obtemos (n = 2): (27/26)% 26 = 1. Adicione. Nós obtemos o resultado final "bb".
Não é tão difícil implementar um algoritmo em qualquer linguagem de programação quando você sabe exatamente como ele funciona. Abaixo, adicionei a implementação do algoritmo no Dart (o aplicativo em que esse problema ocorreu está escrito em Flutter).
Nossa implementação de encontrar a linha "intermediária"
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;
}
Mas isso não é tudo
De qualquer forma, não foi tudo para nós. Adicionamos esse recurso a um aplicativo já lançado, portanto, era necessária uma migração. Escrever migrações para SQL não é problema, mas calcular as classificações padrão não é mais tão fácil. Mas, sabendo como a linha do meio está localizada, não é difícil fazer isso. O algoritmo será o seguinte:
- defina o início e o fim do intervalo (para nós, esses são "aaa" e "zzz", respectivamente)
- contamos quantas combinações de caracteres diferentes entre as linhas, aqui a fórmula 1 nos ajudará
- agora dividimos o resultado pelo número máximo possível de elementos na lista
- então, temos uma etapa, existe uma posição inicial, resta apenas adicionar uma etapa à posição inicial, obter uma classificação e, em seguida, adicionar uma etapa a essa classificação, obter uma nova classificação, adicionar uma etapa novamente e assim por diante
É o mesmo em Dart. o parâmetro forNumOfTasks é responsável por quantas posições você obtém. Se você colocar posições para uma lista em que existem apenas três elementos agora, não faz sentido calcular as posições para toda a lista (em 50, 100 ou outra coisa)
Nossa implementação de encontrar classificações 'padrão'
/// 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, você está cansado? A parte mais difícil acabou, resta muito pouco!
Nós realmente não gostamos da ideia do balde. Objetivamente, ela é boa. Mas não gostamos da idéia de ter um algoritmo de "recuperação": se as posições terminarem, recupere com baldes! Então, sem baldes. No entanto, as fileiras não são infinitas, o que significa que algo deve ser inventado.
E criamos:
Se não havia espaço entre as linhas, decidimos simplesmente adicionar a letra do meio do alfabeto inglês ("n") à borda inferior. Essa. se queremos colocar um elemento entre "aa" e "ab", obtemos "aa", "aan" e "ab". Devido ao fato de que as strings são classificadas em elementos da esquerda para a direita, o alongamento da string não estraga a classificação. Mas temos um lugar para novos elementos, e isso é sem algoritmos de recuperação.
Este pedaço de código também pode ser encontrado no algoritmo para encontrar a linha do meio.
Um pedaço de código com a adição de um caractere 'intermediário'
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
}
Resumo
Os Lexorangs nos pareciam uma excelente ferramenta de indexação, cuja utilização otimiza o trabalho com o banco de dados e o servidor: ao alterar a ordem das tarefas, apenas uma tarefa alterada precisa ser atualizada.
Compartilhe sua opinião sobre lexorangs e que pensamentos você tem sobre a solução de tais problemas.
Bem, para todos os leitores da Habr, propomos avaliar o resultado que obtivemos. E também pegue uma lista útil do "Código dos Autores de Habr" .
Agradecimentos para sua atenção!