为什么 sum 比 insert(:+) 快得多?

2024-04-08

所以我在 Ruby 2.4.0 中运行一些基准测试并意识到

(1...1000000000000000000000000000000).sum

立即计算而

(1...1000000000000000000000000000000).inject(:+)

花了太长时间,我刚刚中止了操作。我的印象是Range#sum是一个别名Range#inject(:+)但似乎事实并非如此。那么如何sum工作,为什么它比inject(:+)?

N.B.的文档Enumerable#sum(这是由Range) 没有提及任何有关惰性求值或类似内容的内容。


简短回答

对于整数范围:

  • Enumerable#sum回报(range.max-range.min+1)*(range.max+range.min)/2
  • Enumerable#inject(:+)迭代每个元素。

Theory

1 到 1 之间的整数之和n被称为三角数 https://en.wikipedia.org/wiki/Triangular_number,并且等于n*(n+1)/2.

之间的整数之和n and m是三角形数m减去三角形数n-1,等于m*(m+1)/2-n*(n-1)/2,并且可以写成(m-n+1)*(m+n)/2.

Ruby 2.4 中的枚举#sum

该属性用于Enumerable#sum http://ruby-doc.org/core-2.4.0/Enumerable.html#method-i-sum对于整数范围:

if (RTEST(rb_range_values(obj, &beg, &end, &excl))) {
    if (!memo.block_given && !memo.float_value &&
            (FIXNUM_P(beg) || RB_TYPE_P(beg, T_BIGNUM)) &&
            (FIXNUM_P(end) || RB_TYPE_P(end, T_BIGNUM))) { 
        return int_range_sum(beg, end, excl, memo.v);
    } 
}

int_range_sum看起来像这样:

VALUE a;
a = rb_int_plus(rb_int_minus(end, beg), LONG2FIX(1));
a = rb_int_mul(a, rb_int_plus(end, beg));
a = rb_int_idiv(a, LONG2FIX(2));
return rb_int_plus(init, a);

这相当于:

(range.max-range.min+1)*(range.max+range.min)/2

前面提到的平等!

复杂

非常感谢 @k_g 和 @Hynek-Pichi-Vychodil 的这一部分!

sum

(1...1000000000000000000000000000000).sum需要三次加法、一次乘法、一次减法和一次除法。

它的运算次数是恒定的,但乘法是 O((log n)²),所以Enumerable#sum对于整数范围来说是 O((log n)²)。

inject

(1...1000000000000000000000000000000).inject(:+)

需要999999999999999999999999999998个补充!

加法是 O(log n),所以Enumerable#inject是 O(n log n)。

With 1E30作为输入,inject永远不会回来。太阳早就爆炸了!

Test

检查 Ruby 整数是否被添加很容易:

module AdditionInspector
  def +(b)
    puts "Calculating #{self}+#{b}"
    super
  end
end

class Integer
  prepend AdditionInspector
end

puts (1..5).sum
#=> 15

puts (1..5).inject(:+)
# Calculating 1+2
# Calculating 3+3
# Calculating 6+4
# Calculating 10+5
#=> 15

确实,从enum.c评论 :

Enumerable#sum方法可能不尊重方法的重新定义"+"方法如Integer#+.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

