Generieren von Sortierschlüsseln beim Neuordnen von Elementen

Wir haben eine Reihe von Artikeln, die der Endbenutzer in einer gewünschten Reihenfolge organisieren kann. Die Menge der Elemente ist ungeordnet, aber jedes Element enthält einen Sortierschlüssel, der geändert werden kann.

Wir suchen nach einem Algorithmus, mit dem ein neuer Sortierschlüssel für ein Element generiert werden kann, das hinzugefügt oder verschoben wird, um entweder das erste Element, das letzte Element oder zwischen zwei beliebigen Elementen zu sein. Wir hoffen, dass wir nur den Sortierschlüssel des zu verschiebenden Elements ändern müssen.

Ein Beispielalgorithmus wäre, dass jeder Sortierschlüssel eine Gleitkommazahl ist, und wenn Sie ein Element zwischen zwei Elementen platzieren, setzen Sie den Sortierschlüssel auf ihren Durchschnitt. Das erste oder letzte Platzieren eines Elements würde den äußersten Wert + - 1 annehmen.

Das Problem hierbei ist, dass die Gleitkommapräzision dazu führen kann, dass die Sortierung fehlschlägt. Die Verwendung von zwei Ganzzahlen zur Darstellung einer Bruchzahl könnte in ähnlicher Weise dazu führen, dass die Zahlen so groß werden, dass sie in regulären numerischen Typen nicht genau dargestellt werden können (z. B. bei der Übertragung als JSON). Wir würden BigInts nicht verwenden wollen.

Gibt es dafür einen geeigneten Algorithmus, der beispielsweise mit Strings funktioniert, die von diesen Mängeln nicht betroffen sind?

Wir möchten keine große Anzahl von Zügen unterstützen, aber der oben beschriebene Algorithmus könnte bei einer Gleitkommazahl mit doppelter Genauigkeit nach etwa 50 Zügen fehlschlagen.

Als Zusammenfassung aller Kommentare und Antworten:

TL; DR - Die Verwendung von Gleitkommazahlen mit doppelter Genauigkeit mit dem ursprünglich vorgeschlagenen Algorithmus sollte für die meisten praktischen (zumindest manuell geordneten) Anforderungen ausreichen. Die Pflege einer separaten geordneten Liste der Elemente sollte ebenfalls berücksichtigt werden. Andere Sortierschlüssellösungen sind etwas umständlich.

Die zwei problematischen Operationen bestehen darin, Elemente am Anfang / Ende immer wieder einzufügen und Elemente wiederholt an derselben Stelle einzufügen oder zu verschieben (z. B. wenn drei Elemente das dritte Element wiederholt zwischen den ersten beiden verschieben oder wiederholt neue Elemente als zweites hinzufügen Element).

Aus theoretischer Sicht (dh Ermöglichen einer unendlichen Neuordnung) besteht die einzige Lösung, die ich mir vorstellen kann, darin, zwei Ganzzahlen mit unbegrenzter Größe als Bruchteil a / b zu verwenden. Dies ermöglicht eine unendliche Präzision für die mittleren Einsätze, aber die Zahlen können immer größer werden.

Strings können möglicherweise eine große Anzahl von Aktualisierungen unterstützen (obwohl ich immer noch Probleme habe, den Algorithmus für beide Operationen herauszufinden), aber nicht unendlich, da Sie an der ersten Position nicht unendlich viele hinzufügen können (zumindest bei Verwendung der regulären String-Sortierung) Vergleich).

Ganzzahlen erfordern die Auswahl eines Anfangsabstands für die Sortierschlüssel, wodurch die Anzahl der Mid-Inserts begrenzt wird, die Sie ausführen können. Wenn Sie die Sortierschlüssel 1024 anfangs voneinander trennen, können Sie nur 10 Worst-Case-Mid-Inserts ausführen, bevor Sie benachbarte Nummern haben. Durch Auswahl eines größeren Anfangsabstands wird die Anzahl der ersten / letzten Einfügungen begrenzt, die Sie ausführen können. Bei Verwendung einer 64-Bit-Ganzzahl sind Sie in beiden Fällen auf ~ 63 Operationen beschränkt, die Sie a priori zwischen Mid-Inserts und First / Last-Inserts aufteilen müssen.

