Optymalna sekwencja indukowania kubełków

Odpowiedz Nowy wątek
2011-08-24 16:19
3

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?


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Wibowit! Przegiąłeś! Za trudne jak widać - nawet na 4p ;) - szypxx 2011-08-24 20:51
Eee :P Może akurat jakiś kozak tu jest :D Tymczasem szukam forów na których jest szansa na odpowiedź na to pytanie. - Wibowit 2011-08-24 20:56
Ciekawe czy egon by coś pomógł :P - szypxx 2011-08-24 21:38
A on pomógł tu komuś kiedykolwiek? Co najwyżej może pomóc komuś popełnić samobójstwo. Oprócz szykan i przechwałek nie napisał tu wiele rzeczy. - Wibowit 2011-08-24 21:45
raczej zbyt specyficzne pytanie, żeby komuś chciało się wgłębiać. - 0x200x20 2011-08-24 22:27

Pozostało 580 znaków

2011-08-24 22:13
0

Trochę dodatkowych podpowiedzi nt działania Copy Transform:

W rzeczywistości mój program sortuje przesunięcia cykliczne, ale można go przerobić na sortowanie sufiksów poprzez dodatnie sentinela (tzn to angielskie słowo, nie znam polskiego odpowiednika) na koniec.

Objaśnię na przykładzie.

Mamy następujący ciąg:
abbababababbbab

Generujemy jego wszystkie przesunięcia cykliczne, będziemy je sortować:

abbababababbbab
babbababababbba
ababbababababbb
bababbababababb
bbababbabababab
bbbababbabababa
abbbababbababab
babbbababbababa
ababbbababbabab
bababbbababbaba
abababbbababbab
babababbbababba
ababababbbababb
bababababbbabab
bbababababbbaba

Zacznijmy od sortowania kubełka b_ba. Oto kubełek przed sortowaniem:

babbababababbba
bababbababababb
babbbababbababa
bababbbababbaba
babababbbababba
bababababbbabab

Po posortowaniu wygląda tak:

bababababbbabab
babababbbababba
bababbababababb
bababbbababbaba
babbababababbba
babbbababbababa

Następnie indukujemy kubełek b_bb z pozostałych kubełków dużego kubełka B_b. W naszym przypadku jest tylko jeden pozostały kubełek. Aby wyindukować kubełek b_bb wybieramy te podciągi, które zaczynają i kończą się na literę b:

bababababbbabab
bababbababababb

Z nich można już wyindukować początek kubełka b_bb:

bbababababbbaba
bbababbabababab

Widzimy, że dostaliśmy kolejny podciąg, który kończy się na b (i zaczyna się też na b). Indukujemy więc następną pozycję (tak jak poprzednio, bierzemy jego przesunięcie o jedną pozycję w lewo) - dodany element jest na końcu:

bbababababbbaba
bbababbabababab
bbbababbabababa

Teraz mamy już gotowy kubełek B_b:

bababababbbabab
babababbbababba
bababbababababb
bababbbababbaba
babbababababbba
babbbababbababa
bbababababbbaba
bbababbabababab
bbbababbabababa

Możemy więc teraz indukować kubełek b_ab. Potrzebne są nam do tego podciągi, które zaczynają się na b i kończą na a:

babababbbababba
bababbbababbaba
babbababababbba
babbbababbababa
bbababababbbaba
bbbababbabababa

Indukujemy z nich zawartość kubełka b_ab w "tradycyjny" sposób:

ababababbbababb
abababbbababbab
ababbababababbb
ababbbababbabab
abbababababbbab
abbbababbababab

Teraz mamy już wszystko posortowane, bo kubełek b_aa był pusty.

Uwaga co do indukowania kubełków typu b_cc:
Jak podałem wcześniej, kubełki typu b_cc można wyindukować z kubełków {b_ca, b_cb, b_cd, ..., b_cz}. Należy jednak pamiętać o odpowiednim porządku: kubełki {b_ca, b_cb} (tzn te które mają drugą literę mniejszą leksykograficznie niż c) skanujemy od początku i wyindukowane podciągi kładziemy na początek b_cc. Natomiast kubełki {b_cd, ..., b_cz} skanujemy od końca i wyindukowane podciągi kładziemy na koniec b_cc.

Generalnie mój problem nie polega jednak na tym, jak indukować kubełki (bo to rozumiem), tylko jak obliczyć optymalną sekwencję indukowania, tak aby sortować jak najmniej podciągów bezpośrednio.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Chodzi o ten -> http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform <- algorytm? (PS. sentitel tłumaczy się na strażnik) (PPS. gdzie są nietuzinkowe tematy kiedy ich potrzeba? :] ) - msm 2011-08-24 23:00
Generalnie do tego może służyć i zwykle do tego się sortowania blokowego używa. Strona na Wiki opisuje temat strasznie pobieżnie, nie ma opisów, ani tym bardziej analiz, metod sortowania blokowego. Sentinel to może i strażnik. W każdym razie to unikalna wartość, dodatkowy symbol w alfabecie (zwykle najniższy lub najwyższy leksykograficznie), który występuje tylko na końcu ciągu. - Wibowit 2011-08-24 23:12

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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