Perché utilizzare la ricerca binaria se esiste una ricerca ternaria?

https://stackoverflow.com/questions/3498382

29-09-2019
|

Domanda

Recentemente ho sentito parlare della ricerca ternaria in cui dividiamo un array in 3 parti e confrontiamo.Qui ci saranno due confronti ma questo ridurrà l'array a n/3.Perché le persone non ne usano così tanto?

Soluzione

In realtà, le persone fanno uso alberi k-ary per k arbitrario.

Questo è, tuttavia, un compromesso.

Per trovare un elemento in un albero k-ario, è bisogno di circa k ln * (N) / ln (k) operazioni (ricordate la formula cambio-di-base). Più grande è la vostra k è, le operazioni più generale è necessario.

La logica estensione di quello che stai dicendo è "il motivo per cui le persone non usano un albero n-ario per elementi di dati N?". Il che, ovviamente, sarebbe un array.

Altri suggerimenti

Un ternario di ricerca sarà ancora vi darà la stessa complessità asintotica O (log N) cercare il tempo, e aggiunge complessità alla implementazione.

Lo stesso ragionamento si può dire per il motivo per cui non si vuole una ricerca quad o qualsiasi altro ordine superiore.

Ricerca 1 miliardo (un miliardo di US - 1000000000) risolto articoli sarebbero prendere una media di circa 15 confronta con ricerca binaria e circa 9 confronta con una ricerca ternario - non è un grande vantaggio. E nota che ogni 'ternario confrontare' potrebbe comportare 2 confronti attuali.

Wow. Il Top Votati risposte perdere la barca su questo, credo.

La CPU non supporta ternario logica come una singola operazione; si rompe logica ternaria in varie fasi della logica binaria. Il codice più ottimale per la CPU è logica binaria. Se i chip erano comuni che ha sostenuto ternario logica come una singola operazione, avreste ragione.

B-alberi può avere più rami per ogni nodo; un ordine-3 B-albero è ternario logica. Ogni passo verso il basso l'albero avrà due confronti invece di uno, e questo sarà probabilmente causa di essere più lento nel tempo di CPU.

B-Alberi, tuttavia, sono piuttosto comuni. Se si assume che ogni nodo dell'albero verrà memorizzato da qualche parte sul disco, si sta andando a trascorrere la maggior parte del vostro tempo a leggere dal disco ... e la CPU non sarà un collo di bottiglia, ma il disco sarà. Quindi si prende un B-albero con 100.000 bambini per nodo, o qualsiasi altra cosa volontà malapena in forma in un unico blocco di memoria. B-alberi con quel tipo di ramificazione fattore sarebbe raramente più di tre nodi di altezza, e si avrebbe solo legge di tre dischi - tre fermate in un collo di bottiglia -. Per cercare un enorme, enorme set di dati

La revisione:

alberi ternari non sono supportati da hardware, quindi corrono meno velocemente.
B-alberi con gli ordini molto, molto, molto più alto di 3 sono comuni per il disco-ottimizzazione di grandi quantità di dati; una volta che sei andato oltre 2, andare più in alto di 3.

L'unico modo una ricerca ternario può essere più veloce di una ricerca binaria è che se una determinazione partizione a 3 vie può essere fatto per meno di circa 1,55 volte il costo di un confronto a 2 vie. Se gli articoli sono memorizzati in un array ordinato, la determinazione a 3 vie saranno pari in media 1,66 volte più costoso come una determinazione a 2 vie. Se le informazioni sono memorizzate in un albero, tuttavia, il costo per recuperare informazioni è elevato rispetto al costo effettivamente confronto, e la cache frazione, il costo di recupero casualmente un paio di dati corrispondenti non è molto peggiore del costo di recupero un'unica datum, un albero ternario o n-senso può migliorare l'efficienza notevolmente.

Cosa ti fa pensare di ricerca ternario dovrebbe essere più veloce?

Numero medio di confronti:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

peggiore numero di confronti:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Quindi sembra che ternario di ricerca è peggio.

Si noti inoltre che questa sequenza generalizza a ricerca lineare se continuiamo a

Binary search
Ternary search
...
...
n-ary search ≡ linear search

Così, in una ricerca n-ario, si avrà "una sola COMPARE" che potrebbe richiedere fino a paragoni n attuali.