为什么 sum 比 insert(:+) 快得多? 的相关文章

  • 通过名称查找进程ID

    如何在 Ruby 中通过名称或完整命令行找到 pid 而不调用外部可执行文件 我正在将 SIGUSR2 发送到命令行包含的进程ruby job rb 我想在不打电话的情况下执行以下操作pgrep uid Process uid pid pg
  • Selenium 找不到“spec”文件夹

    因此 我正在尝试建立本地系统来帮助完成仅使用 Rails 的雇主的现有项目 他们希望我主要关注 rspec 测试 因为该项目几乎可以正常运行 我需要充实他们错过的东西 但是 我无法获取 rake spec 来构建我的测试文件夹 事实上 测试
  • 尝试使用适用于 Windows XP 的 Heroku 时未找到 msvcrt-ruby18.dll

    我有一个学生在 Windows XP 上进行开发 他在尝试运行时遇到了一个奇怪的错误heroku keys add 错误是 This application has failed to start because msvcrt ruby18
  • 如何在 Ruby 中列出局部变量?

    def method a 3 b 4 some method that gives a b end 局部变量 http ruby doc org core Kernel html method i local variables 它输出符号
  • 如何使用 Nokogiri 获取某些标签之后或之前的文本

    我有一个 HTML 文档 如下所示
  • rvm编译安装ruby 2.5.0出错

    我正在尝试使用 rvm 安装 ruby 2 5 0 但出现错误 我在 Ubuntu 18 16 和现在的 Linux Mint Cinnamon 上尝试过 基本上我在运行安装 ruby 的代码之前所做的是 打开 GPG 密钥https rv
  • Rails 中的 PDF 导出

    我需要将包含一些图表的 HTML 页面导出为 PDF 有哪些好的 gem 可以做到这一点 PDFKit http railscasts com episodes 220 pdfkit http railscasts com episodes
  • 转储 YAML 时如何强制使用双引号?

    我有一个小脚本来自动化 YAML 文件中的一些操作 我读取原始 YAML 文件并将其转换为哈希 然后dump http ruby doc org stdlib 1 8 6 libdoc yaml rdoc YAML html method
  • Watir 更改 Mozilla Firefox 首选项

    我正在使用 Watir 运行 Ruby 脚本来自动执行一些操作 我正在尝试自动将一些文件保存到某个目录 因此 在我的 Mozilla 设置中 我将默认下载目录设置为桌面并选择自动保存文件 然而 当我开始运行脚本时 这些更改并未反映出来 似乎
  • 如何计算带有偏移量的异或?

    我想用不同的偏移量进行异或计算以在计算中列出 例子 key 0 1 0 text 0 1 0 1 0 1 0 1 1 1 异或计算 key 0 text 0 key 1 text 1 key 2 text 2 key 0 text 3 ke
  • yard 0.7.3 无法在 Markdown 和 Textile 中构建我的自述文件

    我决定将我的项目中的 README 文件转换为 Markdown 并一直使用yard 验证文档是否正确呈现 所以我安装了 rdiscount 将 README 更改为 README md 并尝试 yard doc README md 这给了
  • Ruby 中的任务/未来

    代表潜在延迟的异步计算并且可以订阅其完成的模式的惯用 Ruby 模拟是什么 即类似于 NET 的东西System Threading Task 或Python 3 xconcurrent futures future 请注意 这并不一定意味
  • Heroku 部署错误

    在 Windows 环境中 尝试部署到 Heroku 时出现以下错误 C Ruby lib ruby gems 1 8 gems heroku 1 9 13 lib heroku commands base rb 32 in 没有这样的文件
  • ruby 中的 #encode 和 #force_encoding 有什么区别?

    我真的不明白之间的区别 encode and force encoding在 Ruby 中String班级 我明白那个 kam force encoding UTF 8 将迫使 kam 是UTF 8编码 但是怎么样 encode encod
  • “rmagick”gem 安装问题

    我在尝试在 centos 上安装 rmagick gem 时遇到问题 以下是我得到的输出 谁能帮我识别一下我缺少什么包裹 我已经安装了所有提到的另一个堆栈溢出线程 RMagick安装错误 https stackoverflow com qu
  • 我在 Rails 中使用了保留字吗?

    这是我的模型 class Record lt ActiveRecord Base belongs to user belongs to directory end class Directory lt ActiveRecord Base h
  • Nokogiri 保持 HTML 实体不变

    我希望 Nokogiri 保持 HTML 实体不变 但它似乎正在将实体转换为实际的符号 例如 Nokogiri HTML fragment p reg p to s 结果是 p p 似乎没有什么可以将原始 HTML 返回给我 inner h
  • rvm gem 安装错误?

    我正在摆弄 ruby gems 和 rvm 它工作得很好 但现在当我尝试安装 gem 时出现错误 gem install Rails错误 同时 执行 gem Errno EACCES 权限被拒绝 Users da rvm gems ruby
  • Bundle 说 gem 丢失了 - 但事实并非如此?

    背景 我正在维护contentRuby On Rails 站点 但我确实没有 Rails 的经验 当尝试运行 Rails 服务器时 rails s我明白了 在任何来源中均找不到 activesupport 3 2 0 Run bundle
  • 用户未定义的方法 attr_accessible 错误

    我正在尝试创建某种登录 我创建了一个用户脚手架并将此代码放在我的 user rb 中 class User lt ActiveRecord Base attr accessible name password digest password

随机推荐