Oszd meg és uralkodj (számítástechnika)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. január 4-én felülvizsgált verziótól ; az ellenőrzések 22 szerkesztést igényelnek .

Az oszd meg és uralkodj a számítástechnikában egy olyan  algoritmusfejlesztési paradigma , amely abból áll, hogy a megoldandó problémát rekurzív módon két vagy több azonos típusú, de kisebb méretű részfeladatra bontják, és ezek megoldásait kombinálják, hogy választ kapjanak az eredeti problémára; a partíciókat addig hajtják végre, amíg az összes részfeladat elemi nem lesz.

Az Oszd meg és uralkodj algoritmusok megértése és tervezése összetett készség, amely megköveteli a megoldandó mögöttes probléma természetének jó megértését. Mint a tétel matematikai indukcióval történő bizonyításakor , a rekurzió inicializálásához gyakran szükséges az eredeti problémát egy általánosabb vagy összetettebb problémával helyettesíteni, és nincs szisztematikus módszer a helyes általánosítás megtalálására. Az Oszd meg és uralkodj módszer ilyen bonyolultságai akkor láthatók, ha a Fibonacci -szám kiszámítását hatékony kettős rekurzióval optimalizáljuk.

Az „Oszd meg és uralkodj” paradigmát követő algoritmus helyességét leggyakrabban a matematikai indukció módszerével igazoljuk, és a futási időt vagy a megfelelő ismétlődő egyenlet közvetlen megoldásával , vagy a fő ismétlődési összefüggéstétel alkalmazásával határozzuk meg .

Oszd meg és uralkodj

Az Oszd meg és uralkodj paradigmát gyakran használják egy adott probléma optimális megoldásának megtalálására. Fő gondolata, hogy egy adott problémát két vagy több hasonló, de egyszerűbb részproblémára bont, ezeket egyenként oldja meg, és összeállítja a megoldásaikat. Például egy adott, n természetes számból álló lista rendezéséhez fel kell osztania két , egyenként kb. n /2 számot tartalmazó listára, sorba kell rendezni mindegyiket, és mindkét eredményt ennek megfelelően rendezni, hogy megkapja a lista rendezett változatát ( lásd az ábrát). Ez a megközelítés összevonási rendezési algoritmusként ismert .

Az „Oszd meg és uralkodj” elnevezést néha olyan algoritmusokra alkalmazzák, amelyek minden problémát csak egy részproblémára redukálnak, mint például a bináris keresési algoritmus , amely egy bejegyzést keres egy rendezett listában (vagy annak speciális esete, a felező algoritmus a gyökerek megtalálásához). [1] Ezek az algoritmusok hatékonyabban implementálhatók, mint az általános Oszd meg és uralkodj algoritmusok; különösen, ha farokrekurziót használnak, egyszerű hurkokká alakíthatók . E tág definíció szerint azonban minden rekurziót vagy hurkot használó algoritmus "oszd meg és uralkodj" algoritmusnak tekinthető. Ezért egyes szerzők úgy vélik, hogy az „Oszd meg és uralkodj” elnevezést csak akkor szabad használni, ha minden feladat két vagy több részfeladatot eredményezhet. [2] Ehelyett a redukálás és hódítás elnevezést javasolták az egyedi problémák osztályára. [3]

Példák

Az ilyen algoritmusok korai példái elsősorban a „Csökkentsd és uralkodj” – az eredeti probléma szekvenciálisan különálló részproblémákra oszlik, és valójában iteratív módon is megoldható.

A bináris keresésnek, a "Csökkentsd és uralkodj" algoritmusnak, amelyben a részproblémák nagyjából feleakkora az eredeti méret, hosszú története van. Bár a számítógépeken alkalmazott algoritmus egyértelmű leírása már 1946-ban megjelent John Mauchly cikkében . Az a gondolat, hogy a keresés megkönnyítése érdekében a tételek rendezett listáját használjuk, legalábbis Babilóniáig nyúlik vissza, ie 200-ban. [4] Egy másik ősi redukálás és meghódítás algoritmus az Euklidész algoritmusa két szám legnagyobb közös osztójának kiszámítására a  számok kisebb és kisebb ekvivalens részproblémákra való redukálásával, amely több évszázaddal ezelőttre nyúlik vissza.

A több részproblémát tartalmazó Oszd meg és uralkodj algoritmus korai példája a Gauss -féle (1805) leírása annak, amit ma Cooley-Tukey gyors Fourier transzformációnak neveznek [5] .

