Drzewa BST, wyszukiwanie liniowe i binarne. Porównanie szybkości.

sebcio_lcp

Oto wersja poprawiona tego artykułu + zastosowanie drzew.
Przepraszam za poprzedni poważny błąd.

Przedstawiam porownanie szybkosci działania przeszukiwania liniowego, binarnego (wersji rekurencyjnej i iteracyjnej) oraz wyszukiwania w drzewie BST.

Podczas badań uwzględnione zostały dwa elementy: czas wykonania algorytmu i ilość porównań potrzebnych do wyszukania elementu. Ze względu na to, że czas działania algorytmu jest niezauważalny, został on wykonany w pętli 100000 razy. Otrzymany wynika został podzielny przez ilość wywołań danego algorytmu.

Przypadek 1

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu od ?10 do 20 (niewielka rozpiętość zakresu danych wejściowych).
Szukany element to 12000 znajdujący się na ostatniej pozycji.

Wyszukiwanie w drzewie BST:
Czas: 0.0056 ms
Ilość porównań: 2

Wyszukiwanie liniowe:
Czas: 0.0871 ms
Ilość porównań: 20000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0178 ms
Ilosc porównań: 28

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 42

Przypadek 2

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu od ?10 do 20. Szukany element to 12000 znajdujący się w środku tablicy.

Wyszukiwanie w drzewie BST:
Czas: 0.0021 ms
Ilość porównań: 3

Wyszukiwanie liniowe:
Czas: 0.0435 ms
Ilość porównań: 10000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0179 ms
Ilosc porównań: 2

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 3

Przypadek 3

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu
od ?32000 do 32000 (duża rozpiętość zakresu danych wejściowych).
Szukany element to 32001 znajdujący się na ostatniej pozycji.

Wyszukiwanie w drzewie BST:
Czas: 0.0002 ms
Ilość porównań: 14

Wyszukiwanie liniowe:
Czas: 0.0871 ms
Ilość porównań: 20000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0177 ms
Ilosc porównań: 28

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 42

Przypadek 4

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu
od ?32000 do 32000 (duża rozpiętość zakresu danych wejściowych).
Szukany element to 32001 znajdujący się w środku tablicy.

Wyszukiwanie w drzewie BST:
Czas: 0.0002 ms
Ilość porównań: 13

Wyszukiwanie liniowe:
Czas: 0.0435 ms
Ilość porównań: 10000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0174 ms
Ilosc porównań: 2

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 3

Przypadek 5

Tablica złożona z 10000 elementów, wypełniona jednakowymi elementami o wartości 1.
Szukany element to 2 znajdujący się na ostatniej pozycji.

Wyszukiwanie w drzewie BST:
Czas: 0.0001 ms
Ilość porównań: 2

Wyszukiwanie liniowe:
Czas: 0.0870 ms
Ilość porównań: 20000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0123 ms
Ilosc porównań: 28

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 42

Przypadek 6

Tablica złożona z 10000 elementów, wypełniona jednakowymi elementami o wartości 1.
Szukany element to 2 znajdujący się w środku.

Wyszukiwanie w drzewie BST:
Czas: 0.0000 ms
Ilość porównań: 2

Wyszukiwanie liniowe:
Czas: 0.0433 ms
Ilość porównań: 10000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0119 ms
Ilosc porównań: 2

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 3

Implementacja operacji wykonywanych na drzewach BST (binary search tree - binarne drzewa poszukiwac).

#include <stdio.h>
#include "table.h"
#include <time.h>

#define N 10000 //liczba elementow tablicy wczytywanej z pliku i rozmieszczanej w drzewie BST

typedef struct BST{
  int data;
  struct BST *left;
  struct BST *right;
} bst;

