» Forum » Programowanie » [C, C++] Szukam pomocy

Wszystkie kombinacje danej ilości liter w "słowie"

Ostatnio zmodyfikowano 2012-08-13 22:20

Admixior

» 2012-08-13 15:59:56

ktory posiada az 2,7 miliona polskich odmienionych slow, wiec nie moze byc zbyt wiele liter w alfabecie, ani za dlugich slow, poniewaz wyszukanie wszystkich nawet 4-literowych slow moglo by potrwac kilka dni, narazie zajmuje to okolo 30 sec.

Jeśli lista słówek polskich które masz zapisanych (najlepiej) w jednym pliku po czym je zapisujesz do (najlepiej) wektora na pamięci ram to szukanie nie powinno trwać dłużej niż kilka setnych sekund, a dokładnie...
szukając tzw. sposobem logarytmicznym który jest bardzo szybki w przeciwieństwie do liniowego (które po kolei sprawdza) będzie znacznie lepszym szukaniem.
Ów sposób mi się kojarzy z metodą dziel i zwyciężaj.
Podobnie jest jak się gra w zgadywanie liczb np z przedziału od 1 do 10.
Pytasz się czy większe niż pięć? Odp.: NIE.
Czy większe niż 2? Odp.:TAK.
Czy większe niż 3? ODP.: NIE.
Więc już wiesz że to liczba 3...

Tak samo z szukaniem słówek. Porównujesz połowę czy jest od niej większe. Tak to porównujesz połowę górnej części, nie to połowę dolnej części. Później znów dzielisz na połowę i tak dalej... aż dojdziesz do tego właściwego momentu gdzie będziesz wiedział że to ten wyraz.

Szukanie to nazywa się logarytmiczne gdyż można obliczyć z wzoru log₂(n)=x
gdzie: n to ilość słówek (2,7 mln),
x to ilość sprawdzeń ile wykonamy
czyli inaczej 2^x=n

Z tego co mi powiedział kalkulator to sprawdzeń będzie: 21,4... czyli w najlepszym wypadku porównasz 21 słówek a w najgorszym 22 i statystycznie co 4 słówko na 10 będzie wymagało 1 więcej sprawdzeń. A jak wiadomo 22 porównań strcmp() to nic wielkiego :)

Podam przykładowy kod funkcji która wyszukuje z uporządkowanego wektora (lekko przerobiony kod Jerzego Grębosza, mam nadzieje że nie będzie za to zły :))
Nie wiem jak przetrzymujesz dane ale założyłem że to wektor stringów

#include <string>
size_t znajdz( vector < string >& wec, string & szuk )
{
// definicja dwoch pomocniczych iteratorow
size_t dobry = 0,
szperacz = 0;

// Sprawdzamy dlugosc listy.
// Jesli zero (zbior pusty), to zadanego obiektu w pojemniku na pewno nie ma
if( !wec.size() )
{
return - 1;
}

// skoro dlugosc jest niezerowa, to zaczynamy szukac
// sprawdzamy czy moze obiekt jest na samym poczatku listy
if( wec[ 0 ] == szuk )
{
return 0;
}

// jesli nie na poczatku, to zacznijmy sondowac zbior-liste
// wedlug metody jak przy zgadywaniu liczby

// pierwotnie skaczemy skokiem o dlugosci rownej dlugosci zbioru
// na ostatni element
for( int skok = wec.size() - 1;; skok = skok / 2 )
{
if( skok == 0 ) skok = 1;

szperacz += skok; // wlasciwe przesuniecie iteratora sondujacego

// to jest moment zadania pytania, czyli
// porownanie poszukiwanego obiektu z tym, na ktorego
// pokazuje szperacz.

if( strcmp( wzor, wec[ szperacz ].c_str() ) > 0 )
{ // poszukiwany jest wiekszy, wiec iterator
// _dobry_ mozemy przesunac na pozycje szperacza
dobry = szperacz;

// czy to juz koniec pojemnika ?
if( szperacz == wec.size() )
{
// tzn. obiektu nie bylo w pojemniku
return - 1;
}
}
else
{
// jesli zas poszukiwany obiekt nie jest wiekszy od tego,
// na ktory pokazuje iterator szperacz....

if( wzor == wec[ szperacz ] ) // --- a moze jest mu rowny ?
{
return szperacz; // tak? - to jest ZNALEZIONE!!!!
}

// nie, tzn. ze sondujacym iteratorem skoczylismy za daleko.
if( skok == 1 )
{ // jesli skoczylismy za daleko skokiem o dlugosci =1
// tzn. ze poprzedni obiekt byl tez niedobry
// czyli miedzy tymi dwoma obiektami powinien byc
// umieszczony szukany - a go nie ma.
// Informujemy wiec o nieznalezieniu
return - 1;
}
else {
// jesli skoczylismy, skokiem dluzszym niz 1, a pokazywany
// szperaczem obiekt jest wiekszy od szukanego,
// to znaczy, ze skoczylismy za daleko.
// Wrocmy tam, skad skoczylismy (po to, by za chwile
// zrobic krotszy skok)

// cofamy szperacza do ostatniej dobrej pozycji
szperacz = dobry;
}
}
}
}

