On 24.11.2012 14:13, bartekltg wrote:
> W każdym razie naszą operację szacujemy na 15-20 minut.
> Długo, trzeba by poprawić.
>
> Ale zaczyna być ciekawie:)

Jest sobie OzSort, który sortuje 250GB danych (100 bajtowe bloki, 10B
klucza, 90B payload) w 30 minut na nie_tak_drogim sprzęcie.

>
> To drzewo dużo miejsca nam nie oszczędza, ale zawsze.
> Nie zaszkodzi spróbować, ale dla losowego ta heurystyka
> zadziała?

Zadziała dopóki różnych wartości jest dostatecznie mało. Każdy wpis do
drzewa to 5 bajtów na poziom (klucz na k-tym poziomie+wskaźnik/licznik
na końcu). Jeżeli dobrze szacuję to wyszukiwanie binarne max 16*8
operacji, wstawianie max 16*255 operacji(nie licząc tego, że
potrzebujemy alokator). Wychodzi około 6 milionów wpisów na 512MB ram.
Dopóki liczba różnych wartości jest mniejsza od maksymalnego drzewa -
powinno działać. Dla losowych raczej nie.


--
Pozdrawiam
Michoo