"Terinary" (ternario?) Di ricerca è più efficiente nel migliore dei casi, il che comporterebbe la ricerca del primo elemento (o forse l'ultimo, a seconda di quale confronto si fa prima). Per gli elementi più lontano dalla fine si sta controllando prima, mentre due confronti sarebbero restringere la matrice di 2/3 di volta in volta, le stesse due confronti con ricerca binaria avrebbero restringere lo spazio di ricerca per 3/4.

A questo si aggiunge, ricerca binaria è più semplice. Basta confrontare e ottenere la metà o l'altro, piuttosto che confrontare, se meno di ottenere il primo terzo, il resto confrontare, se meno di ottenere il secondo terzo, altro ottenere l'ultimo terzo.

ternario di ricerca può essere utilizzato efficacemente su architetture parallele - FPGA e ASIC. Per esempio, se la memoria FPGA interna necessaria per la ricerca è meno della metà della risorsa FPGA, è possibile effettuare un blocco di memoria duplicato. Ciò permetterebbe di accedere contemporaneamente due diversi indirizzi di memoria e fare tutti i confronti in un singolo ciclo di clock. Questo è uno dei motivi per cui 100MHz FPGA a volte può sovraperformare il CPU 4GHz:)

Ecco alcune evidenze sperimentali a caso che ho non sono controllati a tutti mostrando che è più lento di ricerca binaria.

Quasi tutti i libri di testo e i siti web sugli alberi di ricerca binari non parlano realmente di alberi binari!Ti mostrano alberi di ricerca ternari!I veri alberi binari memorizzano i dati nelle loro foglie e non nei nodi interni (ad eccezione delle chiavi per navigare).Alcuni chiamano questi alberi fogliari e fanno la distinzione tra alberi nodo mostrati nei libri di testo:

J.Nievergelt, C.-K.Wong:Limiti superiori per la lunghezza totale del percorso degli alberi binari, Journal ACM 20 (1973) 1–6.

Quanto segue a riguardo è tratto dal libro di Peter Brass sulle strutture dati.

2.1 Due modelli di alberi di ricerca

Nella struttura appena data, abbiamo superato un punto importante che all'inizio sembra banale, ma in effetti porta a due diversi modelli di alberi di ricerca, uno dei quali può essere combinato con gran parte del seguente materiale, ma uno dei quali è fortemente preferibile.

Se confrontiamo in ciascun nodo la chiave di query con la chiave contenuta nel nodo e seguiamo il ramo sinistro se il tasto di query è più piccolo e il ramo destro se la chiave di query è più grande, allora cosa succede se sono uguali?I due modelli di alberi di ricerca sono i seguenti:

Prendi il ramo a sinistra se la chiave della query è inferiore alla chiave del nodo;Altrimenti prendi il ramo giusto, fino a raggiungere una foglia dell'albero.Le chiavi nel nodo interno dell'albero sono solo per il confronto;tutti gli oggetti sono nelle foglie.
Prendi il ramo a sinistra se la chiave della query è inferiore alla chiave del nodo;Prendi il ramo giusto se la chiave di query è più grande della chiave del nodo;e prendi l'oggetto contenuto nel nodo se sono uguali.

Questo piccolo punto ha una serie di conseguenze:

