Génération de clés de tri lors de la réorganisation des éléments

Nous avons un certain nombre d'articles que l'utilisateur final pourra organiser dans une commande souhaitée. L'ensemble des éléments n'est pas ordonné, mais chaque élément contient une clé de tri qui peut être modifiée.

Nous recherchons un algorithme qui permettrait de générer une nouvelle clé de tri pour un élément ajouté ou déplacé pour être le premier élément, le dernier élément ou entre deux éléments. Nous espérons avoir seulement à modifier la clé de tri de l'élément déplacé.

Un exemple d'algorithme serait que chaque clé de tri soit un nombre à virgule flottante, et lorsque vous placez un élément entre deux éléments, définissez la clé de tri sur leur moyenne. Placer un élément en premier ou en dernier prendrait la valeur la plus externe + - 1.

Le problème ici est que la précision en virgule flottante peut entraîner l'échec du tri. L'utilisation de deux nombres entiers pour représenter un nombre fractionnaire pourrait également faire en sorte que les nombres deviennent si grands qu'ils ne pourraient pas être représentés avec précision dans les types numériques réguliers (par exemple lors du transfert en JSON). Nous ne voudrions pas utiliser BigInts.

Existe-t-il un algorithme approprié pour cela qui fonctionnerait, par exemple, en utilisant des chaînes, qui ne seraient pas affectées par ces défauts?

Nous ne cherchons pas à prendre en charge un grand nombre de mouvements, mais l'algorithme décrit ci-dessus pourrait échouer sur un nombre à virgule flottante double précision après environ 50 mouvements.

En résumé de tous les commentaires et réponses:

TL; DR - L'utilisation de nombres à virgule flottante double précision avec l'algorithme initialement proposé devrait être suffisante pour la plupart des besoins pratiques (au moins commandés manuellement). Il convient également de tenir à jour une liste ordonnée séparée des éléments. D'autres solutions clés de tri sont quelque peu lourdes.

Les deux opérations problématiques consistent à insérer des éléments au début / à la fin encore et encore, et à insérer ou à déplacer des éléments de manière répétée au même endroit (par exemple, avec trois éléments déplaçant à plusieurs reprises le troisième élément entre les deux premiers, ou ajoutant à plusieurs reprises de nouveaux éléments comme deuxième élément).

D'un point de vue théorique (c'est-à-dire permettant une réorganisation infinie), la seule solution à laquelle je peux penser est d'utiliser deux entiers de taille illimitée en tant que fractionnaire a / b. Cela permet une précision infinie pour les inserts médians, mais les nombres peuvent devenir de plus en plus grands.

Les chaînes peuvent prendre en charge un grand nombre de mises à jour (bien que j'ai toujours du mal à trouver l'algorithme pour les deux opérations), mais pas infinies, car vous ne pouvez pas en ajouter infiniment à la première position (au moins en utilisant le tri régulier des chaînes Comparaison).

Les entiers nécessitent de choisir un espacement initial pour les clés de tri, ce qui limite le nombre d'insertions intermédiaires que vous pouvez effectuer. Si vous séparez initialement les clés de tri à 1024, vous ne pouvez effectuer que 10 insertions médianes dans le pire des cas avant d'avoir des numéros adjacents. Le choix d'un espacement initial plus grand limite le nombre de premières / dernières insertions que vous pouvez effectuer. En utilisant un entier 64 bits, vous êtes limité à ~ 63 opérations dans les deux cas, que vous devez répartir entre les insertions intermédiaires et les premières / dernières insertions a priori.

L'utilisation de valeurs à virgule flottante supprime la nécessité de sélectionner l'espacement a priori. L'algorithme est simple:

1. Le premier élément inséré a une clé de tri 0.0
2. Un élément inséré (ou déplacé) en premier ou en dernier a la clé de tri du premier élément - 1.0 ou dernier élément + 1.0, respectivement.
3. Un élément inséré (ou déplacé) entre deux éléments a une clé de tri égale à la moyenne des deux.

L'utilisation d'un flotteur à double précision permet 52 inserts médians dans le pire des cas et effectivement infinis (environ 1e15) premier / dernier inserts. En pratique, lorsque vous déplacez des éléments autour de l'algorithme, il doit s'auto-corriger, car chaque fois que vous déplacez un élément en premier ou en dernier, il étend la plage qui peut être utilisée.

Les flotteurs à double précision ont également l'avantage d'être pris en charge par toutes les plates-formes et facilement stockés et transportés par pratiquement tous les formats de transport et bibliothèques. C'est ce que nous avons fini par utiliser.

J'ai rédigé une solution en TypeScript basée sur le résumé de @ Sampo. Le code se trouve ci-dessous.

Quelques informations ont été acquises en cours de route.

• Seule l' insertion au milieu entre deux clés de tri existantes doit générer une nouvelle clé de tri, l'échange (c'est-à-dire la réorganisation) ne provoque pas de fractionnement (c'est-à-dire de nouveaux points médians). Si vous déplacez deux éléments et que vous n'en touchez qu'un, vous perdez des informations sur les deux éléments qui ont changé de position dans la liste. Même si c'était une exigence pour commencer, notez bien que c'est une bonne idée

• Tous les 1074: e fractionnement à mi-chemin, nous devons normaliser la plage de virgule flottante. Nous détectons cela en vérifiant simplement si le nouveau point médian satisfait l'invariant

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

• La mise à l'échelle n'a pas d'importance, car les clés de tri sont normalisées, la normalisation se produit toujours à chaque 1074division du milieu. La situation ne s'améliorerait pas si nous distribuions les chiffres plus largement pour commencer.

• La normalisation des clés de tri est incroyablement rare. Vous amortirez ce coût au point où la normalisation ne sera pas perceptible. Cependant, je serais prudent avec cette approche si vous avez plus de 1000 éléments.

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;
    })
  );
}

J'y suis allé, j'ai fait ça, il faudra peut-être recommencer. Utilisez une chaîne comme clé de tri, vous pouvez toujours trouver une clé qui se trouve entre deux clés données. Si les chaînes deviennent trop longues à votre goût, vous devez modifier plusieurs ou toutes les clés de tri.

Utilisez des entiers et définissez la clé de tri pour la liste initiale sur 500 * numéro d'élément. Lors de l'insertion entre les éléments, vous pouvez utiliser la moyenne. Cela permettra à de nombreuses insertions de commencer par