Tworzę współbieżny algorytm sortowania blokowego, tzn coś w stylu algorytmu stosowanego w bzip2. Przy sortowaniu blokowym (block-sorting) można wyindukować posortowany porządek pewnych podciągów z posortowanego porządku innych podciągów, korzystając z faktu, że sortowanie blokowe sortuje podciągi tego samego ciągu bazowego.
W moim programie używam Copy Transform, wymyślonego przez Juliana Sewarda, autora bzip2. Opiszę jak działa ten algorytm w przypadku sufiksów, najpierw trochę objaśnię sposób zapisu:
B_a to duży kubełek, zawierający wszystkie sufiksy zaczynające się na literę a,
b_ab to mały kubełek, zawierający wszystkie sufiksy zaczynające się od liter "ab"
Duży kubełek B_a składa się z kubełków {b_aa, b_ab, ..., b_az}
Mając posortowany kubełek B_d mogę z niego wyindukować posortowany porządek kubełków {b_ad, b_bd, b_cd, b_ed, ..., b_zd} w zaledwie jednym przejściu po tym dużym kubełku. Tak jest w oryginalnym Copy Transform. Później Seward zorientował się, że kubełek b_dd można wyindukować z kubełków {b_da, b_db, b_dc, d_de, ..., d_dz} (co widocznie przyspieszyło jego bzipa na niektórych danych wejściowych).
Moim problemem jest obliczenie optymalnej sekwencji indukowania kubełków, tzn kubełki mają różne rozmiary, a ja chcę zminimalizować łączny rozmiar kubełków, które muszę posortować za pomocą porównań, aby wyindukować resztę.
Aktualnie wydajność wygląda tak:
Copy ascending Copy simple-ratio Improved two-stage
chr22.dna 35.56 31.67 26.68
etext99 49.75 38.64 31.10
gcc-3.0.tar 42.63 33.46 26.77
howto 45.51 36.13 28.55
jdk13c 47.63 35.05 30.06
linux-2.4.5.tar 44.12 35.20 26.80
rctail96 49.00 36.57 30.28
rfc 40.17 32.28 25.83
sprot34.dat 43.14 38.07 29.26
w3c2 47.46 36.22 29.90
mean 44.50 35.33 28.52
Gdzie:
- Copy ascending, to normalna wersja Copy Transform, gdzie sortuje się kubełki od najmniejszego do największego,
- Copy simple-ratio, to Copy Transform z moją heurezą do obliczania sekwencji indukowania,
- Improved two-stage to inny algorytm indukowania posortowanego porządku, ale nie ma pomysłu jak by go sensownie zrównoleglić,
Liczby oznaczają procent sufiksów, które trzeba posortować, aby móc wyindukować resztę. Jak widać moja heureza znacznie poprawia efektywność Copy Transform, ale i tak daleko jej do ITS. (Nota bene: ITS jest opisany w dokumencie: http://homepage3.nifty.com/wpage/software/itssort.txt ).
Ma ktoś pomysł czego użyć, aby uzyskać optymalną sekwencję indukowania?