หา fibonacci ใน haskell ทำไมถึงเร็ว

warning: realpath() [function.realpath]: SAFE MODE Restriction in effect. The script whose uid is 1005 is not allowed to access /tmp owned by uid 0 in /var/www/sites/sugree/codenone.com/subdomains/www/html/includes/file.inc on line 190.
warning: realpath() [function.realpath]: SAFE MODE Restriction in effect. The script whose uid is 1005 is not allowed to access /tmp owned by uid 0 in /var/www/sites/sugree/codenone.com/subdomains/www/html/includes/file.inc on line 190.

Submitted by bentino on 20 July, 2007 - 00:59

Other Topics

มีอยู่วันหนึ่งอาจารย์ผมให้ลองเขียน fibonacci แบบ recursive ใน c++ ซึ่งถ้าทำ fibo ซัก 40 ตัวก็เริ่มอืดๆ แล้วถ้า 50 ตัว ไม่ต้องพูดถึง พอใช้เขียนแบบ dynamic programming มันก็เร็วขึ้นแบบทันตาด้วยความตื่นเต้นกับ dynamic programming เลยไปเล่าให้เพื่อนฟัง

ทีนี้ปัญหาที่ผมสงสัยก็คือพอฟังเพื่อนก็ลองเขียนลงไปใน ruby มันก็ช้าเหมือน c++ แต่พอเขียนด้วย haskell ปรากฎว่ามันเร็วแบบทันตาเห็นเหมือนกับที่เขียนแบบ dynamic programming เลยครับ อยากจะทราบว่าทำไมมันเป็นแบบนั้นครับ

ขอบคุณครับ

Submitted by sugree on 20 July, 2007 - 01:07.

เดาว่า มันไม่มี stack

Submitted by veer on 20 July, 2007 - 01:28.

tail recursion optimization ทำได้ก็ต่อเมื่อ function นั้นต้อง return ค่าที่ได้จากการเรียกตัวเอง ไปโดยไม่ไปคำนวนอะไรซ้ำ หรือเปล่า? (จำเป็นเปล่า?)

อะไรแบบนี้ได้
function tata(x) {
  ...
  ...
  return tata(x-1); 
}
 
แต่แบบนี้ไม่ได้? หรือเปล่า?
function tata(x) {
  ...
  ...
  return tata(x-1) * tata(x-10); 
}
 
แต่แบบนี้ก็น่าจะได้?
function tata(x) {
  ...
  ...
  return tata(x-1) * 5; 
}

แบบประมาณว่าจริงใช้ค่าที่ return ครั้งสุดท้ายก็พอ ไม่ต้องเก็บว่าก่อนหน้านั้น return อะไรมา? เช่น tata(5) -> tata(4) -> tata(3) -> tata(2) -> tata(1) จริงๆ ถ้าหา tata(1) ได้ก็เสร็จเลย เอาค่านั้นมาตอบได้เลย. แต่พอใช้ท่านี้แล้วมักจะต้องเพิ่ม accumulator เข้ามา. แต่ไม่รู้ Haskell ทำไง :-P.

Submitted by veer on 20 July, 2007 - 01:12.

ไม่เห็นเอา code มาให้ดูเลย. ผมก็ไม่รู้หรอกครับ แต่อยากดู code ด้วย. :-D

Submitted by bentino on 20 July, 2007 - 01:22.

นี่โค้ด ruby นะครับ

def fib(n)
if n<2 then
1
else
fib(n-1)+fib(n-2)
end
end

Submitted by veer on 20 July, 2007 - 01:27.

อยากได้ code haskell อะครับ เวลาพิมพ์ code ใช้ tag ชื่อ blockcode แล้วจะออกมาสวยครับ. :-)

Submitted by bentino on 20 July, 2007 - 01:33.

ส่วนนี่เป็น haskell ครับ

fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-2) + fibo (n-1)

Submitted by veer on 20 July, 2007 - 02:27.

เห็นงี้ผมก็จอดแล้วครับ

ถ้าเป็นแบบข้างล่างยังพออธิบายได้บ้างว่าเป็น tail recursion

function fib(n, acc)
{
   if(n<1) return 1;
   acc = acc * n;
   return fib(n - 1, acc);
}

เล่น haskell เป็นลูกศิษอ.เดฟปะครับ? (ตอบคำถามไม่ได้ ก็พาออกนอกเรื่องไป :-P)

Submitted by bentino on 20 July, 2007 - 02:49.

ใช่ครับ (แม่นแฮะ ^^)

Submitted by veer on 20 July, 2007 - 03:00.

ถ้าเกิดว่ารู้เฉลยจากที่อื่น ไม่ว่าจะมีคนอื่นบอก หรืออ่านวิกีพีเดีย หรือ search google มา อย่าลืมมาเล่าสู่กันฟังบ้างนะครับ ผมก็อยากรู้เหมือนกัน.