bst *create(int data); //przydzielenie pamieci dla nowego wezla 
bst *insert(bst *root, bst *new); //wstawianie wezla do drzewa
void ShowTree(bst *root); //wyswietlenie calego drzewa w porzadku InOrder
bst *search(bst *root, int data, unsigned long *l_por); //wyzukiwanie wezla o podanym kluczu
bst *min(bst *root); //wyszukiwanie elementu najmniejszego 
bst *max(bst *root); //wyszukiwanie elementu najwiekszego
bst *delete(bst *root, int data); //usuniecie wezla z drzewa
bst *succ(bst *root, int data); //nastepnik 
bst *pred(bst *root, int data); //poprzednik
bst *parent(bst *root, bst *syn); //wyznacza adres rodzica syna 'syn'

int main(void)
{
  bst *root, *new, *s;
  int tab[N];
  long i;
  clock_t start, stop;
  float alg_time;
  unsigned long l_porownan = 0;

  root = NULL;
/*  OpenTable("tab.dat",tab,N);
  tab[(N/2)-1] = 32001;
  for (i = 0; i < N; ++i) 
    root = insert(root,create(tab[i]));
  ShowTree(root);
  start = clock();
//  for (i = 0; i < 100000; ++i)
    s = search(root,32001,&l_porownan);
  stop = clock();
  alg_time = (stop - start) / CLK_TCK;
  alg_time /= 10000;
  printf("\nszukany el.: %d\n", s->data);
  printf("\nCzas wykonania alg...: %f\n", alg_time);
  printf("\nLiczba wykonanych porownan: %lu\n", l_porownan);*/
  ShowTree(root);
  return 0;
}

/********************************************************************************
 * Funkcja przydziela pamiec na nowy element i wypelnia go podanymi danymi  *
 * Zwraca natomiast adres nowego elementu                   *
 * data - jakies dane, mozna to traktowac jak klucz             *
 *******************************************************************************/
bst *create(int data) 
{
  bst *tmp; //pomocniczy wskaznik, przechowuje adres pamieci przydzielnej dla nowego elementu

  tmp = (bst *) malloc(sizeof(*tmp));
  if (tmp == NULL) {
    printf("\nBrak wolnej pamieci ...\n");
    return NULL;    
  }
  tmp->data = data;
  tmp->right = NULL;
  tmp->left = NULL;
  return tmp;
}

/********************************************************
 * Funkcja wstawia element do drzewa            *
 * Zwraca adres na korzen nowego drzewa         *
 * root - wskaznik na korzen drzewa         *
 * new - wskaznik na dodawanay element          *
 *******************************************************/
bst *insert(bst *root, bst *new)
{
  bst *tmp;
  bst *ret = root; //przechowuj adres korzenia aby nie zmienic wskaznika na poczatek drzewa

  if (root == NULL) 
    return new;
  else 
    while (root != NULL) {
      tmp = root;
      if (root->data >= new->data)
        root = root->left;
      else
        root = root->right;
    }
  if (tmp->data >= new->data)
    tmp->left = new;
  else
    tmp->right = new;
  return ret; 
}

/********************************************************
 * Funckcja wyswietla cale drzewo w porzadku InOrder    *
 * root - wskaznik na korzen drzewa         *
 *******************************************************/
void ShowTree(bst *root)
{
  if (root == NULL) 
    return;
  ShowTree(root->left);
  printf("\n%d\n", root->data);
  ShowTree(root->right);
  return;   
}

/************************************************************************
 * Funckja wyszukuje w drzewie elementu o podanej wartosci lub kluczu   *
 * Zwraca adres tego elementu                       *
 * root - wskaznik na korzen drzewa                 *
 * data - dane lub klucz                        *
 * l_por - liczba wykonanych porownan w trkacie wyszukiwania        *
 ***********************************************************************/
bst *search(bst *root, int data, unsigned long *l_por)
{
  if (root == NULL || data == root->data) {
    *l_por += 1;
    return root;
  }
  *l_por += 1; 
  if (data < root->data)  
    return search(root->left,data,l_por);
  else
    return search(root->right,data,l_por);
}

