Czy to mnie szukasz?

Algorytmy wyszukiwania i ich implementacje

Pisząc kod lub oprogramowanie, nieuchronnie spotkasz się z sytuacją, w której będziesz musiał znaleźć określoną wartość w danym zbiorze danych. Istnieje kilka różnych sposobów przeprowadzenia tego wyszukiwania. Omówię zarówno wyszukiwania liniowe, jak i binarne oraz inną metodę poprawy wydajności wyszukiwania liniowego. Jeśli chodzi o optymalizację, każda metoda daje inny wynik. Porównując różnice w wydajności pomiędzy akcjami, standardem jest odniesienie się do najgorszej sytuacji, czyli jaka byłaby wydajność, gdyby element został znaleziony podczas ostatniego wykonania funkcji. W przypadku wyszukiwań liniowych i binarnych zobaczymy, jakie będą najgorsze, najlepsze i przeciętne sytuacje.

Wyszukiwanie liniowe

Wyszukiwanie liniowe dosłownie przechodzi przez każdy element zbioru danych kawałek po kawałku, aż znajdzie element, który chcesz znaleźć. Aby znaleźć element x pod indeksem n na uporządkowanej liście, znalezienie elementu zajęłoby mi dokładnie n kroków. Nazywa się to O(n). W przypadku małej listy jest to w porządku i nie stanowi problemu. Na przykład, jeśli mam tablicę wyglądającą tak: [1, 2, 3, 4, 5, 6, 7] i chciałbym znaleźć liczbę 5, znalezienie liczby zajęłoby mi dokładnie 5 kroków szukam. Przyjrzyjmy się, jak to działa w JavaScript z posortowaną tablicą.

let sortedArr = [ 2, 4, 5, 6, 8, 10, 16, 32 ]
function linearSearch(num){
    sortedArr.forEach(function(item, index){
    if(item === num){
      console.log(`I found ${item} at index ${index}!`)
      return
    }
  })
}
linearSearch(32)

Przykład działania: https://repl.it/@r_nilon92/sortedLinearSearchExample

Zatem dla każdego elementu sortedArr sprawdzamy, czy element w każdym indeksie jest równy liczbie (liczbie), którą przekazaliśmy naszej funkcji jako argument.

Ta metoda wyszukiwania doskonale sprawdza się w przypadku małej tablicy, takiej jak ta. Jednakże w przypadku większej listy danych, np. zawierającej 4 000 000 000 pozycji, byłoby to niedogodnością. W najgorszym przypadku (np. liczba, której szukasz, jest ostatnim elementem tablicy lub w ogóle nie istnieje!), znalezienie szukanej liczby zajmie 4 000 000 000 kroków, czyli O(n). . W najlepszym przypadku będzie to dokładnie jeden krok (jeśli szukany element jest pierwszym elementem naszej tablicy) lub O(1). Średni przypadek dla tego typu wyszukiwania to O(n). Jak widać, nie jest to najskuteczniejszy sposób w przypadku przypadków obejmujących większe zbiory danych. Jako programiści zawsze szukamy większej wydajności.

Wyszukiwanie binarne

Wyszukiwanie binarne jest również dość proste i łatwe do zrozumienia, chociaż wymaga nieco więcej logiki niż wyszukiwanie liniowe. Wyszukiwanie binarne, zwane także przeszukiwaniem połówkowym, przeszukiwaniem logarytmicznym lub, moim ulubionym, przeszukiwaniem binarnym, jest znacznie skuteczniejszym sposobem wyszukiwania elementu w określonym zbiorze danych. Jedyną wadą jest to, że dane, które przeglądasz, muszą zostać posortowane.

Aby znaleźć element w uporządkowanej tablicy, najpierw spójrz na punkt środkowy tej tablicy. Jeśli punkt środkowy jest większy niż liczba, którą chcesz znaleźć, ogranicz wyszukiwanie do dolnej połowy i odrzuć górną połowę. Podobnie, jeśli punkt środkowy jest mniejszy niż liczba, której szukasz, wówczas ograniczysz wyszukiwanie do górnej połowy. Liczba występuje tylko w jednej z połówek, więc komputer odrzuca tę połowę, do której szukana liczba nie może należeć. Proces ten powtarza się wielokrotnie, aż do znalezienia liczby. W informatyce wynikową wydajność nazywa się O(log N). Aby zobaczyć różnicę w krokach wykonywanych w trybie liniowym i binarnym, weź wartość logarytmiczną ilości elementów w tablicy, którą chcesz przeszukać. Załóżmy, że mamy tablicę zawierającą 8 000 000 000 elementów. To mnóstwo do przeszukania! Przetnijmy to na pół. Teraz mamy 2 000 000 000 elementów, w których wiemy, że znajduje się żądana liczba. Aby zobaczyć, ile kroków zajmie znalezienie naszego elementu, możemy obliczyć binarną funkcję logarytmiczną log2 8 000 000 000, co daje nam 32. Podczas gdy 32 to dużo kroków potrzebnych do znalezienia liczby jest znacznie krótsza niż 8 000 000 000 w naszym najgorszym przypadku wyszukiwania liniowego. W najgorszym i przeciętnym przypadku element x znajduje się w czasie O(log n), podczas gdy w najlepszym przypadku jest to O(1).

