Wątek zablokowany 2013-07-15 22:15 przez msm.

fast algor - szukanie wg wzorca

0

Mamy wzorzec w stylu: ##B#D#...
gdzie symbol # oznacza dowolną literę (może to być kodowane inaczej, np. 0x0, albo 0xff).
Może być dowolna kombinacja, np. #########, albo ARBUZ.

Długość może być różna - jak słowa w słowniku, czyli od 2 do 20 liter powiedzmy.

Mamy taki wzorzec oraz słownik, w którym szukamy pasujących słówek do tego wzorca.

i tak na piechotę będzie to funkcja w stylu:

int find(w, sl, ls) // w - wzorzec, sl - słownik, ls - długość słów i wzorca
{
  int is = 0; 

  do{
     char *s = sl[is]; // sprawdzamy is-te słowo
     
     for(i = 0; (i < ls) && (w[i] == '#' || w[i] = s[i]); i++) // spr. po jednej literce
         ;
     
     if( i == ls ) return is; // pasuje - koniec szukania
      
    }while( ++is < sl.ilosc_slowek );

 return -1; // nie znaleziono

}

no, ale to będzie straszliwie wolne.
Najlepiej chyba sprawdzać po kilka literek naraz, np. 4, lub 8 -
może są jakieś rozkazy w MMX lub SSE specjalnie do takich operacji na maskach, stringach?

wyrzuciłem tagi (w kgórych było "człowiek, w, masce") - msm

0

Hm skoro # oznacza cokolwiek, to może coś takiego if (w[i] == b && w[i+2] == D), tego co pomiędzy nimi i tak nie ma sensu sprawdzać. Oczywiście trzeba by wpisać wzorzec do jakiejś struktury w której będą znak oraz jego pozycja względem pierwszego znanego znaku z wzorca.

0
sig napisał(a):

Hm skoro # oznacza cokolwiek, to może coś takiego if (w[i] == b && w[i+2] == D), tego co pomiędzy nimi i tak nie ma sensu sprawdzać. Oczywiście trzeba by wpisać wzorzec do jakiejś struktury w której będą znak oraz jego pozycja względem pierwszego znanego znaku z wzorca.

Przecież tych wzorców mogą być tysiące, np.:

A##### -> pięcioliterowe słowa zaczynające się na A
#####A -> pięcioliterowe słowa kończące się A
A####A -> ...

WA### -> tu pasują słowa: WALKA, WARKA, WALUŚ, WALIM, itd.

To tak jak przy rozwiązywaniu krzyżówki:
gdy masz tylko kilka literek z nieznanego słowa, wtedy sobie zgadujesz - dopasowujesz słowa wg takiego wzorca właśnie.

Nie popsute edytory, tylko taki "feature". W teorii to służy do tworzenia list. - msm

0

http://www.boost.org/doc/libs/1_54_0/libs/regex/doc/html/index.html

nie trzeba pisać jak już coś jest napisane ;)

0
fasadin napisał(a):

http://www.boost.org/doc/libs/1_54_0/libs/regex/doc/html/index.html

nie trzeba pisać jak już coś jest napisane ;)

Przestań... takim kodem szukałbyś minutę jednego pasującego słowa.
To ma zasuwać - milions per second!

0

Zrób inną strukturę słownika niż prymitywna tablica.

0

Hm a może karta graficzna? Rdzeni strumieniowych (a takie powinny się tu świetnie sprawdzić, bo robimy dokładnie to samo na dużej ilości danych) tam zwykle dużo. Więc będzie można sprawdzać wiele słów/masek naraz.

0
_13th_Dragon napisał(a):

Zrób inną strukturę słownika niż prymitywna tablica.

Niby jaką?

To musi być sekwencyjne, bo w ogólnym przypadku szukamy nie tylko pierwszego pasującego, lecz również kolejne - alternatywne.