/****************************************************************
 * Funkcja znajduje w drzewie element o najmniejszym kluczu *
 * Zwraca adres tego elementu                   *
 * root - wskaznik na korzen                    *
 ***************************************************************/
bst *min(bst *root)
{
  while (root->left != NULL)
    root = root->left;
  return root;
}

/****************************************************************
 * Funckja znaduje w drzewie element o najwiekszym kluczu   *
 * Zwraca adres tego elementu                   *
 * root - wskaznik na korzen                    *
 ***************************************************************/
bst *max(bst *root)
{
  while (root->right != NULL)
    root = root->right;
  return root;
}

/****************************************************************
 * Funckja usuwa z drzewa wezel o podanym kluczu        *
 * Zwraca adres wstawionego elementu na miejsce usunietego  *
 * root - wskaznik na korzen                    *
 * data - dane lub klucz usuwanego elementu         *
 ***************************************************************/
bst *delete(bst *root, int data)
{
  bst *del; //adres elementu do usuniecia
  bst *x, *y; //pomocnicze wskazniki
  unsigned long l = 0;
  bst *parent_x, *parent_y; //wskazniki na rodzicow

  del = search(root,data,&l);
  if (del->left == NULL || del->right == NULL) //przypadek pierwszy
    y = del;
  else
    y = succ(root,del->data);
  if (y->left != NULL) //przypadek drugi
    x = y->left;
  else
    x = y->right;
  if (x != NULL) {
    parent_x = parent(root,x);
    parent_y = parent(root,y);
    parent_x = parent_y;
  }
  if (parent(root,y) == NULL)
    root = x;
  else if (y == parent(root,y)->left)
    (parent(root,y)->left) = x;
  else
    (parent(root,y)->right) = x;
  if (y != del)
    del->data = y->data;
  return y;
}

/********************************************************************************
 * Funkcja wyznaczajaca nastepnika danego elementu              *
 * Zwraca adres tego elementu                           *
 * root - wskaznik na drzewo                            *
 * data - klucz lub dane elementu ktorego nastepnika bedziemy wyznaczac     *
 *******************************************************************************/
bst *succ(bst *root, int data)
{
  bst *x, *y;
  unsigned long l = 0;

  x = search(root,data,&l);
  if (x->right != NULL)
    return min(x->right);
  y = parent(root,x);
  while (y != NULL && x == y->right) {
    x = y;
    y = parent(root,y);
  }
  return y;
}

/********************************************************************************
 * Funckja wyznaczajaca poprzednika danego elementu             *
 * Zwraca adres na ten element                          *
 * root - wskaznik na korzen                            *   
 * data - dane lub klucz elementu, ktorego porzednika bedziemy wyznaczac    *
 *******************************************************************************/
bst *pred(bst *root, int data)
{
  bst *x, *y;
  unsigned long l = 0;

  x = search(root,data,&l);
  if (x->left != NULL)
    return min(x->left);
  y = parent(root,x);
  while (y != NULL &&  x == y->left) {
    x = y;
    y = parent(root,y);
  }
  return y;
}

/********************************************************
 * Funkcja wyznaczajaca rodzica danego elementu     *
 * Zwraca adres do rodzica              *
 * root - wskaznik na drzewo                *
 * syn - element ktorego rodzica bedziemy wyznaczac *
 *******************************************************/
bst *parent(bst *root, bst *syn)
{
  bst *tmp;

  while (root != syn) {
    tmp = root;
    if (root->data >= syn->data)
      root = root->left;
    else
      root = root->right;
  }
  return tmp;
}

Wyszukiwanie liniowe:

#include <stdio.h>
#include <time.h>
#include "table.h"
#include <time.h>

#define N 10000 //liczba elementow tablicy 

long search(int tab[], long size, int x, unsigned long *l_por);

