Prisijungti

Python darbas su dideliais skaičiais

  • 22 Lie '12

Sveiki, man reikia surasti visų fibonačio skaičių (iki 4 milijonų) sumą. Vykdant kodą išmeta klaidą MemoryError. Gal yra kokios bibliotekos ar kažkas panašaus kad leistų dirbti su daug didelių skaičių?

  • 22 Lie '12

Parašyk kokį kodą naudoji.

Šiaip įdomu kokios architektūros procesosius ir kiek ram, kad tokie skaičiai jau problemų su memory kelia.

  • 22 Lie '12

Naudoju laptop'ą su Intel Core2Duo T6600 2,2GHz i686, 3GB DDR3 RAM, GeForce G210M su Cuda

ats=0.0

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)

for x in range(1, 4000000):
    if fib(x)%2==0:      #Patikrina ar skaicius lyginis
        ats=ats+fib(x)

print "Atsakymas: ", int(ats)

Arba pats kodas gal prastai parašytas?

Šiandien reikėjo sužinoti koks yra 10001-asis pirminis skaičius, tai per ~10min išvedė atsakymą.

  • 22 Lie '12

Galėtum pagreitinti procedūrą cache'indamas fib rezultatus, bent jau taip pataria vienas puslapis).

Šiek tiek perrašiau kodą.

memo = {0:0, 1:1}

def fib(n):
    if not n in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

def getAts(n):
    ats=long(0)
    for x in range(1, n):
        fibval = fib(x)
        if fibval%2==0:      #Patikrina ar skaicius lyginis
            ats += fibval
    return ats

print "Atsakymas: ", getAts(10001)

Šiaip nesu python specas, tai manau galima ir labiau optimizuoti (minėto puslapio iki galo neskaičiau, gal ten dar kokių patarimų like).

  • 22 Lie '12

Keista net ir šitas kodas meta MemoryError :/

Traceback (most recent call last):
  File "/home/linas/Desktop/ad.py", line 16, in <module>
    print "Atsakymas: ", getAts(4000000)
  File "/home/linas/Desktop/ad.py", line 12, in getAts
    if fibval%2==0:      #Patikrina ar skaicius lyginis
MemoryError

Edit2: Gal reikėtų cache'inti tik paskutines 2-3 reikšmes

ShookeesPaulius
  • 22 Lie '12

Sveikas, šiek tiek nesu tikras dėl ieškomos problemos - kaip dirbti su dideliais skaičiais ar išspręsti fibonači problemą. Jei pastaroji, tai internetuose galima nesunkiai rasti matematinius pastebėjimus dirbant su fibonači skaičiais.

  • 22 Lie '12

@Linas2 rašė:
Edit2: Gal reikėtų cache'inti tik paskutines 2-3 reikšmes

Ne, kuo didesnį cache turėtum tuo greičiau suskaičiuotų naują fib skaičių. Jei nepadės ir kitos aptartos fib radimo funkcijos minėtame puslapyje aš galvočiau apie fib skaičiavimo skaidymą intervalais po truputi pildant fib cache.

Jei skaitei minėtą puslapį, ten buvo užsiminta:

Computing fib(100) with the simple recursive version requires 708449696358523830149 function calls

Todėl ir svarbu rasti tą fib skaičių "pigiausiai".. cache padeda, bet matyt geriau jį laikyti kokiam faile taupant ram'ą. Bent jau ant mano PC (i5, fedora 64bit, 8gb ram) sistema tiesiog nukilindavo python'a, apie trukstamus memory nieko nerašydavo (bent jau 4 milijonams, tiesa pusei milijardo jau sakydavo memoryError iškart).

Šiaip jei tai akademinis darbas galbūt tau būtų galima pasinaudoti VU skaičiavimo resursai Python aplinkai (prezentacijoje berods registracijos tvarka užsimenama).

  • 24 Lie '12

