Mam tablicę liczb zmiennoprzecinkowych, posortowanych od najmniejszej do największej, i muszę być w stanie wybrać najbliższy zmiennoprzecinkowy większy lub mniejszy od przekazanej wartości wejściowej. Ta wartość wejściowa niekoniecznie występuje jako wartość w tablicy.
Naiwnym podejściem byłoby proste przeszukiwanie liniowe tablicy. Może to wyglądać tak:
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];
}
}
}Ale oczywiście w miarę powiększania się tablicy, będzie to coraz wolniejsze.
Czy ktoś ma pomysł na algorytm, który pozwoliłby mi znaleźć te dane bardziej optymalnie? Już przeszedłem na wyszukiwanie binarne, które nieco poprawiło sytuację, ale wciąż jest o wiele wolniejsze niż bym chciał, a ponieważ tak naprawdę nie szukam konkretnej wartości, która istnieje w tablicy, nigdy nie może się zakończyć wcześnie.
Więcej informacji: Wartości zmiennoprzecinkowe w tablicy niekoniecznie są rozmieszczone równomiernie (tzn. Tablica może składać się z wartości „1.f, 2.f, 3.f, 4.f, 100.f, 1200.f , 1203.f, 1400.f ”.
Robię tę operację setki tysięcy razy, ale mogę wykonać dowolne przetwarzanie wstępne na tablicy pływaków, jeśli poprawi to czas wyszukiwania. Absolutnie mogę zmienić, aby użyć czegoś innego niż wektor do ich przechowywania, jeśli to pomoże.
źródło
Odpowiedzi:
Kod w pytaniu (wyszukiwanie liniowe), jak słusznie zauważyłeś, zwolni się w przypadku dużych tablic pływających. Technicznie jest to O (n), gdzie n jest liczbą wartości zmiennoprzecinkowych w tablicy.
Ogólnie rzecz biorąc, najlepszym sposobem na znalezienie wartości w uporządkowanej tablicy jest pewnego rodzaju rekurencyjne wyszukiwanie drzewa (np. Wyszukiwanie binarne), w którym to przypadku można osiągnąć czas wyszukiwania O (log n) w liczbie elementów w twojej tablicy. O (log n) jest znacznie lepsze niż O (n) dla dużych wartości n.
Dlatego moim sugerowanym podejściem byłoby proste wyszukiwanie binarne tablicy , tj .:
Jest to algorytm O (log n), który powinien być wystarczająco szybki dla prawie wszystkich sytuacji. Intuicyjnie działa poprzez zmniejszenie o połowę zakresu, który ma być przeszukiwany na każdym kroku, aż do znalezienia właściwej wartości.
Naprawdę trudno jest przeforsować proste wyszukiwanie binarne, więc jeśli już poprawnie to zaimplementowałeś, możesz być już prawie optymalny. Jeśli jednak znasz rozkłady danych i / lub masz ograniczony zakres wartości odnośników (x), możesz spróbować jeszcze innych, bardziej zaawansowanych sztuczek:
Jednak, chyba że znajdujesz się w wyjątkowej sytuacji, prawdopodobnie zaleciłbym trzymanie się prostego wyszukiwania binarnego. Powody:
źródło
Wydaje się to dość proste:
Wykonaj binarne wyszukiwanie pływaka, który chcesz powiązać - czas O (log n).
Następnie element po jego lewej stronie jest dolną granicą, a element po prawej to górna granica.
źródło
Oczywistą odpowiedzią jest przechowywanie pływaków na drzewie . Obsługa „poprzednich” i „następnych” operacji jest banalna w drzewie. Więc po prostu zrób „następną” wartość, a następnie zrób „poprzednią” wartość, którą znajdziesz w pierwszym kroku.
źródło
Ten artykuł („wyszukiwanie sublogarytmiczne bez zwielokrotnienia”) może być interesujący; zawiera nawet kod źródłowy. Dla celów porównania można traktować liczbę zmiennoprzecinkową jako liczbę całkowitą o tym samym wzorze bitowym; był to jeden z celów projektowych standardu zmiennoprzecinkowego IEEE.
źródło