Gerando chaves de classificação ao reordenar itens

Temos vários itens que o usuário final poderá organizar em um pedido desejado. O conjunto de itens não é ordenado, mas cada item contém uma chave de classificação que pode ser modificada.

Estamos procurando um algoritmo que permita gerar uma nova chave de classificação para um item que é adicionado ou movido para ser o primeiro, o último ou entre dois itens. Esperamos ter apenas que modificar a chave de classificação do item que está sendo movido.

Um algoritmo de exemplo seria fazer com que cada chave de classificação fosse um número de ponto flutuante e, ao colocar um item entre dois itens, defina a chave de classificação como sua média. A colocação de um item primeiro ou último levaria o valor mais externo + - 1.

O problema aqui é que a precisão do ponto flutuante pode causar falha na classificação. Usar dois números inteiros para representar um número fracionário pode fazer com que os números se tornem tão grandes que não possam ser representados com precisão em tipos numéricos regulares (por exemplo, ao transferir como JSON). Não gostaríamos de usar BigInts.

Existe um algoritmo adequado para isso que funcionaria, por exemplo, usando seqüências de caracteres, que não seriam afetadas por essas deficiências?

Não queremos oferecer suporte a um grande número de movimentos, mas o algoritmo descrito acima pode falhar em um número de pontos flutuantes de precisão dupla após cerca de 50 movimentos.

Como um resumo de todos os comentários e respostas:

TL; DR - O uso de números de ponto flutuante de precisão dupla com o algoritmo proposto inicialmente deve ser suficiente para as necessidades mais práticas (pelo menos manualmente). A manutenção de uma lista ordenada separada dos elementos também deve ser considerada. Outras soluções de chave de classificação são um pouco complicadas.

As duas operações problemáticas são inserir itens no início / fim repetidas vezes e inserir ou mover itens repetidamente no mesmo local (por exemplo, com três elementos movendo repetidamente o terceiro elemento entre os dois primeiros ou adicionando novos elementos repetidamente como o segundo elemento).

Do ponto de vista teórico (ou seja, permitindo reordenação infinita), a única solução em que posso pensar é usar dois números inteiros de tamanho ilimitado como um a / b fracionário. Isso permite precisão infinita para as inserções intermediárias, mas os números podem se tornar cada vez maiores.

As strings podem suportar um grande número de atualizações (embora eu ainda esteja tendo problemas para descobrir o algoritmo para ambas as operações), mas não infinitas, porque você não pode adicionar infinitamente muitas na primeira posição (pelo menos usando a classificação regular de strings comparação).

Os números inteiros exigiriam a escolha de um espaçamento inicial para as chaves de classificação, o que limita o número de inserções intermediárias que você pode executar. Se você espaçar inicialmente as teclas de classificação 1024, poderá executar apenas 10 inserções médias na pior das hipóteses antes de ter números adjacentes. A escolha de um espaçamento inicial maior limita o número de primeiras / últimas inserções que você pode executar. Usando um número inteiro de 64 bits, você está limitado a ~ 63 operações de qualquer maneira, que precisam ser divididas entre inserções intermediárias e primeiras / últimas inserções a priori.

O uso de valores de ponto flutuante remove a necessidade de selecionar o espaçamento a priori. O algoritmo é simples:

1. O primeiro elemento inserido possui uma chave de classificação 0,0
2. Um elemento inserido (ou movido) primeiro ou último possui a chave de classificação do primeiro elemento - 1,0 ou último elemento + 1,0, respectivamente.
3. Um elemento inserido (ou movido) entre dois elementos possui uma chave de classificação igual à média dos dois.

O uso de um flutuador de precisão dupla permite 52 inserções intermediárias na pior das hipóteses e efetivamente infinitas (cerca de 1e15) primeira / última inserções. Na prática, ao mover itens pelo algoritmo, você deve se auto-corrigir, pois toda vez que você move um item primeiro ou por último, ele expande o intervalo que pode ser usado.

Os flutuadores de precisão dupla também têm o benefício de serem suportados por todas as plataformas e facilmente armazenados e transportados por praticamente todos os formatos e bibliotecas de transporte. Foi isso que acabamos usando.

Eu escrevi uma solução no TypeScript com base no resumo do @ Sampo. O código pode ser encontrado abaixo.

Algumas idéias foram obtidas ao longo do caminho.

• Somente a inserção no meio entre duas chaves de classificação existentes precisa gerar uma nova chave de classificação, a troca (por exemplo, reorganização) não causa divisões (por exemplo, novos pontos médios). Se você mover dois itens e tocar apenas em um deles, estará perdendo informações sobre quais dois elementos mudaram de posição na lista. Mesmo que fosse um requisito para começar, observe se é uma boa ideia

• A cada 1074: th divisão do ponto médio, precisamos normalizar o intervalo do ponto flutuante. Detectamos isso simplesmente verificando se o novo ponto médio satisfaz a invariante

  a.sortKey < m && m < b.sortKey

• A escala não importa, como as chaves de classificação são normalizadas, a normalização ainda acontece a cada 1074divisão do ponto médio. A situação não melhoraria se distribuíssemos os números mais amplamente para começar.

• A normalização da chave de classificação é incrivelmente rara. Você amortizará esse custo até o ponto em que a normalização não é perceptível. No entanto, eu teria cuidado com essa abordagem se você tiver mais de 1000s de elementos.

export interface HasSortKey {
  sortKey: number;
}

function normalizeList<T extends HasSortKey>(list: Array<T>) {
  const normalized = new Array<T>(list.length);
  for (let i = 0; i < list.length; i++) {
    normalized[i] = { ...list[i], sortKey: i };
  }
  return normalized;
}

function insertItem<T extends HasSortKey>(
  list: Array<T>,
  index: number,
  item: Partial<T>
): Array<T> {
  if (list.length === 0) {
    list.push({ ...item, sortKey: 0 } as T);
  } else {
    // list is non-empty

    if (index === 0) {
      list.splice(0, 0, { ...item, sortKey: list[0].sortKey - 1 } as T);
    } else if (index < list.length) {
      // midpoint, index is non-zero and less than length

      const a = list[index - 1];
      const b = list[index];

      const m = (a.sortKey + b.sortKey) / 2;

      if (!(a.sortKey < m && m < b.sortKey)) {
        return insertItem(normalizeList(list), index, item);
      }

      list.splice(index, 0, { ...item, sortKey: m } as T);
    } else if (index === list.length) {
      list.push({ ...item, sortKey: list[list.length - 1].sortKey + 1 } as T);
    }
  }
  return list;
}

export function main() {
  const normalized: Array<number> = [];

  let list: Array<{ n: number } & HasSortKey> = [];

  list = insertItem(list, 0, { n: 0 });

  for (let n = 1; n < 10 * 1000; n++) {
    const list2 = insertItem(list, 1, { n });
    if (list2 !== list) {
      normalized.push(n);
    }
    list = list2;
  }

  let m = normalized[0];

  console.log(
    normalized.slice(1).map(n => {
      const k = n - m;
      m = n;
      return k;
    })
  );
}

Estando lá, feito isso, pode ter que fazer isso novamente. Use uma string como a chave de classificação, para que você possa sempre encontrar uma chave que esteja entre duas chaves fornecidas. Se as seqüências ficarem muito longas para o seu gosto, você deverá modificar várias ou todas as chaves de classificação.

Use números inteiros e defina a chave de classificação para a lista inicial como 500 * número do item. Ao inserir entre itens, você pode usar a média. Isso permitirá que muitas inserções iniciem com