Przykładowo: znalazłem słowo pasujące nr 50, robię z nim coś,
i wtedy może się okazać że ono jest niedobre, więc trzeba je zmienić na inne, więc zaczynam szukać od 51, itd.

0

Załóżmy że zrobisz vector<list<string> > VL(26); to jeżeli masz na pierwszym miejscu literę ch to VL[ch-'A'] - daje ci listę tych zaczynających się na A więc teoretycznie średnio masz jakieś 26 razy szybciej (w rzeczywistości nie będzie aż tak różowo).
Więc jak zrobisz podobnie dla każdej pozycji - to dostaniesz to co chcesz.
Uprzedzam że struktura nie jest trywialna.

3

Ave.

Niby jaką?

Niezbyt miłe.

No dobra, mniejsza z tym. W każdym razie tak:

Algorytm naiwny faktycznie niezbyt wesoły jeśli słów chcesz mieć dużo (setki tysięcy? Tyle chyba w języku polskim nie ma :( ) i robić dużo (tysiące?) zapytań na raz.
Nie szukaj jak go przyśpieszyć, bo nic nie znajdziesz ciekawego. Ma złożoność pesymistyczną = optymistyczną = O(n * m) (n = liczba napisów, m = długość wzorca) - jeśli musisz przejrzeć wszystkie napisy w tekście, nie ma szans żeby to bardzo szybko działało.

Propozycja bardziej algorytmicznych podejść do sprawy (wymaga zmiany struktury danych):

Pierwszym pomysłem przychodzącym do głowy jest trie.
Nie jest tak trudne do implementacji, przy dobrze napisanym będzie bardzo szybkie dla typowego przypadku. Niestety, w pesymistycznym nie będzie tak różowo.

Konkretnie, złożoność to O(min(z + c^n, m)) - gdzie z to liczba znanych znaków we wzorcu, n to liczba nieznanych znaków we wzorcu (wildcardów), c to rozmiar alfabetu a m to łączna liczba słów (wiem, pełno tych oznaczeń) - to znaczy, złożoność rośnie wykładniczo z ilością niewiadomych znaków w napisie, ale na szczęście nigdy nie przekracza ilości słów łącznie.

O co dokładniej chodzi w tym sposobie. Trie to taka sprytna struktura danych, co służy właśnie do wygodnego przechowywania i odpytywania zbiorów napisów.
Wygląda ono tak, że idąc od korzenia przechodząc przez kolejne węzły drzewa odtwarzamy dodane napisy. Na przykład że jeśli są napisy ALA, ALAMAKOTA, ANANAS, ANARCHIA, ANARCHISTA i BATMAN, powstanie drzewo:

          *
         /
      L-A
     /   \
    A     M-A-K-O-T-A-*
   / \
  /   N-A-N-A-S-*
 /     \
*       A-R-C-H-I-A-*
 \               \
  \               S-T-A-*
   \
    B-A-T-M-A-N-*

Jak takiego drzewa użyć do znalezienia wszystkich pasujących (to nie ma byc działający kod, tylko formalny pseudokod. Ale z niewielkimi modyfikacjami, i oczywiście tworzeniem drzewa, powinno zadziałać bez problemów):

struct trie_t {
    trie **child[CHARSET_SIZE];
    // może jeszcze ew. parent do otworzenia słowa.
};

void find_all(trie_t *root, char *left) {
    if (*left == '#') { // jeśli kolejny znak we wzorcu to wildcard
        for (int i = 'a'; i < 'z'; i++) { // sprawdzenie wszystkich możliwych gałęzi trie wychodzących z tego punktu
            // uściślenie - zamiast testować wszystko 'a'-'z' dobrym pomysłem jest trzymanie listy niezerowych gałęzi wychodzących. Nie zrobiłem tego od razu, bo komplikowałoby pseudokod niepotrzebnie a pomysł ten sam.
            if (root.child[i] != 0) { // oczywiście nie można sprawdzać w tablicy po prostu 'a', 'b' itd - trzeba je zamieniać na 1, 2, 3 itp
                find_all(root.child[i], left + 1); // i rekurencyjne szukanie w nich - stąd ta wykładnicza złożoność
            }
        }
    } else {
        if (root.child[*left] != 0) { // jeśli obecny węzeł zawiera kolejny znak z wzorca, sprawdzamy czy doprowadzi nas do końca
            if (*left != '\0') { // jeśli kolejny znak nie jest nulem (to nie koniec napisu)
                find_all(root.child[*left], left + 1); // idziemy wgłąb drzewa sprawdzając dalej.
            } else { // jeśli to nul, znaleźliśmy.
                printf("Znaleziono"); // i tu by wypadało odtworzyć słowo idąc w górę czy coś...
            }
        }
    }
}

Nie wiem czy jasno to wytłumaczyłem, więc przykład na poprzednim drzewie - szukamy A#ANAS:

          *
         /
      L-A
     /   \
    A     M-A-K-O-T-A-*
   / \
  /   N-A-N-A-S-*
 /     \
*       A-R-C-H-I-A-*
 \               \
  \               S-T-A-*
   \
    B-A-T-M-A-N-*

Na początku wzorca znak A - wchodzimy w górne poddrzewo z literą A. Następnie jest wildcard, więc wchodzimy rekurencyjnie we wszystkie poddrzewa. W każdym z poddrzew próbujemy dopasować ANAS, i tak algorytm idzie aż znajdzie wszystkie dopasowania.

To tyle o trie, jeśli będzie Ci się chciało je zaimplementować to będzie prawdopodobnie w realistycznych przypadkach działać bardzo szybko (poza napisami w stylu ####A####, ale to patologia).

Jest też alternatywny algorytm który mógłby być szybszy, ale nie mam na tyle odwagi żeby o drugiej w nocy przeprowadzać analizę jego złożoności ;]. Pomysł opiera się na tym, żeby dla każdego zbioru słów o długości n (słowa różniące się długością z wzorcem i tak nie mogą być dopasowane) trzymać listę zbiorów słów mających tą literę na tym miejscu. Hmm, nic nie wynika z poprzedniego zdania. Tzn. jeśli mamy słowa ABA, GAA, BBB, powstaje struktura:

    /A : ABA
   /-B : BBB
[_]--G : GGG

   /A  : GAA
[_]-B  : ABA, BBB

   /A  : GAA, ABA
[_]-B  : BBB

I teraz szukanie wzorca polega na łączeniu zbiorów - czyli jeśli mamy A#A, to wykonujemy:

zbiór napisów mających A na pierwszym miejscu = { ABA }
drugi znak pomijamy
zbiór napisów mających A na ostatnim miejscu = { GAA, ABA }

i bierzemy część wspólną zbiorów: { ABA } /\ { GAA, ABA } = { ABA }

Wąskim gardłem jest część wspólna zbiorów. Nie jestem pewien jak bym to rozwiązał, ale istnieją szybkie algorytmy części wspólnej z n zbiorów... No i są bloom filtery, które tutaj można by zastosować ;]

