Quando dovrei usare la ricerca di interpolazione invece della ricerca binaria?
Ad esempio, ho un set di dati ordinato, in quali situazioni utilizzerei la ricerca binaria per trovare un elemento in questo set di dati o in quale situazione dovrei usare la ricerca di interpolazione?
Quali proprietà del set di dati sarebbe il fattore determinante?
Ovviamente, per fare una ricerca di interpolazione, hai bisogno di un tipo di chiave per cui è noto più di un ordine: devi essere in grado di fare calcoli sui tasti per stimare una probabile distanza, non solo confrontare i tasti per determinare quale è maggiore o minore.
Per quanto riguarda le proprietà del set di dati, per lo più si tratta di una proprietà: una probabilità che le chiavi siano ragionevolmente in modo uniforme (o almeno prevedibilmente) distribuite in tutta la gamma di possibilità. Senza di ciò, una ricerca di interpolazione può effettivamente essere più lenta di una ricerca binaria.
Ad esempio, considera un set di dati con stringhe di lettere minuscole come chiavi. Supponiamo che tu abbia una chiave che inizia con "x". Una ricerca di interpolazione indicherà chiaramente che si dovrebbe iniziare la ricerca molto vicino alla fine del set. Se, tuttavia, la maggior parte delle tue chiavi inizia effettivamente con 'z', e quasi nessuna con qualcosa da 'a' anche se 'y', quella che stai cercando potrebbe essere molto vicina al all'inizio del set. Può / può richiedere un considerevole numero di iterazioni prima che la ricerca si avvicini all'inizio dove risiede la stringa che inizia con 'w'. Ogni iterazione rimuoverà solo il 10% circa del set di dati dalla considerazione, quindi ci vorranno diverse iterazioni prima che si avvicini all'inizio dove risiedono effettivamente le chiavi che iniziano con "w".
Al contrario, una ricerca binaria dovrebbe iniziare al centro, ottenere il segno di un quarto alla seconda iterazione, un ottavo sul terzo e così via. Le sue prestazioni non risentirebbero praticamente dello sfasamento dei tasti. Ogni iterazione rimuoverà la metà del set di dati dalla considerazione, proprio come se le chiavi fossero equamente distribuite.
Mi affretto ad aggiungere, tuttavia, che ci vuole veramente abbastanza una distribuzione distorta per rendere la ricerca di interpolazione notevolmente peggiore di una ricerca binaria. Ad esempio, può funzionare abbastanza bene anche in presenza di una discreta quantità di clustering localizzato.
Vorrei anche ricordare che una ricerca di interpolazione non ha necessariamente bisogno di usare l'interpolazione lineare. Ad esempio, se è noto che le tue chiavi seguono una distribuzione non lineare (ad esempio una curva a campana), diventa abbastanza facile tenerne conto nella funzione di interpolazione per ottenere risultati leggermente diversi dall'avere una distribuzione uniforme.
Probabilmente penso che la domanda è quanto facilmente riesci a trovare una funzione di interpolazione che in realtà è migliore della ricerca binaria.
Da Wikipedia su Interpolation Search:
Using big-O notation, the performance of the interpolation algorithm on a data set of size N is O(N); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log N).
Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe. It can be useful for locating a record in a large sorted file on disk, where each probe involves a disk seek and is much slower than the interpolation arithmetic.
Index structures like B-trees also reduce the number of disk accesses, and are more often used to index on-disk data in part because they can index many types of data and can be updated online. Still, interpolation search may be useful when one is forced to search certain sorted but unindexed on-disk datasets.
La ricerca binaria e la ricerca di interpolazione sono entrambi considerati metodi di ricerca lineare.
Entrambi si aspettano che l'elenco ricercato venga ordinato nella colonna indicata come chiave . Questo è molto importante.
La ricerca binaria funziona per stringhe o numeri purché siano memorizzati in ordine ordinato. L'idea primaria alla base della ricerca binaria è che si basa sull'esame dell'elemento centrale. La ricerca di interpolazione è una variante. Invece di usare l'elemento centrale esatto, indovina dove si trova l'elemento successivo da confrontare con il valore passato. Vedi il riferimento fornito dalla risposta JB King o quella sotto in questa risposta per i dettagli su come l'algoritmo di ricerca di interpolazione calcola il prossimo valore della chiave.
"La ricerca di interpolazione funziona solo su elementi numerici disposti in ordine di matrici ordinate con distribuzione uniforme (ovvero, l'intervallo tra elementi qualsiasi a elementi successivi è approssimativamente costante" (citazione dal riferimento sotto P 737, anche un confronto di prestazioni tra diverse ricerche lineari metodi sono inclusi).
Leggi altre domande sui tag algorithms