Ruby的数字方法性能

问题描述 投票：5回答：4

我正在使用Ruby解决一些Project Euler问题，特别是在这里我说的是问题25（Fibonacci序列中包含1000位数的第一项的索引是什么？）。

起初，我使用Ruby 2.2.3，我将问题编码为：

number = 3
a = 1
b = 2

while b.to_s.length < 1000
  a, b = b, a + b
  number += 1
end
puts number

但后来我发现版本2.4.2有一个名为digits的方法，这正是我所需要的。我转换为代码：

while b.digits.length < 1000

当我比较这两种方法时，digits要慢得多。

时间

./025/problem025.rb 0.13s user 0.02s system 80% cpu 0.190 total

./025/problem025.rb 2.19s user 0.03s system 97% cpu 2.275 total

有谁知道为什么？

ruby performance
4个回答
9
投票

Ruby的digits

Ruby的to_s

比较从1位到1000位的数字长度的二次到n1.585给出因子15：

(1..1000).sum { |i| i**2 } / (1..1000).sum { |i| i**1.585 }
=> 15.150583254950678

这也是你观察到的大致因素。当然这是一个相当天真的比较，但是，好吧，为什么不呢。

顺便说一下GMP使用/使用了"near O(n * log(n)) FFT-based multiplication algorithm"。

感谢@ Drenmi的answer激励我深入挖掘源头。我希望我做得对，没有保证，我是Ruby初学者。但这就是为什么我把所有的链接留给你自己检查:-P

1
投票

Integer#digits不只是“分裂”这个数字。从文档：

返回数组，包括由基数为int的位值表示法提取的数字。

即使省略了base参数，也会完成此提取。相关来源：

# ruby/numeric.c:4809

while (!FIXNUM_P(num) || FIX2LONG(num) > 0) {
    VALUE qr = rb_int_divmod(num, base);
    rb_ary_push(digits, RARRAY_AREF(qr, 1));
    num = RARRAY_AREF(qr, 0);
}

如您所见，此过程包括重复的模数算术，这可能会影响额外的运行时间。

0
投票

许多ruby方法创建对象（strins，数组等）。在ruby中，ruby中的对象创建“很昂贵”。

例如，to_s创建一个字符串，digits每次评估while条件时都会创建一个数组。

如果要优化示例，可以执行以下操作：

# create the smallest possible 1000 digits number
max = 10**999

number = 3
a = 1
b = 2

# do not create objects in while condition
while b < max
  a, b = b, a + b
  number += 1
end
puts number
0
投票

我没有回答你的问题，但希望针对你所解决的问题提出一个改进的算法。对于给定的十进制数字，n，我已经实现了以下算法。

  • 估计具有f或更少十进制数字的斐波纳契数（“FN”）的数量n。
  • 计算fth和（f-1）st FNs，以及fth FN中的数字m。
  • 如果m >= n从（f-1）st FN向下退回，直到（f-1）st FN小于n十进制数字，此时fth FN是具有n十进制数字的最小FN。
  • 如果m < n增加第f个FN，直到它具有n十进制数字，此时它是具有n十进制数字的最小FN。

关键是在第一步计算一个接近的估计值f。

码

AVG_FNs_PER_DIGIT = 4.784971966781667

def first_fibonacci_with_n_digits(n)
  return [1, 1] if n == 1
  idx = (n * AVG_FNs_PER_DIGIT).round
  fn, prev_fn = fib(idx)
  fn.to_s.size >= n ? fib_down(n, fn, prev_fn, idx) : fib_up(n, fn, prev_fn, idx)
end

def fib(idx)
  a = 1
  b = 2
  (idx - 2).times {a, b = b, a + b }
  [b, a] 
end

def fib_up(n, b, a, idx)
  loop do
    a, b = b, a + b
    idx += 1
    break [idx, b] if b.to_s.size == n
  end
end

def fib_down(n, b, a, idx)
  loop do
    a, b = b - a, a
    break [idx, b] if a.to_s.size == n - 1
    idx -= 1
  end
end

基准

在计算每个Fibonacci数时，通常执行两个操作：

  • 计算最后计算的斐波那契数中的位数，如果该数等于目标位数，则终止（由于下面的解释部分中明确说明，它不能大于目标数）;其他
  • 计算Fibonacci序列中的下一个数字。

相比之下，我提出的方法执行第一步的次数相对较少。

相对于第二步的第一步有多重要？在第一步中n.digits.size的使用与n.to_s.size的比较如何？让我们运行一些基准来找出答案。

def use_to_s(ndigits)
  case ndigits
  when 1
    [1, 1]
  else
    a = 1
    b = 2
    idx = 3
    loop do
      break [idx, b] if b.to_s.length == ndigits
      a, b = b, a + b
      idx += 1
    end
  end