Durch die Verwendung von Gleitkommawerten entfällt die Notwendigkeit, den Abstand a priori auszuwählen. Der Algorithmus ist einfach:

1. Das erste eingefügte Element hat einen Sortierschlüssel 0.0
2. Ein zuerst oder zuletzt eingefügtes (oder verschobenes) Element hat den Sortierschlüssel des ersten Elements - 1.0 bzw. des letzten Elements + 1.0.
3. Ein zwischen zwei Elementen eingefügtes (oder verschobenes) Element hat einen Sortierschlüssel, der dem Durchschnitt der beiden Elemente entspricht.

Die Verwendung eines Schwimmers mit doppelter Genauigkeit ermöglicht 52 Worst-Case-Mid-Inserts und effektiv unendliche (ca. 1e15) First / Last-Inserts. In der Praxis sollte sich das Verschieben von Elementen im Algorithmus selbst korrigieren, da jedes Mal, wenn Sie ein Element zuerst oder zuletzt verschieben, der Bereich erweitert wird, der verwendet werden kann.

Floats mit doppelter Genauigkeit haben auch den Vorteil, dass sie von allen Plattformen unterstützt und von praktisch allen Transportformaten und Bibliotheken problemlos gespeichert und transportiert werden können. Das haben wir letztendlich benutzt.

Ich habe eine Lösung in TypeScript basierend auf der Zusammenfassung von @ Sampo geschrieben. Den Code finden Sie unten.

Ein paar Erkenntnisse auf dem Weg gewonnen.

• Nur das Einfügen in der Mitte zwischen zwei vorhandenen Sortierschlüsseln muss einen neuen Sortierschlüssel generieren. Das Austauschen (dh Neuanordnen) führt nicht zu Teilungen (dh neuen Mittelpunkten). Wenn Sie zwei Elemente verschieben und nur eines davon berühren, verlieren Sie Informationen darüber, welche zwei Elemente die Position in der Liste geändert haben. Auch wenn dies von Anfang an erforderlich war, beachten Sie, dass dies eine gute Idee ist

• Bei jeder 1074: Mittelpunktaufteilung müssen wir den Gleitkommabereich normalisieren. Wir erkennen dies, indem wir einfach prüfen, ob der neue Mittelpunkt die Invariante erfüllt

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

• Die Skalierung spielt keine Rolle, da die Sortierschlüssel normalisiert sind, erfolgt die Normalisierung immer noch bei jeder 1074Mittelpunktaufteilung. Die Situation würde sich nicht verbessern, wenn wir die Zahlen zunächst weiter verteilen würden.

• Die Normalisierung von Sortierschlüsseln ist unglaublich selten. Sie werden diese Kosten bis zu einem Punkt amortisieren, an dem die Normalisierung nicht mehr erkennbar ist. Allerdings wäre ich bei diesem Ansatz vorsichtig, wenn Sie mehr als 1000 Elemente haben.

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

Dort gewesen, getan, muss das vielleicht noch einmal tun. Verwenden Sie eine Zeichenfolge als Sortierschlüssel. Dann finden Sie immer einen Schlüssel zwischen zwei angegebenen Schlüsseln. Wenn die Zeichenfolgen für Ihren Geschmack zu lang werden, müssen Sie mehrere oder alle Sortierschlüssel ändern.

Verwenden Sie Ganzzahlen und setzen Sie den Sortierschlüssel für die Anfangsliste auf 500 * Artikelnummer. Beim Einfügen zwischen Elementen können Sie den Durchschnitt verwenden. Dies ermöglicht zunächst viele Einfügungen