Wyszukiwanie interpolacyjne


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

W posortowanym rosnąco zbiorze Z wyszukać element o wartości (kluczu) k.

 

 

Opisane w poprzednim rozdziale wyszukiwanie binarne (ang. binary search) zawsze szuka elementu o kluczu k w środku zbioru. Tymczasem, jeśli założymy liniowy rozkład wartości elementów w przeszukiwanym zbiorze, to możemy precyzyjniej wytypować spodziewaną pozycję poszukiwanego klucza na podstawie jego wartości. Wzór jest następujący:

 

  Z  – przeszukiwany zbiór
isr = ip   (k - Z[ip]) x (ik - ip)  
Z[ik] - Z[ip]
 
  k  – poszukiwana wartość
  ip  – indeks pierwszego elementu partycji
  ik  – indeks końcowego elementu partycji
  isr  – wyznaczona, przypuszczalna pozycja  

 

Powyższy wzór wyprowadzamy z prostej proporcji. Jeśli zbiór posiada liniowy rozkład elementów, to odległość wartości poszukiwanej k od Z[ip] jest w przybliżeniu proporcjonalna do liczby elementów pomiędzy isr a ip:

 

ip ... isr   ...   ...   ...   ik
Z[ip] ... k   ...   ...   ...   Z[ik]

 

Skoro tak, to zachodzi przybliżona proporcja:

 

isr - ip  ≈  k - Z[ip] , mnożymy obustronnie przez ik - ip
ik - ip Z[ik] - Z[ip]
isr - ip ≈  (k - Z[ip]) x (ik - ip) , dodajemy obustronnie ip
Z[ik] - Z[ip]
isr = ip   (k - Z[ip]) x (ik - ip)   , zaokrąglamy do wartości całkowitej i otrzymujemy wzór końcowy.
Z[ik] - Z[ip]

 

Aby zrozumieć zaletę tego sposobu wyznaczania pozycji, przyjrzyjmy się poniższemu przykładowi, gdzie wyliczyliśmy pozycję wg wzoru z poprzedniego rozdziału oraz wg wzoru podanego powyżej. Poszukiwany element zaznaczono kolorem czerwonym:

 

nr pozycji = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
elementy Z = 10 11 13 13 15 16 18 19 20 22 22 23 25 27 27 28 29 30 32
binarnie isr =                   X                  
interpolacyjnie isr =         X                            

 

Binarne wyznaczenie pozycji:

 

isr =    ip + ik    =    0 + 18    =    18    = 9
 2 2 2

 

Interpolacyjne wyznaczenie pozycji:

 

isr = ip    (k - Z[ip]) x (ik - ip)    = 0 +   (15 - 10) x (18 - 0)    = 0 +   5 x 18    = 0 +   90    = 0 + 4 = 4
Z[ik] - Z[ip] 32 - 10 22 22

 

Metoda interpolacyjna wyznacza pozycję zwykle dużo bliżej poszukiwanego elementu niż metoda binarna (w przykładzie trafiamy za pierwszym razem). Zauważ, iż w metodzie binarnej nie korzystamy zupełnie z wartości elementów na krańcach dzielonej partycji, czyli działamy niejako na ślepo. Natomiast metoda interpolacyjna wyznacza położenie w zależności od wartości elementów zbioru oraz wartości poszukiwanego elementu. Działa zatem celowo dostosowując się do zastanych w zbiorze warunków. Stąd jej dużo większa efektywność.

Po wyznaczeniu położenia isr pozostała część algorytmu jest bardzo podobna do wyszukiwania binarnego. Sprawdzamy, czy element na pozycji isr posiada poszukiwany klucz k. Jeśli tak, to wyszukiwanie kończy się zwróceniem pozycji isr. W przeciwnym razie jeśli k jest mniejsze od klucza elementu Z[isr], to poszukiwania kontynuujemy w lewej części zbioru od elementu Z[ip] do Z[isr - 1]. W przeciwnym razie szukamy w prawej części od Z[isr + 1] do Z[ik]. Wyszukiwanie kończy się porażką, jeśli poszukiwany klucz wyjdzie poza przedział <Z[ip],Z[ik]>. W takim przypadku kończymy zwracając jako pozycję liczbę -1.

