Hey

Muszę napisać (albo skądś dorwać gotową) bardzo wydajną implementację
sortowania. Sortowana będzie wielokrotnie tablica o rozmiarze około
2-10mln elementów. Jeden element będzie miał rozmiar około 12-20 bajtów.
Elementy będą miały przypisane wartości z mało licznego zbioru, np
wartości całkowite z zakresu od 1 do 50.

Pierwsza kwestia od jakiego rozmiaru elementu opłaca się użyć tablicy
wskaźników. Jeśli element jest duży to opłaca się użyć wskaźników
zamiast kopiowania, pytanie czy 12-20 bajtów to już duży element?

Druga sprawa to wybór algorytmu. Na pewno qsort odpada dla małej ilości
wartości. Chyba jakieś sortowanie kubełkowe?

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Mariusz Marszałkowski pisze:
> Hey
>
> Muszę napisać (albo skądś dorwać gotową) bardzo wydajną implementację
> sortowania. Sortowana będzie wielokrotnie tablica o rozmiarze około
> 2-10mln elementów. Jeden element będzie miał rozmiar około 12-20 bajtów.
> Elementy będą miały przypisane wartości z mało licznego zbioru, np
> wartości całkowite z zakresu od 1 do 50.
>
> Pierwsza kwestia od jakiego rozmiaru elementu opłaca się użyć tablicy
> wskaźników. Jeśli element jest duży to opłaca się użyć wskaźników
> zamiast kopiowania, pytanie czy 12-20 bajtów to już duży element?
>
> Druga sprawa to wybór algorytmu. Na pewno qsort odpada dla małej ilości
> wartości. Chyba jakieś sortowanie kubełkowe?
>
> Pozdrawiam
>
>
>
Jeśli chodzi o algorytm to nie musisz sortować elementów w kubełkach
jeśli nie jest to konieczne. Ale myślę że sam na to wpadłeś.

Pozdrawia Łukasz Szpakowski.

do góry

Mariusz Marszałkowski wrote:
> Hey
>
> Muszę napisać (albo skądś dorwać gotową) bardzo wydajną implementację
> sortowania. Sortowana będzie wielokrotnie tablica o rozmiarze około
> 2-10mln elementów. Jeden element będzie miał rozmiar około 12-20
> bajtów. Elementy będą miały przypisane wartości z mało licznego
> zbioru, np wartości całkowite z zakresu od 1 do 50.
>
> Pierwsza kwestia od jakiego rozmiaru elementu opłaca się użyć tablicy
> wskaźników. Jeśli element jest duży to opłaca się użyć wskaźników
> zamiast kopiowania, pytanie czy 12-20 bajtów to już duży element?

Nic nie piszesz o tym, czy zależy Ci na szybkości, czy na oszczędności
pamięci.

Może widok się nada. Polecam artykuł Macieja Sobczaka:

http://www.ddj.com/showArticle.jhtml?articleID=18440
1789

oraz View Template Library.

Rozwiązanie koncepcyjnie podobne do wskaźników, ale zamiast wskaźników,
możesz sortować indeksy (zakładając, że istnieją) z kolekcji macierzystej.

Najgorszy przypadek to będzie sortowanie kolekcji ~0.5 GB danych.
Do tego widok sortujący to dodatkowe ok 10% z w/w pamięci.
Wszystkie indeksy są o tym samym rozmiarze, czyli np. 10 mln * 4 bajty.

> Druga sprawa to wybór algorytmu. Na pewno qsort odpada dla małej
> ilości wartości. Chyba jakieś sortowanie kubełkowe?

Albo to:

http://en.wikipedia.org/wiki/Polyphase_merge_sort

Jak pamięci brak, to istnieje też STXXL (http://stxxl.sourceforge.net/)
implementujące 2 lub 3 tzw. algorytmy external sorting.
Jak pamięci jest dość, a ma być szybko, to być może jest sens aby to
zrównoleglić (choć czytałem jakąś analizę znanych algorytmów z
sekwencyjnych implementacji ale wykonanych z użyciem OpenMP i wyniki nie
były jednoznacznie "za MP", AFAIR).

Pozdrawiam
--
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org

do góry

Mateusz Loskot <s...@s...net> napisał(a):

> Nic nie piszesz o tym, czy zależy Ci na szybkości, czy na oszczędności
> pamięci.

> sekwencyjnych implementacji ale wykonanych z użyciem OpenMP i wyniki nie
> były jednoznacznie "za MP", AFAIR).
>

Dziękuję za odpowiedź, te materiały powinny mi w zupełności wystarczyć.

Na razie zrobiłem tak:
1) wrzucam elementy do hash-table
a) jeśli elementu nie było to go dodaję z licznikiem równym jeden
b) jeśli element był to zwiększam licznik o jeden
2) elementy z hash-table wrzucam do tablicy liniowej
3) sortuję tablicę liniową
4) buduję tablicę wyjściową

Pozdrawiam serdecznie


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

=?ISO-8859-2?Q?Mariusz_Marsza=B3kowski?= wrote:

