-
Data: 2012-10-14 23:43:39
Temat: Re: sortowanie
Od: kenobi <p...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu niedziela, 14 października 2012 23:28:06 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 22:57, kenobi pisze:
>
> > W dniu niedziela, 14 października 2012 22:51:46 UTC+2 użytkownik kenobi napisał:
>
> >> ...użytkownik kenobi napisał:
>
>
>
>
>
> >>> co tu robi to --h ? jest na pewno dobrze?
>
>
>
> Na pewno jest dobrze.
>
>
>
> W h trzymasz liczbę wystąpień.
>
>
>
> Pod h[0] masz liczbę zer, pod h[1] liczbę jedynek
>
>
>
> Robisz sumy częściowe
>
> teraz pod h[0] nadal masz liczbę zer,
>
> ale pod h[1] liczbę zer i jedynek. pod h[2] liczbe zer,
>
> jedynek i dwójek.
>
>
>
> Ta na co pokazuje temp[ h[2] ] ?
>
> pokazuje na pierwsze miejsce _po_ ostatniej dwójce.
>
> Czyli ostatnia dwójka powinna znaleśc się na miejscu
>
> o jeden wcześniej.
>
> Robimy --h[2], pod wynikiem wkłądamy co trzeba.
>
>
>
> h pełni rolę _ruchomych_ wskaźników pokazujących,
>
> gdzie układać daną liczbę.
>
>
>
> Ok, przyznaje, nie jest to wersja edukacyjna,
>
> i zawiera trochę 'chackierskich przedwczesnych
>
> optymalizacji' i skrótowe konstrukcje.
>
> Dopiero co się nimi zachwysałeś
>
>
>
> być może
>
> temp[--h[(unsigned short)tab[j]]]=tab[j];
>
> ->
>
> kategoria = (unsigned short)tab[j];
>
> --h[kategoria]; //przesuwamy wskażnik tablicy dla elementow kategorii
>
> kategoria
>
> indeks = h[kategoria];
>
> temp[indeks] = tab[j]
>
>
>
> byłaby czytelniejsza;)
>
>
>
>
>
> >> nie rozumiem tego zlozenia, jak sortowanie tego
>
> >>
>
> >> co bylo posortowane po niskiej polowie po wysokiej czesci zlozy sie tak by
wszystko bylo ok?
>
>
>
> _Sortowanie stabilne_. Jeśli w drugim sortowaniu dwa elementy są takie
>
> same, to ich względna kolejność pozostanie taka sama jak po pierwszym.
>
>
>
> > w kazdym razie jesli to nie ma bledu i dziala
>
>
>
> Nie ma, działa.
>
>
>
> > to jest to sprytny kawalek kodu - dziwne jednak jakoby to mialo byc tylko 2-3
razy szybsze,
>
>
>
> Bo tu przelatujemy po dużej tablicy 6 razy, a w qsorcie
>
> log(N) razy. Log2(10^7) = 23 (tak naprawdę mniej, bo
>
> końcówkę robi się inaczej, a do tego działa się bardziej
>
> 'lokalnie', co jest szybsze).
>
>
>
> Dopiero co się szkicem tego algorytmu zachwycałeś.
>
> Od szkicu do implementacji droga wiedzie przez
>
> nieraz upierdliwe szczegóły;)
>
>
>
> Drzewa AVL są w idei super. Ale weź na szybko zaimplementuj
>
> równoważenie.
>
>
>
> > new mona wyrzucic i zrobic histogramy na statycznych tablicach
>
>
>
> Statyczna tablica na 40MB?
>
>
>
> To nie jest nawet zły pomysł. To głupi pomysł.
>
>
>
> Zrobiłem wersję z dodatkowym parametrem, buforem tworzonym
>
> raz na zewnątrz (poza licznikiem czasu) i przekazywanym do środka.
>
> Różnice były zbyt małe by warto było o nich wspominać,
>
> więc nawet nie pisałem.
>
>
histogramy maka tu po 256KB wiec o jakich 40MB mowa,
szkoda ze tylko 2-3 razy szybsze :/ oryginalna pojedyncza
wersja dla mniejszych zakrezsow np do miliona pewnie
wiecej szybsza,
jak to dziala a chyba dziala (testuje wlasnie ) to jest
wlasnie to o czym mowilem i to o co mi chodzilo nawet
lepiej jak mowilem sklecone niz myslalem - tak ze
jest to poniekad przypuszczam algorytm najszybszy
z wszystkich omawianych :U
Następne wpisy z tego wątku
- 15.10.12 00:01 bartekltg
- 15.10.12 00:43 kenobi
- 15.10.12 00:54 bartekltg
- 15.10.12 01:39 M.M.
- 15.10.12 07:49 kenobi
- 15.10.12 08:00 kenobi
- 15.10.12 08:53 Tomasz Kaczanowski
- 15.10.12 10:03 kenobi
- 15.10.12 13:25 kenobi
- 15.10.12 16:41 bartekltg
- 15.10.12 17:19 bartekltg
- 15.10.12 17:34 kenobi
- 15.10.12 17:40 kenobi
- 15.10.12 18:18 bartekltg
- 15.10.12 19:13 Michoo
Najnowsze wątki z tej grupy
- 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
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
Najnowsze wątki
- 2024-12-28 Antyradar
- 2024-12-28 Deweloper przegral w sadzie musi zwrócic pieniądze Posypia sie kolejne pozwy?
- 2024-12-28 Warszawa => Full Stack .Net Engineer <=
- 2024-12-28 Warszawa => Sales Assistant <=
- 2024-12-28 Warszawa => Programista Full Stack .Net <=
- 2024-12-28 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-12-28 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-12-28 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2024-12-28 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2024-12-28 Żerniki => Employer Branding Specialist <=
- 2024-12-28 ale zawziętość i cierpliwość
- 2024-12-27 most kilometrowy
- 2024-12-27 Dyplomaci a alkomaty
- 2024-12-27 Zmiana kary
- 2024-12-27 Chiński elektrolizer tester wody