0
_13th_Dragon napisał(a):

Załóżmy że zrobisz vector<list<string> > VL(26); to jeżeli masz na pierwszym miejscu literę ch to VL[ch-'A'] - daje ci listę tych zaczynających się na A więc teoretycznie średnio masz jakieś 26 razy szybciej (w rzeczywistości nie będzie aż tak różowo).
Więc jak zrobisz podobnie dla każdej pozycji - to dostaniesz to co chcesz.
Uprzedzam że struktura nie jest trywialna.

Mamy 35 liter w polskim... w słowackim chyba prawie 50.

Można tak zrobić, ale należałoby po każdej literce nie tylko pierwszej.
I wtedy trzymamy wskaźniki do słówek, np. 8-literowe: 8 x 35 takich niby słowników.

Wówczas czas szukania dla wzorców z jedną literką byłby znikomy - od razu.

Ale dla dwóch liter, np.: #K#R# musimy szukać po K albo po R - minimum z obu.
Dla 3 liter i więcej - podobnie.

Czyli taka metoda przyspiesza z 30 razy takie szukanie w jednym wielkim słowniku.

Można pójść z tym dalej i poindeksować parami liter - wtedy będzie niby 30x30 razy szybciej.

Wówczas tych list byłoby od groma: [i,j][c] tak należałoby to indeksować; i, j - pozycje liter, c - litera.
Dla 8-lierowców byłoby tego minimum: 8(8-1)/2 x 35 = 28 x 35 sztuk.
A dla 16-literowców: 16x15/2 x 35 = 120 x 35

