昨天我问了一个关于比较重叠范围的问题,从那以后它一直卡在我的喉咙里。
共识似乎是我的首选答案涉及使用数组交集运算符 (&),效率低下,因为比较数组的成本很高。
那么我想知道,为什么这个功能在语言中?难道语言的创造者认为有时你需要一种优雅的方式来实现解决方案,即使这样做很昂贵?比较数组的成本是否如此高,以至于您应该尽可能避免它?Ruby 对我的全部吸引力在于关注语法优雅而不是过早优化。
昨天我问了一个关于比较重叠范围的问题,从那以后它一直卡在我的喉咙里。
共识似乎是我的首选答案涉及使用数组交集运算符 (&),效率低下,因为比较数组的成本很高。
那么我想知道,为什么这个功能在语言中?难道语言的创造者认为有时你需要一种优雅的方式来实现解决方案,即使这样做很昂贵?比较数组的成本是否如此高,以至于您应该尽可能避免它?Ruby 对我的全部吸引力在于关注语法优雅而不是过早优化。
&
不是特别低效的方法。我认为您误解了对已接受答案的批评。
您首选的解决方案效率低下,因为它将范围转换为数组。
诸如范围之类1..10000
的内存占用相对较小 - 它仅存储起点和终点。但是,如果将其转换为数组,则会为所有 10,000 个条目分配内存。
昨天问题的措辞听起来像是在计算二进制条件:这些范围是否重叠?给出的答案可以在恒定时间内计算出来,因此如果它们对您有用,那么坚持使用它们是有意义的。
如果您需要知道重叠的程度,则 & 运算符将是合适的,但这不是您要问的。
至于它为什么存在,我只能推测:它不仅增加了便利性,而且不难想象语言环境可以优化数组联合操作的方式——即使它的计算可能仍然需要线性或在最坏的情况下为 n*log(n) 时间。(如果每个操作都必须有一个恒定时间的结果,我们就必须摆脱很多方法!)
Ruby 中的数组是无类型的:它们可以包含多种类型,包括哈希、其他数组、符号等。在类型化数组中,排序和比较要简单得多。比较无类型集合(尤其是包含集合的集合)本质上成本更高。
就测试而言,这似乎并不算太糟糕。机器是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)