matka5432 Temat założony przez niniejszego użytkownika |
Błyskawiczne wyszukiwanie frazy w tekście » 2012-10-28 16:48:04 Siemka, mam do was pytanie. Chodzi o to, ze mam plik z ogromna liczba slow (2,7mln) posortowanych alfabetycznie, a chce zeby program wyszukiwal dana fraze nie jedna setna sekundy, ale jeszcze szybciej. W tym przypadku najlepiej nie uzywac zwyklego sposobu wyszukiwania:
czy 1 slowo jest takie samo jak ..fraza... czy 2 slowo 3, 4...itd itd.
Tutaj najlepiej wykorzystac to, ze slowa sa posortowane alfabetycznie. Sprawdzic pierwsza litere frazy, po czym zaznaczyc kawalek pliku, w ktorym zaczynaja sie slowa na dana litere, ale program bedzie musial policzyc linijki. Takie cos w sumie wyjdzie na to samo. Czlowiekowi przeciez ulozenie alfabetyczne skroci czas szukania kilkaset tysiecy razy :D jak to zrobic na kompie?
Jest jeszcze jeden sposob. Kazda literke alfabetu oznaczyc liczba, od 1 do 23 i program bedzie wyszukiwal frazy na takiej zasadzie:
znajdz liczbe w przedzieale 1 -20 (szukana liczba to 8)
czy 10 jest wieksze od szukanej liczby, lub rowna sie jej? - jest wieksze.
czy 5 jest wieksze od szukanej liczby, lub rowna sie jej? - jest mniejsze.
czy 7 jest wieksze od szukanej liczby, lub rowna sie jej? - jest mniejsze.
czy 8 jest wieksze od szukanej liczby, lub rowna sie jej? - tak, rowna sie jej <-- znaleziono :)
Tutaj tez program bedzie musial liczyc linijki, bo dostanie rozkaz zejscia na linijke 1,3mln - chyba, ze mozna mu "kazac", aby zeszedl mniej wiecej w to miejsce, z dokladnoscia do 1%. Roznica polega wlasnie na tym, ze czlowiek tego nie liczy dokladnie.
|
|
cyklopek11 |
» 2012-10-28 16:58:04 Zrób funkcję w programie, która wywołana, będzie wyszukiwała odkąd się zaczynają słowa na a, b itd. Ustaw tam wskaźniki oraz zapisz je przed wyłączeniem programu do pliku. Ponieważ będziesz pewnie chciał dopisywać coś do słownika, to wtedy dopiszesz sobie jeszcze jakąś funkcję update() tych wskaźników i po sprawie. Jak będziesz program uruchamiał to nastąpi wczytanie położeń z pliku. Powinno to przyspieszyć wyszukiwanie. Dodatkowo, jeśli utworzysz sobie przy każdym uruchomieniu programu coś w rodzaju cache w pamięci, która będzie przechowywać najczęściej statystycznie wyszukiwane wyrazy, powinno to jeszcze bardziej zwiększyć szybkość wyszukiwania. Podejrzewam, że są do tych celów odpowiednie biblioteki. |
|
Dragonit |
» 2012-10-28 17:09:15 A nie lepiej wyrazy podzielić na kilka plików ? Wyrazy zaczynających się od a, b, c, itd ? |
|
DejaVu |
» 2012-10-28 17:10:54 Wyszukiwanie binarne daje złożoność obliczeniową logarytmiczną. Poza tym istotnym ograniczeniem tutaj będzie szybkość dysku, a nie sam algorytm. Plik ze słowami będzie miał bowiem co najmniej 20MB. |
|
matka5432 Temat założony przez niniejszego użytkownika |
» 2012-10-28 17:16:04 Ze na to predzej nie wpadlem... wiadomo, mozna zapisac kazde slowo do tablicy, ale tablic moze byc max 500 000. Wpadlem jednak na inny pomysl, do kazdej tablicy zapisze 6 slow :D Jak skoncze powiem czy dobrze dziala i mam nadzieje, ze komus sie przyda :)
Juz kiedys dzielilem pliki, niedojz, ze mialem ogromny syf, to i tak nie zwiekszylo to wyszukiwania tak jak oczekiwalem, dokladnie 23-krotnie, ale dzieki tym tablicom powinien sie zwiekszyc kilka tysiecy razy, zobacze co z tego bedzie xd |
|
ison |
» 2012-10-28 17:46:17 Skorzystaj z binsearcha #include <cstdio>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
int main()
{
std::string toFind = "dada";
std::ifstream in( "text.txt" );
if( !in ) return 1;
std::vector < std::string > vec;
std::string tmp;
while( in >> tmp ) vec.push_back( tmp );
if( std::binary_search( vec.begin(), vec.end(), toFind ) ) printf( "TAK\n" );
else printf( "NIE\n" );
}
|
|
matka5432 Temat założony przez niniejszego użytkownika |
» 2012-10-28 18:04:07 Wlasnie o takie cos mi chodzilo. Bardzo bardzo dziekuje :D jesli programik wyszukuje slowo 10 000 000 razy to zajmuje mu to okolo 1.5 sec (jeden raz 0,0000015 sec, 1 800 000 000 000 slow na sekunde xd :) ) . robi wrazenie :D. Jeszcze raz bardzo dziekuje. |
|
| « 1 » |