{Nel modello 1, l'albero sottostante è un albero binario, mentre nel modello 2, ogni nodo dell'albero è in realtà un nodo ternario con uno speciale vicino medio.

{Nel modello 1, ogni nodo interno ha una sottostruttura sinistra e destra (ogni forse un nodo fogliare dell'albero), mentre nel modello 2 dobbiamo consentire nodi incompleti, dove potrebbero mancare la sottostruttura sinistra o destra, e solo il L'oggetto e la chiave di confronto sono garantiti per esistere.

Quindi la struttura di un albero di ricerca del modello 1 è più regolare di quella di un albero del modello 2;questo è, almeno per l'implementazione, un chiaro vantaggio.

{Nel modello 1, attraversare un nodo interno richiede un solo confronto, mentre nel modello 2 abbiamo bisogno di due confronti per controllare le tre possibilità.

In effetti, gli alberi della stessa altezza nei modelli 1 e 2 contengono al massimo approssimativamente lo stesso numero di oggetti, ma uno ha bisogno del doppio dei confronti nel Modello 2 per raggiungere gli oggetti più profondi dell'albero.Naturalmente, nel modello 2, ci sono anche alcuni oggetti che sono raggiunti molto prima;L'oggetto nella radice si trova con solo due confronti, ma quasi tutti gli oggetti sono sopra o vicino al livello più profondo.

Teorema.Un albero di altezza h e modello 1 contiene al massimo 2^h oggetti.Un albero di altezza h e modello 2 contiene al massimo 2^h+1 − 1 oggetti.

Questo è facilmente visto perché l'albero di altezza H ha come sottostrutture sinistro e destro un albero di altezza al massimo H - 1 ciascuno e nel modello 2 un oggetto aggiuntivo tra di loro.

{Nel modello 1, le chiavi nei nodi interni servono solo per i confronti e possono riapparire nelle foglie per l'identificazione degli oggetti.Nel modello 2, ogni chiave appare solo una volta, insieme al suo oggetto.

Nel modello 1 è anche possibile che ci siano chiavi utilizzate per il confronto che non appartengono a nessun oggetto, ad esempio, se l'oggetto è stato eliminato.Separando concettualmente queste funzioni di confronto e identificazione, ciò non è sorprendente e nelle strutture successive potremmo anche dover definire test artificiali non corrispondenti a nessun oggetto, solo per ottenere una buona divisione dello spazio di ricerca.Tutte le chiavi utilizzate per il confronto sono necessariamente distinte perché in un albero del modello 1, ogni nodo interno ha sottotei non vuoti e destro.Quindi ogni chiave si verifica al massimo due volte, una volta come chiave di confronto e una volta come chiave di identificazione nella foglia.

Il modello 2 è diventato la versione preferita del libro di testo perché nella maggior parte dei libri di testo la distinzione tra oggetto e la sua chiave non è fatta:la chiave è l'oggetto.Allora diventa innaturale duplicare la chiave nella struttura ad albero.Ma in tutte le applicazioni reali, la distinzione tra chiave e oggetto è piuttosto importante.Non si desidera quasi mai tenere traccia solo di una serie di numeri;I numeri sono normalmente associati ad alcune ulteriori informazioni, che sono spesso molto più grandi della chiave stessa.

Potreste aver sentito ternario cercare di essere utilizzato in tali enigmi che coinvolgono pesare le cose sulle scale. Quelle scale possono restituire 3 risposte: a sinistra è più leggero, entrambi sono gli stessi, o di sinistra è più pesante. Quindi, in una ricerca ternario, ci vuole solo 1 confronto. Tuttavia, i computer utilizzare la logica booleana, che ha solo 2 risposte. Per fare la ricerca ternario, si sarebbe in realtà hanno a che fare 2 confronti invece di 1. Credo che ci sono alcuni casi in cui questo è ancora più veloce come poster in precedenza accennato, ma si può vedere che ternario di ricerca non è sempre meglio, ed è più confusa e meno naturale per implementare su un computer.

In teoria il minimo di k/ln(k) viene raggiunta a e e dal 3 è più vicino al e di 2 richiede meno paragoni. È possibile verificare che 3/ln(3) = 2.73.. e 2/ln(2) = 2.88.. Il motivo per cui la ricerca binaria potrebbe essere più veloce è che il codice per esso avrà meno rami e sarà più veloce sulle CPU moderna.

Ho appena inviato un blog sulla ricerca ternario e io hanno mostrato alcuni risultati. Ho anche fornito alcune implementazioni di livello iniziale sul mio git repo Sono totalmente d'accordo con ognuno circa la parte teoria la ricerca ternario ma perché non fare un tentativo? Come per l'implementazione che parte è abbastanza facile se si dispone di tre anni di esperienza di codifica. Ho scoperto che se si dispone di enormi set di dati ed è necessario cercare più volte di ricerca ternari ha un vantaggio. Se si pensa che si può fare meglio con una ricerca Go ternario per esso.

Anche se si ottiene lo stesso O-grande complessità (ln n) in entrambi gli alberi di ricerca, la differenza è nelle costanti. Devi fare più confronti di un albero di ricerca ternario ad ogni livello. Quindi la differenza si riduce a k / ln (k) per un albero di ricerca k-ario. Questo ha un valore minimo in corrispondenza di e = 2.7 e k = 2 fornisce il risultato ottimale.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow