Algoritmo veloce per cercare una matrice ordinata di float per trovare la coppia di float che combina un valore di input

9

Ho una serie di float, ordinati dal più piccolo al più grande, e devo essere in grado di scegliere il float più vicino maggiore o minore di un valore di input passato. Questo valore di input non è necessariamente presente come valore nella matrice.

Un approccio ingenuo sarebbe fare una semplice ricerca lineare attraverso l'array. Potrebbe apparire come questo:

void FindClosestFloatsInArray( float input, std::vector<float> array, 
                               float *min_out, float *max_out )
{
    assert( input >= array[0] && input < array[ array.size()-1 ] );
    for( int i = 1; i < array.size(); i++ )
    {
        if ( array[i] >= input )
        {
            *min = array[i-1];
            *max = array[i];
        }
    }
}

Ma ovviamente quando l'array diventa più grande, questo diventerà più lento e lento.

Qualcuno ha un'idea di un algoritmo che mi permetterebbe di trovare questi dati in modo più ottimale? Sono già passato a una ricerca binaria, che ha migliorato un po 'le cose, ma è comunque molto più lenta di quanto mi piacerebbe, e dal momento che non sto cercando un valore specifico che esiste nell'array, non può mai terminare presto.

Ulteriori informazioni: i valori in virgola mobile nell'array non sono necessariamente distribuiti in modo uniforme (ovvero, la matrice potrebbe essere costituita dai valori "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f, 1203.f, 1400.f ".

Sto facendo questa operazione centinaia di migliaia di volte, ma posso fare qualsiasi quantità di pre-elaborazione sulla matrice di float, se migliorerà il tempo di ricerca. Posso assolutamente cambiare usare qualcosa di diverso da un vettore per archiviarli, se ciò sarà di aiuto.

    
posta Trevor Powell 20.09.2011 - 08:08
fonte

4 risposte

10

Il codice nella domanda (una ricerca lineare), come giustamente fai notare, diventerà lento per gli array float di grandi dimensioni. Tecnicamente è O (n) dove n è il numero di valori float nell'array.

In generale, la cosa migliore che puoi fare per trovare un valore in un array ordinato è una ricerca ad albero ricorsiva di qualche tipo (ad esempio, la ricerca binaria), nel qual caso puoi ottenere un tempo di ricerca O (log n) nel numero di elementi nel tuo array. O (log n) è molto migliore di O (n) per grandi valori di n.

Il mio approccio suggerito sarebbe quindi una semplice ricerca binaria dell'array , cioè:

  1. Imposta gli indici interi min / max per coprire l'intero array mobile
  2. verifica il valore nel mezzo dell'intervallo a metà dell'indice = (min + max / 2) rispetto al valore di ricerca x
  3. se x è inferiore a questo valore, imposta max a metà, altrimenti imposta min a metà
  4. ripeti (2-4) finché non hai trovato il valore corretto

Questo è un algoritmo O (log n) che dovrebbe essere abbastanza veloce per quasi tutte le situazioni. Intuitivamente, funziona dimezzando l'intervallo da cercare in ogni fase finché non trovi il valore corretto.

È davvero difficile creare una semplice ricerca binaria, quindi se lo hai già implementato correttamente potresti già essere abbastanza vicino a quello ottimale. Tuttavia, se conosci le distribuzioni dei dati e / o hai una gamma limitata di valori di ricerca (x), ci sono ancora altri trucchi più avanzati che puoi provare:

  • Bucketing - crea bucket (ad esempio per ciascun intervallo tra due numeri interi), ognuno dei quali contiene un elenco ordinato più piccolo dei valori float tra i due numeri interi vincolanti più due valori immediatamente inferiori e immediatamente sopra ciascun intervallo. È quindi possibile avviare la ricerca in (trunc (x) +0.5). Questo dovrebbe darti una buona accelerazione se scegli secchi di dimensioni appropriate (aumenta effettivamente il fattore di ramificazione dell'albero .....). Se gli interi non funzionano per te, puoi provare i bucket con qualche altra precisione in virgola fissa (ad esempio multipli di 1/16).
  • Mappatura bit : se l'intervallo di valori di ricerca possibili è sufficientemente ridotto, puoi provare a creare una tabella di ricerca grande indicizzata dal valore bit per bit di x. Questo sarà O (1) ma potresti aver bisogno di molta memoria che sarà molto ostile nella tua cache ... quindi usa con cautela. Questo è particolarmente sgradevole perché stai cercando valori float, quindi potresti aver bisogno di diversi GB per tenere conto di tutti i bit meno significativi ......
  • Arrotondamento e hashing - le tabelle hash probabilmente non sono la migliore struttura dati per questo problema, ma se riesci a perdere un po 'di accuratezza potrebbero lavorare - arrotondare semplicemente i bit più bassi dei valori di ricerca e utilizzare una hashmap per cercare direttamente il valore corretto. Dovrai sperimentare il giusto trade-off tra la dimensione e la precisione di hashmap e anche assicurarti che tutti i possibili valori hash vengano popolati, quindi questo può essere un po 'complicato ......
  • Equilibratura degli alberi : il tuo albero ideale dovrebbe avere il 50% di probabilità di andare a destra oa sinistra. Quindi, se crei un albero basato sulla distribuzione dei valori di ricerca (x), puoi ottimizzare l'albero per produrre risposte con la quantità minima di test. Questa è probabilmente una buona soluzione se molti valori nel tuo array float sono molto ravvicinati, dal momento che ti permetterà di evitare la ricerca di questi rami troppo spesso.
  • Alberi crit-bit - questi sono ancora alberi (quindi ancora O (log n) ... ) ma alcuni casi: dovresti comunque convertire i float in un formato a virgola fissa per far funzionare i confronti

Tuttavia, a meno che tu non sia in una situazione molto speciale, probabilmente ti consiglio di attenermi alla semplice ricerca binaria. Motivi:

  • è molto più semplice da implementare
  • è molto veloce per i casi più comuni
  • il sovraccarico extra degli approcci più complessi (ad esempio un maggiore utilizzo di memoria / pressione cache) supera spesso i minori guadagni teorici
  • sarà più robusto per i futuri cambiamenti nelle distribuzioni di dati ....
risposta data 20.09.2011 - 09:19
fonte
1

Sembra abbastanza semplice:

Fai una ricerca binaria per il float che vuoi rilegare - O (log n) time.

Quindi l'elemento a sinistra di esso è il limite inferiore e l'elemento a destra di esso è il limite superiore.

    
risposta data 20.09.2011 - 09:33
fonte
0

La risposta ovvia è di memorizzare i float in un albero . Supportare le operazioni "precedente" e "successiva" sono banali in un albero. Quindi fai un 'prossimo' sul tuo valore e poi fai un 'precedente' sul valore che trovi nel primo passaggio.

    
risposta data 20.09.2011 - 08:25
fonte
-1

Questo documento ("sublogaritmico ricerca senza moltiplicazioni ") potrebbe essere di interesse; contiene anche qualche codice sorgente. Ai fini del confronto, è possibile trattare un numero float come un numero intero con lo stesso pattern di bit; questo era uno degli obiettivi di progettazione dello standard IEEE in virgola mobile.

    
risposta data 20.09.2011 - 11:42
fonte

Leggi altre domande sui tag