let orderedList = [ 2, 3, 5, 7, 8, 10, 12, 15, 18, 19, 24, 87, 111 ];
function binarySearch(arr, num) {
  
  let lowestNum = 0;
  let highestNum = orderedList.length - 1;
  let midPoint;
  let checkMidpoint;
 
 while(lowestNum <= highestNum) {
    midPoint = Math.floor((lowestNum + highestNum) / 2),
    // midPoint = arr.length/2
     checkMidpoint = arr[midPoint];
if(checkMidpoint === num) {
                console.log('I found the number you were looking for at index: ' + midPoint + '! The value is ' + checkMidpoint + "!");
      return;
     }
     if(num < checkMidpoint) {
         highestNum = midPoint - 1;
            } 
     else {
         lowestNum = midPoint + 1;
     }
        }
 
 return `I couldn't find ${num} in the list.` ;
}
binarySearch(orderedList,10);

Przykład działania: https://repl.it/@r_nilon92/Binary-Search-Example

Wyszukiwanie binarne działa świetnie w tej konkretnej sytuacji. Działa to jednak tylko w sytuacjach, w których dane są posortowane. Co się stanie, jeśli Twoje dane nie zostaną posortowane?

Zmiana zbioru danych w celu zwiększenia efektywności wyszukiwań liniowych

Często podczas wyszukiwania danych chcemy ciągle szukać tych samych danych. W wielu przypadkach 80% naszych wyszukiwań dotyczy 20% obszaru wyszukiwania. Nazywa się to zasadą Pareto, nazwaną na cześć XIX-wiecznego ekonomisty i inżyniera Vilfredo Pareto. Zasadę Pareto pierwotnie stosowano do nierówności i dystrybucji dochodów, ale znalazła ona również miejsce w informatyce w odniesieniu do optymalizacji. Na przykład Microsoft odkrył, że 20% błędów w ich oprogramowaniu spowodowało 80% awarii.

Jeśli przyjmiemy zasadę, że 80% naszych wyszukiwań odbywa się na tak małym obszarze, możemy przenieść te najczęstsze wyszukiwania na początek naszego zbioru danych, dzięki czemu nasze wyszukiwanie w wielu przypadkach będzie znacznie krótsze niż byłoby w innym przypadku. Spójrzmy na przykład.

let unsortedArr = [2, 5, 3, 7, 8, 10, 15, 18, 24, 111, 12, 19, 87];
function linearSearch(num) {   
  
   unsortedArr.forEach(function(itemValue, index, array){
        if(itemValue === num) {
            
            if(index > 0) {
                organizeArr(index, array, index -1);
            }
        }
    });
    return unsortedArr;
}
function organizeArr(index, array, indexSwitch) {
    var tempCurrentValue = array[index];
    //tempCurrentValue stays the same
    array[index] = array[indexSwitch];
    array[indexSwitch] = tempCurrentValue;
}
console.log("Before Organization: " + unsortedArr);
var first = linearSearch(7);
var second = linearSearch(7);
var third = linearSearch(7);
var fourth = linearSearch(7);
console.log("After Organization: " + fourth);
/* 
Before Organization: 2,5,3,7,8,10,15,18,24,111,12,19,87
After Organization: 7,2,5,3,8,10,15,18,24,111,12,19,87
*/

Przykład działania: https://repl.it/@r_nilon92/LinearSearchWIthOrganization

Zmieniając z czasem nasze dane, aby odzwierciedlały najczęstsze wyszukiwania, możemy sprawić, że nasze średnie wyniki będą lepsze niż zwykle.

Streszczenie

Więc co jest lepsze? Liniowy czy binarny? Ogólnie rzecz biorąc, chcielibyśmy używać algorytmów wyszukiwania liniowego, gdy dane, z którymi pracujemy, są nieposortowane. Możemy usprawnić ten proces, tworząc funkcję, która przesuwa najczęściej wyszukiwane elementy na przód tablicy. W przypadku tablic posortowanych, zwłaszcza gdy tablica ma duży rozmiar, algorytmy wyszukiwania binarnego są bardziej pożądane i są znacznie krótsze w wykonaniu.

Źródła