Egy korai két részproblémából álló Oszd meg és uralkodj algoritmus, amelyet kifejezetten számítógépekhez terveztek és megfelelően elemeztek, a   Neumann János által 1945-ben feltalált egyesítési rendezési algoritmus. [6]

Tipikus példa erre az összevonási rendezési algoritmus . Egy számtömb növekvő sorrendbe rendezéséhez azt két egyenlő részre osztja, mindegyiket rendezi, majd a rendezett részeket egyesíti. Ezt az eljárást mindaddig alkalmazzuk az egyes részekre, amíg a tömb rendezendő része legalább két elemet tartalmaz (így két részre bontható). Ennek az algoritmusnak a futási ideje műveletek, míg az egyszerűbb algoritmusok időigényesek, ahol  az eredeti tömb mérete.

Egy másik figyelemre méltó példa az Anatolij Alekszandrovics Karatsuba által 1960-ban feltalált algoritmus [7] , amely n számjegyből két számot megszoroz  a műveleti számmal ( nagy O jelölés ). Ez az algoritmus megcáfolta Andrej Kolmogorov 1956-os hipotézisét, amely szerint ez a feladat műveleteket igényel.

Egy másik példa az Oszd meg és uralkodj algoritmusra, amely eredetileg nem használt számítógépeket. Donald Knuth egy , a posta által általánosan használt módszert ad a levelek továbbítására: a leveleket külön csomagokba rendezik, amelyeket különböző földrajzi területekre szánnak, és ezeket a csomagokat maga is csoportokba rendezi kisebb alrégiók számára, és így tovább, amíg meg nem érkezik. [4] Ez a radix sort -hoz kapcsolódik, amelyet már 1929 -ben leírtak a lyukkártya-válogató gépeknél . [négy]

Előnyök

Összetett problémák megoldása

Az Oszd meg és uralkodj egy hatékony eszköz a fogalmilag összetett problémák megoldására: mindössze egy esetet kell találni a probléma részproblémákra bontására, triviális esetek megoldására és a részproblémák eredeti problémába való kombinálására. Hasonlóképpen, a Reduce and Conquer csak egy kisebb problémára csökkenti a problémát, például a klasszikus Hanoi-toronyra , amely az n magasságú torony mozgatásának megoldását egy n − 1 magasságú torony mozgatására redukálja.

Algoritmus hatékonysága

Az Oszd meg és uralkodj paradigma gyakran segít a hatékony algoritmusok felfedezésében. Ez volt a kulcsa például a Karatsuba gyors szorzási módszerének, a gyorsrendezési és összevonási algoritmusoknak, a Strassen -féle mátrixszorzási algoritmusnak és a gyors Fourier-transzformációknak.

Ezekben a példákban az Oszd meg és uralkodj megközelítés a megoldás aszimptotikus költségének javulását eredményezte magában a megoldásban. Például, ha (a) az alapesetnek egy konstans által határolt mérete van, akkor a probléma particionálása és a részmegoldások kombinálása arányos az n problémamérettel, és (b) korlátozott számú p részprobléma van. méret ~n/p minden szakaszban, akkor az algoritmus hatékonysága " Oszd meg és uralkodj O( n  log p n ).

Egyidejűség

Az Oszd meg és uralkodj algoritmusok természetesen alkalmasak többprocesszoros gépeken való futtatásra, különösen megosztott memória rendszereken , ahol a processzorok közötti adatátvitelt nem kell előre ütemezni, mivel az egyes részfeladatok különböző processzorokon futhatnak.

Memória hozzáférés

Az Oszd meg és uralkodj algoritmusok természetesen általában hatékonyan használják a gyorsítótárat . Ennek az az oka, hogy ha egy részfeladat már elég kicsi, akkor azt és az összes részfeladatot elvileg meg lehet oldani a gyorsítótárban anélkül, hogy hozzáférnének a lassabb fő memóriához. A gyorsítótár ilyen módon történő használatára szolgáló algoritmust cache-obliviousnak nevezik , mivel nem tartalmazza a gyorsítótár méretét explicit paraméterként. [8] Ezenkívül az Oszd meg és uralkodj algoritmusok megtervezhetők úgy, hogy a fontos algoritmusok (pl. rendezés, FFT és mátrixszorzás) optimális gyorsítótár-feledést jelentő algoritmusokká váljanak – a gyorsítótárat valószínűleg optimális módon, aszimptotikus értelemben használják, függetlenül attól, hogy gyorsítótár méretű. Ezzel szemben a gyorsítótár használatának hagyományos megközelítése a blokkolás, mint például a beágyazott hurok optimalizálásnál , ahol a feladat kifejezetten megfelelő méretű darabokra van felosztva – ez is optimálisan tudja használni a gyorsítótárat, de csak akkor, ha az algoritmus egy adott gyorsítótárméretre van hangolva. egy adott gépről.