Submitted by bentino on 20 July, 2007 - 09:15.

ครับ ^^

Submitted by Lemur on 20 July, 2007 - 12:31.

เคยอ่าน haskell เมื่อนานมากแล้ว แล้วก็ไม่ได้ใช้ เ่ท่าที่จำได้มันไม่ได้ทำงานเหมือน function แต่เป็นการแปลงขณะ interpret เหลือแค่บวกกันเฉยๆ
อันนี้ไม่แน่ใจนะครับ ลองเอาคำตอบนี้ไป search ยืนยันอีกที

Submitted by Lemur on 20 July, 2007 - 14:34.

http://en.wikibooks.org/wiki/Haskell/Haskell_Performance
ยืนยันความคิด ข้างบน คือใช้ lazy evaluation แทนการเจอ function เมื่อไหนก็เรียก function
ทำให้ ไม่ต้องใช้ stack ในกรณีที่ reduce form ได้

Submitted by veer on 20 July, 2007 - 15:05.

ดีกว่าอ่านในหน้า Haskell ของวิกิพีเดียแฮะ.

Submitted by pphetra on 20 July, 2007 - 17:05.

ตอนแรกผมก็คิดทำนองนี้นะ
ไหนๆ ก็เป็น functional ที่ no side effect แล้ว
ถ้าเรียกซ้ำด้วย argument เดิม ก็ควรจะไม่ต้องไปคำนวณซ้ำซ้อนอีก

แต่ผลการทดลอง ที่ทดลองหา fib(50) ที่หายต๋อมไป (> 3 นาที ขี้เกียจรอ เลยไม่รู้ว่าต้องใช้เวลาเท่าไร)
มันเหมือนกับว่า มันไม่ได้เกิด reduce form เลยนี่ครับ

Submitted by pphetra on 20 July, 2007 - 13:02.

Note: คำตอบนี้เดาเอาเหมือนกัน, และหวังว่าคำถามนี้จะไม่ใช่การบ้านอาจารย์เดฟด้วยนะ

ลอง code นี้ดูนะ

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
 
main = print $ fib 30

ลอง run แบบ interpreter ด้วย hugs

@pann[~/projects/haskell]$ time runhugs fibonacci.hs
832040

real    0m18.870s
user    0m18.697s
sys     0m0.052s

ลอง run แบบ interpreter ด้วย ghc

@pann[~/projects/haskell]$ time runghc fibonacci.hs
832040

real    0m5.738s
user    0m5.636s
sys     0m0.068s

จะเห็นว่า แต่ละ implement ก็มีความเก่งไม่เท่ากัน

ที่นี้ลองเทียบกับ ruby ดูบ้าง
code แบบนี้

def fib(n)
  if (n <= 2) 
    1
  else
    fib(n-1) + fib(n-2)
  end
end
 
puts fib 30

จับเวลาดู

@pann[~/projects/ruby]$ time ruby fib.rb
832040

real    0m2.070s
user    0m1.812s
sys     0m0.220s

กลายเป็นว่า interpreter mode, ruby ทำงานเร็วกว่า

ทีนี้ลอง compile เป็น native ดูบ้าง

@pann[~/projects/haskell]$ ghc fibonacci.hs -o fibonacci
@pann[~/projects/haskell]$ time ./fibonacci
832040

real    0m0.531s
user    0m0.488s
sys     0m0.012s

เร็วขึ้นแบบสุดๆ
ถามว่ามันเร็วได้อย่างไร
ถ้าดูอย่างนี้ ก็ต้องเดาตอบว่าเพราะ optimizer ของ ghc
เนื่องจาก haskell มันเป็น pure functional language
ไม่มี side effect
การที่เราเรียก fib(ุx) ไม่ว่าจะกี่ครั้งก็ตาม เนื่องจากไม่มี side effect
มันก็ต้องได้คำตอบเดิมออกมาเสมอ
ดังนั้นคาดว่า ghc คงใส่กลไก memoization เข้าไปให้ด้วย
(ซึ่งมันก็คือ dynamic programming แบบ top-down approch นั่นเอง)

Submitted by pphetra on 20 July, 2007 - 13:23.

แก้ไขข้างบน
> ดังนั้นคาดว่า ghc คงใส่กลไก memoization เข้าไปให้ด้วย
> (ซึ่งมันก็คือ dynamic programming แบบ top-down approch นั่นเอง)
เดาผิด, มันไม่ได้ทำอย่างนั้นหรอก
เพราะลองเปลี่ยนเป็น fib(50) แล้ว ก็หายต๋อมไปเลย

สรุปว่า ไม่รู้ ghc มัน implement อย่างไรเหมือนกัน

Submitted by pphetra on 20 July, 2007 - 14:02.

หลังจากทบทวนดูอีกที
เราหลงทางกับคำถามเองนี่หว่า

สรุปว่า haskell เร็วเพราะ มัน compile เป็น native (no more no less)
แต่ถ้า run ใน interpreter mode แล้ว ช้ากว่า ruby เสียอีก

Submitted by bentino on 21 July, 2007 - 04:23.

ไม่ใช่การบ้าน อ.เดฟ หรอกครับผมสงสัยเฉยๆ เลยมาโพสต์ถาม

Submitted by pphetra on 20 July, 2007 - 14:06.

้ที่บอกว่าเร็วพอๆกับ version dynamic นั้น
เครื่องผมไม่ได้ผลแบบนั้นนะ

อันนี้ version recursive
@pann[~/projects/haskell]$ time ./fibonacci
832040

real    0m0.545s
user    0m0.512s
sys     0m0.004s

อันนี้ version dynamic
@pann[~/projects/haskell]$ time ./fibonacci2
832040

real    0m0.003s
user    0m0.004s
sys     0m0.000s
@pann[~/projects/haskell]$

Submitted by veer on 20 July, 2007 - 14:14.

bentino ลองใช้ C++ แล้วทำการทดลองแบบ pphetra ได้เปล่า? ลองเทียบ C++ recursive กับอย่างอื่นๆ.

Submitted by bentino on 21 July, 2007 - 04:17.

ขออ่านหนังสือสอบก่อนนะครับ (อาทิตย์นี้แล้ว) เดี๋ยวได้ผลอย่างไรจะมาโพสต์ให้ดูครับ

Submitted by veer on 21 July, 2007 - 04:21.

ครับ รอดูนะ. ว่าจะลองเขียน ocaml หรือ scheme มาประกวดบ้างดีมะ :-P.

Submitted by sugree on 20 July, 2007 - 14:33.

อันนี้แบบ python

def fib1(n):
    if n <= 2:
        return 1
    else:
        return fib1(n-1)+fib1(n-2)
 
print fib1(30)

sugree@sugree-laptop:20070720$ time python fib.py
832040
 
real    0m0.816s
user    0m0.764s
sys     0m0.016s

sugree@sugree-laptop:20070720$ time ruby fib.rb
fib.rb:9: warning: parenthesize argument(s) for future version
832040
 
real    0m1.839s
user    0m1.612s
sys     0m0.188s

Submitted by pphetra on 20 July, 2007 - 16:44.

บนเครื่องผม ถ้าเป็น recursive c

int fib(int n) {
 if (n <= 2) return 1;
 return fib(n-1) + fib(n-2);
}
void main() {
 printf ("%d", fib(30));
}

@pann[~/projects/c]$ time ./fib
832040
real    0m0.047s
user    0m0.040s
sys     0m0.000s

เทียบกับ ghc ข้างบน ที่ใช้เวลา 0.5xx แล้ว magnitude ก็ระดับ 10x

Submitted by bow_der_kleine on 22 July, 2007 - 00:25.

ผมคิดว่าการคำนวน fibonaci จะช้าหรือเร็ว ในกรณีนี้ไม่น่าจะขึ้นอยู่กับภาษาเขียนโปรแกรม แต่น่าจะอยู่ที่วิธีการมากกว่าครับ ผมได้ลองนับจำนวนการเรียกฟังก์ชั่นดู ปรากฏว่าได้ผลดังนี้ครับ

call_no = 0
 
def fibo_rec(n):
	global call_no
	call_no = call_no+1
	if n <= 2 :
		return 1
	else:
		return fibo_rec(n-1)+fibo_rec(n-2)
 
for i in xrange(32):
	print 'n : ', i,' => Fibonaci', fibo_rec(i), ' call function', call_no,' times'
	call_no = 0

ผลการรันโปรแกรม

n :  0  => Fibonaci 1  call function 1  times
n :  1  => Fibonaci 1  call function 1  times
n :  2  => Fibonaci 1  call function 1  times
n :  3  => Fibonaci 2  call function 3  times
n :  4  => Fibonaci 3  call function 5  times
n :  5  => Fibonaci 5  call function 9  times
n :  6  => Fibonaci 8  call function 15  times
n :  7  => Fibonaci 13  call function 25  times
n :  8  => Fibonaci 21  call function 41  times
n :  9  => Fibonaci 34  call function 67  times
n :  10  => Fibonaci 55  call function 109  times
n :  11  => Fibonaci 89  call function 177  times
n :  12  => Fibonaci 144  call function 287  times
n :  13  => Fibonaci 233  call function 465  times
n :  14  => Fibonaci 377  call function 753  times
n :  15  => Fibonaci 610  call function 1219  times
n :  16  => Fibonaci 987  call function 1973  times
n :  17  => Fibonaci 1597  call function 3193  times
n :  18  => Fibonaci 2584  call function 5167  times
n :  19  => Fibonaci 4181  call function 8361  times
n :  20  => Fibonaci 6765  call function 13529  times
n :  21  => Fibonaci 10946  call function 21891  times
n :  22  => Fibonaci 17711  call function 35421  times
n :  23  => Fibonaci 28657  call function 57313  times
n :  24  => Fibonaci 46368  call function 92735  times
n :  25  => Fibonaci 75025  call function 150049  times
n :  26  => Fibonaci 121393  call function 242785  times
n :  27  => Fibonaci 196418  call function 392835  times
n :  28  => Fibonaci 317811  call function 635621  times
n :  29  => Fibonaci 514229  call function 1028457  times
n :  30  => Fibonaci 832040  call function 1664079  times
n :  31  => Fibonaci 1346269  call function 2692537  times

จากกผลอันนี้ สรุปได้ว่า จำนวนครั้งในการเรียกฟังก์ชั่น เท่ากับ 2*fibonaci -1 ซึ่งแน่นอนว่า ไม่ว่าภาษาไหนก็ต้องอืดเป็นธรรมดา แต่ haskell จะเร็วกว่าภาษาอื่น เพราะว่า ไม่มี if (เดาเอา) หาก n = 30 และใช้ haskell ก็จะประหยัดการใช้ if ไปได้ 1664079 ! ครั้ง ผมคิดว่ามีผลกับ performance แน่นอน

วิธีแก้ที่ถูกจึงไม่ใช่เปลี่ยนภาษาเขียนโปรแกรมครับ แต่น่าจะเปลี่ยน algorithm มากกว่า ยกตัวอย่างเช่น

def fibo(n):
	fibo1 = 1
	fibo2 = 1
	for i in xrange(n-2):
		fiboTmp = fibo1
		fibo1 = fibo1 + fibo2
		fibo2 = fiboTmp
	return fibo1

ฟังก็ชั่นนี้มีการวนลูป เท่ากับ n-2 ทำให้ประหยัดการทำงานของโปรแกรมได้เยอะอย่างประมาณไม่ได้ ยกตัวอย่างเช่น ผมหาค่า fibo(100000) ซึ่งมีค่าประมาณ 2.597e20899 (สิบยกกำลังสองหมื่นกว่า ๆ) ได้ในเวลาไม่ถึงหนึ่งวินาที เพราะมีการวนลูปเพียง 999998 ครั้ง แต่หากใช้ recursive ต้องเรียกฟังก์ชั่นกัน 5.194e20899 ครั้ง

Submitted by veer on 23 July, 2007 - 05:20.

ใช้ท่า recursive แบบโกงหน่อยได้ก็เร็วขึ้น

def f(n,a,b):
  if n <= 1:
    return a
  else:
    return f(n-1, a+b, a)
 
def fib(n):
  return f(n,1,1)
 
print fib(100000)

แต่ก็จะไปติดปัญหาว่า stack เต็มแทน

เปลี่ยนมาใช้ scheme ที่มี tail recursive แทนก็ทำได้

(define (f n a b)
  (if (<= n 1)
      a
      (f (- n 1) (+ a b) a)))
 
(define (fib n) (f n 1 1))
 
(fib 100000)

ใช้ mzscheme เกือบๆ 4 วินาทีก็ออก

real 0m3.396s
user 0m2.347s
sys 0m0.440s

แต่หลายคนก็อาจจะบอกว่าจะเขียน recursion ทำไม :-P ... สำหรับแล้วตอบว่า "ขำๆ".

Submitted by jittat on 28 July, 2007 - 22:02.

เขียนง่าย/ตรง definition มั้ง

ขำๆ

Submitted by veer on 30 July, 2007 - 02:14.

พอมี accumlator แล้วก็ห่าง definition ออกไปอีกอะครับ. แต่ดู condition ข้างในก็ยังเหลือเค้า.

ย้าย Codenone

ประกาศย้าย Codenone ไปใช้ Forum ของ Blognone แทนครับ ตามไปตั้งกระทู้ต่อได้ที่ Codenone Forum (รายละเอียดอ่านจากกระทู้ ย้าย Codenone ไปรวมกับ Blognone)

กระทู้เก่าๆ จะย้ายตามไปในภายหลัง ตอนนี้ปิดการโพสต์กระทู้ไว้ เหลือไว้เฉพาะอ้างอิงเท่านั้น

Codenone

Book navigation

Forum List

หา fibonacci ใน haskell ทำไมถึงเร็ว

ย้าย Codenone