W dniu wtorek, 15 stycznia 2013 12:21:52 UTC+1 użytkownik firr kenobi napisał:
> NIe jestem przekonany czy gdybym chioial
> np napisac takie edytor ktory by mial sprawnie
> pomagac w edycji 100 megabajtowych plikow txt
> to indeksowanie byloby lepszym wyjsciem niz
> szybki algorytm wyszukiwania. :-? Za duzo
> tekstu do indeksowania pewnie..
To kolejny ciekawy i trudny aspekt tego i wielu innych
zadań programistycznych. Czy lepiej coś zaindeksować, czy
lepiej zostawić użytkownikowi więcej wolnej pamięci RAM?
Gdy pamięci zabraknie na indeks, to lepiej dać sobie
spokój, ale zwykle nie wiemy na jakim statystycznym
komputerze będzie odpalany nasz program.

Poza tym z indeksami jest drugi problem, chyba nie da się
efektywnie zaindeksować wzorców o różnych długościach, a w praktyce
rzadko kiedy chcemy wyszukiwać tekst o stałej długości.

W praktyce jest jeszcze gorszy problem, jak poniżej pisałeś,
w edytorach możemy mieć listę wierszy a nie ciąg znaków. Wiersze
mogą być alokowane dynamicznie, czyli każdy wiersz może
zaczynać się pod losowym adresem. Wąskim gardłem w wyszukiwaniu
może okazać się problem z cashowaniem takiej struktury danych i
żaden algorytm nie przyspieszy.

Kolejny problem - w praktyce często chcemy wyszukiwać krótkie podciągi, a
to może oznaczać że wyrafinowane algorytmy odpadną z powodu zbyt
dużego narzutu liniowego.

Pozdrawiam