Szybkość działania generatora krzyżówek panoramicznych.

Niedawno bawiłem się wersją demo generatora krzyżówek panoramicznych i zdziwiła mnie szybkość układania słów. Siatkę 11x16 układa w sekundę, a może mniej. Prawie nie znam się na programowaniu (tzn. jakieś podstawy podstaw JAVA), ale taka wydajność wydawała mi się niemożliwa do uzyskania. Taka krzyżówka ma wiele ściśle powiązanych ze sobą słów, więc myślałem, że ilość działań, które trzeba wykonać musi zająć dużo więcej czasu. Pytanie, czy tak krótki czas wydaje Wam się normalny, czy programista musiał znaleźć jakieś niezwykłe rozwiązania?

Chodzi o Crossword Compiler.

To jest poważny program, napisamy przez poważych ludzi; musi być szybki :)

Może Cię zaskoczę, ale program stworzył jeden gość, w dodatku nie będący zawodowym programistą. Nauczył się programować, bo uważał, że dotychczasowe programy są słabe i chciał napisać lepszy. Programowanie nadal nie jest jego głównym zajęciem. Natomiast masz rację, że "napisany przez poważnych ludzi", bo gość jest astrofizykiem.

masz chyba błędne pojęcie o komputerach - procesory wykonują kilka miliardów operacji na sekundę. Sekunda to bardzo dużo

Zgaduje, że zapewne ma zestaw indeksów gdzie słowa są poindeksowane po każdej pozycji w słowie osobno i możliwość szybkiego liczenia przecięć indeksów. Indeksy oczywiście mieszczą się całkowicie w pamięci bo słów masz zapewne raptem kilkanaście tysięcy. W tej sposób wyszukanie listy słów spełniających np. warunek pierwsza B, trzecia O, a przedostatnia I powinno trwać ułamki milisekund.

Załóżmy że mamy indeks bitmapowy dla każdej litery i 10k słów, a rozważamy słowa maks 10-literowe. Daje nam to 10 tys bitów na zaindeksowanie każdej pozycji x litera (ustawiany bit 1 jeśli słowo zawiera litere na danej pozycji lub 0 jeśli nie zawiera). Każda litera i pozycja ma osobny indeks, ciągły w pamięci, zajmujący nieco ponad 1kB. Współczesny procesor umie robić operacje logiczne na 256 bitach równocześnie, w jednym cyklu na jednym rdzeniu. Czyli na przeskanowanie całego indeksu dla jednej litery i jednej pozycji w słowie potrzebujesz raptem 40 cykli, a zapewne nie musisz skanować całego a tylko tyle aby znaleźć jakieś jedynki (dopasowanie słowa). Przecięcie indeksów robisz instrukcja vpand.

Zakładając pesymistyczne że musimy szukać słowa mając określonych 9 liter (szukamy tej jednej brakującej dziesiątej literki), potrzebujemy 360 cykli CPU. To poniżej jednej mikrosekundy. Cały indeks dla wszystkich liter i pozycji powinien się zmieścić w cache L2 (30 liter x 10 pozycji x bitmapa 1,2 kB - ok 400 kB) a transfery z L2 są na poziomie dziesiątek GBps.

Krzyżówka na słów nie więcej niż 100. Nawet jeśli trzeba jakieś nawroty robić bo trafimy na sytuację gdzie nie da się umieścić słowa, to sekunda wydaje się aż za dużo czasu. :).

@Krolik: Bardzo dziękuję za wyjaśnienie. Próbuję (nieintensywnie :)) uczyć się JAVA, traktując to jako rozrywkę umysłową. Aby uczyć się na jakimś przykładzie, tworzyłem sobie właśnie generator krzyżówek panoramicznych, oczywiście jak na moje skromne możliwości. Zaczął układać mi krzyżówkę w kilka minut i stąd zdziwienie, że możliwe jest ułożenie w sekundę. No ale zamiast z indeksu bitmapowego, o którym wcześniej nie słyszałem, korzystałem z wyrażeń regularnych i bazy słów w pliku tekstowym.:)