int main(void)
{
  int tab[N], x = 2, i; //x - szukany element
  clock_t start, stop;
  float alg_time;
  long indeks;
  unsigned long l_porownan = 0;

  OpenTable("tab.dat",tab,N);
  PrintTable(tab,N,col);
  tab[N-1] = x; //ustawiam szukany element na srodku tablicy, zeby zbadac rozne przypadki
  start = clock(); //odczytanie aktualnego czasu
  /* 
   * zbadanie czasu wykonania odbywa sie w petli (trzeba usunac komentarz)
   * jesli chcemy zbadac ilosc wykonanych porownan trzeba usunac petle czyli dac jako komentarz
  */
//  for (i = 0; i < 100000; ++i) 
    indeks = search(tab,N,x,&l_porownan);
  stop = clock(); //odczytanie czasu po wykonaniu algorytmu
  alg_time = (stop - start) / CLK_TCK; //obliczenie czasu
  alg_time /= 10000; //czas w sekundach
  printf("\nIndeks szukanego elementu: %d\n", indeks);
  printf("\nCzas wykonywania algorytmu: %f\n", alg_time);
  printf("\nLiczba wykonanych porownan: %lu\n", l_porownan);
}

/*************************************************************
 * funkcja wyszukuje w tablicy indeks elementu x             *
 * tab[] - wksaznik do pierwszego elementu tablicy           *
 * x - szukany element                                       *
 * *l_por - wskaznik do elementu przechowujacego liczbe      *
 *          wykonanych porownan                  *
 ************************************************************/
long search(int tab[], long size, int x, unsigned long *l_por)
{
  long i;

  for (i = 0; i < size; ++i) { //jedno porownanie - i < size
    *l_por += 2;
    if (tab[i] == x) //drugie porownanie
      return i;
  }
}

Wyszukiwanie binarne:

#include <stdio.h>
#include "table.h"
#include <time.h>

#define N 10000 //liczba elementow w tablicy

int searchrek(int *ptab, int l, int p, int x, unsigned long *l_por); //wyszukiwanie rekurencyjnie
int searchiter(int *ptab, int l, int p, int x, unsigned long *l_por); //wyszukiwanie iteracyjnie
void zamien(int *l, int *p); //zamiana miejscami dwoch elementow
void sort(int *ptab); //sortowanie tablicy (ustawienie elementow niemalejaco)

int main(void)
{
  int tab[N], *ptab = tab, x = 2, indeks;
  clock_t start, stop;
  float alg_time;
  long i;
  unsigned long l_porownan = 0;

  OpenTable("tab.dat",tab,N); //wczytanie tablicy z pliku
  tab[N-1] = x; //ustawienie szukanego elementu
  sort(tab); //posotowanie tablicy
  start = clock();
  //for (i = 0; i < 100000; ++i)
    indeks = searchrek(ptab,0,N-1,x,&l_porownan);
  printf("\nans = %d\n", indeks);
  stop = clock();
  alg_time = (stop - start) / CLK_TCK;
  alg_time /= 10000;
  printf("\nTime rec.: %f\n", alg_time);
  printf("\nLiczba wykonanych porownan: %lu\n", l_porownan);
  start = clock();
  //for (i = 0; i < 100000; ++i)
    indeks = searchiter(ptab,0,N-1,x,&l_porownan);
  printf("\nans = %d\n", indeks);
  stop = clock();
  alg_time = (stop - start) / CLK_TCK;
  alg_time /= 10000;
  printf("\nTime iter.: %f\n", alg_time);
  printf("\nLiczba wykonancyh porownan: %lu\n", l_porownan);
  return 0;
}

int searchrek(int *ptab, int l, int p, int x, unsigned long *l_por)
{
  int m;

  *l_por += 1;
  if (l > p)
    return -1;
  m = (l+p) / 2;
  *l_por += 1;
  if (x == *(ptab+m))
    return m;
  else if (x < *(ptab+m)) {
    *l_por += 1; 
    return searchrek(ptab,l,m-1,x,l_por);
  }
  else
    return searchrek(ptab,m+1,p,x,l_por);
}

void zamien(int *l, int *p)
{
  int tmp;

  tmp = *l;
  *l = *p;
  *p = tmp;
}

