2012-01-15 13 views
8

Non sono sicuro del perché List come una struttura di dati generale dovrebbe avere un algoritmo di ricerca binaria dato che l'elenco è ordinato. Non è il metodo get che accetta l'indice attraversa la lista in modo sequenziale, almeno per il sottotipo ? LinkedList? In tal caso, non vedo alcun vantaggio nell'utilizzare binarySearch confrontando con il confronto sequenziale per LinkedList. Ovviamente, a meno che non limitiamo List a ArrayList, possiamo fare binarySearch con maggiore sicurezza.Perché binarySearch su un elenco in Java?

La mia comprensione è corretta? Grazie.

+1

"dato l'elenco è ordinato" - non è un dato. –

+0

Sto solo dando per scontato che sia vero. Oppure possiamo sempre ordinarlo prima. –

+0

Hai ragione, fare una ricerca binaria su LinkedList è una cattiva idea. – Seramme

risposta

13

Esistono molti modi per implementare lo List. C'è , , CopyOnWriteArrayList, ecc. Nelle librerie Java standard e una serie di altre implementazioni oltre a quelle (VLists, buffer circolari, elenchi di binomiali obliqua, extendible arrays, 2-3 finger trees, ecc.). L'idea alla base della ricerca binaria è che mentre non tutte le implementazioni di List supportano l'accesso casuale, quelle che trarrebbero vantaggio dall'avere una implementazione generica della ricerca binaria disponibile in modo che gli autori di ciascuna struttura di dati non debbano reimplementarlo da zero. Ad esempio, se implemento una nuova struttura lista pazzesca che supporta l'accesso casuale, se implemento l'interfaccia Elenco, è possibile ottenere automaticamente una ricerca binaria disponibile dalla classe Collections.

È interessante notare che il metodo binarySearch è scritto in modo tale che si guarda al tipo di List e vede se si implementa l'interfaccia RandomAccess prima che effettivamente fa la ricerca binaria. Se l'elenco non implementa RandomAccess, anziché utilizzare una ricerca binaria standard, il metodo utilizza una ricerca binaria modificata con iteratori che è garantita per eseguire al massimo O (n) iterazioni e O (log n) confronti. L'idea è di tenere traccia di dove l'ultima sonda è atterrato, quindi di camminare avanti o indietro il numero appropriato di passi per trovare la prossima posizione della sonda, ecc. Il lavoro totale svolto è quindi al massimo n/2 + n/4 + n/8 + n/16 + ... = 2n, quindi nel caso peggiore è solo il doppio di una ricerca lineare nel caso peggiore.

In breve, fornire un'implementazione generica di binarySearch non sempre consente di cercare rapidamente un elenco per qualcosa, ma per le strutture che supportano l'accesso rapido può fare un'enorme differenza e risparmiare molto tempo per l'implementatore . Inoltre, avere il gradevole degrado della ricerca binaria modificata che viene eseguita nel tempo O (n) significa che l'implementazione non sarà mai peggiore di una scansione lineare standard.

Questo ragionamento è simile al ragionamento alla base del progetto degli algoritmi C++, che operano su intervalli di valori generici. L'efficienza di questi algoritmi potrebbe essere molto peggiore di una versione specializzata dell'algoritmo basata su una struttura per-data, ma avere la versione generale disponibile significa che qualsiasi nuovo contenitore che supporta gli iteratori può avere automaticamente molte funzionalità disponibili oltre a ciò che è specificato nell'interfaccia.

Spero che questo aiuti!

+0

+1. sì, quello che hai detto sicuramente aiuta. Il fatto che List abbia una ricerca binaria in realtà farà male ai neofiti che pensano che sarà più veloce senza pensarci due volte, ma in realtà sarà molto più lento se applicato a un 'LinkedList'. Quindi potrebbe confondere i principianti piuttosto che fornire benefici. :) –

+4

Inoltre, c'è un'altra possibilità: cosa succede se il tuo metodo compareTo è così lento che in realtà supera il tempo necessario per attraversare una LinkedList? Questo non è impossibile, e in questi casi Collections.binarySearch potrebbe effettivamente vincere una ricerca sequenziale, anche per LinkedList. –

+0

@ LouisWasserman- Questo è un punto eccellente. Grazie per averlo portato! – templatetypedef

3

Sì, hai ragione, se un elenco non fornisce accesso casuale, come nel caso di LinkedList, non c'è alcun vantaggio. Dal javadoc di Collections.binarySearch():

Questo metodo viene eseguito in log (n) per una lista "accesso casuale" (che fornisce quasi costante accesso in tempo posizionale). Se l'elenco specificato non implementa l'interfaccia {@link RandomAccess} ed è di grandi dimensioni, questo metodo eseguirà una ricerca binaria basata su iteratore che esegue gli attraversamenti di link O (n) e confronti di elementi O (log n).

Quindi, la complessità in questo caso sarà la stessa come nel caso di confronto sequenziale - O (n). Praticamente, credo che il confronto sequenziale potrebbe essere più veloce in molti casi.

+0

commento sul tuo "il vantaggio non è grande". Direi che in molti casi le prestazioni effettive di binarySearch sono peggiori rispetto al confronto sequenziale, anche se la complessità asintotica è la stessa. –

+0

Grazie per aver sottolineato il degrado grazioso! – templatetypedef

+0

sì, hai ragione, testo sbagliato dalla mia parte. – digger