2

昨天我问了一个关于比较重叠范围的问题，从那以后它一直卡在我的喉咙里。

共识似乎是我的首选答案涉及使用数组交集运算符 (&)，效率低下，因为比较数组的成本很高。

那么我想知道，为什么这个功能在语言中？难道语言的创造者认为有时你需要一种优雅的方式来实现解决方案，即使这样做很昂贵？比较数组的成本是否如此高，以至于您应该尽可能避免它？Ruby 对我的全部吸引力在于关注语法优雅而不是过早优化。

4

4 回答 4

13

&不是特别低效的方法。我认为您误解了对已接受答案的批评。

您首选的解决方案效率低下，因为它将范围转换为数组。

诸如范围之类1..10000的内存占用相对较小 - 它仅存储起点和终点。但是，如果将其转换为数组，则会为所有 10,000 个条目分配内存。

于 2009-03-31T17:06:10.153 回答
4

昨天问题的措辞听起来像是在计算二进制条件：这些范围是否重叠？给出的答案可以在恒定时间内计算出来，因此如果它们对您有用，那么坚持使用它们是有意义的。

如果您需要知道重叠的程度，则 & 运算符将是合适的，但这不是您要问的。

至于它为什么存在，我只能推测：它不仅增加了便利性，而且不难想象语言环境可以优化数组联合操作的方式——即使它的计算可能仍然需要线性或在最坏的情况下为 n*log(n) 时间。（如果每个操作都必须有一个恒定时间的结果，我们就必须摆脱很多方法！）

于 2009-03-31T17:00:31.680 回答
0

Ruby 中的数组是无类型的：它们可以包含多种类型，包括哈希、其他数组、符号等。在类型化数组中，排序和比较要简单得多。比较无类型集合（尤其是包含集合的集合）本质上成本更高。

于 2009-03-31T17:12:24.477 回答
0

就测试而言，这似乎并不算太​​糟糕。机器是i7（2.0Ghz双核）

#!/bin/ruby
require 'benchmark'
n = []
1.upto(10_000_000) do |i|
  n << i
end

m = Array.new(1000000){ rand(10_000_000)+1 }

Benchmark.bm(10) do |x|
  x.report('array_intersection'){ n & m }
end

                    user     system      total        real
array_intersection  2.870000   0.040000   2.910000 (  2.895202)
于 2012-07-26T00:13:48.490 回答