!
!
!
!
!
!
!
ZAAWANSOWANE ALGORYTMY
Projekt #1
!
!
!
!
!
!
!!
AUTOR:
Maciej Czapla (336374)
!!!!!!!!!
BADANIE PIERWSZE
!
WYNIK
!
MLN
Naive Search Morris–Pratt! Knuth–Morris–Pratt Sunday
1
0,0849864
0,0669019 !
0,054589
0,0009615
2
0,0525335
0,150624 !
0,106101
0,0012703
3
0,126063
0,181195 !
0,149476
0,0028157
5
0,212773
0,231841 !
0,236448
0,0044616
10
0,302371
0,53678
!!
0,495503
0,0085808
20
0,441662
0,886484 !
0,902073
0,0182463
40
0,750992
1,60966
!
1,71828
0,0309622
80
2,35211
3,60046
!
3,65957
0,0705065
!
WYKRES
Tekst mówion !
4
!
y (dane pesymistyczne)
!
3,5
Naive Search
Morris–Pratt
!
3
Knuth–Morris–Pratt
!
[s]ia
Sunday
n
!
a 2,5
w
!
ki
2
!
yszuw 1,5
!
s
za
!
C
1
!
0,5
!!
0
1
2
3
5
!
10
20
40
80
Ilość !
znaków [mln]
!!!
WNIOSKI
Badanie polegało na znalezieniu wzorca w tekście mówionym (książce). Szukany wzorzec znajdował się na samym końcu tekstu by uzyskać dane pesymistyczne dla każdego z algorytmów. Zakładamy, że szukany fragment tekstu występuje tylko raz. Ilość znaków do przeszukania była w zakresie 1-80 milionów.
Najskuteczniejszym z algorytmów okazał się Algorytm Sundaya, drugim w kolejności okazało się wyszukiwanie naiwne a najgorszymi algorytmami okazały się algorytm Knutha-Morrisa-Pratta oraz Morrisa-Pratta, które uzyskały zbliżone czasy wyszukiwania.
BADANIE DRUGIE
!
WYNIK
MLN
Naive Search Morris–Pratt !
! Knuth–Morris–Pratt Sunday
1
0,042668
0,192021
!
0,0796671
0,0156581
2
0,0510857
0,174408
!
0,0884576
0,027844
3
0,119491
0,13307
!
0,10354
0,0300089
5
0,195446
0,253063
!
0,22453
0,0696588
10
0,279339
0,427191
!
0,467406
0,131963
20
0,474117
1,22008
!! 1,38402
0,301024
40
0,728452
1,98318
!
2,20106
0,497789
80
1,57689
3,42585
!
3,83643
1,49375
!
WYKRES
„AB” (dan !
4
!e pesymistyczne)
!
3,5
!
3
Naive Search
!
[s]ia
Morris–Pratt
n
!
a 2,5
Knuth–Morris–Pratt w
Sunday
!
ki
2
!
yszuw 1,5
!
s
za
!
C
1
!
0,5
!!
0
1
2
3
5
!
10
20
40
80
Ilość !
!znaków [mln]
!!
WNIOSKI
Badanie polegało na znalezieniu wzorca w tekście zbudowanym z dwóch rodzajów liter - „A” oraz „B”. Szukany wzorzec znajdował się na samym końcu tekstu by uzyskać dane pesymistyczne dla każdego z algorytmów. Zakładamy, że szukany fragment tekstu występuje tylko raz. Ilość znaków do przeszukania była w zakresie 1-80 milionów. Najskuteczniejszym z algorytmów okazał się Algorytm Sundaya, drugim w kolejności okazało się wyszukiwanie naiwne a najgorszymi algorytmami okazały się algorytm Knutha-Morrisa-Pratta oraz Morrisa-Pratta, które uzyskały zbliżone czasy wyszukiwania.