Trójkami już raczej nie ma sensu indeksować.

No, ale tamte porównania - literka po literce z wzorcem i tak tu muszą pozostać.

Gdyby testować naraz po 4 literki, będzie już 4 razy szybciej, albo i lepiej, bo tam jest sporo instrukcji:

i < l && w[i] == '#' || w[i] == s[i]; i++

A te drzewa koronowe, czy jakoś tak, to raczej nie przejdzie.

Takie coś może byłoby dobre do tradycyjnego szukania kluczy, czyli pełnych haseł, a nie takich podziurawionych: ??B??Z

Algor musiałby jakoś strasznie dziwnie tu kombinować - chodzić po tym drzewie.
Tak przynajmniej to wygląda z lotu... węża. :)

1
wir napisał(a)

...

Hint: przeczytaj mój post.

Chyba że drzewa koronowe były o mnie, w takim przeczytaj do końca. Opisałem dokładnie problem podziurawionych + podałem pseudokod + złożoność. Nie mówię że trie jest idealne do tego problemu (dlatego podałem też drugi algorytm...) - ale nawet w pesymistycznym przypadku jest znacznie szybsze niż Twoje sprawdzanie wszystkiego jak leci. Chętnie wysłucham konstruktywnej krytyki, ale konstruktywnej zamiast raczej nie przejdzie.

Koncentrujesz się na mikrooptymalizacji tego kodu, podczas gdy masz fundamentalny problem - zawsze przeglądasz wszystkie słowa. Z tego powodu nigdy nie będziesz w stanie zmniejszyć czasu wykonania poniżej pewnej granicy, bo będzie Cię trzymać sam czas czytania danych (wyobraź sobie sporą (mającą kilka GB danych powiedzmy) bazę danych która dla każdego zapytania przechodzi po wszystkich zapisanych rekordach...).
No chyba że faktycznie ratuje Cię taki niewielki zysk jak czterokrotny.

0

Ja kiedyś myślałem o czymś takim, ale jak mówiłem: nie da rady w tym drzewie szybko dochodzić do szukanych pozycji, gdy brakuje liter w szukanym kluczu.

Mamy przykładowo taki wzór: ???BRA, i co - gdzie zaczynamy?

Musimy lecieć po całym tym drzewie i szukać liści z BRA, które są najniżej, czyli tysiące operacji -
przeszukujemy właśnie cały słownik, i nie byłoby to proste indeksowanie tablicy słów, jak w przypadku listy,
lecz znacznie bardziej złożone, tym samy i wielokrotnie wolniejsze.

To byłoby dobre dla szukania prefiksów, czyli odwrotnie: BA???
Można całe drzewo zbudować odwrotnie, no ale wtedy byłoby to szybkie tylko dla postfiksów.

Tu należy zredukować liczbę przeszukiwanych - testowanych słów, plus optymalizacja tego testu.
I chyba tylko to indeksowanie parami liter jest sensowne... jako tako.

