Soft heap: cos'è la corruzione e perché è utile?

Question

Di recente ho letto l'articolo di Bernard Chazelle "The Soft Heap, una coda di priorità approssimativo con Optimal Error Rate da Bernard Chazelle" (http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf)

Il documento parla molto di "corruzione". Cos'è la corruzione, come si corrompono gli elementi e come ti aiuta?

Ho passato molto tempo a leggere il giornale e su Google e questo non ha ancora senso.

Answer 1

La risposta è nella seconda pagina:.

"Il mucchio morbido può, in qualsiasi momento, aumentare il valore di alcuni tasti Tali chiavi, e per estensione, gli elementi corrispondenti sono chiamati danneggiato danneggiamento. è interamente a discrezione della struttura dati e l'utente non ha il controllo su di esso Naturalmente findmin restituisce la chiave corrente minima, che potrebbe o meno essere corrotta. Il vantaggio è la velocità: durante gli aggiornamenti dell'heap, le voci viaggiano insieme nei pacchetti sotto forma di "car pooling", per risparmiare tempo Dal punto di vista dell'informatica, la corruzione è un modo per ecrease l'entropia dei dati memorizzati nella struttura dati, e quindi facilitare il suo trattamento . L'entropia è definita come il logaritmo, nella seconda base, del numero di assegnazioni di chiavi distinte (ad esempio, entropia della distribuzione uniforme sulle assegnazioni della chiave ). Per vedere la solidità di questa idea, spingerla al limite e osservare che se ogni chiave era corrotta aumentando il suo valore a `, allora il set di chiavi avrebbe zero entropia e potremmo banalmente eseguire tutte le operazioni in costante tempo. È interessante notare che, cumuli soffici mostrano che l'entropia non deve cadere a zero per la complessità di diventare costante."

Si tratta di una struttura di dati autolesionista?

Answer 2

Nella maggior parte dei documenti di ricerca su code di priorità, ogni elemento la coda ha un numero associato chiamato una priorità che viene impostata quando l'elemento è inserito.Gli elementi vengono poi rimossi dalla coda in ordine di priorità crescente.La maggior parte dei linguaggi di programmazione in questi giorni che supportano le code prioritarie in realtà non usano priorità esplicite e invece si basano su un confronto funzione per classificare gli elementi, ma l'heap morbido utilizza il modello di "priorità numerica associata"

Bec ause le code di priorità rimuovono gli elementi in ordine crescente di priorità, possono essere usati per ordinare una sequenza di valori - inizia inserendo ogni elemento nella coda di priorità con priorità uguale alla sua posizione nella sequenza, quindi rimuovendo tutti gli elementi dalla coda di priorità . Questo tira fuori gli elementi in ordine.

Questa connessione tra le code di priorità e l'ordinamento ha un costo, tuttavia. Esistono limiti inferiori noti negli algoritmi di confronto (nessun algoritmo di ordinamento di confronto può avere un tempo di esecuzione migliore di O (n log n)). Di conseguenza, esiste un limite inferiore sul runtime di qualsiasi coda di priorità basata sul confronto. Specificamente, n accodamenti e n dequeues devono avere un costo totale non migliore di O (n log n). Il più delle volte, va bene, ma in alcuni casi questo non è abbastanza veloce.

Fintantoché la coda di priorità può essere utilizzata per ordinare la sequenza di input, il tempo di esecuzione di n accodamenti e n dequeues non supererà mai O (n log n). Ma cosa succede se la coda di priorità non ordina l'input? Portalo all'estremo - se la coda di priorità restituisce gli elementi in un ordine totalmente arbitrario, allora è possibile implementare n accodamenti e cancellazioni nel tempo O (n) - basta usare uno stack o una coda, per esempio.

Intuitivamente, si può pensare a un ammasso morbido come un ponte tra i due estremi di "sempre ordinati" e "nessuna garanzia sull'ordine". Ogni heap di ordinamento è parametrizzato su alcune quantità e epsilon; chiamato "parametro di corruzione" che determina quanto vicino possono essere ordinati i valori che escono dall'heap morbido. Nello specifico, come & epsilon; si avvicina a 0, l'output sarà progressivamente più ordinato e come & epsilon; si avvicina a 1, l'uscita diventerà progressivamente più arbitraria. Appropriatamente, il runtime delle operazioni di heap virtuale è determinato come una funzione di O (log & epsilon; ^-1), quindi il runtime delle operazioni diventa più economico ed economico come & epsilon; sale (e, quindi, l'output diventa meno ordinato) e le operazioni diventano più costose come & epsilon; scende (nel qual caso l'output diventa sempre più ordinato).

L'heap morbido quantifica con precisione quanto l'output non sarà utilizzato utilizzando il nuovo concetto di "corruzione". In una normale coda di priorità, una volta inserita una coppia elemento/priorità, la priorità dell'elemento non cambia mai. In un heap morbido, gli elementi associati a una priorità possono diventare corretti quando l'elemento si trova nell'heap morbido. Quando la priorità di un elemento è corrotta, la sua priorità aumenta di qualche importo. (Poiché l'heap soft rimuove gli elementi in ordine crescente di priorità, la priorità di un elemento in aumento significa che uscirà dalla coda più tardi di quanto dovrebbe normalmente). In altre parole, la corruzione farà sì che gli elementi non vengano fuori in ordine, poiché le priorità degli elementi quando vengono rimosse dalla coda non sono necessariamente le stesse di quando sono accodate.

