Dijkstra su Java: ottenere risultati interessanti utilizzando un heap di Fibonacci rispetto a PriorityQueue

Question

Ho recentemente effettuato un confronto iniziale del tempo di esecuzione dell'algoritmo di Dijkstra utilizzando due strutture dati, il PriorityQueue basato su Java (basato su un heap binario, se I ' non mi sbaglio), e un ammasso di Fibonacci. Ho usato Java currentTimeMillis() per fare i miei calcoli. I risultati alla fine sono piuttosto interessanti. Questa è l'uscita per uno dei miei casi di test:

Running Dijkstra's with 8 nodes and 27 links 
- Execution time with binary heap: 1 miliseconds 
- Execution time with Fibonacci heap: 4 miliseconds 

Certo, io sono a corto di insiemi di dati al momento, con il grafico qui sopra è il mio più grande (ho intenzione di fare più presto). Ma ha senso? Ho sempre pensato che gli heap di Fibonacci fossero più veloci di altre strutture dati a causa del loro tempo di esecuzione ammortizzato rispetto alle altre strutture di dati. Non sono davvero sicuro di dove questa differenza di 3 millisecondi provenga. (Lo sto eseguendo su un processore Intel Core Ivy Bridge i7-3630M, se questo aiuta.)

Nota: sono incappato su this thread che potrebbe spiegare il problema, anche se non sono ancora chiaro il motivo per cui l'heap di Fibonacci la versione sta impiegando più tempo. Secondo quel thread, potrebbe essere dovuto al fatto che il mio grafico non è abbastanza denso e quindi il numero di operazioni con il tasto di diminuzione non è abbastanza grande da far brillare davvero le prestazioni dell'heap di Fibonacci. Questa sarebbe l'unica conclusione plausibile, o c'è qualcos'altro che mi manca?

Answer 1

di Fibonacci sono asintoticamente più veloce di cumuli binari (la struttura di dati utilizzata nella coda di priorità di Java), in algoritmo che di Dijkstra prenderanno O (m + n log n) con un mucchio di Fibonacci, ma O (m log n) con un heap binario. Ciò significa che per i grafici grandi e densi, nel caso peggiore, gli heap di Fibonacci saranno più veloci.

Sebbene gli heap di Fibonacci siano asintoticamente più veloci degli heap binari, hanno notoriamente grandi fattori costanti e molte operazioni di base sugli heap di Fibonacci richiedono molto tempo per essere completate. A lungo termine supereranno gli heap binari, ma per i piccoli grafici i termini costanti potrebbero essere così grandi che l'heap di Fibonacci è in realtà più lento.

In secondo luogo, confrontare i runtime asintotici (O (m + n log n) contro O (m log n)). Se il grafico che stai usando è sparse (cioè, m = O (n)), allora entrambi questi runtime asintotici sono gli stessi (O (n log n)). In tal caso, il vantaggio teorico degli heap di Fibonacci non è presente e l'heap binario potrebbe essere la scelta migliore.

Infine, si noti che la notazione O grande fa riferimento al comportamento del caso peggiore in questo caso, piuttosto che al caso medio. Qualche tempo fa c'era un documento che mostrava che per i grafici casuali di un certo tipo, l'algoritmo di Dijkstra sull'aspettativa è molto più basso del numero peggiore di operazioni con la chiave di decremento e di cancellazione. In tal caso, un heap binario potrebbe sovraperformare un heap di Fibonacci anche su grafici di grandi dimensioni, poiché il comportamento del caso peggiore non viene mai attivato.

Spero che questo aiuti!

Answer 2

Gli heap di Fibonacci sono più veloci asintotici, ma i loro fattori costanti non sono necessariamente eccezionali. Con input ridicolmente enormi di oltre un milione, potrebbero essere più veloci, ma per i piccoli input gli heap binari risulteranno notevolmente più veloci.

cumuli