Wówczas testujemy średnio: L^2 razy mniej, L - liczba liter.
Dla L = 30, wyjdzie tu ~1/1000 słów do sprawdzenia.
8 literowych jest chyba najwięcej - z 20 tyś. (podstawowych), więc sprawdzalibyśmy zazwyczaj mniej niż 20 sztuk, zamiast całe 20000.

2
wir napisał(a):

Ja kiedyś myślałem o czymś takim, ale jak mówiłem: nie da rady w tym drzewie szybko dochodzić do szukanych pozycji, gdy brakuje liter w szukanym kluczu.
Totalne bzdury.

wir napisał(a):

Mamy przykładowo taki wzór: ???BRA, i co - gdzie zaczynamy?
Zaczynamy od korzenia i pierwsze trzy poziomy bierzemy całe.

wir napisał(a):

Musimy lecieć po całym tym drzewie i szukać liści z BRA, które są najniżej, czyli tysiące operacji -
przeszukujemy właśnie cały słownik, i nie byłoby to proste indeksowanie tablicy słów, jak w przypadku listy,
lecz znacznie bardziej złożone, tym samy i wielokrotnie wolniejsze.
i tak 26^3 razy szybciej niż to co masz dotychczas.

  1. Poczytaj jeszcze raz i się zastanów.
  2. Jeżeli nadal nie widzisz że jest znacznie szybciej od twojego to wróć do punktu 1.
  3. Po zrozumieniu że to co podał @msm jest znacznie szybsze od twego podejścia przeczytaj jeszcze raz moją poprzednią propozycje.
0
_13th_Dragon napisał(a):

Zaczynamy od korzenia i pierwsze trzy poziomy bierzemy całe.

A co to znaczy 'bierzemy trzy poziomy' w czymś takim:

         *
         /
      L-A
     /   \
    A     M-A-K-O-T-A-*
   / \
  /   N-A-N-A-S-*
 /     \
*       A-R-C-H-I-A-*
 \               \
  \               S-T-A-*
   \
    B-A-T-M-A-N-*
_13th_Dragon napisał(a):
wir napisał(a):

Musimy lecieć po całym tym drzewie i szukać liści z BRA, które są najniżej, czyli tysiące operacji -
przeszukujemy właśnie cały słownik, i nie byłoby to proste indeksowanie tablicy słów, jak w przypadku listy,
lecz znacznie bardziej złożone, tym samy i wielokrotnie wolniejsze.
i tak 26^3 razy szybciej niż to co masz dotychczas.
</quote>

Chwilowa to ja mam tamte: N/L^2, co daje kilka sprawdzeń na wzorzec, zamiast N = tysiące.
Za pomocą prostego indeksowania parami literami.

A Ty masz zamiar 'brać' do 26^3 węzłów naraz w tym drzewie - pewnie do jednego rejestru. ;)

0

Wszystkie słowa w słowniku podziel na tyle grup, ile słów o różnej długości. W każdej grupie niech znajdują się słowa o identycznej liczbie liter. Teraz na podstawie wzorca zawężasz obszar poszukiwań do jednej grupy, która jest znacznie mniejsza od całego słownika. Dostęp do grupy ma pomijalną złożoność, zatem żadnym kosztem zyskujesz dość wiele, dodatkowo pozbędziesz się problemu, który zacznie Ciebie za chwilę trapić (sądząc po tym, w jakim to kierunku idzie). - Tacet dzisiaj, 02:09

Wiadomo że słowa każdej długości są w osobnych listach.

Lepiej, a nawet gorzej: jest aż l*(l-1)/2 x L^2 list dla jednej długości !
l - długość, L - liczba liter alfabetu, dla polskiego L = 35

I przykładowo dla haseł 4-literowych -

l = 4: 4x3/2 x 352 = 6 x 352 = 7350 aż tyle list,
co jest grubą przesadą, bo takich słów nie ma więcej od 4000 i łącznie z egzotycznymi nazwami geograficznymi,
czyli wyjdzie mniej niż 1/2 hasła na listę, no i tyle przeszukujemy średnio.