Wyszukiwanie interpolacyjne posiada klasę czasowej złożoności obliczeniowej równą O(log log n), zatem wyszukuje znacząco szybciej w zbiorach o liniowym rozkładzie elementów niż wyszukiwanie binarne o klasie O(log n).

 

Algorytm wyszukiwania interpolacyjnego

Wejście
ip  –   indeks pierwszego elementu w tablicy Z, ip C
ik  – indeks ostatniego elementu w tablicy Z, ik C
Z  – tablica do wyszukania elementu. Indeksy od ip do ik
k  – wartość poszukiwanego elementu – tzw. klucz
Wyjście:

p = indeks elementu o kluczu k lub
p
= -1, jeśli nie odnalezienia elementu o takim kluczu.

Zmienne pomocnicze
isr  –   indeks elementu środkowego. isr C
Lista kroków:
K01: p ← -1 ; zakładamy, iż k nie występuje w zbiorze
K02: Dopóki Z[ip] ≤ kZ[ik] wykonuj K02...K10 ; w pętli poszukujemy elementu o wartości k
K03:
isrip   (k - Z[ip]) x (ik - ip)  
Z[ik] - Z[ip]
; wyznaczamy pozycję elementu interpolowanego
K04:     Jeśli k ≠ Z[isr], to idź do K07  
K05:     pisr ; element znaleziony, kończymy
K06:     Idź do K11  
K07:     Jeśli k < Z[isr], to idź do K10 ; wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania
K08:     ipisr + 1 ; k > Z[isr] → druga połówka
K09:     Następny obieg pętli K02  
K10:     ikisr - 1 ; k < Z[isr] → pierwsza połówka
K11: Zakończ z wynikiem p  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program wypełnia tablicę 100 elementową Z liczbami naturalnymi w taki sposób, aby powstał z nich ciąg rosnący. Następnie generuje liczbę pseudolosową k z zakresu od Z[0] do Z[99] i wyszukuje interpolacyjnie jej położenia w tablicy. Na koniec wyświetlana jest liczba k, jej położenie w Z oraz zawartość tablicy Z z zaznaczonym elementem o wartości k. Jeśli k nie występuje w Z, to zamiast położenia program wyświetla słowo BRAK. Dodatkowo program zlicza wykonane obiegi pętli i wypisuje ich liczbę.

 

Lazarus
// Wyszukiwanie interpolacyjne
// Data:   8.05.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 100;

var
  Z : array[0..N - 1] of integer;
  i,ip,ik,isr,k,L,p : integer;

begin
  randomize;

  // wypełniamy tablicę Z[]

  Z[0] := random(5);
  for i := 1 to N - 1 do Z[i] := Z[i - 1] + random(5);

  // generujemy klucz k

  k := Z[0] + random(Z[N - 1] - Z[0] + 1);

  // poszukujemy interpolacyjnie elementu k

  L  := 0; p  := -1; ip := 0; ik := N - 1;
  while (Z[ip] <= k) and (k <= Z[ik]) do
  begin
    inc(L);
    isr := ip + (k-Z[ip])*(ik-ip) div (Z[ik]-Z[ip]);
    if Z[isr] = k then
    begin
      p := isr; break;
    end
    else if k < Z[isr] then
      ik := isr - 1
    else
      ip := isr + 1;
  end;

  // wyświetlamy wyniki

  write(k,' : ');
  if p >= 0 then write(p) else write('BRAK');
  writeln(' : obiegi = ',L);
  writeln;
  for i := 0 to N - 1 do
  begin
    write(Z[i]:3);
    if p = i then write('<') else write(' ');
  end;
  writeln;
  writeln;