> Dziękuję za odpowiedź, te materiały powinny mi w zupełności wystarczyć.
>
> Na razie zrobiłem tak:
> 1) wrzucam elementy do hash-table
> a) jeśli elementu nie było to go dodaję z licznikiem równym jeden
> b) jeśli element był to zwiększam licznik o jeden
> 2) elementy z hash-table wrzucam do tablicy liniowej
> 3) sortuję tablicę liniową
> 4) buduję tablicę wyjściową


zamiast (2) i (3) -- ustalasz porzadek w hash-table i od razu po tym (4).

milego dnia, hej

do góry

Mariusz Marszałkowski pisze:
> Mateusz Loskot <s...@s...net> napisał(a):
>
>> Nic nie piszesz o tym, czy zależy Ci na szybkości, czy na oszczędności
>> pamięci.
>
>> sekwencyjnych implementacji ale wykonanych z użyciem OpenMP i wyniki nie
>> były jednoznacznie "za MP", AFAIR).
>>
>
> Dziękuję za odpowiedź, te materiały powinny mi w zupełności wystarczyć.
>
> Na razie zrobiłem tak:
> 1) wrzucam elementy do hash-table
> a) jeśli elementu nie było to go dodaję z licznikiem równym jeden
> b) jeśli element był to zwiększam licznik o jeden
> 2) elementy z hash-table wrzucam do tablicy liniowej
> 3) sortuję tablicę liniową
> 4) buduję tablicę wyjściową
>
> Pozdrawiam serdecznie
>
>
Nie lepiej wykorzystać sortowanie przez zliczanie?

Pozdrawia Łukasz Szpakowski.

do góry

luckboy <l...@v...pl> napisał(a):

> Mariusz Marszałkowski pisze:
> > Mateusz Loskot <s...@s...net> napisał(a):
> >
> >> Nic nie piszesz o tym, czy zależy Ci na szybkości, czy na oszczędności
> >> pamięci.
> >
> >> sekwencyjnych implementacji ale wykonanych z użyciem OpenMP i wyniki nie
> >> były jednoznacznie "za MP", AFAIR).
> >>
> >
> > Dziękuję za odpowiedź, te materiały powinny mi w zupełności wystarczyć.
> >
> > Na razie zrobiłem tak:
> > 1) wrzucam elementy do hash-table
> > a) jeśli elementu nie było to go dodaję z licznikiem równym jeden
> > b) jeśli element był to zwiększam licznik o jeden
> > 2) elementy z hash-table wrzucam do tablicy liniowej
> > 3) sortuję tablicę liniową
> > 4) buduję tablicę wyjściową
> >
> > Pozdrawiam serdecznie
> >
> >
> Nie lepiej wykorzystać sortowanie przez zliczanie?
>

Jeszcze nie wiem.
Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Mariusz Marszałkowski pisze:
> luckboy <l...@v...pl> napisał(a):
>
>> Mariusz Marszałkowski pisze:
>>> Mateusz Loskot <s...@s...net> napisał(a):
>>>
>>>> Nic nie piszesz o tym, czy zależy Ci na szybkości, czy na oszczędności
>>>> pamięci.
>>>> sekwencyjnych implementacji ale wykonanych z użyciem OpenMP i wyniki nie
>>>> były jednoznacznie "za MP", AFAIR).
>>>>
>>> Dziękuję za odpowiedź, te materiały powinny mi w zupełności wystarczyć.
>>>
>>> Na razie zrobiłem tak:
>>> 1) wrzucam elementy do hash-table
>>> a) jeśli elementu nie było to go dodaję z licznikiem równym jeden
>>> b) jeśli element był to zwiększam licznik o jeden
>>> 2) elementy z hash-table wrzucam do tablicy liniowej
>>> 3) sortuję tablicę liniową
>>> 4) buduję tablicę wyjściową
>>>
>>> Pozdrawiam serdecznie
>>>
>>>
>> Nie lepiej wykorzystać sortowanie przez zliczanie?
>>
>
> Jeszcze nie wiem.
> Pozdrawiam
>
>
>

A ha jeśli potrzebujesz zachować wszystkie elementy o tej samej wartości
to powinieneś zastosować sortowanie kubełkowe bez sortowania kubełków.

Ponieważ jeśli będziesz tylko zliczał elementy to utracisz wszystkie
które będą liczone jako nie pierwsze. Zamiast nich otrzymasz kopie
pierwszego elementu który zliczyłeś. Czy tego chcesz?

Pozdrawia Łukasz Szpakowski.

do góry

luckboy <l...@v...pl> napisał(a):
> >>>
> >> Nie lepiej wykorzystać sortowanie przez zliczanie?
> >
> > Jeszcze nie wiem.
>
> Czy tego chcesz?

Oj chcę wiele rzeczy... raz tak, raz inaczej, a raz tylko "połowę" algorytmu
sortowania, aby obliczyć sumy częściowe... Za dużo szczegółów aby zaśmiecać
grupę, dojdę sam, chciałem tylko poprosić o kilka dobrych linków, abym
nie musiał odfiltrowywać całego tego bagna jakie wyświetlają google :)

Pozdrawiam i dziękuję



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

> Druga sprawa to wybór algorytmu. Na pewno qsort odpada dla małej
> ilości wartości.

introsort powinien się wtedy lepiej od qsorta sprawdzić.


--
Azarien

do góry