l = 8: 8x7/2 x 352 = 28 x 352 = 34300 list
a haseł jest poniżej 20 tyś., czyli tu testujemy średnio 1.5 sztuki na listę.

A co to znaczy 'bierzemy trzy poziomy' w czymś takim - przecież wynika z pseudokodu podanego wcześniej.

To znaczy do 26^3 sprawdzeń, i nie takich prostych - if jest then bęc,
lecz skomplikowane łażenie po drzewie, czyli metoda traci zupełnie swoje zalety - nie działa w tym przypadku.

Nawet na takim marne wyjdzie: ARB?Z
Po ścieżce ARB zjedziemy szybko - i teraz co?
Nic musimy sprawdzać L = 35 sztuk, bo tyle jest możliwych ścieżek do następnej litery.

ARB??K - tu sprawdzasz już 352 - szukasz litery Z w 352 liściach (zwykle mniej, bo nie mamy przecież wszystkich permutacji w alfabecie...)

A?B?K - a tu ile węzłów należy sprawdzać?
Chyba też do L2 = 352, albo i gorzej...

0
wir napisał(a):

l = 8: 8x7/2 x 352 = 28 x 352 = 34300 list
a haseł jest poniżej 20 tyś., czyli tu testujemy średnio 1.5 sztuki na listę.

Powinno być odwrotnie, tj.: 20000/34300 = ~ 1/2 na listę, czy to samo co dla l = 4.

Pewnie dla wszystkich długości tak będzie, ponieważ to wynika z rozkładu występowania par liter w słowach.

Tu jest bardzo nierównomierny rozkład:
AK, AR, AS, AT, BE, RE, TE, SA, FE, JA, JE, KI, KO, ... - tego typu pary bardzo często występują w słowach, natomiast:
AA, BB, RR, ... oraz: BS, SB, PT, TP, ... - praktycznie wcale;
pozostałe jakoś pośrednio: RW, WR, KR, TR.

A odległe pary liter, typu: P?A, T??A pewnie idą już normalnie, znaczy z frekwencją pojedynczych liter.

No i tu od tej strony należałoby kombinować, znaczy uwzględniać statystykę liter w słowach: pojedynczych i par pewnie wystarczy.

Podobnie byłoby z kompresją tekstów, i tu algorytm zakładający równomierny rozkład byłby bardzo słaby,
no i takie są stosowane w praktyce - kompresja tekstu 50% jest tu sukcesem,
a i tylko dzięki temu że mamy alfabet krótki: L << 256.

1

Pierwszy poziom drzewa powinien rozdzielać słowa ze względu na ich długość. Czemu wiadomo.
Słownik ma około 60tysięcy słów zapewne najpopularniejsza długość słów będzie zawierać około 12tysięcy.
W kolejnym poziomie drzewa, rozdzielasz na pozycje i litery, czyli na tablicę <wielkość alfabetu>*<długość słowa>. W pesymistycznej wersji w jednym zbiorze powinno zostać około 2000 słów a to czyni zbiór już na tyle małym, że można z czystym sumieniem lecieć brute force.

Podczas wyszukiwania należy oczywiście zaczynać od liter mało popularnych, więc jeśli masz wzorzec ##a#b# to filtrujesz najpierw po b bo jest ono dość rzadko występującą literą.

W bardziej zaawansowanej wersji można próbować wykonać przecięcie indeksów uzyskanych za pomocą takiego drzewa, co też nie powinno być trudne.

0
MarekR22 napisał(a):

Pierwszy poziom drzewa powinien rozdzielać słowa ze względu na ich długość. Czemu wiadomo.

Te drzewa są beznadziejne w tym przypadku.
Jeśli już to być jakieś B-drzewa można by tu próbować.

Słownik - leksykon ma grubo ponad 100 tyś. pozycji.
Samych popularnych, łatwych - niefachowych jest chyba około 60 tyś.