end.
Code::Blocks
// Wyszukiwanie interpolacyjne
// Data:   8.05.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 100;

int main()
{
  int Z[N],i,ip,ik,isr,k,L,p;

  srand((unsigned)time(NULL));

  // wypełniamy tablicę Z[]

  Z[0] = rand() % 5;
  for(i = 1; i < N; i++) Z[i] = Z[i - 1] + (rand() % 5);

  // generujemy klucz k

  k = Z[0] + (rand() % (Z[N - 1] - Z[0] + 1));

  // poszukujemy interpolacyjnie elementu k

  p = -1; L = ip = 0; ik = N - 1;
  while((Z[ip] <= k) && (k <= Z[ik]))
  {
    L++;
    isr = ip + (k-Z[ip])*(ik-ip) / (Z[ik]-Z[ip]);
    if(Z[isr] == k)
    {
      p = isr; break;
    }
    else if(k < Z[isr])
      ik = isr - 1;
    else
      ip = isr + 1;
  }

  // wyświetlamy wyniki

  cout << k << " : ";
  if(p >= 0) cout << p; else cout << "BRAK";
  cout << " : obiegi = " << L << endl << endl;
  for(i = 0; i < N; i++)
  {
    cout << setw(3) << Z[i];
    if(p == i) cout << "<"; else cout << " ";
  }
  cout << endl << endl;
  return 0;
}
Free Basic
' Wyszukiwanie interpolacyjne
' Data:   8.05.2008
' (C)2012 mgr Jerzy Wałaszek
'---------------------------

Const N = 100

Dim As Integer Z(N-1),i,ip,ik,isr,k,L,p

Randomize

' wypełniamy tablicę Z[]

Z(0) = Cint(Rnd * 4)
For i = 1 To N - 1: Z(i) = Z(i-1) + Cint(Rnd * 4): Next

' generujemy klucz k

k = Z(0) + Cint(Rnd * (Z(N - 1) - Z(0)))

' poszukujemy interpolacyjnie elementu k

L  = 0: p  = -1: ip = 0: ik = N - 1
While (Z(ip) <= k) And (k <= Z(ik))
  L += 1
  isr = ip + (k - Z(ip)) * (ik - ip) \ (Z(ik) - Z(ip))
  If Z(isr) = k Then
    p = isr: Exit While
  Elseif k < Z(isr) Then
    ik = isr - 1
  Else
    ip = isr + 1
  End If
Wend

' wyświetlamy wyniki

Print k;" : ";
If p >= 0 Then Print p;: Else Print "BRAK";
Print " : obiegi =";L
Print
For i = 0 To N - 1
  Print Using "###";Z(i);
  If p = i Then Print "<";: Else Print " ";
Next
Print
Print
End
Wynik
151 : BRAK : obiegi = 1

  4   5   9  12  15  15  15  19  21  24  24  24  25  28  32  33  33  35  39  40
 41  43  44  45  47  47  51  54  56  57  58  59  62  64  66  68  69  71  71  72
 72  74  77  81  84  87  91  91  95  95  95  99  99 101 103 104 108 111 114 116
117 120 120 122 125 129 130 133 136 139 140 141 145 149 153 155 157 161 164 166
168 170 170 170 171 174 176 177 181 183 183 186 188 191 191 195 195 199 199 201

83 : 44 : obiegi = 2

  3   4   6   8  10  10  13  14  14  14  18  18  20  24  24  24  24  25  25  25
 26  28  31  33  34  36  36  38  42  42  43  47  51  52  54  55  59  63  63  67
 71  75  76  80  83< 86  86  87  90  92  96  98 101 103 103 107 108 111 113 116
119 122 125 128 128 128 128 131 135 139 139 142 142 143 145 149 150 150 152 153
156 160 161 163 164 164 165 168 169 169 169 170 171 172 174 176 176 179 180 184

 

Wyszukiwanie interpolacyjne
(C)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.