La scelta di & epsilon; sintonizza quanti elementi diversi possono avere le loro priorità corrotte. Con & epsilon; piccoli, pochi elementi hanno priorità danneggiate e con & epsilon; grandi, più elementi avranno priorità danneggiate.

Ora, alle vostre domande specifiche: in che modo le priorità degli elementi vengono danneggiate e in che modo ciò vi aiuta? La tua prima domanda è buona: come decide la struttura dei dati quando correggere le priorità? Ci sono due modi per vederlo. Innanzitutto, si può pensare a un heap morbido come una struttura di dati in cui si specifica in anticipo quanto sia accettabile la corruzione (è il parametro & epsilon;) e la struttura dei dati decide internamente quando e come corrompere le priorità finché non lo fa t superare alcuni livelli di corruzione totale. Se sembra strano che una struttura dati prenda decisioni come questa, pensa a qualcosa come un filtro Bloom o skiplist, in cui ci sono davvero scelte casuali interne che possono avere un impatto sul comportamento osservabile della struttura dei dati. Si scopre che l'heap morbido in genere non è implementato usando la casualità (una caratteristica impressionante da avere!), Ma non è particolarmente rilevante qui.

Internamente, i due implementazioni note di cumuli morbide (quello dal lavoro originale di Chazelle, e una pulizia in seguito utilizzando gli alberi binari) attuare corruzione utilizzando una tecnica chiamata carpooling cui elementi sono raggruppati insieme e condividono una priorità comune. La corruzione si verifica perché le priorità originali di tutti gli elementi di ciascun gruppo vengono dimenticate e viene invece utilizzata una nuova priorità. I dettagli effettivi di come gli elementi sono raggruppati sono spaventosamente complessi e non vale la pena esaminarli, quindi è probabilmente meglio lasciarli come "la struttura dati sceglie di corrompere come vuole, a patto che non corrompa più elementi di quanto hai specificato quando hai scelto & epsilon ;. "

Quindi, perché è utile? In pratica, non lo è. Il mucchio molle è quasi esclusivamente di interesse teorico. Il motivo per cui è bello in teoria è che il runtime di n inserzioni e cancellazioni n da un heap morbido può essere O (n) - più veloce di O (n log n) - se & epsilon; è scelto correttamente. Originariamente, gli heap morbidi sono stati utilizzati come un blocco predefinito in un algoritmo veloce per la costruzione di alberi con spanning minimo. Vengono anche utilizzati in un nuovo algoritmo per la selezione del tempo lineare, il primo algoritmo deterministico che viene eseguito in tempo lineare dal famoso algoritmo mediano-di-mediani.In entrambi questi casi, l'heap virtuale viene utilizzato per "approssimativamente" ordinare gli elementi di input in un modo che consenta agli algoritmi di ottenere un'approssimazione approssimativa di una sequenza ordinata, a quel punto l'algoritmo esegue una logica aggiuntiva per correggere la mancanza di perfezione. Quasi sicuramente non vedrai mai un mucchio morbido usato nella pratica, ma se finisci per trovare un caso in cui lo fai, lascia un commento e fammi sapere!

Riassumendo:

priorità

• corrompere è un modo di fare un compromesso tra perfetto ordinamento (esatta, ma lento) e ordine arbitrario (inesatta, ma molto veloce). Il parametro & epsilon; determina dove sullo spettro si trova la quantità di corruzione.
• La corruzione funziona modificando le priorità degli elementi esistenti nell'heap morbido, in particolare aumentando le priorità di alcuni elementi. La bassa corruzione corrisponde a sequenze approssimativamente ordinate, mentre l'alta corruzione corrisponde a sequenze più arbitrarie.
• Il modo in cui viene eseguita la corruzione è specifico per la struttura dei dati e molto difficile da comprendere. È meglio pensare ai soft stack come corruzione quando necessario, ma mai in un modo che superi il limite imposto dalla scelta di & epsilon ;.
• La corruzione è utile nelle impostazioni teoriche in cui l'ordinamento è troppo lento, ma una sequenza ordinata approssimativamente correttamente è sufficiente per scopi pratici. È improbabile che sia utile nella pratica.

Spero che questo aiuti!