Witam.
Mam napisać program, który wyszukuje minimalny okres słowa. Zrobiłem to za pomocą KMP i MP, ale wciąż mam pewien problem, gdyż sprawdzarka która sprawdza poprawność zadania (zaznaczam, że nie chodzi o spoja) oznajmia iż program przekracza limit pamięci. I tu mam pytanie do was przyjaciele: czy da się to zrobić pomijając użycie tablicy prefikso-sufiksów?
Myślę, że to pozwoliłoby zjechać na pamięci.
Proszę o jakieś sugestie i pozdrawiam.
Dzięki :)
- Rejestracja:około 12 lat
- Ostatnio:około 10 lat
- Postów:161
0
- Rejestracja:około 12 lat
- Ostatnio:około 10 lat
- Postów:161
0
W największym teście jest limit 55MB.
A co do danych to: http://ideone.com/dRgAgl tutaj są przykładowe.
- Rejestracja:prawie 20 lat
- Ostatnio:około 3 godziny
1
Wstępnie rozwiązanie może być takie:
- ciągu pomocniczego nigdzie nie zapisujesz, generujesz od razu ciąg główny,
- ciąg główny jest ciągiem zer i jedynek, a te możesz bezproblemowo zapakować do bajtów, dzięki czemu zamiast 16 mebagajtów używasz dwóch,
- maksymalna długość ciągu jest mniejsza niż 2^24, więc teoretycznie mógłbyś użyć 24-bitowego unsigned inta + atrybutów packed itd i tego używać, w sensie:
pragma<packed coś tam>
struct {
unsigned int wartość : 24;
} mój_int;
- dzięki powyższemu trikowi tablica KMP zmniejsza się do 16 mln * 24 bity = 48 megabajtów,
- razem daje to 50 megabajtów i dzięki temu mieścisz się w limicie,
- pakowanie cyfr do bitów też możesz zrobić bit fieldami z C++a dzięki czemu kod będzie elegancki,
Jak jesteś hardkorem to możesz spróbować z algorytmem Galila-Seiferasa, który nie wymaga dodatkowej tablicy, a którą wymaga algorytm KMP.
edytowany 5x, ostatnio: Wibowit
- Rejestracja:prawie 20 lat
- Ostatnio:około 3 godziny
0
Prawdopodobnie to pakowanie intów powoduje problem wydajnościowy. Spróbuj zrobić pewną hybrydę:
- pierwsze np 2^20 elementów trzymaj jako zwykłe niespakowane inty,
- resztę trzymaj jako spakowane,
Poza tym: o ile przekracza?
Możesz jeszcze spróbować przyspieszyć generowanie ciągu głównego poprzez wykorzystanie: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556 jeżeli dzielenie jest wąskim gardłem przy liczeniu.
Prościej jest to opisane w http://agner.org/optimize/optimizing_assembly.pdf w paragrafie: Repeated integer division by the same value
edytowany 3x, ostatnio: Wibowit
- Rejestracja:około 12 lat
- Ostatnio:około 10 lat
- Postów:161
0
Ale czasy przekraczało i bez tego pakowania. Tak że raczej to nie to. Możliwe że to przez vector? Używam vectora zamiast zwykłych tablic (bo potrzebuję implementacji bitów a ponoć vector jest wydajniejszy do takich operacji). Jeśli chcesz to mogę ci pokazać kod na priva.
- Rejestracja:prawie 20 lat
- Ostatnio:około 3 godziny
0
Jeśli vector nic nie ułatwia w zadaniu na algorytmy to nie używaj wektora. W tym przypadku polecam użycie zwykłej tablicy, ale z dodatkami typu packed pragma coś tam bit field o których już tu wspomniałem :)
Przekracza czasy? No to może przez to liczenie ciągu głównego. Tam jest dzielenie modulo które może spowalniać mocno cały proces. Ten trik z optymalizacją który podałem powinien polepszyć czas, ale z drugiej strony raczej żaden ćwiczeniowiec/ wykładowca nie powinien takich rzeczy wymagać.