🚀 go-pugleaf

Gracjan Ziółek napisał(a) w artykule
<345A351B.26F4@celebris.bdk.lublin.pl>...

>Robert Maron wrote:
>>
>> Jacek: [pl.comp.lang.c: Thu, 30 Oct 1997 23:00:57 +0100]
>> : Proponowalbym uzyc do tego B-drzewa. Jest to o ile wiem najszybsza
znana
>> [...]
>>
>> w zasadzie racja... ale po co sie tak meczyc;
>> wystarczy:
>> - podzielic plik na czesci tak duze, jak duze porcje mozemy sortowac
>>   w pamieci,
>> - posortowac kazda
>> - potem parami merdzowac
>> - wyniki znowu parami merdzowac, itd.
>>
>> to bedzie bardzo szybkie, a w unixie da sie zaimplementowac
kilkulinijkowym
>> skryptem, pod dosem/winda kilkunastolinijkowym programem...
>
>W takich przypadkach merging to jedyne sensowne rozwiazanie :). Ale zeby
>tak rekordy skryptem?... Ja to bym wolal C :)

Zapomnieliście (R.M. i G.Z.) że w przypadku "mergowania" trzeba się
trochę tych danych "naprzerzucać" co powoduje że już nie jest tak szybko
jakbyście chcieli. I mój algorytm (b-drzewa) i wasz (mergowanie) ma
złożoność O(n log n) ze względu na liczbę dostępów do dysku.
Jednakże mój operuje tylko na "kluczach" służących do indeksowania a
wasz na całych rekordach. Jeżeli te rekordy to na int'y to rzeczywiście
wasz jest lepszy, jeżeli jednak mają one po np 1000 bajtów to wasza
metoda "wysiada". W "mojej" metodzie każdy rekord jest dokładnie dwa razy
czytany z dysku i raz zapisywany.

pozdrawiam
Porkis

porkis@kki.net.pl - jeśli nie działa spróbuj:
@bbs.chip.pl, @polbox.com, @tempus.ii.uni.wroc.pl
http://polbox.com/p/porkis, http://www.kki.net.pl/porkis