Idő kontra tárhely

Van egy új információm. Kapcsolatba léptem a NASA mérnöki irodájával, és megtudtam, hogy az új marsjáró ugyanazt a memóriatípust használja, mint a Curiosity. A Curiosity marsjárón két számítógép volt, de egyszerre mindig csak egy működött, amiknek az alábbi volt a specifikációja: 2 gigabájt flash memóriája, 256 megabájt véletlen elérésű memóriája (RAM) és 256 kilobájt csak olvasható memóriája volt, az utóbbiban az alapvető rendszereljárások voltak. A teljes programunkat a RAM-ban szeretnénk tárolni, de mivel ezt a helyet más programokkal közösen kell használni, nekünk maximum a RAM 5%-a jut. Ez körülbelül összesen 12,8 megabájt. Ezt azért hoztam fel, mert beszélni szeretnék az idő kontra tárhely problémakörről, ami a számítástudomány területén gyakran felmerül. Néztem IV42 programját, ott egy milliós prím tömb szerepelt, így az algoritmus, amíg lehetett, csak prímszámokkal próbálkozott, amikor a próbálkozásos osztást végezte a prímteszt során. Ez felveti azt a kérdést: miért nem tároljuk az összes prímszámot egy adott határig egy tömbben, ahelyett, hogy menet közben számoljuk ki? Az előző videóban volt arról szó, hogy ez lenne az ideális megoldás a próbálkozásos osztáshoz. Bár látható, hogy ez az algoritmus nem igényel sok lépést, de egy idő után lelassult, és végül a program összeomlott, mielőtt elérte volna a lépéshatárt. Nem volt képes gyorsan megoldani a feladatot a korábban definiált méret esetén. Ebben a megoldásban azért, hogy az ismételt oszthatósági tesztekkel csökkentsék a számítási időt, azt a felhasznált tárhelyet növelték, ami a tömb tárolásához szükséges memóriát jelenti. Ez miért nem működött? Végezzünk egy közelítő számítást annak alapján, amit tanultunk, hogy megnézzük, ez az eljárás alkalmazható-e az adott memória korlát mellett. Tartsd szem előtt, hogy 9 kvadrillió feletti számokkal kell dolgoznunk. A próbálkozásos osztás algoritmusának csak a szám négyzetgyökéig kell elmennie, ha eljut eddig, anélkül, hogy találna egy osztót, akkor 100%-os biztonsággal állíthatja, hogy az prímszám. Hány prímszám van az adott korlát négyzetgyökéig, ha 9 kvadrillió négyzetgyöke 94,9 millió? Hány 95 milliónál kisebb prímszám van? Szerencsére megtanultunk a válasz becsléséhez egy matematikai megoldást, a prímszám tételt. Tehát, hány x-nél kisebb prímszám van? Nos, x osztva x természetes alapú logaritmusával. Ha x valamivel nagyobb, mint 94,9 millió, akkor a prímek száma megközelítőleg 5,1 millió. Mivel mi tárolni fogjuk ezeket a prímeket, tudnunk kell a legnagyobb szám méretét, ebben az esetben kb. az 5,1 milliomodik prímszámot, amiről tudjuk, hogy 94,9 milliónál kisebb lesz. Kétszer is ellenőriztem a táblázatot, és ennek az általunk tárolandó prímszámnak az értéke, ami a felső határunk négyzetgyökénél kisebb, 89 078 611. Mekkora memória kell egy ekkora prímszám tárolásához? Ehhez konvertáljuk ezt a számot bináris számmá, mert a számítógép így fogja azt tárolni a memória apró kapcsolói segítségével. Ezt a számítógép memóriájáról szóló videóban láttuk. Bitekben a legnagyobb prímszám így néz ki: ez 24 bit, vagy 3 bájt, ami ennek az egy számnak a tárolásához kell. Tegyük fel, hogy a számokat a memóriában szeretnénk tárolni, és mivel tudjuk, hogy a legnagyobb számhoz 24 bit kell, képzelj el egy hosszú, 24 bites tömbből álló listát, ahol a prímeket tárolod. Hány bit kell az egész listához? A szükséges memória az értékek számától, azaz a prímszámok számától és az egyes értékek tárigényétől függ. Körülbelül 5,1 millió értékünk van, szorozva értékenként 24 bittel, ez egy kicsivel meghaladja a 124 millió bitet, ami bájtra átszámítva kb. 14,7 millió bájt. Ez majdnem 15 millió megabájt. Vagyis nem lehet az adott korlátok mellett ezeket a számokat a memóriában tárolni. Ez nem csupán egy játék példa. Valójában ez alulbecsüli a ténylegesen szükséges tárhelyet. Például a tömbhöz pointert is kell tárolni az egyes elemekhez, és minden pointerhez egy 32 bites gépen 4 bájt kell. Úgyhogy a tényleges helyigény jóval meghaladja a 15 megabájtot. Ezek után tudjuk, hogy a mi relatíve kis korlátunk négyzetgyökénél kisebb prímszámok tárolása nem lehetséges az adott tárhelykorlát mellett. Ez az út nem járható. De mi lesz akkor, ha az árak az ezredére, vagy tízezredére esnek? A mai kriptográfiai rendszerek 512 bitet használnak, esetenként ennél nagyobb számokat is, ami a keresést és a tárolást lehetetlenné teszi. Ha valaki megkér, hogy készítsd el a max. 200 számjegyet tartalmazó prímek listáját, bele se fogj, mert a prímszámok tárolásához szükséges merevlemez súlya meghaladná a látható világegyetem súlyát. Meghagyom neked, hogy kiszámítsd, ha legközelebb egy vendéglőben leszel sok ceruzával és papírral körülvéve. Ne feledd, megközelítőleg 10 a 80.-on atom van a látható világegyetemben. Ez egy 80 [pontosabban 81] számjegyet tartalmazó szám. Látod már, hogy itt egy megkerülhetetlen korlátot jelent a rendelkezésre álló memória? Függetlenül attól, hogy mennyi az időigénye, ez a húzd meg-ereszd meg mindig jelen van a helyigény és a futási idő között. A prímteszt probléma gyors és kis tárhelyet igénylő megoldásához egy gyökeresen más kiindulópont kell.