Generowanie kluczy sortowania podczas zmiany kolejności elementów

Mamy wiele elementów, które użytkownik końcowy będzie mógł uporządkować w pożądanym porządku. Zestaw elementów jest nieuporządkowany, ale każdy element zawiera klucz sortowania, który można modyfikować.

Szukamy algorytmu, który pozwoliłby wygenerować nowy klucz sortowania dla elementu, który jest dodawany lub przenoszony jako pierwszy element, ostatni element lub pomiędzy dowolnymi dwoma elementami. Mamy nadzieję, że będziemy musieli jedynie zmodyfikować klucz sortowania przenoszonego elementu.

Przykładowym algorytmem byłoby, aby każdy klucz sortowania był liczbą zmiennoprzecinkową, a umieszczając element między dwoma elementami, ustaw klucz sortowania na ich średnią. Umieszczenie przedmiotu na pierwszym lub ostatnim miejscu przyjąłoby najwyższą wartość + - 1.

Problem polega na tym, że precyzja zmiennoprzecinkowa może spowodować niepowodzenie sortowania. Użycie dwóch liczb całkowitych do przedstawienia liczby ułamkowej może również spowodować, że liczby staną się tak duże, że nie będą mogły być dokładnie przedstawione w zwykłych typach liczbowych (np. Podczas przesyłania jako JSON). Nie chcielibyśmy używać BigInts.

Czy istnieje odpowiedni algorytm, który działałby na przykład przy użyciu ciągów, na które te niedociągnięcia nie miałyby wpływu?

Nie chcemy obsługiwać dużej liczby ruchów, ale algorytm opisany powyżej może zawieść na liczbach zmiennoprzecinkowych podwójnej precyzji po około 50 ruchach.

Jako podsumowanie wszystkich komentarzy i odpowiedzi:

TL; DR - Użycie liczb zmiennoprzecinkowych podwójnej precyzji z wstępnie zaproponowanym algorytmem powinno wystarczyć do najbardziej praktycznych (przynajmniej ręcznie zamówionych) potrzeb. Należy również wziąć pod uwagę oddzielną uporządkowaną listę elementów. Inne kluczowe rozwiązania są nieco kłopotliwe.

Dwie problematyczne operacje to ciągłe wstawianie elementów na początku / końcu oraz wielokrotne wstawianie lub przenoszenie elementów w to samo miejsce (np. Trzy elementy wielokrotnie przesuwają trzeci element między pierwszymi dwoma lub wielokrotnie dodają nowe elementy jako drugi element).

Z teoretycznego punktu widzenia (tj. Umożliwienia nieskończonego ponownego zamawiania) jedynym rozwiązaniem, o którym mogę myśleć, jest użycie dwóch liczb całkowitych o nieograniczonym rozmiarze jako ułamka a / b. Pozwala to na nieskończoną precyzję wstawek środkowych, ale liczby mogą być coraz większe.

Ciągi mogą być w stanie obsłużyć dużą liczbę aktualizacji (chociaż wciąż mam problem z ustaleniem algorytmu dla obu operacji), ale nie są nieskończone, ponieważ nie można dodać nieskończenie wielu na pierwszej pozycji (przynajmniej używając zwykłego sortowania ciągów porównanie).

Liczby całkowite wymagałyby wybrania początkowego odstępu dla klawiszy sortowania, co ogranicza liczbę możliwych do wprowadzenia wstawek środkowych. Jeśli początkowo rozdzielisz klawisze sortowania 1024 od siebie, możesz wykonać tylko 10 najgorszych wstawień środkowych, zanim będziesz mieć sąsiednie liczby. Wybór większego początkowego odstępu ogranicza liczbę pierwszych / ostatnich wstawek, które można wykonać. Używając 64-bitowej liczby całkowitej, w obu przypadkach jesteś ograniczony do ~ 63 operacji, które musisz podzielić pomiędzy wstawki środkowe i wstawienia a priori pierwsze / ostatnie.

Korzystanie z wartości zmiennoprzecinkowych eliminuje potrzebę wybierania odstępów z góry. Algorytm jest prosty:

1. Pierwszy wstawiony element ma klucz sortowania 0.0
2. Element wstawiony (lub przeniesiony) pierwszy lub ostatni ma klucz sortowania pierwszego elementu - odpowiednio 1.0 lub ostatni element + 1.0.
3. Element wstawiony (lub przesunięty) między dwoma elementami ma klucz sortowania równy średniej z dwóch.

Zastosowanie pływaka o podwójnej precyzji pozwala na 52 najgorsze wstawki środkowe i skutecznie nieskończone (około 1e15) pierwsze / ostatnie wstawki. W praktyce przenoszenie elementów wokół algorytmu powinno się samo korygować, ponieważ za każdym razem, gdy przenosisz element pierwszy lub ostatni, rozszerza zakres, którego można użyć.

Pływaki podwójnej precyzji mają również tę zaletę, że są obsługiwane przez wszystkie platformy oraz łatwe do przechowywania i transportu przez praktycznie wszystkie formaty i biblioteki transportowe. Tego właśnie użyliśmy.

Napisałem rozwiązanie w TypeScript na podstawie podsumowania @ Sampo. Kod można znaleźć poniżej.

Kilka spostrzeżeń zdobytych po drodze.

• Tylko wstawienie w środku między dwoma istniejącymi kluczami sortowania wymaga wygenerowania nowego klucza sortowania, zamiana (tj. Zmiana kolejności) nie powoduje podziałów (tj. Nowych punktów środkowych). Jeśli przesuniesz dwa elementy i dotkniesz tylko jednego z nich, tracisz informacje o tym, jakie dwa elementy zmieniły pozycję na liście. Nawet jeśli był to wymóg na początek, pamiętaj, że to dobry pomysł

• Co 1074: piąty punkt środkowy musimy znormalizować zakres zmiennoprzecinkowy. Wykrywamy to po prostu sprawdzając, czy nowy punkt środkowy spełnia niezmiennik

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

• Skalowanie nie ma znaczenia, ponieważ klucze sortowania są znormalizowane, normalizacja wciąż zachodzi przy każdym 1074podziale punktu środkowego. Sytuacja nie poprawiłaby się, gdybyśmy na początku rozpowszechnili liczby szerzej.

• Normalizacja sortowania kluczy jest niezwykle rzadka. Zamortyzujesz ten koszt do momentu, w którym normalizacja nie będzie zauważalna. Chociaż byłbym ostrożny z tym podejściem, jeśli masz ponad 1000 elementów.

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

Byłem tam, zrobiłem to, może trzeba to zrobić ponownie. Użyj ciągu jako klucza sortowania, wtedy zawsze możesz znaleźć klucz, który znajduje się między dwoma danymi kluczami. Jeśli ciągi stają się zbyt długie jak na twój gust, musisz zmodyfikować wiele lub wszystkie klucze sortowania.

Użyj liczb całkowitych i ustaw klucz sortowania dla początkowej listy na 500 * numer pozycji. Podczas wstawiania między elementami można użyć średniej. Umożliwi to rozpoczęcie wielu wstawień