tifyty

pure Java, what else ?

Mese az ügyféligényről és a numerikus módszerekről

Történt valamikor a rendszerváltás után, amikor a jó állami vállalatok sorban mentek tönkre meg privatizálódtak, és úgy általában átalakultak, hogy egy ismerősöm elvesztette a munkáját. Mihez kezdjen ötven fölött egy alkalmazott fizikus, aki addig egy nagyvállalat óvó szárnyai alatt fejlesztette a hardvert és a hozzátartozó szoftvert? Keresett valami hasonlót. Több kitérő után eljutott egy olyan céghez, amelyik feltehetően szintén valamely korábbi szocialista nagyvállalat romjain kivirágzott rózsa volt, és akik külföldi piacra geológia szoftvert fejlesztettek. Lehet, hogy geodéziai, ami persze nem mindegy, hiszen Descartes sem azt mondta, hogy “coito ergo sum”, pedig mondhatta volna. A mi kis történetünk szempontjából viszont mindegy.

Főhősünk kapott egy feladatot, hogy optimalizáljon egy numerikus számítási kódrészletet, amelyik akkori állapotában kb. 24 órát futott egy szokásos PC-n, és azt szerették volna, hogy 8 órán belül lefusson. Ha ugyanis több, mint 8 óra, akkor a felhasználó elindítja, és aznap már nincs készen. Ha viszont 8 órán belül van, akkor egy nap az előző futás eredménye alapján akár rögtön elindíthat egy második számítást. Ha hat óra, vagy öt: akkor sem jobb. Négy órára leszorítani pedig a 24-ről nem tűnt reálisnak.

Valószínűleg nem nagyon számítottak rá, hogy az “öreg” fizikus megoldja a dolgot, hiszen eddig sem a programozás volt a fő területe, bár alkotott programokat, de clean code és társai olyan messze voltak tőle, mint a finn mezei nyúltól az Alpha-Centauri. De a programok működtek, és ha nem csapatban kell dolgozni, és nem túl méretes a kód, akkor az optimalizálás komolyabb szakértelem híján try and fail módszerrel is olvashatatlan, karbantarthatatlan, de működő és valamelyest gyorsabb kódot eredményezhet. Programot akár gyárthatunk úgy is, hogy teszteljük a futási eredményeket, és addig rakunk össze random karaktereket, amíg egyszer csak olyan fájlt kapunk, ami lefordul, és azt is csinálja amit szeretnénk. Ha Shakespeare szonátát lehetett így előállítani, programot miért ne lehetne. Csak sok virtuális majom kell.

Szóval a fizikus leült egy asztalhoz, és nekiállt tanulni. Megtanulta, hogy mit csinál a cég, mit csinál a szoftver, mi mögötte a fizika, és addig számolt, amíg rájött, hogy ezt a numerikus számolást, ami a program aktuális változatában 24 órát futott meg lehet oldani zárt képlettel. Ugyan kibabrált durva nagy az a képlet, de a számítás futási ideje még így is inkább az ezredmásodperc környékére esett, semmint a 86,400 másodperc közelébe. Boldogan vitte be a főnökéhez, aki a következőket mondta:

  • Ez nagyon jó, csak az eredmény nekünk két hét alatt kellett volna, mostanra meg eltelt három hónap.
  • Az ifjú titánok közben leszorították az eredeti algoritmus futási idejét hét és fél órára különböző programozási trükkökkel, és a nemzetközi vásárra ki is ment ez a release.
  • A következő release fél év múlva lesz.
  • Ha a számítási idő ilyen nagyon rövid, akkor a vevők nem fogják elhinni, hogy ez egy komoly számítás, és hamarosan nem lesznek hajlandók prémium árat fizetni a modulért.
  • Persze a munka nem volt haszontalan, mert majd bekerül a következő release-be, és az ifjú titánok írnak köré egy kis kódot, ami vár, meg forgatja a homokórát, hogy hihető legyen, hogy sokáig számol. Viszont ha a konkurencia kijön egy gyorsabb változattal, pillanat alatt leveszünk a várakozási időből, és megint mi vagyunk a nyerők.

Természetesen nem szó szerint idéztem, hiszen nem voltam ott, és közel húsz éve történt a dolog, inkább tessék úgy felfogni, mint egy mesét. De azért a mese tanulságos!

Hogy történt, hogy rá sem néztek az új kollégára három hónapig? (Ez már nem nagy szoci vállalat volt, hanem kis magyar Kft.) A kultúra folytonos.

Az “ügyfél” által adott feladat leírása, megfogalmazása nem fedte az igazi ügyféligényt. És ez általában mindig így van. Általában. Mindig.

Ha fizikai modellekkel dolgozunk, akkor jobb ha a csapatban kezdetektől van valaki aki matematikus, fizikus. De általánosan is igaz: ha XXX modellel dolgozunk, jobb ha a csapatban van a kezdetektől XXX-hez értő szakember. Ne gondoljuk, hogy majd mi értünk hozzá. Mi a clean code-hoz értünk.

És akkor most levezetésnek itt egy programozási feladat, ha valaki még emlékszik a középiskolás fizikára, és a numerikus módszerekre. Semmi köze a fenti meséhez (á, dehogy), hacsak ki nem derül, hogy hazudok.

Adott egy inga, a hossza L, földi környezetben, ahol konstans a nehézségi gyorsulás, vagyis L elég kicsi ahhoz, hogy a gyorsulás ne függjön attól, hogy mennyire tér ki az inga: nem kisebb a nehézségi gyorsulás akkor sem, amikor kitér az inga, és ezért távolabb van éppen a föld tömegvonzási központjától.

Az inga végén a tömeg pontszerű. Nincs légellenállás, és az inga nulla tömegű, teljesen rugalmatlan szálon lóg. Nem kell figyelembe vennünk semmilyen torziós erőt.

Meglökjük az ingát a nyugalmi helyzetében, olyan sebességgel elindítva, hogy az inga túljut a vízszintes helyzeten, de nem éri el a körpálya tetejét, hanem egy ponton elhagyja a körpályát, és parabola pályán repül, majd egy ponton újra eléri a körpályát.

Írjunk programot, amelyik kiszámolja, hogy ha ismerjük, hogy hol hagyja el az inga a körpályát, akkor hol fog visszatérni!

Bónuszkérdés: Miért éppen a finn nyulakat emlegettem? Mi a helyzet a nem őshonos, behurcolt ausztrál nyulakkal? (A juhokkal, meg a lámákkal már foglalkoztunk eleget.)

23 responses to “Mese az ügyféligényről és a numerikus módszerekről

  1. S.E. május 24, 2013 11:37 de.

    De hát ehhez kéne fizikául tudni…ennyire meg már nem tudok. Talán soha nem is tudtam…

  2. Pipogya május 24, 2013 4:49 du.

    A juhok, a lámák és a manufaktúrák emlékére majd egyszer itt http://www.theslaughteredlambpub.com/ áldozunk egy-két sörrel. Rip.

  3. Peter Verhas május 24, 2013 6:02 du.

    A bónuszkérdésre tényleg várok választ. De a numerikus feladatnak is neki lehet ugrani, néha nem árt egy kicsit kitekinteni az elefántcsont toronyból.

  4. zuzmo május 25, 2013 9:07 de.

    miért nem az kérdezted, milyen sebesség mellett történhet ez meg? 🙂
    mellesleg nem értem, ez miért numerikus feladat, hisz egzakt analitikusan is megoldja a dgy-nél első hónapban bárki 🙂

  5. Kofa május 27, 2013 8:47 du.

    Bachd meg, Shakespeare szonetteket írt, nem szonátákat! 🙂

  6. Hollosi Jozsef május 28, 2013 2:11 de.

    “Ki az a dgy?”

    Dávid Gyula https://fizika.elte.hu/hu/index.php?page=munkatars&tid=1&id=23

    Gyula egy “intézmény”, nagyjából minden ELTE-n végzett fizikusnak valamilyen módon van köze hozzá, gólyatáboroktól és kirándulásoktól kezdve különféle versenyeken át a vízválasztó vektorszámítás gyakorlatokig, ahol nagyjából az első félévben eldőlt, ki fog fizikusként végezni, és ki nem.

    Galilei után szabadon:

    Ami mérhető, azt mérd meg,
    Ami nem mérhető, azt számold ki,
    Amit nem tudsz kiszámolni, azt dgy adta fel hazifeladatnak! 😉

  7. lsm május 29, 2013 12:00 de.

    Tanulságos történet… egyszer volt, hol nem volt, volt egyszer olyan is, hogy egy új fejlesztést azért kezdtek el, mert a megoldás elképesztően lassú volt. Amikor már félig kész volt az új szoftver, valamelyik birkapásztor lemászott a szakadék mélyére a cache tövisei közé, és talált vala egy akkora hibát, amit kiküszöbölve a szoftver megtáltosodott. De mivel az új programra már sokan vártak és sok befektetett pénz volt benne, így ezt a feature-t a fent vázoltaknak megfelelően oldotta meg a menedzsment. (Végeredményben jobb lett az új, de e gond nélkül valszeg el se kezdték volna.)

  8. Bartók István június 3, 2013 1:45 du.

    Ez beugratós feladat?
    Túl könnyűnek tűnik…

    Abból, hogy hol hagyja el a körpályát, kiszámolható a sebessége azon a ponton (zárt képlettel).
    Ebből, és az irányszögből meghatározható a parabola pálya egyenlete, ami szerint tovább esik.
    A kör is felírható egyenlettel.
    Innentől triviális…

    • Peter Verhas június 3, 2013 2:07 du.

      Ha triviális, akkor miért nincs itt a válasz?

      • Bartók István június 3, 2013 2:14 du.

        Ez alapján a gondolatmenet alapján levezethető X idő alatt (teszteléssel együtt 1-2 órának tippelem).
        A gondolatmenetre rászántam pár percet, de a részletes levezetésre az 1-2 órát most nem tudom rászánni – ezért nincs pontos válasz.

        • Peter Verhas június 3, 2013 2:25 du.

          Ezek szerint mégsem triviális. 1-2 óra az már nem triviális, annyi idő alatt sok minden előjöhet. Bizonyára sokan tudják, hogy a nagy Fermat sejtés eredeti cetlijének az oldalára Fermat odaírta: ennek a bizonyítása olyan egyszerű, hogy le sem írom. Azóta sem tudják, hogy tudott-e egy triviális megoldást, amit azóta sem sikerült megtalálni a matematikusoknak, vagy csak hitte, hogy tud egy megoldást, vagy csak trollkodott. (Talán nem haragszol meg a párhuzamért, nem akárkihez hasonlítottalak.)

          Ugyanakkor annak, aki rászánja az időt ennek a feladatnak a megoldására, nagyon tanulságos. Csak, hogy fokozzam a drámát: ha figyelmesen elolvasod ami ezen az oldalon szerepel, akkor elolvashatod a megoldást is. És még így sem triviális.

          Én annak idején még gimnazista koromban édesapám segítségével számoltam végig. Az történt, hogy a Runge-Kutta módszer kipróbálásához jó feladatnak tűnt a fenti, és amikor kirajzoltattam az eredményt, akkor gyanús lett, hogy van erre analitikus, szép megoldás.

          Amúgy a kör egyenlete másodfokú, a parabola is másodfokú, amiből adódóan a kettő metszéspontjai általános esetben negyedfokú egyenletrendszert jelentenek, ami már nem garantáltan oldható meg zárt képlettel. De a feladat még továbbra is nyitott!

          • Bartók István június 3, 2013 2:50 du.

            Ha nem is általános zárt képlet, de az a sejtésem hogy az adott feladatban a két másodfokú görbe metszéspontját elég könnyen meg tudjuk találni. Ha másképp nem, akkor felosztjuk a problémateret (a kört 4 negyedre).

            Ezt jelentené a “triviális” (ki van találva, már csak csinálni kell).
            Plusz ez egy vicc a gráfelmélet tanárunktól: olyanra mondani hogy triviális, ami azért nem teljesen az (kinek mi a triviális:).

            De valóban, még így is lehet hogy közben bonyolultabb dolgokba fut bele az ember mint az ilyen messziről tűnik.

          • Verhás István november 7, 2013 3:13 de.

            “amit azóta sem sikerült megtalálni a matematikusoknak”? Mármint a triviális és egyszerű bizonyítást? Azt nem, de Andrew Wiles-nak 1994-ben sikerült bizonyítania http://hu.wikipedia.org/wiki/Nagy_Fermat-t%C3%A9tel .

  9. Bence június 14, 2013 10:44 de.

    – Ondólkodom, tehát vagyok – szóla Descartes, majd a következő business requirementet támasztá: http://thedailywtf.com/Articles/The-Slow-Down-Loop.aspx

  10. Márton augusztus 14, 2013 11:16 de.

    Én ugyan matematikus vagyok, szóval a clean code viszonylatában megáll az Alpha Centauri hasonlat, viszont a finn nyulak pár tízezer km-rel távolabb vannak tőle, mint ausztrál társaik. Akkor is, ha ez beleesik a 4,635 + 0,007 fényév távolság hibahatárába.

  11. Laszlo Simon szeptember 28, 2013 2:26 du.

    Kicsit bosszant a dolog, mert nem találok nagyon szép megoldást:(
    Ami triviálisnak tűnik: nyilván ott válik el az ellipszispálya a körtől, ahol a függvényérték, az első deriváltja, de még a második is megegyezik. (Ezt fizikailag is érteni vélem: pozíció, sebesség, gyorsulás, a centrifugális gyorsulás éppen megszűnik stb). Szóval ez ad három egyenletet, ezekből a parabola a,b,c paramétere x0-val kifejezhető. (Kényelemből y0-t is használom, de még a tga = x0/y0-t is). És akkor a parabola és a kör különbségének a négyzete viszonylag kellemes negyedfokú fv. lesz. Mivel ott, ahol a kört elhagyta, ennek inflexiója lesz, megelégszik két megoldással (ahogy fizikailag várjuk is). A legmezeibb Newton-Raphsonnal x=1.0-ból iterálható.
    Nagyon érdekes, hogy pont x0=0,5-nél van a szélsőértéke, és Excelben kirajzolva egy harmad-, vagy negyedfokú polinomra hajaz, de tovább nem jutottam…

    public class Inga {
        static double a, b, c;
    
        // kör és parabola különbségének a négyzete
        static double diffSqr(double x) {
            return ((a * x * x + b * x + c) * (a * x * x + b * x + c) - 1 + x * x);
        }
    
        // a fenti fv deriváltja
        static double diffSqrDeriv(double x) {
            return (2 * x + 2 * (2 * a * x + b) * (a * x * x + b * x + c));
        }
    
        public static void main(String[] args) {
            double x0, y0, tga, xn, yn;
            for (x0 = -0.99; x0  0.001) {
                    xn -= diffSqr(xn) / diffSqrDeriv(xn);
                    yn = diffSqr(xn);
                }
                System.out.println(x0 + "\t" + xn);
            }
        }
    }
    
  12. Laszlo Simon szeptember 28, 2013 2:30 du.

    Bocs, de a kódból egy rész eltűnt (????)
    Itt van a teljes kód:

    public class Verhas {
        static double a, b, c;
    
        // kör és parabola különbségének a négyzete
        static double diffSqr(double x) {
            return ((a * x * x + b * x + c) * (a * x * x + b * x + c) - 1 + x * x);
        }
    
        // a fenti fv deriváltja
        static double diffSqrDeriv(double x) {
            return (2 * x + 2 * (2 * a * x + b) * (a * x * x + b * x + c));
        }
    
        public static void main(String[] args) {
            double x0, y0, tga, xn, yn;
            for (x0 = -0.99; x0  0.001) {
                    xn -= diffSqr(xn) / diffSqrDeriv(xn);
                    yn = diffSqr(xn);
                }
                System.out.println(x0 + "\t" + xn);
            }
        }
    }
    
  13. Laszlo Simon szeptember 28, 2013 2:31 du.

    Hmmmm…..
    A kódot elküldöm levélben.
    Üdv
    Laci

    • Peter Verhas szeptember 28, 2013 3:35 du.

      Legyen a függőlegestől mért alfa szög, ahol elhagyja, és béta ahol visszajön. Rajzold ki a programból és optimalizálj tovább.

      • Laszlo Simon szeptember 28, 2013 7:34 du.

        Köszönöm a segítséget, a szögekkel kiszámolgatva a diagramból látszik, hogy béta=3*alfa+pi (ahogy én vettem fel őket). Ebből, ha xn=sin(béta), x0=sin(alfa) => xn = -3*x0+4*x0^3, vagyis tényleg harmadfokú lesz x-ben, ahogy sejtettem. Ezek szerint a páros kitevőjű tagok valahol kiesnek, ha végigszámolom. Már csak az zavar, hogy a diagram a nulla körül eltér, szép ívesen megy át xn =x0-ba. Lehet, hogy ez nem a double pontossága miatt van, hanem azért, mert a szép alak csak valamilyen magasabb (ill. mélyebb) fokú tag elhanyagolásával jön ki…
        (rég firkáltam már ennyi polinomot meg szögfüggvényt:)

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s

%d blogger ezt kedveli: