Generazione di chiavi di ordinamento durante il riordino degli articoli

Come riepilogo di tutti i commenti e le risposte:

TL; DR - L'uso di numeri in virgola mobile a precisione doppia con l'algoritmo inizialmente proposto dovrebbe essere sufficiente per la maggior parte dei bisogni pratici (almeno ordinati manualmente). Dovrebbe essere considerato anche il mantenimento di un elenco ordinato separato degli elementi. Altre soluzioni chiave di ordinamento sono piuttosto ingombranti.

Le due operazioni problematiche sono l'inserimento di elementi all'inizio / alla fine più e più volte, e l'inserimento ripetuto o lo spostamento di oggetti nello stesso punto (ad esempio con tre elementi ripetutamente spostando il terzo elemento tra i primi due o ripetutamente aggiungendo nuovi elementi come secondo elemento).

Da un punto di vista teorico (cioè permettendo il riordino infinito), l'unica soluzione che posso pensare è usare due numeri interi illimitati come un a / b frazionario. Ciò consente una precisione infinita per gli inserti intermedi, ma i numeri possono diventare sempre più grandi.

Le stringhe possono essere in grado di supportare un gran numero di aggiornamenti (anche se sto ancora avendo problemi a capire l'algoritmo per entrambe le operazioni), ma non infinito, perché non puoi aggiungere infinitamente molti nella prima posizione (almeno usando confronto ordinamento di stringhe regolari).

Gli integer richiederebbero una spaziatura iniziale per le chiavi di ordinamento, il che limita il numero di inserti intermedi che è possibile eseguire. Se inizialmente si spaziano le chiavi di ordinamento 1024 a parte, è possibile eseguire solo 10 inserti intermedi nella peggiore delle ipotesi prima di avere numeri adiacenti. La scelta di una spaziatura iniziale più ampia limita il numero di primi / ultimi inserimenti che è possibile eseguire. Usando un numero intero a 64 bit, sei limitato a ~ 63 operazioni in entrambi i modi, che devi dividere a metà tra inserti a metà e primo / ultimo inserto a priori.

L'utilizzo dei valori a virgola mobile elimina la necessità di selezionare a priori la spaziatura. L'algoritmo è semplice:

1. Il primo elemento inserito ha una chiave di ordinamento 0.0
2. Un elemento inserito (o spostato) prima o l'ultimo ha la chiave di ordinamento del primo elemento - 1.0 o ultimo elemento + 1.0, rispettivamente.
3. Un elemento inserito (o spostato) tra due elementi ha una chiave di ordinamento uguale alla media dei due.

L'uso di un float a precisione doppia consente di inserire 52 inserti intermedi nel caso peggiore e di inserire il primo / ultimo effettivamente infinito (circa 1e15). In pratica quando lo spostamento degli elementi attorno all'algoritmo dovrebbe auto-correggersi, poiché ogni volta che si sposta un oggetto per primo o per ultimo si espande l'intervallo che può essere utilizzato.

I galleggianti a doppia precisione hanno anche il vantaggio che sono supportati da tutte le piattaforme e facilmente memorizzati e trasportati praticamente da tutti i formati e librerie di trasporto. Questo è quello che abbiamo finito usando.

Stai cercando di risolvere un problema che nasce da una mancata corrispondenza tra il tipo di informazioni con cui vuoi lavorare (sequenza ordinata) e i dati che hai (set non ordinato). Una buona strategia per risolvere questo problema è assicurarsi che le informazioni e i dati corrispondano, perché allora il programma sarà semplice.

Quindi consiglierei il seguente approccio:

• Crea un elenco ordinato dei dati non ordinati
• Consenti all'utente di lavorare con l'elenco ora ordinato

Sono abbastanza sicuro che non comporterà runtime o costi di memoria apprezzabili (rispetto alle chiavi di ordinamento) se fatto bene.

Usa numeri interi e imposta la chiave di ordinamento per l'elenco iniziale come un numero di articolo di 500 *. Quando si inserisce tra gli elementi è possibile utilizzare la media. Ciò consentirà a molti inserimenti di iniziare con