Witam,

mam problem z wyszukiwaniem w słowniku. Gdy wyszukuję jednego klucza
wszystko jest ok, tzn. bardzo szybko. Problem pojawia się w momencie gdy
chcę sprawdzić powiedzmy milion kluczy. Mój program generuje najpierw listę
kombinacji liter a następnie sprawdza w słowniku które z tych kombinacji się
tam znajdują. Samo generowanie listy zabiera góra do 2-3 sekund, natomiast
sprawdzanie które z tych kombinacji są w słowniku - od 20s do kilku minut.

Kod wygląda tak:
bool Check(string słowo)
{
if(dictionary.contains(new KeyValuePair<string, bool>(słowo, false))
return true;
else
return false;
}

[...]

string ret = "";
foreach(string s in kombinacje)
{
if(Check)
ret += s+", ";
}

Próbowałem też dictionary.containsKey(słowo) ale jest jeszcze wolniejsze niż
z kvp.

Moje pytanie brzmi jak to przyspieszyć??? Zastanawiałem się nad
zrezygnowaniem z metody "na siłę" czyli sprawdzania wszystkich kombinacji i
zastąpieniu jej szukaniem wzorca klucza w słowniku, ale nie wiem czy takie
coś jest w ogóle możliwe w .net? Może coś z linqiem? Proszę o rady...

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dnia 16.08.2009 Marcin Połeć <u...@g...pl> napisał/a:

> Witam,
>
> mam problem z wyszukiwaniem w słowniku. Gdy wyszukuję jednego klucza
> wszystko jest ok, tzn. bardzo szybko. Problem pojawia się w momencie gdy
> chcę sprawdzić powiedzmy milion kluczy. Mój program generuje najpierw listę
> kombinacji liter a następnie sprawdza w słowniku które z tych kombinacji się
> tam znajdują. Samo generowanie listy zabiera góra do 2-3 sekund, natomiast
> sprawdzanie które z tych kombinacji są w słowniku - od 20s do kilku minut.

Nie znam .Net, ale to wygląda na przypadek, w którym warto użyć
specjalizowanej struktury danych. Google: "directed acyclic word
graphs"; patrz też: Marcin G. Ciura, Sebastian Deorowicz, "How to
squeeze a lexicon", Software--Practice and Experience 2001;
31(11):1077-1090.

--
Daniel 'Nathell' Janus, m...@n...korpus.pl, http://danieljanus.pl
"Don't treat fictional people as if they were human beings.
It only encourages them."
-- Aris Katsaris, rec.arts.int-fiction

do góry

Marcin Połeć wrote:
> string ret = "";
> foreach(string s in kombinacje)
> {
> if(Check)
> ret += s+", ";
> }
>

Witam,

na pierwszy rzut oka to problem może być z robieniem wielu konkatenacji
(o ile Check(s) wiele razy zwraca prawdę). Spróbuj tak:

StringBuilder result = new StringBuilder();
foreach (string s in kombinacje)
if (Check(s))
{
result.Append(s);
result.Append(", "); // albo zamiast tych dwóch
result.AppendFormat("{0}, ", s);
}
ret = result.ToString();

Powinno być szybciej. Nie kompilowałem tego, metoda ctrl+c, ctrl+v
działać nie musi. :)

Pozdrawiam,
--
Bartek Etenkowski

do góry

Daniel Janus <p...@n...korpus.pl> napisał(a):

> Dnia 16.08.2009 Marcin Połeć <u...@g...pl> napisał/a:
>
> > Witam,
> >
> > mam problem z wyszukiwaniem w słowniku. Gdy wyszukuję jednego klucza
> > wszystko jest ok, tzn. bardzo szybko. Problem pojawia się w momencie gdy
> > chcę sprawdzić powiedzmy milion kluczy. Mój program generuje najpierw
listę
> > kombinacji liter a następnie sprawdza w słowniku które z tych kombinacji
się
> > tam znajdują. Samo generowanie listy zabiera góra do 2-3 sekund,
natomiast
> > sprawdzanie które z tych kombinacji są w słowniku - od 20s do kilku
minut.
>
> Nie znam .Net, ale to wygląda na przypadek, w którym warto użyć
> specjalizowanej struktury danych. Google: "directed acyclic word
> graphs"; patrz też: Marcin G. Ciura, Sebastian Deorowicz, "How to
> squeeze a lexicon", Software--Practice and Experience 2001;
> 31(11):1077-1090.
>

tak to jest bardzo dobry trop!!! Problemem jest znalezienie gotowego
algorytmu na DAWG (tzn. są dostępne ale nie na polskie litery). Jest też
jeszcze szybsza wersja niż DAWG zwana GADDAC, no i wyczytałem że został
opracowany jeszcze szybszy algorytm od GADDACa oparty na DAWGU który nazywa
się optimal DAWG czy jakoś tak :)

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Bartek Etenkowski <n...@c...cz> napisał(a):

> Marcin Połeć wrote:
> > string ret = "";
> > foreach(string s in kombinacje)
> > {
> > if(Check)
> > ret += s+", ";
> > }
> >
>
> Witam,
>
> na pierwszy rzut oka to problem może być z robieniem wielu konkatenacji
> (o ile Check(s) wiele razy zwraca prawdę). Spróbuj tak:
>
> StringBuilder result = new StringBuilder();
> foreach (string s in kombinacje)
> if (Check(s))
> {
> result.Append(s);
> result.Append(", "); // albo zamiast tych dwĂłch
> result.AppendFormat("{0}, ", s);
> }
> ret = result.ToString();
>
> Powinno być szybciej. Nie kompilowałem tego, metoda ctrl+c, ctrl+v
> działać nie musi. :)
>
> Pozdrawiam,
znacznego przyspieszenia nie odnotowałem, średni czas przeszukiwania wciąż
jest około 17sekund

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dnia 19.08.2009 Marcin Połeć <u...@g...pl> napisał/a:

> tak to jest bardzo dobry trop!!! Problemem jest znalezienie gotowego
> algorytmu na DAWG (tzn. są dostępne ale nie na polskie litery).

E tam, wydaje mi się, że powinny działać z dowolnymi znakami. Poza tym
idea jest na tyle prosta, że łatwo machnąć implementację w jeden
wieczór. Moja implementacja deserializatora i trawersera DAWG-ów w
Clojure zajmuje jakieś trzydzieści linii kodu.

> Jest też
> jeszcze szybsza wersja niż DAWG zwana GADDAC, no i wyczytałem że został
> opracowany jeszcze szybszy algorytm od GADDACa oparty na DAWGU który nazywa
> się optimal DAWG czy jakoś tak :)

Zależy do czego. Jeśli potrzebujesz tylko sprawdzać, czy napis jest w
słowniku, to DAWG-i wystarczają w zupełności (oczywiście, najlepiej
optymalne w sensie liczby węzłów -- patrz wspominany przeze mnie
artykuł). GADDAG przydaje się, gdy chcesz pracować z podnapisami
niekoniecznie zaczynającymi się na początku napisu ze słownika.

--
Daniel 'Nathell' Janus, m...@n...korpus.pl, http://danieljanus.pl
- Proč má člověk mlčet?
- Aby slyšel melodie lidí kolem sebe.
[Rok diabła]

do góry

W dniu 2009-08-19 18:31, Marcin Połeć pisze:
> Bartek Etenkowski<n...@c...cz> napisał(a):
>> na pierwszy rzut oka to problem moĹźe byÄ? z robieniem wielu konkatenacji
>> (o ile Check(s) wiele razy zwraca prawdÄ?). SprĂłbuj tak:
>>
>> StringBuilder result = new StringBuilder();
>> foreach (string s in kombinacje)
>> if (Check(s))
>> {
>> result.Append(s);
>> result.Append(", "); // albo zamiast tych dwĂłch
>> result.AppendFormat("{0}, ", s);
>> }
>> ret = result.ToString();
>>
>> Powinno byÄ? szybciej. Nie kompilowaĹ?em tego, metoda ctrl+c, ctrl+v
>> dziaĹ?aÄ? nie musi. :)
>>
>> Pozdrawiam,
> znacznego przyspieszenia nie odnotowałem, średni czas przeszukiwania wciąż
> jest około 17sekund

Generalnie to jak juz wyzej poradzono lepiej skupic sie na zlozonosci
algorytmu. To tutaj to kwestie implementacyjne. Jakkolwiek, dla duzej
liczby konkatenacji StringBuilder jest wydajniejszy. Jezeli funkcja go
uzywajaca jest czesto wolana to warto StringBuildera tworzyc raz i
odpalac clear() na poczatku funkcji go uzywajacej. (Chodzi o
zmniejszenie liczby alokacji). Inna sprawa - jezeli chcesz bawic sie w
takie drobnostki - zamiast foreach uzyj zwyklego for.
np.

int liczbaKombinacji = kombinacje.Count;
string s = String.Empty;

for(int i = 0; i < liczbaKombinacji; i++)
{
s = liczbaKombinacji[i];
// operacje na s
}

--
Pozdrawiam
Marcin Kral

do góry