-
Data: 2012-11-24 12:53:01
Temat: Re: Potyczki
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu 2012-11-24 12:36, bartekltg pisze:
>
> Mając dodatkową pamięć dysku równo pierwotnej tablicy
> (a tak naprawdę 0.5) możemy posortować tablicę
> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.
>
> Dominantę w posortowanej tablicy znajdujemy już
> liniowo i szybko.
>
> Jak sortujemy: pobieramy paczki po 512MB (albo mnijsze,
> jeśli nasze 512MB jest sztywne i nie możemy dodać tym
> czegoś lon(n)), sortujemy w RAM czymkolwiek sprawnym.
>
> Mamy 8 posortowanych fragmentów pliku. Łączymy je mergesortem.
> w 4, w 2, i w końcu w posortowany.
>
> Co istotne, merga robimy nie bezpośrednio na dysku, ale na
> buforach w ramie. Pobieramy odcinki po jakies 100MB,
> kręcimy procedurą w mergesort, jak któryś bufor się wyczerpie,
> napełniamy go ponownie kolejnymi danymi z dysku.
>
> Dzięki temu czytamy sekwencyjnie, dysk nie lata ciągle np między
> początkiem a środkiem pliku.
>
> Niestety, nadal n log (n) i n*log(n/|RAM|) operacji (Sekwencyjnych)
> na dysku, ale równoważnych przesłaniu tych kilkudziesięciu GB
> - robialne.
Optymalizacja: znajdowanie dominanty można upchnąć w ostatnią
fazę mergesorta. Odpada jeden odczyt.
Jeśli posortowana tablica nie jest nam do szczęścia potrzebna,
możemy też jej nie zapisywać.
Czyli 4 odczyty i 3 zapisy (4 zapisy, jeśli chcemy zachować
posortowaną tablicę na potem)
oba +1 jeśli użyjemy kawałków po 256MB.
pzdr
bartek
Następne wpisy z tego wątku
- 24.11.12 12:54 PK
- 24.11.12 13:02 Roman W
- 24.11.12 13:04 bartekltg
- 24.11.12 13:08 Roman W
- 24.11.12 13:09 Roman W
- 24.11.12 13:09 e...@g...com
- 24.11.12 13:11 Roman W
- 24.11.12 13:11 Michoo
- 24.11.12 13:14 Michoo
- 24.11.12 13:16 e...@g...com
- 24.11.12 13:18 bartekltg
- 24.11.12 13:37 slawek
- 24.11.12 13:39 Michoo
- 24.11.12 13:40 slawek
- 24.11.12 14:13 bartekltg
Najnowsze wątki z tej grupy
- Nowa ustawa o ochronie praw autorskich - opis problemu i szkic ustawy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
Najnowsze wątki
- 2025-03-18 Tesla na złom
- 2025-03-18 Ziobrotura 3.0 będzie w prawie przesłuchać "świadka" Tuska bez adwokata w sprawach Sienkiewicza/Bodnara/...?
- 2025-03-18 Produkty ,,Made in Germany" wciąż na topie - art. na www.dw.com
- 2025-03-18 ulaskawienia
- 2025-03-18 Gdynia => Sales Executive / KAM <=
- 2025-03-18 42 MILIARDY ZŁOTYCH ZYSKU W ROK. DLACZEGO BANKI TYLE ZARABIAJĄ W POLSCE?
- 2025-03-17 Nie matura lecz chęć szczera ...
- 2025-03-17 Pendrive zdycha, czy coś jeszcze innego? Problem z plikami.
- 2025-03-17 Odkurzacz Smapp Dynamic - dawny Zelmer
- 2025-03-17 Nagra IV i zewnętrzny pilot
- 2025-03-17 Rzeszów => Spedytor Międzynarodowy <=
- 2025-03-17 Warszawa => Junior Account Manager <=
- 2025-03-17 Białystok => Gen AI Engineer <=
- 2025-03-17 Białystok => Generative AI Engineer <=
- 2025-03-17 Częstochowa => Backend Developer (Node + Java) <=