Jestem ciekawy, czy ktoś mógłby mi wyjaśnić implementację wyszukiwania binarnego bez branchingu. Widziałem to w niedawnym numerze question, ale nie mogę sobie wyobrazić, w jaki sposób zostałby zaimplementowany. Zakładam, że przydatne byłoby unikanie oddziałów, jeśli liczba przedmiotów jest dość duża.Bezlistne wyszukiwanie binarne
Zakładam, że mówisz o zdaniu "Utwórz tablicę z wszystkimi idealnymi kwadratami w domenie, którą chcesz obsłużyć, i wykonaj szybkie bezgałęzowe wyszukiwanie binarne". znaleziono w this answer.
"Bezlistne" wyszukiwanie binarne jest po prostu rozwiniętą pętlą wyszukiwania binarnego. Działa to tylko wtedy, gdy znasz z góry liczbę przedmiotów w szukanej macierzy (tak jak w przypadku, gdy jest to static const). Możesz napisać program do napisania rozwiniętego kodu, jeśli jest zbyt długi, aby zrobić go ręcznie.
Następnie należy test porównawczy rozwiązanie, aby zobaczyć, czy rzeczywiście jest szybszy niż pętli. Jeśli twój bezkierunkowy kod jest zbyt duży, nie zmieści się on w pamięci podręcznej instrukcji szybkiego procesora i potrwa dłużej niż odpowiednia pętla.
Jeśli ktoś ma funkcję, która zwraca +1, -1 lub 0 w zależności od pozycji właściwej pozycji w porównaniu z bieżącą, można zainicjować pozycję do rozmiaru listy/2 i zmienić na pozycję/2, i następnie po każdym porównaniu wykonaj pozycję + = kierunek * stepsize; stepsize = stepsize/2. Iteruj, aż liczba kroków wynosi zero.
"Powtórzyć, aż liczba kroków wynosi zero." Jak to jest bez gałęzi, że robisz gałąź nie zero? – rlibby
Jeśli znasz wartość początkową, możesz rozwinąć pętlę wymaganą liczbę razy. Alternatywnie niektóre platformy sprzętowe (zwłaszcza DSP) obsługują pętlę "DO" w stylu Fortran; gdy instrukcja zostanie pobrana z adresu odpowiadającego adresowi końca pętli, licznik pętli zmniejszy się, a licznik programu zostanie załadowany adresem rozpoczęcia pętli. Zero cykli dla pętli. – supercat
obliczone oddziały są nadal gałęziami. Rozwijanie pętli jest bezlistne (a przynajmniej może być), ale nie używa żadnych warunków, takich jak "dopóki nie wynosi zero". – rlibby
Ah okej, rozumiem, dzięki. Zakładałem, że było trochę dziwnego drwala, aby uniknąć instrukcji if wewnątrz pętli. – GWW
+1, ponieważ jest to rzeczywiście przydatny sposób usuwania gałęzi pętli, chociaż z późniejszego komentarza na to pytanie wydaje się, że R. zamierzał zamiast tego "bity twiddle, aby uniknąć rozgałęzień warunkowych". Robiąc to, możesz w zasadzie unikać * wszystkich * gałęzi. –
Takie "bezlistne" rozwijane wyszukiwanie znajduje się w "Programming Pearls" firmy Bentley, IIRC, gdzie dokładnie tłumaczy technikę –