-
Data: 2012-10-14 18:25:09
Temat: Re: sortowanie
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu 2012-10-14 16:42, Michoo pisze:
> On 14.10.2012 13:56, bartekltg wrote:
>>
>> Zrozum, że to legenda zrobiona na ignorancji autora.
> Autor zrobił jakiś dziwne kombinacje z tym qsortem - prawdopodobnie użył
> "naiwną" implementację i jeszcze spreparował dane:
>
> Przetestowałem std::sort na cyrixie@133MHz (60MB ram) i geodzie@400MHz
> (256MB ram)
>
> sortowanie miliona:
> 7.1s/2.6s
> sortowanie 10 milionów:
> -84.6s/31s
>
> (btw: counting sort miliona (z zakresem 0-mln) na cirixie trwa 1.6s - 5x
> różnica)
>
> A on podobno na Athlonie, procesorze pracującym z ponad 1GHz miał czasy
> 3.6s/300s
>
> ktoś tu najzwyczajniej w świecie robi czytelnika w *.
A może to rzeczywiście był najlepszy qsort jaki byl w stanie napisac?
> Do tego popełnia dość istotny błąd rzeczowy:
>> Actually, the amount of required memory is Cmem = N_VAL*sizeof(cell),
>> where N_VAL is the number of allowed values
>
> Well, w zaprezentowanej implementacji po lekkich poprawkach N_VAL może
> być max(data)-min(data). Np posortujmy wartości ze zbioru
> (10-100)\/(2^30-2^30+5); No chyba, że autor zakłada użycie jakiejś
> sterty/drzewa jako hashmapy...
Można do zamiast tablicy zliczającej użyć zrównoważonego drzewa
zawierającego, poza liczbą jako kluczem, krotność wystąpienia.
Jeśli tablica ma długość N, i znajduje się w niej D różnych wartości,
taki algorytm zadziała w czasie N*log(D).
Znów w przyrodzie nic nie ginie;)
> Sugestia użycia sparse table też imo zakłada o kiepski żart. (Genialny
> algorytm sortowania, który czasami się wywala z OOM-exception.)
:)
>> In particular, sorting data belonging to the range of [0; 1,000,000]
>> will require no more than 4 MB of memory, a rather insignificant amount.
>
> I to jest imo jedyny sensowny wniosek z całego rozdziału - dane LICZBOWE
> (a rzadko sortujemy same liczby, częściej jednak struktury danych) z
> małego zakresu opłaca się sortować przez zliczanie.
Struktury tu nic nie przeszkadzają. Byle pole, po którym sortujemy
było zmienną dyskretną (cłkowitą) i miała niewielki zakres.
pzdr
bartekltg
Następne wpisy z tego wątku
- 14.10.12 18:27 kenobi
- 14.10.12 18:29 M.M.
- 14.10.12 18:31 bartekltg
- 14.10.12 18:45 kenobi
- 14.10.12 18:57 bartekltg
- 14.10.12 19:43 kenobi
- 14.10.12 19:56 kenobi
- 14.10.12 20:01 bartekltg
- 14.10.12 20:14 bartekltg
- 14.10.12 20:14 kenobi
- 14.10.12 22:19 bartekltg
- 14.10.12 22:42 kenobi
- 14.10.12 22:51 kenobi
- 14.10.12 22:57 kenobi
- 14.10.12 23:27 bartekltg
Najnowsze wątki z tej grupy
- Grok zaczął nadużywać wulgaryzmów i wprost obrażać niektóre znane osoby
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
Najnowsze wątki
- 2025-07-25 Drastycznie rośnie import stali - w hucie w Dąbrowie Górniczej zostanie wygaszony wielki piec
- 2025-07-25 Drastycznie rośnie import stali - w hucie w Dąbrowie Górniczej zostanie wygaszony wielki piec
- 2025-07-25 I kolejny inżynier...
- 2025-07-25 Kobiety, bójcie się inżynierów...
- 2025-07-25 Warszawa => Konsultant Wiodący SAP PP <=
- 2025-07-25 Re: Brawo !!! Osy chronione w Niemczech. Za usunięcie gniazda grozi mandat
- 2025-07-25 cudzoziemiec bez biletu
- 2025-07-25 Gdynia => Sales Executive / KAM <=
- 2025-07-25 Inżynierzy z prawomocnym...
- 2025-07-25 Łódź => Mainframe (z/OS, Assembler) Developer <=
- 2025-07-25 Warszawa => Inżynier oprogramowania .Net <=
- 2025-07-25 Kraków => Senior Fullstack Engineer (Low-Code Platform) <=
- 2025-07-25 Skrobanie
- 2025-07-25 Lublin => Konsultant ds. Wdrożeń ERP (moduł FK) <=
- 2025-07-25 Warszawa => Senior Frontend Developer (React + React Native) <=