end

def use_digits(ndigits)
  case ndigits
  when 1
    [1, 1]
  else
    a = 1
    b = 2
    idx = 3
    loop do
      break [idx, b] if b.digits.size == ndigits
      a, b = b, a + b
      idx += 1
    end
  end
end


require 'fruity'

def test(ndigits)
  nfibs, last_fib = use_to_s(ndigits)
  puts "\nndigits = #{ndigits}, nfibs=#{nfibs}, last_fib=#{last_fib}"
  compare do
    try_use_to_s   { use_to_s(ndigits) }
    try_use_digits { use_digits(ndigits) }
    try_estimate   { first_fibonacci_with_n_digits(ndigits) }
  end
end


test 20
ndigits = 20, nfibs=93, last_fib=12200160415121876738
Running each test 128 times. Test will take about 1 second.
try_estimate is faster than try_use_to_s by 2x ± 0.1
try_use_to_s is faster than try_use_digits by 80.0% ± 10.0%


test 100
ndigits = 100, nfibs=476, last_fib=13447...37757 (90 digits omitted)
Running each test 16 times. Test will take about 4 seconds.
try_estimate is faster than try_use_to_s by 5x ± 0.1
try_use_to_s is faster than try_use_digits by 10x ± 1.0


test 500
ndigits = 500, nfibs=2390, last_fib=13519...63145 (490 digits omitted)
Running each test 2 times. Test will take about 27 seconds.
try_estimate is faster than try_use_to_s by 9x ± 0.1
try_use_to_s is faster than try_use_digits by 60x ± 1.0


test 1000
ndigits = 1000, nfibs=4782, last_fib=10700...27816 (990 digits omitted)
Running each test once. Test will take about 1 minute.
try_estimate is faster than try_use_to_s by 12x ± 10.0
try_use_to_s is faster than try_use_digits by 120x ± 100.0

这些结果有两个主要的结果：

  • “try_estimate”是最快的，因为它执行第一步的次数相对较少;和
  • to_s的使用比digits快得多。

除了这些观察中的第一个之外，还注意到与实际指数相比，具有给定位数的第一个FN的索引的初始估计如下：

  • 20位数：96 est。对93实际
  • 100位数：479 est。对476实际
  • 500位数：2392 est。对2390实际
  • 对于1000位数：4785 est。对4782实际

偏差最多为3，意味着必须计算最多3个FN的数字位数才能获得所需的结果。

说明

上面代码部分给出的方法的唯一解释是常量AVG_FNs_PER_DIGIT的推导，它用于计算具有指定位数的第一个FN的索引的估计。

这个常数的推导源于给出here的问题和选定的答案。 （Wiki for Fibonacci numbers提供了对FN数学性质的很好的概述。）

众所周知，前7个FN（包括零）有一个数字;此后，FN每4或5个FN获得一个额外的数字（即，有时为4，否则为5）。因此，作为一个非常粗略的计算，我们看到用n数字计算第一个FN，n >= 2，它将不会小于4*nth FN。对于n = 1000，那将是4,000。 （实际上，4,782nd是最小的有1000位数。）换句话说，我们不需要计算前4,000个FN中的位数。但是，我们可以改进这一估计。

当n接近无穷大时，包含5个FN的范围10**n...10**(n+1)（n-digit interval）与包含4个FN的范围的比率可以如下计算。

LOG_10 = Math.log(10)
  #=> 2.302585092994046
GR = (1 + Math.sqrt(5))/2
  #=> 1.618033988749895
LOG_GR = Math.log(GR)
  #=> 0.48121182505960347

RATIO_5to4 = (LOG_10 - 4*LOG_GR)/(5*LOG_GR - LOG_10)
  #=> 3.6505564183095474

其中GR是Golden Ratio。

在大量的n位数间隔中，n4是包含4个FN的那些间隔的数量，n5是包含5个FN的数量。因此，每个间隔的平均FN数是（n4 * 4 + n5 * 5）/（n4 + n5）。由于n5 / n4收敛到RATIO_5to4，n5接近限制中的RATIO_5to4 * n4（丢弃舍入误差）。如果我们替换n5，然后让

b = 1/(1 + RATIO_5to4)
  #=> 0.21502803321833364

我们发现每n位数间隔的FN平均数收敛于

avg = b * 4 + (1-b) *5
  #=> 4.784971966781667

如果fn是第一个拥有n十进制数字的FN，那么序列中包含fn的FN数量可以近似为

n * avg

例如，如果第一个FN的索引的估计值为1000个十进制数，则为1000 * 4.784971966781667).round #=> 4785。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.