Algoritmi di smistamento vicino - Quando si usa?

Question

Di tanto in tanto navigo sul web e cerco interessanti algoritmi e strutture dati da mettere nella mia borsa dei trucchi. Un anno fa mi sono imbattuto nella Soft Heap e ho imparato a conoscere l'ordinamento vicino.

L'idea alla base di ciò è che è possibile rompere la barriera O (n log n) degli ordinamenti basati sul confronto se si riesce a convivere con il fatto che l'algoritmo di ordinamento imbroglia un po '. Ottieni un elenco quasi ordinato ma devi convivere anche con alcuni errori.

Ho giocato con gli algoritmi in un ambiente di test ma non ho mai trovato un uso per loro.

Quindi la domanda: qualcuno ha mai usato vicino all'ordinamento in pratica? In tal caso in quale tipo di applicazioni? Riesci a pensare a un caso d'uso in cui lo smistamento vicino è la cosa giusta da fare?

Answer 1

Ci sono molti "golosi" euristica in cui si seleziona periodicamente il minimo di un set. L'euristica avida non è perfetta, quindi anche se scegli il minimo non sei sicuro di arrivare alla migliore risposta finale. In effetti, il GRASP meta-euristico, si introduce intenzionalmente un errore casuale in modo da ottenere più finali soluzioni e selezionare quella migliore. In tal caso, introdurre un errore nella routine di ordinamento in cambio della velocità sarebbe un buon compromesso.

Answer 2

Questa è un'ipotesi di volo totale, ma data la soggettività intrinseca di "pertinenza" misure durante l'ordinamento dei risultati di ricerca, mi permetto di non importa se sono perfettamente ordinati o meno. Lo stesso si può dire per le raccomandazioni. Se riesci in qualche modo a sistemare che ogni altra parte del tuo algoritmo per quelle cose è O (n), potresti cercare di evitare una specie.

Ricorda anche che nel peggiore dei casi il tuo "quasi ordinato" i dati non soddisfano una possibile idea intuitiva di "quasi ordinata", ovvero che ha solo un piccolo numero di inversioni. La ragione di ciò è solo che se i tuoi dati hanno solo inversioni O (n), puoi finire di ordinarli in tempo O (n) usando l'ordinamento di inserzione o l'ordinamento cocktail (ovvero l'ordinamento a bolle bidirezionale). Ne consegue che non è possibile aver raggiunto questo punto da completamente indifferenziato, in O (n) tempo (usando i confronti). Quindi stai cercando applicazioni in cui un sottoinsieme maggioritario dei dati è ordinato e il resto è sparso, non per le applicazioni che richiedono che ogni elemento sia vicino alla sua posizione corretta.

Answer 3

Sto solo speculando qui, ma una cosa che immagino è l'ottimizzazione delle query del database.

Una query di database in un linguaggio dichiarativo come SQL deve essere tradotta in un programma passo-passo chiamato "piano di esecuzione". Una query SQL può in genere essere tradotta in un numero di tali piani di esecuzione, che danno tutti lo stesso risultato ma possono avere prestazioni molto diverse. Query Optimizer deve trovare il più veloce, o almeno uno che sia ragionevolmente veloce.

Gli ottimizzatori di query basati sui costi hanno una "funzione di costo" che usano per stimare i tempi di esecuzione di un determinato piano. Gli ottimizzatori esaustivi esaminano tutti i possibili piani (per un certo valore di "tutti i possibili") e selezionano il più veloce. Per domande complicate il numero di possibili piani può essere proibitivamente elevato, portando a tempi di ottimizzazione eccessivamente lunghi (prima ancora di iniziare la ricerca nel database!), Quindi ci sono anche ottimizzatori non esaustivi. Osservano solo alcuni dei piani, forse con un elemento casuale nella scelta di quali. Funziona, dato che di solito c'è un gran numero di "buono" piani, e potrebbe non essere così importante trovare il migliore in assoluto - è probabilmente meglio scegliere un piano di 5 secondi anziché il piano ottimale di 2 secondi, se per trovare i 2 secondi sono necessari diversi minuti di ottimizzazione piano.

Alcuni algoritmi di ottimizzazione utilizzano una coda ordinata di " promettente " piani (parziali). Se non importa davvero se trovi il piano assolutamente migliore, forse potresti usare una coda quasi ordinata?

Un'altra idea (e sto ancora solo ipotizzando) è uno scheduler per processi o thread in un sistema di condivisione del tempo, dove potrebbe non essere importante se un determinato processo o thread ottiene il suo intervallo di tempo pochi millisecondi dopo che se rigorosamente ordinati per priorità.

Answer 4

Un'applicazione comune per l'ordinamento vicino è quando un essere umano sta facendo il confronto a coppie e non si vuole fare loro tante domande.

Supponi di avere un sacco di oggetti che vorresti ordinare da un essere umano tramite un confronto a coppie. Puoi ridurre notevolmente il numero di confronti che devi fare se sei disposto ad accettare che l'ordine non sarà esatto. Ad esempio, potresti non preoccuparti se gli oggetti adiacenti sono stati scambiati a condizione che gli elementi preferiti siano in alto.

Answer 5

Ovunque

1. dovresti reagire velocemente,
2. non stai promettendo un comportamento esatto al cliente,
3. ma internamente hai delle regole

puoi usarlo. Che ne dici di "non così rigoroso" coda di priorità basata su regole? Dove sarebbe utile? Forse pianificazione thread / processo / risorsa. Nella pianificazione di thread / processi non stai davvero promettendo che nessun thread andrà per primo, secondo o ultimo, ma in genere vuoi dare a tutti una possibilità. Potresti voler applicare una regola libera in modo che sia preventiva, prioritaria, blabla ..

Un esempio di pianificazione delle risorse potrebbe rispondere alla consegna della pizza o alla spedizione di scatole di libri a persone, ecc. Non puoi usarlo dove ci si aspetta un risultato deterministico, ma ci sono molti esempi nella vita reale in cui le cose non sono così deterministiche / prevedibile.

Answer 6

O (n log n) è già abbastanza veloce. Non penso che nessuno avrebbe mai iniziato usando un algoritmo quasi-ordinato. Inizieresti con un codice che fa solo un ordinamento completo (dal momento che il tuo linguaggio di programmazione prescelto fornisce probabilmente una funzione sort e non una funzione nearsort ), e quando lo hai trovato empiricamente che l'ordinamento stava impiegando troppo tempo, inizieresti a chiederti se i tuoi dati realmente debbano essere completamente ordinati e prendere in considerazione l'uso di un quasi ordinamento.

Fondamentalmente, non prenderei mai in considerazione l'uso di un ordinamento vicino a meno che tu non abbia scoperto l'ordinamento come un grave collo di bottiglia nel tuo programma.