Ruby中select方法的性能

Question

Ruby中的select方法简单直接.它将选择符合特定条件的数组中的元素.

例如,

>> x = [4,5,7,89,4,5,3,6,8,9,4,45,56,23,2,7,3,5,4,224,234,565,546,345,23,234,234,234,23466,25,54]
x = [4,5,7,89,4,5,3,6,8,9,4,45,56,23,2,7,3,5,4,224,234,565,546,345,23,234,234,234,23466,25,54]
=> [4, 5, 7, 89, 4, 5, 3, 6, 8, 9, 4, 45, 56, 23, 2, 7, 3, 5, 4, 224, 234, 565, 546, 345, 23, 234, 234, 234, 23466, 25, 54]
>> y = x.select{|m| m>20 && m<200}
y = x.select{|m| m>20 && m<200}
=> [89, 45, 56, 23, 23, 25, 54]

关于这一点的一个问题显然是时间损失.选择必须遍历该数组中的所有值,并执行顺序检查,这将导致在O(n)时间内运行.有没有更好的选择来选择哪一个在较短的时间内完成.空间对我来说不是问题.

我正在谈论重复使用相同选择的情况.如果我要在一个大小为n的数组的循环中使用相同的选择条件1000次,那么我将必须执行1000*n次的操作.如果它针对空间进行了优化,那么我只会做1000*1次.

谢谢.

Answer 1

我不知道有一种方法可以比线性时间更好地对数组中的每个元素执行操作 - 这个想法听起来是自相矛盾的.如果你需要在同一个数组上多次进行相同的计算,以便在后续运行中交换空间以获得恒定时间性能,你可以记住结果,但我认为O(n)和其他方面一样好.