Najlepszy algorytm sortowania ciągu częściowo posortowanego
resident.evilWYTNIJTO@poczta.onet.pl - 24-12-2006 01:16
Najlepszy algorytm sortowania ciągu częściowo posortowanego
Witam
Mój problem tyczy się programowania rozproszonego w którym P procesów
sortuje n-elementowy ciąg losowych liczb. Każdy z procesów otrzymuje
do posortowania n/P elementów (ponieważ czasem nie można podzielić
ciągu tak, aby każdy proces dostał tą sama liczbę elementów podział
jest realizowany tak, że:
ilosc=dlugosc_tablicy/ilosc_procesow;
reszta=dlugosc_tablicy%ilosc_procesow;
Każdy z procesów dostaje do posortowania część tablicy o wielkości
"ilosc" natomiast jeden z procesów tablice o wilekości "ilosc+reszta"
Podciągi te muszą być posortowane metodą QuickSort. Po posortowaniu
podciągi łączone są za pomocą scalania, czyli spośród wszystkich
podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
czym wpisuje go do nowej tablicy zwiększając indeks w tablicy z której
wziąłem element minimalny (i tak w kółko)... wszystko to pięknie działa,
ale moje chciałbym agregacje tablicy bardziej usprawnić.
Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
tych posortowanych podciągów ?
Mam nadzieję, że uda się komuś przeczytać ten post do końca ;)
Dziękuje oczywiście za pomoc z moim problemem.
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
Brodacz 100 - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl napisał(a):
> Witam
>
> Mój problem tyczy się programowania rozproszonego w którym P procesów
> sortuje n-elementowy ciąg losowych liczb. Każdy z procesów otrzymuje
> do posortowania n/P elementów (ponieważ czasem nie można podzielić
> ciągu tak, aby każdy proces dostał tą sama liczbę elementów podział
> jest realizowany tak, że:
>
> ilosc=dlugosc_tablicy/ilosc_procesow;
> reszta=dlugosc_tablicy%ilosc_procesow;
>
> Każdy z procesów dostaje do posortowania część tablicy o wielkości
> "ilosc" natomiast jeden z procesów tablice o wilekości "ilosc+reszta"
>
> Podciągi te muszą być posortowane metodą QuickSort. Po posortowaniu
> podciągi łączone są za pomocą scalania, czyli spośród wszystkich
> podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
> czym wpisuje go do nowej tablicy zwiększając indeks w tablicy z której
> wziąłem element minimalny (i tak w kółko)... wszystko to pięknie działa,
> ale moje chciałbym agregacje tablicy bardziej usprawnić.
>
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
>
> Mam nadzieję, że uda się komuś przeczytać ten post do końca ;)
> Dziękuje oczywiście za pomoc z moim problemem.
>
Ciekawe rzeczy opisujesz.
Wszystko zależy od ilości danych, czyli elementów do posortowania.
Jak się tym bawisz, to zmierz od ilu elementów q-sort działa szybciej
od jakiegoś sortowania bombelkowego. Kiedyś to zmierzylem i się
zdziwiłem, bo ilość elementów musiała być znacznie(!) większa niż
się spodziewałem.
W przypadku zastosowania wielu procesorów, narzut liniowy jest jeszcze
większy, samo utworzenie wątku trwa być może tyle, co posortowanie
kilkudziesięciu tysięcy elemnetów :)
Nie jestem znawcą od sortowania, ale ja do sortowanai na wielu
procesorach zastosował bym sortowanie przez złączanie, przy czym
rekurencyjne wywołania tej procedury tworzyłbym w nowych wątkach.
Należy wtedy oczywiście kontrolować ilość utworzonych wątków, gdyż
jak pisałem wcześniej, narzut na ich tworzenie jest ogromny.
Zastosowanie sekcji krytycznych do zliczania ilości wątków powoduje
też ogromny narzut, szczególnie pod windows, częste wywołania
EnterCriticalSection potrafią zarżnąć cały system. Możę należałoby
więc napisać wersję wielowątkową, a jak wywołania rekurencyjne dojdą
na głębokość N to stosować wersję jednowątkową? Do tego wszystkiego
należy wymienić poważną wadę meargesort, czyli to że on potrzebuje O(N)
dodatkowej pamięci RAM. Takie zabawy opłaca się stosować dla bardzo
dużej ilości danych (milard?), a jeśli zabraknie RAM i dojdzie do
stronicowania to chyba lepiej posortować qsortem na jednym wątku :)
Do tego wszystkiego dochodzi problem danych częściwo posortowanych.
Używam tego słowa bardziej ogólniej niż Ty użyłeś, zwróć uwagę, że
np. dla ciągu prawie posortowanego (np. posortowany w którym
losowo przestawiony 1% elementów) proste sortowanie bombelkowe
zadziała znacznie szybciej niż q-sort, mergesort, itd. Ktoś kiedyś
wspominał, nie wiem czy można w to wierzyć, że są algorytmy do
rozpoznawania jakim algorytmem należy posortować dane :)
Co do problemu złączania N-posortowanych pod-ciągów, to w przypadku
merge-sort go nie ma, gdyż każdy wątek złącza dwa "swoje" pod-ciągi.
Są wydajne wielowątkowe algorytmy wyboru maksymalnego(minimalnego)
elementu z n-elementów. Nawet są wydajne algorytmy do wyboru n-tego
co dowielkości elementu, niekoniecznie max-go czy min-go. Jednak
idę o zakład, że opłaca się zastosować więcej niż jeden wątek, gdy
tych elementów jest powyżej 50tys. Ogólnie chyba chodzi zrównoleglenie
metod dziel i zwyciężaj, np. tworzysz dwa wątki i każdy wyszukuje
maksimim z połowy tablicy.
Pozdrawiam
Mariusz
Brodacz 100 - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl napisał(a):
> Witam
>
> Mój problem tyczy się programowania rozproszonego w którym P procesów
> sortuje n-elementowy ciąg losowych liczb. Każdy z procesów otrzymuje
> do posortowania n/P elementów (ponieważ czasem nie można podzielić
> ciągu tak, aby każdy proces dostał tą sama liczbę elementów podział
> jest realizowany tak, że:
>
> ilosc=dlugosc_tablicy/ilosc_procesow;
> reszta=dlugosc_tablicy%ilosc_procesow;
>
> Każdy z procesów dostaje do posortowania część tablicy o wielkości
> "ilosc" natomiast jeden z procesów tablice o wilekości "ilosc+reszta"
>
> Podciągi te muszą być posortowane metodą QuickSort. Po posortowaniu
> podciągi łączone są za pomocą scalania, czyli spośród wszystkich
> podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
> czym wpisuje go do nowej tablicy zwiększając indeks w tablicy z której
> wziąłem element minimalny (i tak w kółko)... wszystko to pięknie działa,
> ale moje chciałbym agregacje tablicy bardziej usprawnić.
>
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
>
> Mam nadzieję, że uda się komuś przeczytać ten post do końca ;)
> Dziękuje oczywiście za pomoc z moim problemem.
>
Ciekawe rzeczy opisujesz.
Wszystko zależy od ilości danych, czyli elementów do posortowania.
Jak się tym bawisz, to zmierz od ilu elementów q-sort działa szybciej
od jakiegoś sortowania bombelkowego. Kiedyś to zmierzylem i się
zdziwiłem, bo ilość elementów musiała być znacznie(!) większa niż
się spodziewałem.
W przypadku zastosowania wielu procesorów, narzut liniowy jest jeszcze
większy, samo utworzenie wątku trwa być może tyle, co posortowanie
kilkudziesięciu tysięcy elemnetów :)
Nie jestem znawcą od sortowania, ale ja do sortowanai na wielu
procesorach zastosował bym sortowanie przez złączanie, przy czym
rekurencyjne wywołania tej procedury tworzyłbym w nowych wątkach.
Należy wtedy oczywiście kontrolować ilość utworzonych wątków, gdyż
jak pisałem wcześniej, narzut na ich tworzenie jest ogromny.
Zastosowanie sekcji krytycznych do zliczania ilości wątków powoduje
też ogromny narzut, szczególnie pod windows, częste wywołania
EnterCriticalSection potrafią zarżnąć cały system. Możę należałoby
więc napisać wersję wielowątkową, a jak wywołania rekurencyjne dojdą
na głębokość N to stosować wersję jednowątkową? Do tego wszystkiego
należy wymienić poważną wadę meargesort, czyli to że on potrzebuje O(N)
dodatkowej pamięci RAM. Takie zabawy opłaca się stosować dla bardzo
dużej ilości danych (milard?), a jeśli zabraknie RAM i dojdzie do
stronicowania to chyba lepiej posortować qsortem na jednym wątku :)
Do tego wszystkiego dochodzi problem danych częściwo posortowanych.
Używam tego słowa bardziej ogólniej niż Ty użyłeś, zwróć uwagę, że
np. dla ciągu prawie posortowanego (np. posortowany w którym
losowo przestawiony 1% elementów) proste sortowanie bombelkowe
zadziała znacznie szybciej niż q-sort, mergesort, itd. Ktoś kiedyś
wspominał, nie wiem czy można w to wierzyć, że są algorytmy do
rozpoznawania jakim algorytmem należy posortować dane :)
Co do problemu złączania N-posortowanych pod-ciągów, to w przypadku
merge-sort go nie ma, gdyż każdy wątek złącza dwa "swoje" pod-ciągi.
Są wydajne wielowątkowe algorytmy wyboru maksymalnego(minimalnego)
elementu z n-elementów. Nawet są wydajne algorytmy do wyboru n-tego
co dowielkości elementu, niekoniecznie max-go czy min-go. Jednak
idę o zakład, że opłaca się zastosować więcej niż jeden wątek, gdy
tych elementów jest powyżej 50tys. Ogólnie chyba chodzi zrównoleglenie
metod dziel i zwyciężaj, np. tworzysz dwa wątki i każdy wyszukuje
maksimim z połowy tablicy.
Pozdrawiam
Mariusz
Jakub Lisowski - 24-12-2006 01:16
Dnia 6 Nov 2006 20:42:47 +0100, resident.evilWYTNIJTO@poczta.onet.pl <resident.evilWYTNIJTO@poczta.onet.pl>
w <5cd1.00000130.454f9036@newsgate.onet.pl> napisał:
> Witam
>
> Mój problem tyczy się programowania rozproszonego w którym P procesów
> sortuje n-elementowy ciąg losowych liczb. Każdy z procesów otrzymuje
> do posortowania n/P elementów (ponieważ czasem nie można podzielić
> ciągu tak, aby każdy proces dostał tą sama liczbę elementów podział
> jest realizowany tak, że:
>
> ilosc=dlugosc_tablicy/ilosc_procesow;
> reszta=dlugosc_tablicy%ilosc_procesow;
>
> Każdy z procesów dostaje do posortowania część tablicy o wielkości
> "ilosc" natomiast jeden z procesów tablice o wilekości "ilosc+reszta"
>
> Podciągi te muszą być posortowane metodą QuickSort. Po posortowaniu
Dlaczego akurat QS?
> podciągi łączone są za pomocą scalania, czyli spośród wszystkich
> podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
Chyba taki sobie pomysł. IMO lepiej zrobić standardowe łączenie:
miałeś P procesorów i one posortowały p przedziałów.
Teraz masz P/2 wątków, i każdy z nich scala 2 przedziały poprzednio
posortowane, i tak do momentu, gdy zostanie jeden proces, który scali 2
posortowane ciągi.
[ ... ]
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
Jak rozwiązujesz problem z nadpisywaniem elementów tablicy, na przykład:
[[3,4],[1,2]]
Bierzesz 3 i 1, 1 wstawiasz w miejsce 3, co robisz z 3, bo potem
bierzesz z kolei 2, i ją musisz wstawić w miejsce 4, z 3 i 4 musisz
coś zrobić.
ja czyli jakub
--
Z zaparkowanego Forda Fulkersona wysiedli generał Grant i porucznik
Revoke.
Jakub Lisowski - 24-12-2006 01:16
Dnia 6 Nov 2006 20:42:47 +0100, resident.evilWYTNIJTO@poczta.onet.pl <resident.evilWYTNIJTO@poczta.onet.pl>
w <5cd1.00000130.454f9036@newsgate.onet.pl> napisał:
> Witam
>
> Mój problem tyczy się programowania rozproszonego w którym P procesów
> sortuje n-elementowy ciąg losowych liczb. Każdy z procesów otrzymuje
> do posortowania n/P elementów (ponieważ czasem nie można podzielić
> ciągu tak, aby każdy proces dostał tą sama liczbę elementów podział
> jest realizowany tak, że:
>
> ilosc=dlugosc_tablicy/ilosc_procesow;
> reszta=dlugosc_tablicy%ilosc_procesow;
>
> Każdy z procesów dostaje do posortowania część tablicy o wielkości
> "ilosc" natomiast jeden z procesów tablice o wilekości "ilosc+reszta"
>
> Podciągi te muszą być posortowane metodą QuickSort. Po posortowaniu
Dlaczego akurat QS?
> podciągi łączone są za pomocą scalania, czyli spośród wszystkich
> podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
Chyba taki sobie pomysł. IMO lepiej zrobić standardowe łączenie:
miałeś P procesorów i one posortowały p przedziałów.
Teraz masz P/2 wątków, i każdy z nich scala 2 przedziały poprzednio
posortowane, i tak do momentu, gdy zostanie jeden proces, który scali 2
posortowane ciągi.
[ ... ]
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
Jak rozwiązujesz problem z nadpisywaniem elementów tablicy, na przykład:
[[3,4],[1,2]]
Bierzesz 3 i 1, 1 wstawiasz w miejsce 3, co robisz z 3, bo potem
bierzesz z kolei 2, i ją musisz wstawić w miejsce 4, z 3 i 4 musisz
coś zrobić.
ja czyli jakub
--
Z zaparkowanego Forda Fulkersona wysiedli generał Grant i porucznik
Revoke.
resident.evilWYTNIJTO@poczta.onet.pl - 24-12-2006 01:16
> Dlaczego akurat QS?
Dostałem do rozwiązania problem w którym musiałem użyć QuickSort do sortowania.
Równie dobrze mógł być to dowolny inny algorytm sortowania.
Ale, że za pomocą scalania posortowanych podciągów dość łatwo rozwiązałem
problem agregacji posortowanych tablic w jedną dużą, to utrudniono mi zadanie.
Teraz muszę znaleźć algorytm łączenia podciągów posortowanych w jeden ciąg
posortowany lub sortowania tablicy częściowo posortowanej, która składa się
z tych kilku tablic posortowanych przez podciągi - ale taki, który jest szybszy
od scalania, które zastosowałem ;)
> Jak rozwiązujesz problem z nadpisywaniem elementów tablicy, na przykład:
> [[3,4],[1,2]]
> Bierzesz 3 i 1, 1 wstawiasz w miejsce 3, co robisz z 3, bo potem
> bierzesz z kolei 2, i ją musisz wstawić w miejsce 4, z 3 i 4 musisz
> coś zrobić.
tablica1 [3,4] - indeks1=0
tablica2 [1,2] - indeks2=0
Sprawdzam wartości o indeksie 1 i 2 =0 z tablicy1 i tablicy2 - wartość "1" jest
najmniejsza, zatem w tablicy wynikowej wpisuje "1" i zwiększam indeks2 o 1.
W kolejnej iteracji biorę do porównania wartości o indeksie1=0 i indeksie2=1
(z odpowiednich tablic), czyli "2" i "3" - wartość "2" jest najmniejsza, zatem
do tablicy wynikowej wpisuje "2". Oczywiście jest ograniczenie, które powoduje, że
jeżeli danej tablicy wziąłem już wszystkie wartości, to w kolejnej iteracji nie jest
ona już brana pod uwagę ;)
I jeszcze jedno wyjaśnienie dla jasności - pisząc o podprocesach mam na myśli
programy uruchomione na różnych komputerach, do których fragmenty tablicy są
wysyłane za pomocą sieci. A ponieważ opóźnienia na sieci są większe niż czas
potrzebny
procesorowi na wykonanie algorytmu, tak więc optymalnym rozwiązaniem tego
problemy byłby algorytm, który wykonuje jak najmniej przesyłów danych (wymian
tablicami) między podprocesami - pytanie - jaki jest algorytm zadziała szybciej
niż zaproponowany przez mnie, gdy weźmiemy pod uwagę opóźnienia powstałe
podczas przesyłania danych do sieci?
W moim pomyśle tak na prawdę dane przesyłane są dwa razy:
1) gdy program główny wysyła programom po sieci fragmenty tablicy do sortowania
(i tak będzie w każdym algorytmie ;) )
2) gdy programy wysyłają posortowane tablice do programu głównego
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
resident.evilWYTNIJTO@poczta.onet.pl - 24-12-2006 01:16
> Dlaczego akurat QS?
Dostałem do rozwiązania problem w którym musiałem użyć QuickSort do sortowania.
Równie dobrze mógł być to dowolny inny algorytm sortowania.
Ale, że za pomocą scalania posortowanych podciągów dość łatwo rozwiązałem
problem agregacji posortowanych tablic w jedną dużą, to utrudniono mi zadanie.
Teraz muszę znaleźć algorytm łączenia podciągów posortowanych w jeden ciąg
posortowany lub sortowania tablicy częściowo posortowanej, która składa się
z tych kilku tablic posortowanych przez podciągi - ale taki, który jest szybszy
od scalania, które zastosowałem ;)
> Jak rozwiązujesz problem z nadpisywaniem elementów tablicy, na przykład:
> [[3,4],[1,2]]
> Bierzesz 3 i 1, 1 wstawiasz w miejsce 3, co robisz z 3, bo potem
> bierzesz z kolei 2, i ją musisz wstawić w miejsce 4, z 3 i 4 musisz
> coś zrobić.
tablica1 [3,4] - indeks1=0
tablica2 [1,2] - indeks2=0
Sprawdzam wartości o indeksie 1 i 2 =0 z tablicy1 i tablicy2 - wartość "1" jest
najmniejsza, zatem w tablicy wynikowej wpisuje "1" i zwiększam indeks2 o 1.
W kolejnej iteracji biorę do porównania wartości o indeksie1=0 i indeksie2=1
(z odpowiednich tablic), czyli "2" i "3" - wartość "2" jest najmniejsza, zatem
do tablicy wynikowej wpisuje "2". Oczywiście jest ograniczenie, które powoduje, że
jeżeli danej tablicy wziąłem już wszystkie wartości, to w kolejnej iteracji nie jest
ona już brana pod uwagę ;)
I jeszcze jedno wyjaśnienie dla jasności - pisząc o podprocesach mam na myśli
programy uruchomione na różnych komputerach, do których fragmenty tablicy są
wysyłane za pomocą sieci. A ponieważ opóźnienia na sieci są większe niż czas
potrzebny
procesorowi na wykonanie algorytmu, tak więc optymalnym rozwiązaniem tego
problemy byłby algorytm, który wykonuje jak najmniej przesyłów danych (wymian
tablicami) między podprocesami - pytanie - jaki jest algorytm zadziała szybciej
niż zaproponowany przez mnie, gdy weźmiemy pod uwagę opóźnienia powstałe
podczas przesyłania danych do sieci?
W moim pomyśle tak na prawdę dane przesyłane są dwa razy:
1) gdy program główny wysyła programom po sieci fragmenty tablicy do sortowania
(i tak będzie w każdym algorytmie ;) )
2) gdy programy wysyłają posortowane tablice do programu głównego
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
Marcin Stefaniak - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl napisał(a):
> [CIACH] Po posortowaniu
> podciągi łączone są za pomocą scalania, czyli spośród wszystkich
> podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
> czym wpisuje go do nowej tablicy zwiększając indeks w tablicy z której
> wziąłem element minimalny (i tak w kółko)... wszystko to pięknie działa,
> ale moje chciałbym agregacje tablicy bardziej usprawnić.
>
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
Dobrze robisz. Kwestia, jak spośród tych p elementów wybierasz najmniejszy?
Jeśli po prostu, używając O(p) operacji, no to niefajnie. Użyjesz kolejki
priorytetowej, to operacji tych bedzie tylko O(lg p). W szczególności dla n=p
ten algorytm "scalania" zamienia się w heapsort (a nie selection-sort)
No i druga sprawa - skoro masz tyle procesorów, to tą operację agregacji /
scalania można by też rozproszyć jakoś pewnie...
Marcin Stefaniak
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
Marcin Stefaniak - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl napisał(a):
> [CIACH] Po posortowaniu
> podciągi łączone są za pomocą scalania, czyli spośród wszystkich
> podciągów biorę pierwsze elementy i wybieram z nich najmniejszy, po
> czym wpisuje go do nowej tablicy zwiększając indeks w tablicy z której
> wziąłem element minimalny (i tak w kółko)... wszystko to pięknie działa,
> ale moje chciałbym agregacje tablicy bardziej usprawnić.
>
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
Dobrze robisz. Kwestia, jak spośród tych p elementów wybierasz najmniejszy?
Jeśli po prostu, używając O(p) operacji, no to niefajnie. Użyjesz kolejki
priorytetowej, to operacji tych bedzie tylko O(lg p). W szczególności dla n=p
ten algorytm "scalania" zamienia się w heapsort (a nie selection-sort)
No i druga sprawa - skoro masz tyle procesorów, to tą operację agregacji /
scalania można by też rozproszyć jakoś pewnie...
Marcin Stefaniak
--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/
resident.evilWYTNIJTO@poczta.onet.pl - 24-12-2006 01:16
> Dobrze robisz. Kwestia, jak spośród tych p elementów wybierasz najmniejszy?
> Jeśli po prostu, używając O(p) operacji, no to niefajnie. Użyjesz kolejki
> priorytetowej, to operacji tych bedzie tylko O(lg p). W szczególności dla n=p
> ten algorytm "scalania" zamienia się w heapsort (a nie selection-sort)
Każda z podtablic posiada licznik, wskazujący na element tablicy, który aktualnie
ma być porównywany z pozostałymi elementami z innych tablic. W wyniku takiego
porównania spośród najmniejszych wartości z wszystkich tablic wybierana jest
wartość minimalna, a licznik dla tej tablicy z której pochodzi wartość minimalna
jest inkrementowany, tak aby wskazywał na kolejny element w tablicy. Wartość
minimalna jest wpisywana do tablicy wynikowej. W ten sposób dla N-elementów
(N-suma elementów ze wszystkich podtatblic) po N operacjach wyboru wartości
minimalnej otrzymuje tablicę posortowaną.
Przykład:
A[1,2] licznikA=0, B[3,4] licznikB=0
1) wybieram minimum spośród A[0]=1 i B[0]=3 => czyli 1
2) zwiększam licznikA => licznikA=1
3) na pozycje 0 tablicy wynikowej wpisuje "1"
3) wybieram minimum spośród A[1]=2 i B[0]=3 => czyli 2
4) zwiekszam licznikA => licznikA=2 (ponieważ licznikA=ilość_elementów_tablicy_A
ta tablica w kolejnych krokach nie będzie brana pod uwagę)
5) na pozycje 1 tablicy wynikowej wpisuje "2"
6) etc.
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
resident.evilWYTNIJTO@poczta.onet.pl - 24-12-2006 01:16
> Dobrze robisz. Kwestia, jak spośród tych p elementów wybierasz najmniejszy?
> Jeśli po prostu, używając O(p) operacji, no to niefajnie. Użyjesz kolejki
> priorytetowej, to operacji tych bedzie tylko O(lg p). W szczególności dla n=p
> ten algorytm "scalania" zamienia się w heapsort (a nie selection-sort)
Każda z podtablic posiada licznik, wskazujący na element tablicy, który aktualnie
ma być porównywany z pozostałymi elementami z innych tablic. W wyniku takiego
porównania spośród najmniejszych wartości z wszystkich tablic wybierana jest
wartość minimalna, a licznik dla tej tablicy z której pochodzi wartość minimalna
jest inkrementowany, tak aby wskazywał na kolejny element w tablicy. Wartość
minimalna jest wpisywana do tablicy wynikowej. W ten sposób dla N-elementów
(N-suma elementów ze wszystkich podtatblic) po N operacjach wyboru wartości
minimalnej otrzymuje tablicę posortowaną.
Przykład:
A[1,2] licznikA=0, B[3,4] licznikB=0
1) wybieram minimum spośród A[0]=1 i B[0]=3 => czyli 1
2) zwiększam licznikA => licznikA=1
3) na pozycje 0 tablicy wynikowej wpisuje "1"
3) wybieram minimum spośród A[1]=2 i B[0]=3 => czyli 2
4) zwiekszam licznikA => licznikA=2 (ponieważ licznikA=ilość_elementów_tablicy_A
ta tablica w kolejnych krokach nie będzie brana pod uwagę)
5) na pozycje 1 tablicy wynikowej wpisuje "2"
6) etc.
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
karbi - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl napisał(a):
> Ale, że za pomocą scalania posortowanych podciągów dość łatwo rozwiązałem
> problem agregacji posortowanych tablic w jedną dużą, to utrudniono mi zadanie.
> Teraz muszę znaleźć algorytm łączenia podciągów posortowanych w jeden ciąg
> posortowany lub sortowania tablicy częściowo posortowanej, która składa się
> z tych kilku tablic posortowanych przez podciągi - ale taki, który jest szybszy
> od scalania, które zastosowałem ;)
Sam algorytm jest niezły. Dla dwóch zbiorów o łącznej ilość n elementów
każdy, potrzebujesz n porównań. Jestem w stanie sobie wyobrazić
algorytmy wymagające mniejszej ilości porównań, ale będą wiązały się z
przestawianiem/usuwaniem elementów, bądź strukturach drzewiastych. W
najgorszym przypadku i tak będziesz potrzebował n porównań (w jednym
zbiorze liczby parzyste, w drugim nieparzyste). Może się mylę, ale z
założenia że zbiory są losowe, wynika że ilość porównań będzie zbliżona
do n. Więc chyba nie ma co kombinować.
> W moim pomyśle tak na prawdę dane przesyłane są dwa razy:
> 1) gdy program główny wysyła programom po sieci fragmenty tablicy do sortowania
> (i tak będzie w każdym algorytmie ;) )
> 2) gdy programy wysyłają posortowane tablice do programu głównego
Mniej razy tego nie prześlesz. Kiedy narzuty na komunikację będą
większe od korzyści, to nie ma co się bawić w rozpraszanie obliczeń :)
Zbiór powinien byż duży i dzielony na rozsądną ilość procesów. To
powinno być założenie tego projektu.
Moje rozwiązenie - zmień trochę koncepcję, tak żeby procesy działały w
parach. Nazwę je parzyste i nieparzyste. Każdy sortuje połowę danych. Po
posortowaniu nieparzysty odbiera dane od parzystego i scala dwie tablice
w jedną. Następnie przekazuje ją swojemu rodzicowi.
Zamiast płaskiej struktury procesów dostaniesz strukturę drzewiastą i
zrównoleglisz proces scalania. Wadą jest większy narzut związany z
przesyłaniem danych. Ale od tego, jak wspomniałem, nie uciekniesz.
--
karbi
karbi - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl napisał(a):
> Ale, że za pomocą scalania posortowanych podciągów dość łatwo rozwiązałem
> problem agregacji posortowanych tablic w jedną dużą, to utrudniono mi zadanie.
> Teraz muszę znaleźć algorytm łączenia podciągów posortowanych w jeden ciąg
> posortowany lub sortowania tablicy częściowo posortowanej, która składa się
> z tych kilku tablic posortowanych przez podciągi - ale taki, który jest szybszy
> od scalania, które zastosowałem ;)
Sam algorytm jest niezły. Dla dwóch zbiorów o łącznej ilość n elementów
każdy, potrzebujesz n porównań. Jestem w stanie sobie wyobrazić
algorytmy wymagające mniejszej ilości porównań, ale będą wiązały się z
przestawianiem/usuwaniem elementów, bądź strukturach drzewiastych. W
najgorszym przypadku i tak będziesz potrzebował n porównań (w jednym
zbiorze liczby parzyste, w drugim nieparzyste). Może się mylę, ale z
założenia że zbiory są losowe, wynika że ilość porównań będzie zbliżona
do n. Więc chyba nie ma co kombinować.
> W moim pomyśle tak na prawdę dane przesyłane są dwa razy:
> 1) gdy program główny wysyła programom po sieci fragmenty tablicy do sortowania
> (i tak będzie w każdym algorytmie ;) )
> 2) gdy programy wysyłają posortowane tablice do programu głównego
Mniej razy tego nie prześlesz. Kiedy narzuty na komunikację będą
większe od korzyści, to nie ma co się bawić w rozpraszanie obliczeń :)
Zbiór powinien byż duży i dzielony na rozsądną ilość procesów. To
powinno być założenie tego projektu.
Moje rozwiązenie - zmień trochę koncepcję, tak żeby procesy działały w
parach. Nazwę je parzyste i nieparzyste. Każdy sortuje połowę danych. Po
posortowaniu nieparzysty odbiera dane od parzystego i scala dwie tablice
w jedną. Następnie przekazuje ją swojemu rodzicowi.
Zamiast płaskiej struktury procesów dostaniesz strukturę drzewiastą i
zrównoleglisz proces scalania. Wadą jest większy narzut związany z
przesyłaniem danych. Ale od tego, jak wspomniałem, nie uciekniesz.
--
karbi
Marcin 'Qrczak' Kowalczyk - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl writes:
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
Inspiracji dostarcza implementacja sortowania przez Tima Petersa w Pythonie:
http://svn.python.org/view/python/tr...xt?view=markup
--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin \'Qrczak\' Kowalczyk - 24-12-2006 01:16
resident.evilWYTNIJTO@poczta.onet.pl writes:
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej niż
> mój sposób w przypadku agregacji kilku podciągów w jeden posortowany ciąg
> lub sortowania tablicy częściowo posortowanej, która powstała z połączenia
> tych posortowanych podciągów ?
Inspiracji dostarcza implementacja sortowania przez Tima Petersa w Pythonie:
http://svn.python.org/view/python/tr...xt?view=markup
--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Piotr Dembiński - 24-12-2006 01:17
resident.evilWYTNIJTO@poczta.onet.pl writes:
[...]
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej
> niż mój sposób
Nie wiem, ale warto pamiętać, że nie zawsze \'najlepszy\' to
\'najbardziej efektywny\' albo \'najszybszy\' :>
Piotr Dembiński - 24-12-2006 01:17
resident.evilWYTNIJTO@poczta.onet.pl writes:
[...]
> Tu moje pytanie - czy istnieje algorytm, który zadziała efektywniej
> niż mój sposób
Nie wiem, ale warto pamiętać, że nie zawsze \'najlepszy\' to
\'najbardziej efektywny\' albo \'najszybszy\' :>
zanotowane.pldoc.pisz.plpdf.pisz.pleffulla.pev.pl
|
=?ISO-8859-2?Q?=5BORACLE=2C_ORDER_BY=5D_Czy_indeksowane_?==?I SO-8859-2?Q?kolumny_przy=B6piesz=B1_sortowanie=3F?=
Dopasowanie do "najlepszego" dopasowania :) [ PostgreSQL]
sql -> tworzenie nowej kolumny z dzielenia 2 innych i sortowanie po niej
=?iso-8859-2?q?Sortowanie_wyniku_wg_dw=F3ch_kryteri=F3w?=
[ORACLE] sortowanie =?ISO-8859-2?Q?wed=B3ug_ci=B1gu?=
mysql: left join group by order by - problem z sortowaniem
=?iso-8859-2?Q?PostgreSQL_-_jak_ustawi=E6_sortowanie=3F?=
[MySQL] Dwa typy sortowania w jednej tabeli
jak wymusic sortowanie mysql dla znakow kodowanych w cp1250
[PGSQL] Sortowanie wg indeksu innej tabeli
zanotowane.pldoc.pisz.plpdf.pisz.pltejsza.htw.pl
Cytat
Decede mihi sole - nie zasłaniaj mi słonca.
Gdy kogoś kochasz, jesteś jak stworzyciel świata - na cokolwiek spojrzysz, nabiera to kształtu, wypełnia się barwą, światłem. Powietrze przytula się do ciebie, choćby był mróz, a ty masz w sobie tyle radości, że musisz ją rozdawać wokoło, bo się w tobie nie mieści
Hoc fac - tak czyń.
A tergo - od tyłu; z tyłu.
I czarne włosy posiwieją. Safona |
|
