eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingsortowanieRe: sortowanie
  • 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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: