{"id":461,"date":"2007-12-01T16:17:00","date_gmt":"2007-12-01T16:17:00","guid":{"rendered":"http:\/\/witpoko.com\/?p=461"},"modified":"2007-12-01T16:17:00","modified_gmt":"2007-12-01T16:17:00","slug":"%e0%b8%84%e0%b8%b3%e0%b8%99%e0%b8%a7%e0%b8%93%e0%b9%80%e0%b8%a5%e0%b8%82-fibonacci-%e0%b8%94%e0%b9%89%e0%b8%a7%e0%b8%a2-python-%e0%b9%81%e0%b8%9a%e0%b8%9a%e0%b9%84%e0%b8%a1%e0%b9%88%e0%b8%8a%e0%b9%89","status":"publish","type":"post","link":"https:\/\/witpoko.com\/?p=461","title":{"rendered":"\u0e04\u0e33\u0e19\u0e27\u0e13\u0e40\u0e25\u0e02 Fibonacci \u0e14\u0e49\u0e27\u0e22 Python \u0e41\u0e1a\u0e1a\u0e44\u0e21\u0e48\u0e0a\u0e49\u0e32\u0e19\u0e31\u0e01"},"content":{"rendered":"

\u0e1c\u0e21\u0e40\u0e2b\u0e47\u0e19\u0e2b\u0e31\u0e27\u0e02\u0e49\u0e2d blog post \u0e27\u0e48\u0e32 “Holy Shmoly, Ruby 1.9 smokes Python away!<\/a>” \u0e01\u0e47\u0e40\u0e25\u0e22\u0e01\u0e14\u0e40\u0e02\u0e49\u0e32\u0e44\u0e1b\u0e14\u0e39 \u0e1b\u0e23\u0e32\u0e01\u0e0e\u0e27\u0e48\u0e32\u0e1c\u0e39\u0e49\u0e40\u0e02\u0e35\u0e22\u0e19\u0e44\u0e14\u0e49\u0e08\u0e31\u0e1a\u0e40\u0e27\u0e25\u0e32\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e40\u0e25\u0e02 Fibonacci<\/a> (0, 1, 1, 2, 3, 5, 8, 13, 21, … ) \u0e2b\u0e23\u0e37\u0e2d\u0e40\u0e25\u0e02\u0e15\u0e31\u0e27\u0e17\u0e35\u0e48 n \u0e40\u0e17\u0e48\u0e32\u0e01\u0e31\u0e1a\u0e1c\u0e25\u0e23\u0e27\u0e21\u0e02\u0e2d\u0e07\u0e15\u0e31\u0e27\u0e17\u0e35\u0e48 n-1 \u0e01\u0e31\u0e1a n-2 \u0e41\u0e25\u0e30 Python \u0e43\u0e0a\u0e49\u0e40\u0e27\u0e25\u0e32\u0e1b\u0e23\u0e30\u0e21\u0e32\u0e13 30 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35 \u0e02\u0e13\u0e30\u0e17\u0e35\u0e48 Ruby 1.9.0 \u0e43\u0e0a\u0e49\u0e1b\u0e23\u0e30\u0e21\u0e32\u0e13 12 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35 \u0e43\u0e19\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e15\u0e31\u0e27\u0e40\u0e25\u0e02 35 \u0e15\u0e31\u0e27\u0e41\u0e23\u0e01<\/p>\n

\u0e42\u0e1b\u0e23\u0e41\u0e01\u0e23\u0e21\u0e17\u0e35\u0e48\u0e43\u0e0a\u0e49\u0e04\u0e33\u0e19\u0e27\u0e13\u0e2b\u0e19\u0e49\u0e32\u0e15\u0e32\u0e41\u0e1a\u0e1a\u0e19\u0e35\u0e49:<\/p>\n

<\/p>\n

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

for i in range(36):
    print \"n=%d => %d\" % (i, fib(i))<\/span><\/pre>\n
\u0e1c\u0e21\u0e25\u0e2d\u0e07\u0e23\u0e31\u0e19\u0e42\u0e1b\u0e23\u0e41\u0e01\u0e23\u0e21\u0e1a\u0e19\u0e40\u0e04\u0e23\u0e37\u0e48\u0e2d\u0e07\u0e1c\u0e21\u0e01\u0e47\u0e43\u0e0a\u0e49\u0e40\u0e27\u0e25\u0e32 36 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35 \u0e1c\u0e21\u0e23\u0e39\u0e49\u0e2a\u0e36\u0e01\u0e1b\u0e23\u0e30\u0e2b\u0e25\u0e32\u0e14\u0e43\u0e08\u0e40\u0e19\u0e37\u0e48\u0e2d\u0e07\u0e08\u0e32\u0e01\u0e44\u0e21\u0e48\u0e04\u0e34\u0e14\u0e27\u0e48\u0e32\u0e08\u0e30\u0e43\u0e0a\u0e49\u0e40\u0e27\u0e25\u0e32\u0e19\u0e32\u0e19\u0e2d\u0e22\u0e48\u0e32\u0e07\u0e19\u0e35\u0e49\u0e40\u0e25\u0e22\u0e04\u0e34\u0e14\u0e16\u0e36\u0e07\u0e2a\u0e32\u0e40\u0e2b\u0e15\u0e38\u0e17\u0e35\u0e48\u0e17\u0e33\u0e43\u0e2b\u0e49\u0e43\u0e0a\u0e49\u0e40\u0e27\u0e25\u0e32\u0e19\u0e32\u0e19 \u0e2a\u0e32\u0e40\u0e2b\u0e15\u0e38\u0e17\u0e35\u0e48\u0e1c\u0e21\u0e1e\u0e1a\u0e21\u0e35\u0e14\u0e31\u0e07\u0e19\u0e35\u0e49:<\/span><\/p>\n
1. \u0e15\u0e31\u0e27\u0e41\u0e1b\u0e23\u0e43\u0e19\u0e20\u0e32\u0e29\u0e32 Python \u0e40\u0e1b\u0e47\u0e19\u0e15\u0e31\u0e27\u0e41\u0e1b\u0e23\u0e17\u0e35\u0e48\u0e21\u0e35 run-time type information \u0e17\u0e35\u0e48 CPU \u0e44\u0e21\u0e48\u0e2a\u0e32\u0e21\u0e32\u0e23\u0e16\u0e17\u0e33\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e42\u0e14\u0e22\u0e15\u0e23\u0e07\u0e44\u0e14\u0e49\u0e40\u0e2b\u0e21\u0e37\u0e2d\u0e19\u0e15\u0e31\u0e27\u0e41\u0e1b\u0e23\u0e1e\u0e27\u0e01 int \u0e2b\u0e23\u0e37\u0e2d double \u0e43\u0e19\u0e20\u0e32\u0e29\u0e32 C<\/p>\n
\u0e40\u0e27\u0e25\u0e32 Python interpreter \u0e17\u0e33\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13 \u0e08\u0e30\u0e15\u0e49\u0e2d\u0e07\u0e2b\u0e32\u0e27\u0e48\u0e32\u0e15\u0e31\u0e27\u0e41\u0e1b\u0e23\u0e40\u0e1b\u0e47\u0e19\u0e1b\u0e23\u0e30\u0e40\u0e20\u0e17\u0e2d\u0e30\u0e44\u0e23\u0e01\u0e48\u0e2d\u0e19 \u0e08\u0e36\u0e07\u0e08\u0e30\u0e40\u0e25\u0e37\u0e2d\u0e01\u0e04\u0e33\u0e2a\u0e31\u0e48\u0e07 CPU \u0e17\u0e35\u0e48\u0e16\u0e39\u0e01\u0e21\u0e32\u0e43\u0e0a\u0e49<\/p>\n
2. \u0e08\u0e30\u0e40\u0e2b\u0e47\u0e19\u0e44\u0e14\u0e49\u0e27\u0e48\u0e32\u0e1f\u0e31\u0e07\u0e04\u0e4c\u0e0a\u0e31\u0e19 fib(n) \u0e40\u0e1b\u0e47\u0e19\u0e1f\u0e31\u0e07\u0e04\u0e4c\u0e0a\u0e31\u0e19\u0e17\u0e35\u0e48\u0e40\u0e23\u0e35\u0e22\u0e01\u0e15\u0e31\u0e27\u0e40\u0e2d\u0e07 (\u0e2b\u0e23\u0e37\u0e2d recursive function) \u0e04\u0e37\u0e2d\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13 fib(n) \u0e08\u0e30\u0e40\u0e23\u0e35\u0e22\u0e01\u0e43\u0e0a\u0e49 fib(n-1) \u0e41\u0e25\u0e30 fib(n-2) \u0e41\u0e25\u0e30\u0e04\u0e48\u0e32 fib(0), fib(1), …, fib(k) \u0e01\u0e47\u0e16\u0e39\u0e01\u0e04\u0e33\u0e19\u0e27\u0e13\u0e0b\u0e49\u0e33\u0e0b\u0e32\u0e01\u0e2d\u0e22\u0e39\u0e48\u0e1a\u0e48\u0e2d\u0e22\u0e46<\/p>\n
\u0e1c\u0e21\u0e01\u0e47\u0e40\u0e25\u0e22\u0e04\u0e34\u0e14\u0e16\u0e36\u0e07\u0e27\u0e34\u0e18\u0e35\u0e17\u0e35\u0e48\u0e08\u0e30\u0e41\u0e01\u0e49\u0e1b\u0e31\u0e0d\u0e2b\u0e32\u0e2a\u0e2d\u0e07\u0e02\u0e49\u0e2d\u0e19\u0e35\u0e49 \u0e2a\u0e33\u0e2b\u0e23\u0e31\u0e1a\u0e2a\u0e32\u0e40\u0e2b\u0e15\u0e38\u0e02\u0e49\u0e2d\u0e41\u0e23\u0e01\u0e40\u0e23\u0e32\u0e2a\u0e32\u0e21\u0e32\u0e23\u0e16\u0e43\u0e0a\u0e49\u0e40\u0e04\u0e23\u0e37\u0e48\u0e2d\u0e07\u0e21\u0e37\u0e2d\u0e17\u0e35\u0e48\u0e40\u0e23\u0e35\u0e22\u0e01\u0e27\u0e48\u0e32 Psyco<\/a> \u0e0b\u0e36\u0e48\u0e07\u0e17\u0e33\u0e2b\u0e19\u0e49\u0e32\u0e17\u0e35\u0e48\u0e40\u0e2b\u0e21\u0e37\u0e2d\u0e19 JIT<\/a> (Just-in-Time) compiler \u0e17\u0e35\u0e48\u0e41\u0e1b\u0e25\u0e07\u0e42\u0e1b\u0e23\u0e41\u0e01\u0e23\u0e21 Python \u0e40\u0e1b\u0e47\u0e19\u0e04\u0e33\u0e2a\u0e31\u0e48\u0e07\u0e17\u0e35\u0e48\u0e21\u0e35\u0e1b\u0e23\u0e30\u0e2a\u0e34\u0e17\u0e18\u0e34\u0e20\u0e32\u0e1e\u0e2a\u0e39\u0e07\u0e02\u0e2d\u0e07 CPU \u0e42\u0e14\u0e22\u0e15\u0e23\u0e07 \u0e1e\u0e2d\u0e1c\u0e21\u0e40\u0e1e\u0e34\u0e48\u0e21\u0e2a\u0e2d\u0e07\u0e1a\u0e31\u0e19\u0e17\u0e31\u0e14 (\u0e2a\u0e35\u0e41\u0e14\u0e07) \u0e40\u0e02\u0e49\u0e32\u0e44\u0e1b:<\/p>\n
<\/p>\n
import psyco
psyco.full()<\/span>

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

for i in range(36):
    print \"n=%d => %d\" % (i, fib(i))<\/span><\/pre>\n
\u0e40\u0e27\u0e25\u0e32\u0e43\u0e19\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e01\u0e47\u0e25\u0e14\u0e08\u0e32\u0e01 36 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35\u0e40\u0e2b\u0e25\u0e37\u0e2d 2 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35<\/p>\n
\u0e2a\u0e33\u0e2b\u0e23\u0e31\u0e1a\u0e2a\u0e32\u0e40\u0e2b\u0e15\u0e38\u0e17\u0e35\u0e48\u0e2a\u0e2d\u0e07\u0e40\u0e23\u0e32\u0e41\u0e01\u0e49\u0e44\u0e14\u0e49\u0e42\u0e14\u0e22\u0e44\u0e21\u0e48\u0e04\u0e33\u0e19\u0e27\u0e13\u0e2d\u0e30\u0e44\u0e23\u0e0b\u0e49\u0e33\u0e46 \u0e42\u0e14\u0e22\u0e40\u0e01\u0e47\u0e1a\u0e04\u0e48\u0e32\u0e17\u0e35\u0e48\u0e40\u0e04\u0e22\u0e04\u0e33\u0e19\u0e27\u0e13\u0e44\u0e27\u0e49\u0e44\u0e21\u0e48\u0e15\u0e49\u0e2d\u0e07\u0e17\u0e33\u0e43\u0e2b\u0e21\u0e48\u0e17\u0e38\u0e01\u0e46\u0e04\u0e23\u0e31\u0e49\u0e07 (\u0e40\u0e17\u0e04\u0e19\u0e34\u0e04\u0e1b\u0e23\u0e30\u0e40\u0e20\u0e17\u0e19\u0e35\u0e49\u0e40\u0e23\u0e35\u0e22\u0e01\u0e27\u0e48\u0e32 Caching \u0e2b\u0e23\u0e37\u0e2d Memoization<\/a>):<\/p>\n
<\/p>\n
class cachedFib:
def __init__(self):
    self.f = {}
    self.f[0] = 0
    self.f[1] = 1

def fib(self,n):
    if n in self.f:
        return self.f[n]
    else:
        self.f[n] = self.f[n-1]+self.f[n-2]
        return self.f[n]

cf = cachedFib()
for i in range(36):
    print \"n=%d => %d\" % (i, cf.fib(i))<\/span><\/pre>\n
<\/span>\u0e40\u0e27\u0e25\u0e32\u0e43\u0e19\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e01\u0e47\u0e25\u0e14\u0e08\u0e32\u0e01 36 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35\u0e40\u0e2b\u0e25\u0e37\u0e2d 0.08 \u0e27\u0e34\u0e19\u0e32\u0e17\u0e35<\/p>\n
— – —- – —– ———
P.S.
1. \u0e42\u0e1b\u0e23\u0e41\u0e01\u0e23\u0e21\u0e2a\u0e33\u0e2b\u0e23\u0e31\u0e1a\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e41\u0e1a\u0e1a\u0e2d\u0e37\u0e48\u0e19 (\u0e42\u0e14\u0e22\u0e44\u0e21\u0e48\u0e43\u0e0a\u0e49 recursion \u0e41\u0e25\u0e30\u0e43\u0e19\u0e20\u0e32\u0e29\u0e32\u0e2d\u0e37\u0e48\u0e19\u0e46) \u0e14\u0e39\u0e44\u0e14\u0e49\u0e17\u0e35\u0e48\u0e19\u0e35\u0e48<\/a>
2. \u0e15\u0e32\u0e23\u0e32\u0e07 Fibonacci 300 \u0e15\u0e31\u0e27\u0e41\u0e23\u0e01<\/a> (\u0e41\u0e16\u0e21\u0e41\u0e22\u0e01\u0e15\u0e31\u0e27\u0e1b\u0e23\u0e30\u0e01\u0e2d\u0e1a)
3. Fibonacci \u0e15\u0e31\u0e27\u0e17\u0e35\u0e48 10,000,000<\/a>
4. \u0e2a\u0e39\u0e15\u0e23\u0e19\u0e48\u0e32\u0e2a\u0e19\u0e43\u0e08\u0e43\u0e19\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e40\u0e25\u0e02 Fibonacci<\/a>
<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"
\u0e1c\u0e21\u0e40\u0e2b\u0e47\u0e19\u0e2b\u0e31\u0e27\u0e02\u0e49\u0e2d blog post \u0e27\u0e48\u0e32 “Holy Shmoly, Ruby 1.9 smokes Python away!” \u0e01\u0e47\u0e40\u0e25\u0e22\u0e01\u0e14\u0e40\u0e02\u0e49\u0e32\u0e44\u0e1b\u0e14\u0e39 \u0e1b\u0e23\u0e32\u0e01\u0e0e\u0e27\u0e48\u0e32\u0e1c\u0e39\u0e49\u0e40\u0e02\u0e35\u0e22\u0e19\u0e44\u0e14\u0e49\u0e08\u0e31\u0e1a\u0e40\u0e27\u0e25\u0e32\u0e01\u0e32\u0e23\u0e04\u0e33\u0e19\u0e27\u0e13\u0e40\u0e25\u0e02 Fibonacci (0, 1, … \u0e04\u0e33\u0e19\u0e27\u0e13\u0e40\u0e25\u0e02 Fibonacci \u0e14\u0e49\u0e27\u0e22 Python \u0e41\u0e1a\u0e1a\u0e44\u0e21\u0e48\u0e0a\u0e49\u0e32\u0e19\u0e31\u0e01<\/span>Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[117,4],"tags":[311,310,116],"class_list":["post-461","post","type-post","status-publish","format-standard","hentry","category-programming","category-4","tag-fibonacci-number","tag-optimization","tag-python"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p4UNq0-7r","_links":{"self":[{"href":"https:\/\/witpoko.com\/index.php?rest_route=\/wp\/v2\/posts\/461","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/witpoko.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/witpoko.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/witpoko.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/witpoko.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=461"}],"version-history":[{"count":0,"href":"https:\/\/witpoko.com\/index.php?rest_route=\/wp\/v2\/posts\/461\/revisions"}],"wp:attachment":[{"href":"https:\/\/witpoko.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/witpoko.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/witpoko.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}