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