Qual è l'utilizzo di Splay Trees nel mondo reale?

Naviga le tue risposte
6

Ho deciso di conoscere gli alberi di ricerca bilanciati, quindi ho scelto 2-3-4 e alberi splay. Quali sono gli esempi dell'uso di splay tree nel mondo reale?

In questo Cornell: link Ho letto che gli Splay Tree sono "Un buon esempio è un router di rete". Ma dal resto della spiegazione le cuciture come i router di rete usano le tabelle hash e non gli alberi splay poiché il tempo di ricerca è costante invece di O (log n).

    
posta Meena 21.10.2012 - 00:32
fonte

1 risposta

4

È importante notare che le tabelle hash hanno solo un tempo di accesso medio di O(1) . Ciò significa che un'operazione particolare potrebbe essere molto peggio. Inoltre, ci sono diversi requisiti per gli hash opportunamente formati:

  • Quasi vuoto - alcuni algoritmi di hash funzionano ben oltre il 70% di utilizzo e la maggior parte consiglia l'utilizzo del 50%.
  • La gestione delle collisioni è complessa: è necessario utilizzare un elenco come "valore memorizzato" o accettare un tempo di ricerca lineare nel caso peggiore
  • Costo di hash: devi eseguire un'operazione di hashing, che può richiedere o meno un sacco di lavoro

Sembra che il corso menzioni che in molti router questi problemi sono stati risolti, quindi usano una tabella hash per l'archiviazione. Tuttavia, ci sono diversi vantaggi nello splay tree

  • Nessun sovraccarico - se assegni 10 MB allo spazio di archiviazione ottieni 10 MB di dati senza modificare i tuoi tempi di esecuzione
  • Preferenze di accesso recenti: i dati recenti sono più facilmente accessibili e i router accedono frequentemente a dati più recenti (è probabile che i nuovi nodi di rete parlino e la maggior parte delle reti non venga utilizzata in modo uniforme)
  • I duplicati vanno bene - può essere utile a seconda di cosa stai memorizzando
  • Implementazione semplice: i router vengono generalmente eseguiti su processori abbastanza deboli e sono incredibilmente difficili da aggiornare, quindi la semplicità è buona

Sfortunatamente questo non risponde alla tua domanda direttamente, ma spero che faccia luce sul perché questo sia il caso.

A proposito, ecco alcune note sul motivo per cui i router potrebbero essersi allontanati (questi si allineano con vantaggi):

  • Le dimensioni dello spazio di archiviazione sono aumentate, a causa del costo della RAM in esaurimento, la possibilità di conservare le cose in memoria è più semplice
  • Le tabelle hash, se correttamente gestite, hanno accesso costante a tutti gli elementi
  • Le tabelle hash possono gestire i duplicati se ne hai bisogno a
  • I produttori di router sono generalmente di lunga durata e possono superare i problemi di complessità con il tempo
risposta data 21.10.2012 - 00:48
fonte

Leggi altre domande sui tag

Come recuperare i messaggi di commit da bitbucket per consentire al project manager di vedere assegnazione della variabile globale Pythonesque