Ugyanez az előny más hierarchikus tárolórendszereknél, mint például a NUMA vagy a virtuális memória , valamint a több szintű gyorsítótár esetében: ha egy részprobléma elég kicsi, akkor a hierarchia azon szintjén belül megoldható anélkül, hogy hozzáférne a magasabb (magasabb lassú) szintekhez. .

Alkalmazási problémák

Rekurzió

Az Oszd meg és uralkodj algoritmusokat természetesen rekurzív módszerek formájában alkalmazzák . Ebben az esetben az éppen megoldandó feladathoz vezető privát részfeladatok automatikusan az eljáráshívási veremben tárolódnak . A rekurzív függvény egy numerikus argumentum numerikus függvénye, amely önmagát tartalmazza a jelölésében.

Explicit verem

Az Oszd meg és uralkodj algoritmusokat nem rekurzív programok is alkalmazhatják, amelyek a privát részproblémákat valamilyen explicit adatstruktúrában tárolják, például veremben , várólistákban vagy prioritási sorokban . Ez a megközelítés nagyobb szabadságot tesz lehetővé a következő részproblémák kiválasztásában. Egyes alkalmazásokban fontos funkció - például az elágazás és a funkciók optimalizálása érdekében történő összekapcsolás módszerében . Ez a megközelítés olyan programozási nyelvekben is szabványos, amelyek nem támogatják a rekurzív eljárásokat.

Verem mérete

Az Oszd meg és uralkodj algoritmusok rekurzív megvalósításainál gondoskodni kell arról, hogy elegendő memória legyen lefoglalva a rekurziós verem számára, különben a végrehajtás meghiúsulhat a verem túlcsordulása miatt . Az időhatékony Oszd meg és uralkodj algoritmusok gyakran viszonylag sekély rekurziós mélységgel rendelkeznek. Például egy gyorsrendezési algoritmust úgy is meg lehet valósítani, hogy soha nem igényel több mint log2 n beágyazott rekurzív hívást n elem rendezéséhez.

A veremtúlcsordulást nehéz lehet elkerülni rekurzív rutinok használatakor, mivel sok fordító azt feltételezi, hogy a rekurziós verem szomszédos a memóriában, és egyesek meghatározott mennyiségű helyet foglalnak le számára. A fordítók a feltétlenül szükségesnél több információt is tárolhatnak a rekurziós veremben, például a visszatérési címet, a megváltoztathatatlan paramétereket és az eljárások belső változóit. Így a verem túlcsordulás kockázata csökkenthető a rekurzív eljárás paramétereinek és belső változóinak minimalizálásával, vagy explicit veremstruktúra használatával.

Az alapbeállítások kiválasztása

Bármely rekurzív algoritmusban jelentős szabadság van az alapesetek, a kis részproblémák kiválasztásában, amelyeket közvetlenül a rekurzió befejezése érdekében oldanak meg.

A lehető legkisebb vagy legegyszerűbb alapeset kiválasztása elegánsabb, és általában egyszerűbb programokat eredményez, mivel kevesebb a mérlegelendő eset és könnyebben megoldható. Például az FFT leállíthatja a rekurziót, ha a bemenet egyetlen minta, és a lista gyorsrendezési rendezési algoritmusa leállhat, ha a bemenet üres lista; mindkét példában csak egy alapesetet kell figyelembe venni, és azt nem kell feldolgozni.

Másrészt a hatékonyság gyakran javul, ha a rekurzió viszonylag nagy alapeseteknél megáll, és ezeket nem rekurzív módon oldjuk meg, ami egy hibrid algoritmust eredményez . Ez a stratégia elkerüli az átfedő rekurzív hívásokat, amelyek alig vagy egyáltalán nem működnek, és lehetővé teszi speciális, nem rekurzív algoritmusok használatát is, amelyek ezekben az alapvető esetekben hatékonyabbak, mint az explicit rekurzió. Az egyszerű hibrid rekurzív algoritmus általános eljárása az alapeset rövidre zárása, más néven karnyújtásnyi rekurzió . Ebben az esetben a függvény meghívása előtt ellenőrizzük, hogy a következő lépés az alapregiszterhez vezet-e, elkerülve a szükségtelen függvényhívást. Mivel az Oszd meg és uralkodj algoritmus végül a probléma vagy részprobléma minden egyes példányát nagyszámú alappéldányra redukálja, gyakran ezek uralják az algoritmus általános hatékonyságát, különösen akkor, ha a felosztás/csatlakozás többletterhelése alacsony. Ezenkívül ezek a megfontolások nem függnek attól, hogy a rekurziót a fordító vagy egy explicit verem valósítja-e meg.

