Pertanyaan mengapa tail recursive gcd lebih cepat daripada while dengan rubinius


Saya memiliki dua implementasi fungsi gcd ini:

def gcd1(a,b)
  if a==b
    a
  elsif a>b
    if (a%b)==0
      b
    else
      gcd1(a%b,b)
    end
  else
    if (b%a)==0
      a
    else
      gcd1(a,b%a)
    end
  end
end
def gcd2(a,b)
  if(a==b)
    return a
  elsif b>a
    min,max=a,b
  else
    min,max=b,a
  end
  while (max%min)!=0
    min,max=max%min,min
  end
  min
end

Fungsi gcd1 adalah tail recursive sementara gcd2 menggunakan loop while.

Saya telah memverifikasi bahwa rubinius melakukan TCO dengan membandingkan fungsi faktorial, hanya dengan fungsi faktorial tolok ukur menunjukkan bahwa versi rekursif dan versi iterasi adalah "same-ish" (saya menggunakan benchmark-ips).

Tetapi untuk di atas, tolok ukur menunjukkan bahwa gcd1 lebih cepat setidaknya dengan faktor dua daripada gcd2 (rekursi dua kali lebih cepat daripada iterasi, bahkan lebih cepat).

Kode yang saya gunakan untuk patokan adalah ini:

Benchmark.ips do |x|
  x.report "gcd1 tail recursive" do
    gcd1(12016,18016)
  end
  x.report "gcd2 while loop" do
    gcd2(12016,18016)
  end
  x.compare!
end

hasil :

Warming up --------------------------------------
 gcd1 tail recursive    47.720k i/100ms
     gcd2 while loop    23.118k i/100ms
Calculating -------------------------------------
 gcd1 tail recursive    874.210k (± 7.1%) i/s -      4.343M
     gcd2 while loop    299.676k (± 6.6%) i/s -      1.503M

Comparison:
 gcd1 tail recursive:   874209.8 i/s
     gcd2 while loop:   299676.2 i/s - 2.92x slower

Saya menjalankan Arch linux x64, prosesor i5-5200 2.2 GHZ quad-core.

Implementasi rubi adalah Rubinius 3.40.

Jadi bagaimana bisa rekursi lebih cepat daripada loop?

Memperbarui

Hanya untuk mengatakan bahwa fibonacci memiliki situasi yang sama: versi rekursif ekor setidaknya dua kali lebih cepat dari versi loop, program yang saya gunakan untuk fibonacci: http://pastebin.com/C8ZFB0FR


6
2018-06-19 21:29


asal


Jawaban:


Dalam contoh yang Anda gunakan hanya dibutuhkan 3 panggilan / loop untuk mendapatkan jawabannya, jadi saya tidak berpikir Anda benar-benar menguji hal yang benar. Coba dengan dua angka Fibonacci berturut-turut sebagai gantinya (misalnya 2000 dan 2001) dan hasilnya tidak boleh berbeda banyak.

(Maaf, saya belum punya reputasi untuk berkomentar).

EDIT: Saya akhirnya berhasil menginstal [sebagian] rubinius dan berhasil menciptakan kembali fenomena yang Anda maksud. Ini bukan tentang rekursi, ini tentang banyak tugas. Jika kamu berubah

      while n>0
        a,b=b,a+b
        n-=1
      end

untuk

      while n>0
        t=a
        a=b
        b=t+b
        n-=1
      end

sementara versi loop harus tampil (sedikit) lebih cepat. Hal yang sama berlaku untuk program GCD asli, yaitu menggantikan

        min,max=max%min,min

dengan

        t=min
        min=max%t
        max=t

adalah masalahnya.

Ini bukan kasus dengan ruby-2.1, yaitu loop sementara tampak lebih cepat, hanya dalam bentuk yang Anda berikan.

Semoga itu membantu!


2
2018-06-24 03:00