-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!news.supermedia.pl!news.nask.pl!news.nask.org.pl!news.internetia.pl!no
t-for-mail
From: Edek Pienkowski <e...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: sortowanie
Date: Sat, 13 Oct 2012 21:48:41 +0000 (UTC)
Organization: Netia S.A.
Lines: 78
Message-ID: <k5cnjp$d0e$1@mx1.internetia.pl>
References: <k59gbj$be7$1@node2.news.atman.pl>
<6...@g...com>
<k59jgh$mb7$1@mx1.internetia.pl> <k59jvr$360$1@node1.news.atman.pl>
<k59q5n$np3$1@mx1.internetia.pl> <k5bc6k$4ea$1@mx1.internetia.pl>
<50795bb6$0$1297$65785112@news.neostrada.pl>
<k5bo04$n79$2@mx1.internetia.pl>
<507968f5$0$1220$65785112@news.neostrada.pl>
<k5bqi2$n79$3@mx1.internetia.pl>
<5079736f$0$1228$65785112@news.neostrada.pl>
<k5bvji$n79$7@mx1.internetia.pl>
<7...@g...com>
<k5c6ta$hlr$1@mx1.internetia.pl>
<2...@g...com>
<b...@g...com>
<c...@g...com>
<k5cf35$lnp$2@mx1.internetia.pl>
<0...@g...com>
NNTP-Posting-Host: as4-251.poleczki.dialup.inetia.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: 8bit
X-Trace: mx1.internetia.pl 1350164921 13326 195.114.165.251 (13 Oct 2012 21:48:41
GMT)
X-Complaints-To: a...@i...pl
NNTP-Posting-Date: Sat, 13 Oct 2012 21:48:41 +0000 (UTC)
X-Tech-Contact: u...@i...pl
User-Agent: Pan/0.135 (Tomorrow I'll Wake Up and Scald Myself with Tea; GIT 30dc37b
master)
X-Server-Info: http://www.internetia.pl/
Xref: news-archive.icm.edu.pl pl.comp.programming:199831
[ ukryj nagłówki ]Dnia Sat, 13 Oct 2012 12:33:40 -0700, kenobi napisal:
> W dniu sobota, 13 października 2012 21:18:12 UTC+2 użytkownik Edek Pienkowski
napisał:
>> Dnia Sat, 13 Oct 2012 11:58:34 -0700, kenobi napisal:
>>
>>
>>
>> > za jakis czas sobie klepne pewnie to uogolnienie, np dla 32 bit mozna
>>
>> > pewnie w jednym przebiegu zrobic histogram na gornych bitach wygenerowac
>>
>> > czesciowo uporzadkowany wynik i w kolejnym posortowac kawalki, albo tez i
>>
>> > inaczej ladnie dobierajac po efektywnosci - w kazdym razie raczej da sie
>>
>> > to uogolnic :U
>>
>>
>>
>> Dla string�w te� si� da. Taki 8-bajtowy string to 2^64 tak jak int64
>>
>> to 2^64 jak i float to 2^64. Ymmv, ale widz� morfizm, wystarczy uzupe�ni�
>>
>> string zerami do najd�u�szego, zera tak rzadko wyst�puj�. Jedynie te
>>
>> floaty majďż˝ jakieďż˝ NaNy i InfY, ale int siďż˝ nadaje. A jak siďż˝ zmienne
>>
>> typu String wrzuci w histogram potem, to mo�na histogramowa� po
>>
>> intach zbudowanych ze znak�w, robi si� to raz, a nie z bajt�w, wystarczy
>>
>> jak wszystkiemu por�wnywalnemu waln�c raz przypisanie znaku do liczby,
>>
>> znaki s� znane, wed�ug lexykografii i jeste�my w domu po jednym
>>
>> przebiegu, chyba �e wszystkie przypisane liczby s� takie same, ale
>>
>> wtedy zaczyna si� od string�w obci�tych uprzednio co sprawia
>>
>> �e por�wnanie potem jest szybsze, mo�na bezkosztowo prawie
>>
>> offsetem za�atwi�.
>>
>>
>>
>> Uog�lniaj�c, ma si� mo�liwo�� histogramowania wszystkiego do czego
>>
>> mo�na przypisa� liczb� bez uprzedniego sortowania.
>>
>>
> nieczytelny tekst da sie przeczytac tylko niektore slowa - tu jest zrodlo tego
pomyslu
> przynajmniej ja stad sie o tym dowiedzialem
>
> The quick-sort algorithm requires O(n lg n) operations on average and O(n2)
operations in the worst situation. This
> algorithm is very fast. Nevertheless, it needs to be improved! It reminds me of a
quotation from a sci-fi novel by Arkady
> and Boris Strugatsky: "We are well aware that this task has no solution... We want
to know how to solve it."
> A simple and efficient sorting algorithm exists that, in the worst situation,
requires O(n) operations. No, this is not a joke!
> There is such an algorithm. On AMD Athlon 1050, it sorts 10 million numbers in
approximately 0.3 seconds, thousand
> times faster than quick sort.
> I discovered this algorithm time when I was participated in a computer-science
contest. One of the problems required the
> participants to sort seven numbers using no more than three comparison operations.
Seeing this problem as a perfect
> opportunity for showing off, I wrote a small program that sorted the numbers
without using any comparison operations.
> Unfortunately, my solution was not considered superior. Only after a couple of
years of carefully exploring the existing
> sorting algorithms could I evaluate the importance of the result.
>
> kriss kaspersky code optimization effective memory usage
>
> (dalej jest opis ale sprowadza sie to mw do tego co mowie) problemem jest tu ze
dobrze
> to dziala jesli wartosci jest duzo a zakres jest waski a niezbyt nadaje sie kiedy
wartosci jest malo, a zakres szeroki ale kiedy wartosci jest duzo i zakres szeroki,
da sie to mz
> podzilic pokombinowac i tez ogolnie wykorzystac ten sposob
>
>
> i tak czesto ja potrzebowalbym sortowac po prostu male inty i wtedy to dziala
blyskawicznie i jest hipergenialna metoda
"Doing the impossible is fun" - Walt Disney.
--
Edek
Następne wpisy z tego wątku
- 13.10.12 23:54 PK
- 13.10.12 23:56 PK
- 14.10.12 00:04 kenobi
- 14.10.12 00:04 bartekltg
- 14.10.12 00:04 bartekltg
- 14.10.12 00:10 M.M.
- 14.10.12 00:18 bartekltg
- 14.10.12 00:21 M.M.
- 14.10.12 00:35 PK
- 14.10.12 00:41 bartekltg
- 14.10.12 00:49 bartekltg
- 14.10.12 00:51 PK
- 14.10.12 00:54 bartekltg
- 14.10.12 00:58 bartekltg
- 14.10.12 00:59 PK
Najnowsze wątki z tej grupy
- 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
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-03-01 Warszawa => Expert Recruiter 360 <=
- 2025-03-01 Chrzanów => NodeJS Developer <=
- 2025-03-01 Warszawa => Gen AI Engineer <=
- 2025-03-01 Wrocław => Konsultant wdrożeniowy Comarch XL/Optima (Księgowość i
- 2025-03-01 Kraków => Technical Team Leader (Clojure, Java) <=
- 2025-03-01 Zrobił TV OLED z TV LCD
- 2025-03-01 Gdynia => Sales Executive / KAM <=
- 2025-03-01 Błonie => Sales Specialist <=
- 2025-03-01 Ryga => Konsultant Wdrożeniowy Comarch XL/Optima (Księgowość i Kad
- 2025-03-01 Żerniki => Dyspozytor Międzynarodowy <=
- 2025-03-01 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2025-03-01 Wróblewo => Analityk finansowy <=
- 2025-03-01 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-02-28 Chrzanów => Regionalny Kierownik Sprzedaży (OZE) <=
- 2025-02-28 Warszawa => Java Full Stack Developer (Angular2+ experience) <=