N Királynő-probléma avagy "A lustaság fél egészség"

Ebben a blog bejegyzésben azt boncolgatom, hogy egy egyszerű algoritmust hogyan lehet hatékonyabbá tenni. Mindehhez nem kell más, csak egy kis lustaság! ;)

Vigyázat funkcionális programozást tartalmaz és egyébként is túl hosszú, ne olvasd el!

Nagyon jó előadások a témában:
Let’s Get Lazy—The Real Power of Functional Programming - Venkat Subramaniam
Laziness is the Ultimate Sophistication, both in Life and in Programming - Venkat Subramaniam

Hozzászólások

Nekem ilyesmik meg a kezdeti programozoi oraim alatt voltak - egy nagyon jo tanarral. Az akkori feldat olyasmi volt hogy hogyan lehet egy sakktablat lougrassal bejarni, hogy a vegen minden kockara lepjen egyszer... Szerintem ez kialt a rekurziv fuggvenyhivasert... Kiralyno letesz -> (van utkozes?) NEM: -> hivja a kiralyno letesz / IGEN: Rekurzio visszalep -> Kiralyno mashova.

Nagyvonalakban barmifele programnyelvet, semantikat es hibakezelest hanyagolva valahogy igy:

Kiralyno_letesz(pozicio)
if Pozicio=MAX
Print(osszes pozicio)
Programvege :)
if Nincs Utkozes
Kiralyno_letesz (Pozicio+1)
Pozicio = Uj_Pozicio
END

Jó is a rekurzió, amíg elég erős hozzá a számítógép,van elég memória meg elég nagy a verem is. Volt már, hogy olyan eszközre írtam egy kétszereplős játékot, ahol nem csak a rekurzió volt lehetetlen, hanem, ha túl sokáig futott a ciklus, akkor is lehalt az egész :) (watchdog timeout). Ami végül sikerült, rohadt lassú lett, de nem is az volt a lényeg, hanem, hogy működött :) . Igaz vagy 3 évbe került, bár ebből 2.9 év arra ment el, hogy elodázzam, aztán kényszerszabadságon lett rá időm :D

Jó is a rekurzió, amíg elég erős hozzá a számítógép,van elég memória meg elég nagy a verem is.

Tisztán funkcionális nyelveken nincsenek ciklus utasítások, mivel kiválthatók rekurzív függvényhívással.
Ha jól van megírva egy rekurzív függvény (FP nyelveken), lásd Tail Call, akkor a fordító ki tudja optimalizálni (Tail call Optimization) és gyakorlatilag egy ciklusként fut le.

"Míg a szorgalmas szépen csinálja egymás után a feladatait, amíg nem végez, a lusta ezzel szemben mindig csak azt a feladatát csinálja, ami már végképp nem tűr halasztást, így a lusta a kitűzött idő alatt a legfontosabb munkáit megcsinálta, míg a szorgalmas nem."

Egy programozó, aki egyből nekiáll, és "szépen csinálja egymás után a feladatait", de nem veszi előre azt, amelyik határideje a legsürgetőbb, az nem szorgalmas, hanem hülye.
Egy programozó, aki csak akkor áll neki valaminek, amikor az "már végképp nem tűr halasztást", szintén nem csak lusta, hanem hülye, mert jól megszívja, amikor felmerül egy előre nem látott probléma, vagy, mivel a rugalmasság a végén szempont volt, ha váratlanul kap egy plusz feladatot szűk határidővel.

"Ezen túlmenően még olyan extrém elvárást is könnyen megoldhatunk, mint pl. olyan három megoldás érdekel, amelyiknél az 1., 5. és 7. sorban levő királynő oszloppozícióinak szorzata nagyobb, mint 80 [...] Ezt az imperatív megoldásnál csak nagy átalakítások után tudnánk elérni."

Imperatív megoldásnál csak egy ciklus kell, ami végigmegy a megoldásokon, és eldönti, hogy melyik megoldás kell és melyik nem. foreach esetén két if, hagyományos for esetén akár egy if is elég lehet. Nem egy sor kód, az igaz, de nagyon messze van attól, hogy "nagy átalakítások"-nak lehessen nevezni.

"Még, ha ugyanannyi lépésből is megtalálja a megoldást, akkor is több idő alatt teszi meg.
Nagyobb a memória használata, mivel az egyes félbehagyott, elvégzendő funkciókat is tárolnia kell.
"

Tehát akkor "hatékonyabb" az pont nem lett.

Egy programozó, aki egyből nekiáll, és "szépen csinálja egymás után a feladatait", de nem veszi előre azt, amelyik határideje a legsürgetőbb, az nem szorgalmas, hanem hülye.

A blogban szereplő lusta és szorgalmas definíciója és természete nem egyezik meg teljesen a valósággal, de azért vannak közös pontok. Próbálj meg elvonatkoztatni a valóságtól és próbáld elfogadni a cikkben szereplő definíciókat! Ha segít, akkor a szorgalmas helyett használd a stréber, ügybuzgó, ... szavakat.

Imperatív megoldásnál csak egy ciklus kell, ami végigmegy a megoldásokon,

A ciklus akkor tud végigmenni a megoldásokon, ha már mind megvan. Épp ez az egyik lényege, hogy nem kell minden megoldást kiszámolnunk, csak éppen annyit amely a támasztott extrém feltételeket kielégíti. Ezt előre nem tudod megmondani, hogy mennyi lesz, így a "csak egy ciklus kell" algoritmusnak és a backtrack algoritmusnak mindenképp kommunikálniuk kell. Ha ilyen egyszerű, azt az egy foreach-et és két if-es algoritmust megadhatnád a wikipédiás C-s példához.

Tehát akkor "hatékonyabb" az pont nem lett.

A Javított brute-force algoritmusnál lett hatékonyabb a Lusta, javított brute-force. A backtrack-nél nem lett hatékonyabb, ugyanolyan hatékony lett, ugyanannyi lépésből találja meg az első megoldást (ugyanaz a nagy ordója).

Sose szerettem a párhuzamaidat és hasonlataidat :)

"A ciklus akkor tud végigmenni a megoldásokon, ha már mind megvan. Épp ez az egyik lényege, hogy nem kell minden megoldást kiszámolnunk, csak éppen annyit amely a támasztott extrém feltételeket kielégíti"

Ez igaz, ezt nem vettem figyelembe.