ruby กับ gcd

คุณ sugree พูดถึง gcd ใน howforge
และไปตั้งโจทย์ไว้ใน codenone.com

ผมก็เลยลองไปแคะดูว่า method หรือ function gcd ใน ruby นั้นมีอยู่หรือยัง
ลองอ่านดูใน document ของ ruby
ก็พบว่า class Integer มี method ที่ทำ gcd อยู่ 2 version ก็คือ
gcd กับ gcd2
ในเอกสาร ก็ไม่ได้อธิบายว่าทำไมถึงมี 2 version
แต่เดาได้เลยว่า น่าจะเกี่ยวกับ algorithm ในการ implement

เพื่อแก้ความสงสัย ผมก็เลยทดสอบจัด benchmark เปรียบเทียบดู

require 'benchmark'
r = (1..10000)
m = 70
Benchmark.bm do |x|
  x.report("gcd") { r.each {|n| n.gcd m}}
  x.report("gcd2") { r.each {|n| n.gcd2 m}}
end

ผลที่ได้ ก็คือ gcd2 นั้นทำงานเร็วกว่า

      user     system      total        real
gcd   0.300000   0.000000   0.300000 (  0.303847)
gcd2  0.130000   0.000000   0.130000 (  0.126843)

ถ้าลองแกะดู source code ของ ruby 1.8.4 จะเห็นว่า gcd2
ใน algorithm แบบ Euclidean algorithm
มีหน้าตาแบบนี้

def gcd2(int)
  a = self.abs
  b = int.abs

  a, b = b, a if a < b

  while b != 0
    void, a = a.divmod(b)
    a, b = b, a
  end
  return a
end

ที่สนุกกว่านั้นก็คือ ใน library 'mathn' มันมีการ override
method gcd2 ด้วย algorithm "prime factorizations"
ผลที่ได้คือ ช้าสุดๆ
ลองดู benchmark ของ gcd2 ที่ถูก override แล้ว

require 'mathn'
Benchmark.bm do |x|
  x.report("gcd2-mathn") { x.each {|n| n.gcd2 m}}
end

      user     system      total        real
gcd2-mathn  4.450000   0.030000   4.480000 (  4.545717)

จะเห็นว่า การ re-open-class ได้แบบ ruby มันมาทั้งข้อดีและข้อเสีย
อย่างตัวอย่างข้างบน programmer คนแรกรู้ว่า gcd2 มันเร็ว
ก็เลยเขียน code โดยเรียกใช้ gcd2
แต่อยู่มาวันหนึ่งมีคนเกิดอยากได้ function ที่อยู่ใน 'mathn' เข้า
effect ที่เกิดจากการ require 'mathn'
ก็จะทำให้ gcd2 ที่เคยเร็วจี๋เปลี่ยนเป็นช้าสุดๆ โดยไม่มีใครรู้ตัว

จากการไล่ดู code ต่อ ก็พบว่า ruby 1.8.6 มีการเปลี่ยนแปลงใหม่
โดยตัด method gcd2 ออกไป และเปลี่ยนให้ gcd ไปใช้ Euclidean algorithm แทน

Note: ผมเขียนโปรแกรมมาก็นานแล้ว ยังไม่เคยใช้ gcd เลย