@apocalipso rašė:
....
Šiaip jei tai akademinis darbas galbūt tau būtų galima pasinaudoti VU skaičiavimo resursai Python aplinkai (prezentacijoje berods registracijos tvarka užsimenama).

Ačiū už nuorodą Tai ne akademinis darbas, tiesiog spręndžiu http://projecteuler.net/ problemas ir "pakibau" ties šita
Bandžiau į failą surašyti lyginius skaičius (pastebėjau kad kas 3 sekos skaičius lyginis ), klaidos neišmetė, bet baigės mano kantrybė
Dabar atradau kad į tuple (sąrašas turbūt?) galima sutalpinti daaaug reikšmių, tai bandysiu su juo kažkaip daryti

Parodo kiek reikšmių galima sutalpinti:

import sys
print sys.maxsize
2147483647

@Shookees rašė:
Sveikas, šiek tiek nesu tikras dėl ieškomos problemos - kaip dirbti su dideliais skaičiais ar išspręsti fibonači problemą. Jei pastaroji, tai internetuose galima nesunkiai rasti matematinius pastebėjimus dirbant su fibonači skaičiais.

Problema kad neteko anksčiau dirbti su tokiais dideliais skaičiais (virš 50 skaitmenų).
O ta fibonači problema yra užduotis, kurią spręsdamas susidūriau su tais didžiuliais skaičiais.

  • 24 Lie '12

Patobulintas variantas:

def iterfib(n):
    assert n > 0
    i = 1
    f1, f2 = 0, 1
    yield f1
    while i < n:
        i += 1
        f1, f2 = f2, f2 + f1
        yield f2

print(sum(iterfib(4000000)))

Bet palaukus 5 minutes, nebeužteko kantrybės, o 400 000 sumą suskaičiuoja per ~20 sekundžių ir rezultatas gavosi toks (83596 skaitmenų skaičius, kuris net netelpa į vieną šio forumo postą):
http://pastebin.ubuntu.com/1108885/

Problema yra tame, kad skaičius labai greitai didėja ir kuo toliau, tuo ilgiau užtrunka sumavimo operacija, dėl to kuo toliau, tuo labiau sumavimas lėtėja, todėl 400 000 užtrunka 20 sekundžių, o 4000 000 susumuoti jau nebeužtenka 5 minučių.

Kas turit kantrybės galit pabandyti palaukti kol suskaičiuos 4000 000, įtariu, skaičius bus labai didelis.

  • 24 Lie '12

Jei naudotų visus kompiuterio resursus t.y Visus branduolius. Viskas vyktų kurkas greičiau.
http://docs.python.org/library/multiprocessing.html


Show Big

  • 25 Lie '12

Paskirstymas tarp branduolių ne visada įmanomas. Dabartiniame variante galima nebent kaupti sąrašą fibonacci skaičių ir karts nuo karto perduoti paskaičiuoti jų sumą kitam branduoliui, bet nesu įsitikinęs ar tai bus efektyvu dėl tarp procesinio overhead'o.

  • 13 Rugp '12

Na gal ir per senai atsakau, bet pradiniame tavo programos variante as pastebejau kad naudoji rekursines funkcijas kas yra labai blogai. Tai greiciausiai ir yra tavo memory problemos saknis. Sirex variantas naudoja jau loopa ir tokios problemos neturetu buti.

Tai yra ka reiktu atsiminti, kad kompiuteris sudarydamas vis gilesnius rekursiniu funkciju medzius pradeda naudoti vis didesnius kompiuterio resursus. Tai yra jis pastoviai turi issaugoti pradines funkcijos busenas (rodos kai kuriose kompiliatoriuose/interpretatoriuose isvis budavo apribojama rekursijos gylis).

Siaip del dideliu fibonaci skaiciu tai tam galima panaudot
http://mathworld.wolfram.com/BinetsFibo ... rmula.html

Neuztruksi ir sekundes savo milijoniniam skaiciui.

Atsakyti