Lista di priorità efficiente

Question

Sto cercando una struttura di dati efficiente per rappresentare una lista di priorità. Nello specifico, devo assegnare una priorità a un insieme di elementi e restituire solo gli elementi con il punteggio più alto. Ho esaminato le code di priorità che funzionano su heap, ma non sembrano adattarsi alle mie esigenze. Riorganizzeranno la struttura dell'heap non appena eseguirò il polling dell'elemento di valutazione superiore dalla coda.

La soluzione più semplice sarebbe ovviamente una lista collegata, che nel peggiore dei casi sarebbe necessario molto tempo per l'operazione di inserimento.

Qualcuno ha una soluzione migliore?

Answer 1

Cumuli sembrano molto adatto, e sembra che si sta andando su di esso in modo sbagliato.

detto che volevi gli elementi x top (come fa questo x confronta con n, btw?)

Quello che state facendo è mettere tutto in un max-heap e ottenere la x in alto.

Suggerisco, invece, di utilizzare un min-heap di esattamente x elementi.

I primi x elementi inseriti nell'heap.

Elemento successivo in entrata, si confronta con il minimo che può essere eseguito molto rapidamente (O (1) volta) nell'heap. Se è più piccolo, ignori semplicemente l'elemento in entrata.

Se l'elemento in entrata è più grande di min, quindi si aumenta il minimo per l'elemento in entrata e lo si spazia in basso nell'heap. Questo dovrebbe essere il momento logx nel peggiore dei casi.

Una volta fatto (nel tempo nlogx), è possibile recuperare gli elementi dal mucchio in modo ordinato in O (xlogx) tempo.

A seconda di come i dati sono al (e quanto piccolo x è), utilizzando questa soluzione min-heap può essere veramente veloce.

---

Se davvero vuole veramente gli inserti di essere super-veloce e non si preoccupano molto circa il recupero allora si può anche effettuare le seguenti operazioni.

inserire gli elementi in un vettore (array con O ammortizzato (1) inserire tempo) nell'ordine vengono.

L'uso l'algoritmo di selezione per trovare l'elemento X più grande (in O (n), ma le costanti potrebbero essere grande). Dire che il numero è S.

Ora piedi la matrice si confrontano ogni elemento con S e selezionare quelli grandi come S.

Se x è di dimensioni ragionevoli e paragonabile a n (come n/2 o qualcosa del genere) questo potrebbe funzionare bene, ma se x è piccolo rispetto a n, suggerirei di andare con il min-heap.

Answer 2

Hmm. Skip lists? Dovrebbero avere l'inserimento O (log n) (come coda basata su heap) ma ottenere l'elemento superiore dovrebbe essere O (1) [compresa la sua rimozione]. Potrebbero essere implementati anche usando l'algoritmo lock-free.

Answer 3

Il JDK ha una classe pqueue built-in (java.util.PriorityQueue) che si basa su un algoritmo heap.

Mi dispiace, ho appena visto il po 'di cumuli non si adattano alle vostre esigenze. Puoi spiegare perché? Puoi scrivere un comparatore personalizzato (o rendere i tuoi articoli comparabili) e PriorityQueue ordinerà i tuoi articoli in modo appropriato.

Answer 4

se avete bisogno solo le k migliori articoli e si mai bisogno di guardare agli altri, è possibile utilizzare una semplice lista collegata o un array memorizzare solo l'attuale top k articoli, più un numero (il punteggio peggiore degli elementi nell'elenco).

Nell'operazione Add() è sufficiente confrontare l'elemento con il valore peggiore nell'elenco e, se possibile, scambiare l'attuale peggiore con l'elemento aggiunto. Questo richiede O (k) tempo nel caso peggioreper l'inserimento in quanto è necessario trovare l'elemento che ha attualmente il punteggio peggiore. Il caso medio, tuttavia, è O (1), poiché, quando si aggiungono elementi migliori all'elenco, la probabilità di dover eseguire uno swap tende a 0 (ovvero, in realtà non si aggiungono oggetti) .

Quindi, se si generano elementi a caso, le prestazioni è probabile che sia molto buono. Anche se generi articoli ordinati (caso peggiore), potrebbe essere abbastanza veloce per il tuo valore di k.