Nie jestem pewny co do 100% działalności kodu ale powinien działać.
Jeśli inaczej przechowujesz dane (chociaż ten sposób bym polecał), to przerób tę funkcję

PS. jeśli wiesz co to mapa (lub dobitniej - słownik) w programowaniu to to by było najlepsze rozwiązanie ;]

P-62407

matka5432

Temat założony przez niniejszego użytkownika

» 2012-08-13 22:17:45

Noo takie cos bedzie zdecydowanie szybsze, ale ja wole miec slownik podzielony na kilka plikow, poniewaz c++ wolno dziala na plikach, w ktorych jest tak duza ilosc znakow.

Mam kilka pytan
1. Czy da sie w jakis sposob przyspieszyc wyznaczanie jakiejs kombinacji zaszyfrowanego slowa? (Nie chce kodu, i tak juz duzo zrobiles za co ci dziekiuje :) )

I Co do powyzszego kodu
1. Co oznacza " if( !wec.size() ) " - ja to rozumuje tak: "jezeli nie wielkosc tablicy wec, to zrob cos.." ;p.
2. Po co znaki & w tworzeniu zmiennych w funkcji?
3. Dlaczego na poczatku petli for od skoku(ktory rowna sie wec.size()) odjales 1? Czemu to bedzie ostatnie, a nie przedostatnie slowo?

Sprawdzilbym odpowiedzi na te pytania sam, ale nie wiem jak tego wyszukac, poniewaz nie znam nazw tych metod.
Z gory wielkie dzieki.

Mrovqa, mam tutaj duzo trudnych kodow do przeanalizowania(nie mam duzej wiedzy, ani doswiadczenia w c++), w przeciwienstwie do czasu jakim ostatnimi dniami dysponowalem ;p. Jak przeanalizuje te wszystkie kody i znajde troche czasu w najblizsym czasie, to z pewnoscia sproboje zrozumiec twoj i zobacze czy dam rade wykorzystac z moja wiedza.

P-62432

DejaVu

» 2012-08-13 22:20:56

Nie ma sensu zadawać takich pytań skoro samodzielnie nie byłeś w stanie rozwiązać wyczerpująco swojego problemu. Zresztą... jeden temat = jeden problem, a ten wydaje się być rozwiązany więc powinieneś go zamknąć zgodnie z zasadami obowiązującymi na tym forum. Na resztę pytań pytań masz odpowiedź w komentarzach otrzymanego kodu.

P-62433

1 2 « 3 »

Poprzednia strona

Strona 3 z 3

» Forum » Programowanie » [C, C++] Szukam pomocy