Így például a gyorsrendezés számos könyvtári alkalmazása egyszerű hurok alapú beillesztési rendezési algoritmussá (vagy hasonlóvá) válik, amint a rendezendő elemek száma kellően kicsi. Sőt, ha egy üres lista lenne az egyetlen alapeset, akkor egy n bejegyzést tartalmazó lista rendezése legfeljebb n számú gyorsrendezési hívást eredményezne, amelyek nem tesznek mást, mint azonnal visszatérnek. Az alapesetek 2-es vagy annál kisebb méretűre növelése megszünteti a legtöbb ilyen „ne csinálj semmit” hívást, és általában a 2-nél nagyobb alapeseteket általában a takarítással vagy a halomkezeléssel töltött idő arányának csökkentésére használják.

Alternatív megoldásként nagy alapesetek is használhatók, amelyek továbbra is az Oszd meg és uralkodj algoritmust használják, de az algoritmust egy előre meghatározott fix méretű halmazhoz valósítják meg, ahol az algoritmus teljesen kibővíthető olyan kóddal , amely nem tartalmaz rekurziót, ciklusokat vagy konvenciókat (kapcsolódó részleges értékelés módszerével ). Ezt a megközelítést például néhány hatékony FFT-alkalmazásban használják, ahol az alapesetek az Oszd meg és uralkodj FFT-algoritmusok kiterjesztett implementációi egy rögzített méretkészlethez. [9] A forráskód-generálási technikák felhasználhatók a stratégia hatékony megvalósításához szükséges nagyszámú különálló alapeset létrehozására.

Ennek az ötletnek egy általánosított változatát „bővítési” vagy „növekedési” rekurziónak nevezik, és különféle módszereket javasoltak az alapeset-kiterjesztési eljárás automatizálására. [9]

Ismétlődő részfeladatok megosztása

Egyes feladatoknál az elágazó rekurzió ugyanazon részfeladat többszöri kiértékelését eredményezheti. Ilyen esetekben érdemes lehet azonosítani és tárolni a megoldásokat ezekre az átfedő részproblémákra, ez a technika, amelyet általában memoizálásként ismernek . A határértéket betartva ez alulról felfelé építkező Oszd meg és uralkodj algoritmusokhoz vezet, mint például a dinamikus programozás és a diagramelemzés .

Lásd még

Jegyzetek

  1. ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Bevezetés az algoritmusokba  (neopr.) . - MIT Press , 2009. - ISBN 978-0-262-53305-8 .
  2. ↑ Brassard, G. és Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. ↑ Anany V. Levitin, Bevezetés az algoritmusok tervezésébe és elemzésébe (Addison Wesley, 2002).
  4. ↑ 1 2 3 Donald E. Knuth, The Art of Computer Programming: 3. kötet, Sorting and Searching , második kiadás (Addison-Wesley, 1998).
  5. ↑ Heideman, MT, DH Johnson és CS Burrus, „ Gauss és a gyors Fourier-transzformáció története Archiválva : 2020. július 31. a Wayback Machine -nél ”, IEEE ASSP Magazine, 1, (4), 14–21 (1984).
  6. ↑ Donald Knuth . A számítógépes programozás művészete : 3. kötet Rendezés és keresés  . - 1998. - P. 159. - ISBN 0-201-89685-0 .
  7. ↑ Karatsuba, Anatolii A. ; Yuri P. Ofman . Többértékű számok szorzása automatákon  (neopr.)  // A Tudományos Akadémia jelentései . - 1962. - T. 146 . - S. 293-294 . Fordította: Többjegyű számok szorzása automatán   // Szovjet fizika Doklady : folyóirat. - 1963. - 1. évf. 7 . - P. 595-596 .
  8. ↑ M. Frigo; CE Leiserson; H. Prokop. Gyorsítótárat nem felejtő algoritmusok  (neopr.)  // Proc. 40. Symp. a számítástechnika alapjairól. – 1999.
  9. ↑ 1 2 Frigo, M.; Johnson, SG  Az FFTW3 tervezése és megvalósítása  // Proceedings of the IEEE : folyóirat. - 2005. - február ( 93. évf. , 2. sz.). - P. 216-231 . - doi : 10.1109/JPROC.2004.840301 .

Irodalom

Linkek