To pytanie dotyczy wydajności wyszukiwania liniowego w porównaniu z wydajnością wyszukiwania binarnego dla wstępnie posortowanej tablicy w pamięci ciągłej ...

Mam aplikację napisaną w fortran (77!). Jedną z częstych operacji dla mojej części kodu jest znalezienie indeksu w tablicy takiej, żegx(i) <= xin < gx(i+1). Obecnie zaimplementowałem to jakobinary search - przepraszam za etykiety instrukcji igoto - Skomentowałem, jakie równoważne stany będą używać fortran 90 ...

<code>        i=1
        ih=nx/2
201     continue  !do while (.true.)
           if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then  !found what we want
              ilow=i+1; ihigh=i
              s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow))
              s2=1.0-s1
              return
           endif
           if(i.ge.ih)then
              goto 202 !exit
           endif
           if(xin.le.(gx(ih))then !xin is in second half of array
              i=ih
              ih=nx-(nx-ih)/2
           else !xin is in first half of array
              i=i+1
              ih=i+(ih-i)/2
           endif
        goto 201  !enddo
</code>

Jednak dzisiaj czytałem na Wikipedii o wyszukiwaniu binarnym i natknąłem się na to:

<code>Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a
linear search may have superior performance simply because 
it exhibits better locality of reference.
</code>

Nie do końca rozumiem to stwierdzenie - miałem wrażenie, że pobieranie pamięci podręcznej było gromadzone w dużych (ih) kawałkach naraz, więc jeśli zaczniemy na początku tablicy, pomyślałem, że większość tablicy będzie w pamięci podręcznej już (przynajmniej tyle, ile byłoby w przypadku wyszukiwania liniowego), więc nie sądziłem, że to ma znaczenie.

Tak więc moje pytanie brzmi: czy jest jakiś sposób na określenie, który algorytm będzie działał lepiej (wyszukiwanie liniowe lub binarne?) Czy istnieje granica rozmiaru tablicy? Obecnie używam tablic o rozmiarze około 100 elementów ...