Algoritmusok sebessége
2014-05-08T18:27:58+02:00
2014-05-09T16:39:53+02:00
2022-06-29T07:30:37+02:00
  • Igazsag szerint csak az tunt nekem fel, hogy 300ezer elemnél egy ilyen szituacioban durvan belassult. A worst case azert tulzas, de ugy mondanam, hogy az egy meglepoen bad case volt.


    Az a baj, hogy ha van benne egy k hosszúságú rendezett részsorozat, akkor ha peched van, akkor ez akár k^2-el is megdobhatja a futásidőt. Ezért tud veszélyes lenni a naiv QuickSort...

    Ami nekem nagyon tetszik a qsortban, hogy az ido 99%-aban az oszzehasonlitasoknak csak az egyik elemét kell mindig elérni, a masik hosszu ideig 'cache'-olhato.

    Na igen, ez az, ami nagyon gyorsá teszi.
    Plusz mellé szekvenciálisan nyúlkál az elemekhez, úgyhogy a cache is jól érzi magát.
    Egyébként épp ez utóbbi miatt a randomizált quicksort valamivel lassabban működik nagy adatsorokon, mert a random ugrások miatt (pivot kiolvasása) megnő a valószínűsége +1 cache missnek. (Arról nem is beszélve, hogy le is kell generálni a véletlenszámot, bár azt szerintem nyugodtan vehetjük elhanyagolható időnek. Ide nem kell semmi durva generátor)


    Amikor egy expressiont kellett evalualni a rendezeshez, akkor ez a tulajdonsaga a qsortnak nagyon jol jott.

    Mondjuk itt megteheted, hogy előre kiszámoltatod az összes expressiont, majd azt rendezed... Igaz, ez megdobja a memóriahasználatot egy O(n)-el...
    Mutasd a teljes hozzászólást!
  • Hu tenyleg, random pivot.
    Igazsag szerint csak az tunt nekem fel, hogy 300ezer elemnél egy ilyen szituacioban durvan belassult. A worst case azert tulzas, de ugy mondanam, hogy az egy meglepoen bad case volt.

    Ami nekem nagyon tetszik a qsortban, hogy az ido 99%-aban az oszzehasonlitasoknak csak az egyik elemét kell mindig elérni, a masik hosszu ideig 'cache'-olhato. Amikor egy expressiont kellett evalualni a rendezeshez, akkor ez a tulajdonsaga a qsortnak nagyon jol jott.
    Mutasd a teljes hozzászólást!
  • Ez mondjuk attól függ, hogy hogy választod a pivot elementet.
    Ha például a legegyszerűbb módon mindig a legelsőt választod, akkor az alábbi példát majdnem a worst-case (a teljesen rendezett a worst-case).
    De például a randomized quicksort-nál ezt már elég jól lehet kerülni és elhanyagolható a valószínűsége, hogy akárcsak meg is közelítse az O(n^2) futásidőt...
    Mutasd a teljes hozzászólást!
  • Ja, nagyon fontos az input.

    Ha jol emlekszem, ez peldaul egy quicksort worst case (nagyon regen belefutottam, asszem valami ilyesmi volt): 1,2,3,4,5,6,7,8,9,0 Ilyen adatokkon lassabb lesz, mint a bubble sort.

    Mutasd a teljes hozzászólást!
  • vannak erre vonatkozó matematikai eszközök, a programok aszimptotikus bonyolultságvizsgálata körül keresgélj (pl. http://en.wikipedia.org/wiki/Asymptotic_computational_complexity)

    persze ez elsősorban elmélet. a gyakorlatban a legcélravezetőbb az, amit Mekkelek5 írt, meg kell mérni. ezzel meg az lesz a baj, hogy az adott implementációt és környezetet is méri, meg a tesztadatokat, stb., úgyhogy ebből meg általános igazságokat nem lehet levonni.
    Mutasd a teljes hozzászólást!
  • De még ha igaz lenne... akkor sem igaz.

    Legfeljebb általános esetekre lehetne kijelenteni valamit, olyan meg nincs

    Minden esetben van az adatoknak szerkezete, jellemzői, aztán a környezetnek is van jellege (memória, háttértár, cpu mennyiség, sebesség, kihasználtság, akár még karakterisztika is )

    Szóval mint minden esetben, egy szint (igény) felett ez is egy külön tudomány.
    Mutasd a teljes hozzászólást!
  • " rendezésre a QuickSort a leggyorsabb"

    Megint egy kijelentés....


    Rendezőalgoritmusok - szemléletesen ábrázolva - Médiatár - Prog.Hu
    Mutasd a teljes hozzászólást!
  • Azt tudod bizonyítani, hogy az ismert eljárások közül a tesztkörnyezetben melyik a leggyorsabb. Leméred és kész. De ez nem bizonyíték arra, hogy MINDEN feltételek mellett az a leggyorsabb, és azt sem hogy 1 hét vagy 1 év múlva nem lesz annál hatékonyabb, vagy nem lesz rá célhardver (pl tömb rendezésre, vagy fa bejárásra).

    A szoftver és hardver környezet is változik, fejlődik, esetleg a programozás technika is. (Pl kitalálod, hogy nem is kell rendezned azt a tömböt, megoldod e nélkül is a feladatot.)
    Mutasd a teljes hozzászólást!
  • Pl. rendezésre a QuickSort a leggyorsabb (azt hiszem).

    Nem ez a leggyorsabb. Kb egy elterjedt library se (csak) QuickSort-ot használ, hanem különböző hibrid algoritmusokat. [1]

    Egyébként is a QuickSort worst-case komplexitása O(n^2), ennél pl helyből jobb a Mergesorté.

    Nagyon ritka esetekben egyébként bizonyítható is egy adott algoritmusról, hogy az a létező legjobb az adott általános problémára és architektúrára+konfigurációra (ez utóbbi kettő rendkívül fontos), de az ilyen nagyon-nagyon ritka. Specializált esetekre meg a legtöbbször lehet még gyorsabbat kitalálni.


    Visszatérve a rendezésre, itt megint külön alkategória az összehasonlító rendezés (amire a QuickSort például egy példa). Itt könnyedén bizonyítható, hogy mindig minimum O(n*log n) lépésre van szükség az általános problémánál.
    De ott vannak a nem összehasonlító rendezések, mint például a bucket-sort, ami O(n) idő alatt végez.


    Visszatérve a kérdésre:
    Igen, elméletileg lehetséges, de nagyon ritka (és kb kizárólag csak nagyon egyszerű problémáknál).
    Sokkal gyakoribb az (bár így is nagyon ritka), hogy bizonyítod egy algoritmusról, hogy aszimptotikusan optimális. Ilyen például a merge-sort (míg a quicksort nem). Ez azonban nem azt jelenti, hogy ez a való életben is, mai számítógépen megvalósítva igaz (ezért gyorsabb általában a quicksort a merge-sort-nál).


    [1] Pl Timsort (pl. Java) (Ennek pl semmi köze a Quicksorthoz) vagy Introsort (C++ vagy .net)
    Mutasd a teljes hozzászólást!
  • Generikus válasz nincs a kérdésedre, egy külön szakterület a számítástudományon belül az algoritmusok műveletigényének elemzése.

    Azért az utolsó kérdésedre tudok válaszolni: ha egy bináris fát a 'szokott módon' reprezentálunk (vagyis a szülőben van két mutató a gyerekeire', akkor egy rendezett fában a keresés leggyorsabb (és egyetlen lehetséges) módja az, amit leírtál.
    Mutasd a teljes hozzászólást!
  • Üdvözlet,

     többségünk gyakran használ valamilyen algoritmust munkája során. Pl. keresési
    algoritmust, rendezést, stb. Ezekre leginkább sok évvel ezelőtt kitalált algoritmusokat használunk. Arra volnék kiváncsi, hogy van arra bizonyitási módszer, hogy egy adott algoritmusnál nincs jobb ? Pl. rendezésre a QuickSort a leggyorsabb (azt hiszem). De bizonyitható, hogy ennél nem lehet gyorsabbat kitalálni ? Vagy pl. rendezett bináris fában való keresésre nem lehet gyorsabbat kitalálni, mint azt, hogy "balra és jobbra nézek, majd  ennek ismeretében valamelyik irányba egy szintet lejebb megyek, stb." ?

    üdv, PedroIsmerőse
    Mutasd a teljes hozzászólást!
Címkék
abcd