0

Wydaje mi się, że jeśli chodzi o wydajność (prędkość wyszukiwania) to najlepszym (prostym rozwiązaniem) byłaby jakaś baza z full text search, albo utworzenie odpowiednich własnych indeksów dla Twoje struktury danych. Szukałbym informacji o indeksach pełnotekstowych a rozwiązania podpatrywał w bazach danych dla bibliotek :)

4

Zamiast być gołosłownym to lepiej pokazać, że coś działa.
Jako, że miałem troszkę czasu, w załączniku projekt Qt z moją metodą (każdy dowolny znak, który nie jest polskim znakiem jest traktowany jako dowolna litera). Słownik do pobrania można znaleźć tutaj.
Na moim dość starym laptopie (Intel Core 2 Duo 2GHz), wyniki daje w zasadzie natychmiast.
Jedynie bardzo długie hasła z jedną literą 'a' zajmują odczuwalny kawałek czasu, ale opóźnienie to wynika z przygotowania danych do wyświetlania (budowanie modelu), gdy danych jest bardzo dużo. Gdybym napisał swój model danych problem zniknie całkowicie.


Okazało się, że jest bug w QListView :) i dlatego performance bywa do bani (zawsze tworzy wszystkie elementy zamiast tylko te widoczne). W załączniku dałem nową wersje z modelem danych i zmieniłem QListView na QTableView i teraz zawsze działa szybko.
Oczyściłem jeszcze kod (literówki i pozostałości z poprzedniej wersji).
0
MarekR22 napisał(a):

Na moim dość starym laptopie (Intel Core 2 Duo 2GHz), wyniki daje w zasadzie natychmiast.

Co natychmiast?
Ma być milion wyszukań na sekundę dla losowych wzorców!

MarekR22 napisał(a):

Jedynie bardzo długie hasła z jedną literą 'a' zajmują odczuwalny kawałek czasu, ale opóźnienie to wynika z przygotowania danych do wyświetlania (budowanie modelu), gdy danych jest bardzo dużo. Gdybym napisał swój model danych problem zniknie całkowicie.

To fatalnie, bo w moim zastosowaniu będą najczęściej wzorce z niewielką liczbą liter - najczęściej 1, 2 i 3.

Program ma układać właśnie krzyżówki, więc wyszukujemy tu ciągle i do zmieniających się wzorców, aż do zapełnienia całej matrycy słowami.
W średniej krzyżówce, tj. o wymiarach z 15 x 15 jest około 50 słówek, i o długościach od 3 do 15, rzecz jasna.

3

Co natychmiast?
Ma być milion wyszukań na sekundę dla losowych wzorców!

To fatalnie, bo w moim zastosowaniu będą najczęściej wzorce z niewielką liczbą liter - najczęściej 1, 2 i 3.

Wydaje mi się żę ta rozmowa zmierza do niczego. Nie wspominając że Co natychniast?, Ma być (...)!, To fatalnie, nie jest zbyt miłą odpowiedzią dla kogoś kto chce pomóc (oczekujesz grzeczności, grzecznym bądź).

Program ma układać właśnie krzyżówki, więc wyszukujemy tu ciągle i do zmieniających się wzorców, aż do zapełnienia całej matrycy słowami.

Nie mogłeś tego napisać od razu (było jedynie niejasne wspomnienie o rozwiązywaniu krzyżówki)? Podejrzewam że od początku upatrzyłeś sobie jakieś bezsensowne rozwiązanie i próbujesz jak koń pod górę go zaimplementować.

Napisz dokładnie co chcesz zrobić i dopiero wtedy będzie można Ci pomóc. W nowym wątku, żeby ktoś kto trafi na to pytanie nie musiał czytać trzech stron postów z których nic nie wynika - dlatego też ten blokuję.

1 użytkowników online, w tym zalogowanych: 0, gości: 1