13
Sto provando a scrivere un bilanciatore di carico in Haskell con la strategia di leastconn (in parte per divertimento ..). Ho bisogno di una coda di priorità dove solo le seguenti operazioni devono essere 'veloce':Coda di priorità rapida con aggiornamenti incrementali
- lettura minima della chiave
- +1 minima della chiave
- -1 su qualsiasi tasto
Se ho avuto un linguaggio imperativo con i puntatori, probabilmente venire con:
Head
|
Priority 0 -> Item <-> Item <-> Item <-> Item
|
Priority 1 -> Item <-> Item
|
Priority 4 -> Item <-> Item <-> Item
Le priorità sono collegati tramite un doppio collegamento lista, anche gli articoli per ogni priorità. Ogni Item contiene un collegamento alla priorità della testa. Tale struttura avrebbe complessità:
- O (1) per la chiave minima leggere - Prendere prima dalla coda sotto la testa
- O (1) per 1 - rimuovere prima voce sotto prioritaria, inserirla a livello inferiore (possibilmente creando un nuovo livello)
- O (1) per -1 - a condizione che abbiamo un puntatore all'elemento, possiamo accedere immediatamente alla Priorità, rimuovere l'elemento dall'elenco doppiamente collegato e inserirlo in uno diverso
Esiste una struttura dati (funzionale?) Che si comporterebbe in modo approssimativo? Il numero di elementi sarebbe approssimativamente al massimo un paio di centinaia.
Penso che sia un fatto abbastanza stabilito che non è possibile avere tutte le operazioni della coda di priorità O (1). Mentre l '"inserimento" o "rimozione" in quanto tale sono a buon mercato, il costo appare quando si considera il tempo per trovare il punto da inserire o rimuovere, e lo sforzo per riequilibrare (mantenere ordinati). –
Che dire di 'Data.Heap'? – josejuan
Sassa, questo vale per gli heap generici, ma quando limito le operazioni a +/- 1, posso aggiornare la priorità semplicemente spostandola verso l'alto o verso il basso nell'elenco delle priorità da un livello noto e cioè O (1) – ondra