W dniu 2012-11-24 13:39, Michoo pisze:
> On 24.11.2012 12:36, bartekltg wrote:
>>
>> Mając dodatkową pamięć dysku równo pierwotnej tablicy
>> (a tak naprawdę 0.5) możemy posortować tablicę
>> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.
>
> slawek się potem "poprawił", że plik jest "dużo" (10x) większy niż ram.

Aj, wszytko liczyłem dla 4GB, czyli 8 razy większego.

Problem jest gdzie indziej, nie zauważyłem, że ciągi
na siebie nachodzą. To powiększa mój bufor 16 razy;)
Zaczyna być nieprzyjemnie, ale nadal robialnie.

Zwłaszcza, że w normalnych warunkach ma się 12GB z czego 8 wolne;)
niech będzie 10GB danych, *16. 160GB.
RAMu niech będize 41GB, to daje ok 7 cykli, czyli
powiedzmy 13 (odczytów+zapisów=13)
Trzeba przewalić. 2TB


Powiedzmy, ze nie korzystamy ze sprzętu za 60k$ typu
dysk na PCI-16 6GB transger 4GB/s.
Jakiś dysk SSD na szybko zerknięty na Agito, odczyt/zapis 500MB/s.
Dysk maagnetyczny: "Szybkość przesyłu danych sformatowanych: 6 Gbit/s"
Cokolwiek to znaczy;)

W każdym razie naszą operację szacujemy na 15-20 minut.
Długo, trzeba by poprawić.

Ale zaczyna być ciekawie:)


> Nie do końca rozumiem to 0.5 nawet przy założeniu dane 4 razy większe od
> tablicy - mergesort potrzebuje na każdy merge drugie tyle miejsca.

> Wychodzi więc mi minimum 1.5 zakładając, że nie robimy ostatniego
> scalania. (Mamy 4 bloki po 1/4 n zajmujące na dysku n i żeby dwa z nich
> scalić potrzebujemy dodatkowe 0.5n na wynik.)

Moja pomyłka. +1 w dobrą stronę i -4 w złą;)

>> Kołaczą mi się sztuczki ze statystyką i nie jestem pewien,
>> czy nie da się tego zrobić lepiej. Ale ciężko będzie,
>> 5 przbiegów po dysku to podejrzewam minimum.
>> W koncu nawet log(n) jest większe.
>
> W praktycznym przypadku (a nie maksymalnie złośliwym) spróbowałbym z
> drzewem prefiksowym w ramie a jak by się przestało mieścić to dopiero
> fallback do sortowania. Daje jeden dodatkowy odczyt sekwencyjny i
> złożoność k*log(k) w RAMie gdzie k to liczba różnych wartości.

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

pzdr
bartekltg