void sort(int *ptab)
{
  int i, j;

  for (i = 0; i < N-1; ++i)
    for (j = 0; j < N-1; ++j)
      if (*(ptab+j) > *(ptab+(j+1)))
        zamien(ptab+j,ptab+(j+1));
}

int searchiter(int *ptab, int l, int p, int x, unsigned long *l_por)
{
  int m;

  m = (l+p) / 2;

  while (l <= p && x != *(ptab+m)) {
    *l_por += 1;
    if (x < *(ptab+m)) {
      *l_por += 1;
      p = m - 1;
    }
    else
      l = m + 1;
    m = (l+p) / 2;
  }
  *l_por += 1;
  if (x == *(ptab+m))
    return m;
  else
    return -1;
}

Z otrzymanych wyników od razu można zauważyć słabość przeszukiwania liniowego. Widać, że jest to najwolniejszy algorytm i w swoim działaniu wykonuje największą liczbę porównań. Podczas takiego przeszukiwania porównujemy każdy element z szukanym i nie mamy tutaj żadnej struktury posiadającej pewne własności dzięki, którym wyszukiwanie mogłoby odbywać się w krótszym czasie i wymagałoby mniej porównań. Jednak jest to algorytm prosty i szybki w implementacji. Kiedy mamy problem, w którym operujemy niewielką ilością danych lepiej wybrać prosty i szybki do napisania algorytm. Nikt chyba nie tworzyłby specjalnie drzewa BST dla 100 elementów i wykonywał operacje wyszukiwania w tym drzewie. Przeszukiwanie liniowe dobrze jest również stosować wtedy gdy nie mamy żadnych informacji na temat struktury przeszukiwanych danych lub ich składowaniu w pamięci. Algorytm ten jest klasy O(n) ? [1]. Czas trwania algorytmu i ilość porównań zmieniają się w sposób liniowy. Jeżeli umieścimy szukany element na środku tablicy to ilość porównań i czas będą dwa razy mniejsze niż w przypadku gdy element znajdowałby się na końcu tablicy, co widać z otrzymanych wyników. Widać również, że algorytm wyszukiwania liniowego jest niezależny na dane tzn. zakres wartości, czy częste powtarzanie się elementów.
W przypadku wyszukiwania binarnego od razu możemy stwierdzić, że wersja rekurencyjna jest wolniejsza pod względem czasowym od wersji iteracyjnej. Fakt ten wynika z ?właściwości rekurencji? (konieczność odstawiania na stos przy każdym wywołaniu funkcji pewnych informacji pozwalających wrócić do poprzedniego stanu, tzw. ramka stosu. Jednak wersja iteracyjna wymaga większej ilości porównań. Wynika to z derekursywacji rekurencji, co jest związane z zastosowaniem pętli, a co za tym idzie większej liczby porównań. Jeżeli szukany element znajduje się w środku tablicy to od razu go znajdujemy i algorytm wykonuje minimalną dla tego przypadku liczbę porównań. Algorytm ten jest klasy O(log2N) = [2], a o jego sile może świadczyć fakt, że dla N równego miliard, liczba porównań w przypadku pesymistycznym wynosi log2N = 30. W naszych wynikach widać również algorytm ten nie jest odporny na zakres wartości.
Jeżeli spojrzymy na wyniki otrzymane dla drzew BST to od razu widać, że algorytm wyszukiwania w drzewach BST jest najlepszy. Nie wynika to do końca z faktu tego algorytmu, ale ze struktury danych jaką tworzą drzewa. Poprzez odpowiednie ustawienie elementów mamy szybki dostęp do szukanego elementu przy najmniejszej liczbie porównań w porównaniu do pozostałych algorytmów. Wynika to z faktu, że elementy mniejsze znajdują się na lewo od swojego rodzica, a większe na prawo. Dlatego też można zauważyć, że w przypadku drzew duże znaczenie mają dane wejściowe, a mianowicie ich zakres i częstość występowania. Od razu widać, że im większy zakres tym szybciej znajdujemy nasz element bo od razu odrzucamy pewną część danych. W przypadku gdy nasze wartości są z wąskiego zakresu wówczas część naszego drzewa może przeobrazić się w listę. Dlatego stosuje się pewne odmiany drzew (np. drzewa czerwono ? czarne). Podstawowe operacje na drzewach wymagają czasu proporcjonalnego do wysokości drzewa ? [3]. W drzewie binarnym o n węzłach operacje takie w przypadku pesymistycznym działają w czasie ?(lg n).
Podsumowując wyszukiwanie w drzewach BST jest najszybsze i wymaga najmniejszej ilości porównań do znalezienia naszego elementu.
Drzewa BST mają szerokie zastosowanie - [1]:

Reprezentowanie wyrażeń arytmetycznych ? [1]: element drzewa oprócz standardowych wskaźników posiada dwa pola ? operatora i danych. Po napisaniu odpowiednich funkcji obsługujących taką strukturę można wyrazić dowolnie skomplikowane wyrażenie arytmetyczne oraz wykonywać różne operacje jak np. różniczkowanie.
USS ? Uniwersalna Struktura Słownikowa ? [1]: funkcje sprawdzające poprawność ortograficzną wprowadzanych informacji (arkusze kalkulacyjne, edytory tekstu).
Drzewa pozycyjne ? [3]: do reprezentowanie wszystkich możliwych kombinacji funkcji logicznej i jej minimalizacji

  1. Literatura:

[1] ? P. Wróblewski, Algorytmy struktury danych i techniki programowani, Helion 2003
[2] ? D. Harel, Rzecz o istocie informatyki, WNT 2001
[3] ? T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT 2004

7 komentarzy

W sumie nieźle, ale wdało się trochę nieścisłości:
"Tablica złożona z 10000 elementów", "Ilość porównań: 20000" - jakim cudem ilość porównań jest większa od ilości elementów tablicy?
"wypełniona wartościami z zakresu od ?10 do 20", "Szukany element to 12000" - jeśli w wartościach jest 12000, to zakresem bynajmniej nie jest -10..20.
Ponadto bardzo tendencyjnie dobierasz położenie wyszukiwanych elementów - albo środek, albo koniec tablicy; dla szukania binarnego to albo pierwszy, albo drugi krok, więc nie jest to reprezentatywne. Powinieneś umieścić szukany element w losowym miejscu, i przeprowadzić szukanie kilka tysięcy razy - wtedy miałbyś wiarygodne czasy dla wszystkich trzech algorytmów.

Ilość porównań wynosi 20000 ponieważ w algorytmie wyszukiania liniowego są wykonywane dwie instrukcje porównanią (patrz komentarze w kodzie źródłowym). Tak zakres jest od - 10 do 20. Szukany element może być 21. Ale akurat sobie wziąłem 12000 tak o bez powodu. No a co do położenie elementów to masz racje, nie uwględniłem przypadku gdy wyszukiwany element będzie na początku tablicy. Jednak na podstawie dokonanych wyników myślę że można co nie co już powiedzieć jak sytuacja będzie się miała gdy element będzie się znajdował na początku tablicy. Pozdrawiam ...

nie chodzi mi o "początek" tablicy - tablica ma więcej, niż trzy elementy.

zrobiłeś diagnoze, a gdzie wnioski ? przy takich testach zawsze jest umieszczane podsumowanie

Wnioski się pokażą niebawem (wotrek), narazie nie miałem czasu. Pozdrawiam

ciekawy i konkretny artykuł, tylko ten kod bez kolorowania i normalnych wcięć ciężko czytać

W artykule jest poważny błąd, który był wynikiem mojej nie uwagi, za przepraszam wszystkich. Mianowiecie w wyszukiwaniu binarnym zapomniałem posortować tablicę :) Dziwne, że wogóle to zadziałało niedługo umieszczę werjsę poprawioną wraz z pomiarami i wnioskami.