如何确定 Big O 比较 Ruby 中的两个数组
How to determine Big O comparing two arrays in Ruby
我的算法水平不行。我创建了一个方法来查看两个数组是否包含相同的元素（重复无关紧要）：
one = [1, "taco", 3, 2, :piece, 4, 5, 5, 5, 5]
two = [:piece, 2, 5, 4, 1, "taco", 3]
def same_elements?(array_one, array_two)
return true if ( (array_one - array_two).empty? && (array_two - array_one).empty? )
return false
end
same_elements?(one, two)
这 returns 正确（正确）。问题是，我不确定这个算法的效率是多少。我的第一个猜测是 O(n^2)，因为我们必须同时检查 a-b 和 b-a。我知道 O(n^2) 非常糟糕。有没有更有效的方法来做到这一点？
令第一个和第二个数组的大小分别为m和n。查看 rb_ary_diff 的源代码（参见上面 Joel Cornett 的评论），有一个 for 循环运行 O(m) 次。在循环内部有一个似乎搜索散列的调用。此操作通常需要 O(n) 时间。因此，假设所有其他调用都比 O(mn) 渐近地快，那么总体差异函数复杂度为 O(mn)。调用此函数两次，然后进行空检查导致您的算法为 O(mn)。
平均而言，哈希搜索是恒定的，即 O(1)，这意味着在这种情况下，您的算法在 O(n) 中执行。不过，哈希搜索最坏情况下的复杂度是 O(n)，这意味着您的算法是 O(mn)。找到一个证明这一点的例子是一个很好的练习。
简答
O(n+m) 平均
最坏的情况是 O(nm)，但只有当你真的想实现它时才会发生（见最后一段）。
如果选择array_one大于array_two，O(m+n)就是O(n)，所以这个算法平均线性时间运行s .
备选
另一个更短的检查方法是：
one = [1, "taco", 3, 2, :piece, 4, 5, 5, 5, 5]
two = [:piece, 2, 5, 4, 1, "taco", 3]
puts Set[*one] == Set[*two] #=> true
# or
puts one.to_set == two.to_set #=> true
小型重构
return true if x
return false
等同于
x
所以你的代码可以这样写:
def same_elements?(array_one, array_two)
(array_one - array_two).empty? && (array_two - array_one).empty?
end
基准
我创建了一个包含 1E6 个元素的数组，其中一半是 0 到 199999 之间的随机数（用于碰撞），另一半是普通 Ruby 个对象。
另一个数组只是第一个，随机打乱。
N = 1_000_000
one = (1..N).map{rand < 0.5 ? rand(N/5) : Object.new}
two = one.sort_by{rand}
比较集合需要 1 分钟，fruity 报告说集合比较比 OP 的方法快大约 20%。
对于较小的整数数组，OP 的方法要快一些。
注意：据报道@engineersmnky 在评论中提出的代码具有与其他方法相似的速度。
时间复杂度
你的代码肯定是不是 O(nm)当与通常的数组一起使用时。
大约时间是：
- 1E4 为 1 秒
- 1E5 为 8 秒
- 1E6 为 160 秒
查看array.c中的rb_ary_diff，难怪上面描述的所有方法同时出现运行：它们的工作原理基本相同。
rb_ary_diff 为 array_two 创建哈希 [=104=]（在 O(m) 中），并迭代 array_one 的每个元素（在 O(n) 中） ，寻找散列 table 中的值（平均 O(1)）。整个操作平均为 O(n+m)。
这个blog post analyses set intersection，实现方式非常相似。
做两次不会改变任何东西，所以总体时间复杂度保持为 O(n+m)。
寻找 O(mn)
使该算法成为 O(mn) 的一种方法是完全禁用散列方法。没有理由这样做，只是为了证明这是一个非常糟糕的主意。
有 10_000 个 KeyObjects :
class KeyObject < Object
end
集合比较不到1秒
有 10_000 个 KeyObjects :
class KeyObject < Object
def hash
1
end
end
集合比较需要超过 14 分钟！
2 个不同的随机 Ruby 对象具有相同哈希值的概率约为 1E-20。严格来说，这个算法的最坏情况是 O(mn)，但如果你不去寻找它，它 永远不会 发生。找到与 2 个元素的碰撞并非易事，找到与 1E6 个元素的碰撞不会偶然发生。
我的算法水平不行。我创建了一个方法来查看两个数组是否包含相同的元素（重复无关紧要）：
one = [1, "taco", 3, 2, :piece, 4, 5, 5, 5, 5]
two = [:piece, 2, 5, 4, 1, "taco", 3]
def same_elements?(array_one, array_two)
return true if ( (array_one - array_two).empty? && (array_two - array_one).empty? )
return false
end
same_elements?(one, two)
这 returns 正确（正确）。问题是，我不确定这个算法的效率是多少。我的第一个猜测是 O(n^2)，因为我们必须同时检查 a-b 和 b-a。我知道 O(n^2) 非常糟糕。有没有更有效的方法来做到这一点？
令第一个和第二个数组的大小分别为m和n。查看 rb_ary_diff 的源代码（参见上面 Joel Cornett 的评论），有一个 for 循环运行 O(m) 次。在循环内部有一个似乎搜索散列的调用。此操作通常需要 O(n) 时间。因此，假设所有其他调用都比 O(mn) 渐近地快，那么总体差异函数复杂度为 O(mn)。调用此函数两次，然后进行空检查导致您的算法为 O(mn)。
平均而言，哈希搜索是恒定的，即 O(1)，这意味着在这种情况下，您的算法在 O(n) 中执行。不过，哈希搜索最坏情况下的复杂度是 O(n)，这意味着您的算法是 O(mn)。找到一个证明这一点的例子是一个很好的练习。
简答
O(n+m) 平均
最坏的情况是 O(nm)，但只有当你真的想实现它时才会发生（见最后一段）。
如果选择array_one大于array_two，O(m+n)就是O(n)，所以这个算法平均线性时间运行s .
备选
另一个更短的检查方法是：
one = [1, "taco", 3, 2, :piece, 4, 5, 5, 5, 5]
two = [:piece, 2, 5, 4, 1, "taco", 3]
puts Set[*one] == Set[*two] #=> true
# or
puts one.to_set == two.to_set #=> true
小型重构
return true if x
return false
等同于
x
所以你的代码可以这样写:
def same_elements?(array_one, array_two)
(array_one - array_two).empty? && (array_two - array_one).empty?
end
基准
我创建了一个包含 1E6 个元素的数组，其中一半是 0 到 199999 之间的随机数（用于碰撞），另一半是普通 Ruby 个对象。
另一个数组只是第一个，随机打乱。
N = 1_000_000
one = (1..N).map{rand < 0.5 ? rand(N/5) : Object.new}
two = one.sort_by{rand}
比较集合需要 1 分钟，fruity 报告说集合比较比 OP 的方法快大约 20%。
对于较小的整数数组，OP 的方法要快一些。
注意：据报道@engineersmnky 在评论中提出的代码具有与其他方法相似的速度。
时间复杂度
你的代码肯定是不是 O(nm)当与通常的数组一起使用时。
大约时间是：
- 1E4 为 1 秒
- 1E5 为 8 秒
- 1E6 为 160 秒
查看array.c中的rb_ary_diff，难怪上面描述的所有方法同时出现运行：它们的工作原理基本相同。
rb_ary_diff 为 array_two 创建哈希 [=104=]（在 O(m) 中），并迭代 array_one 的每个元素（在 O(n) 中） ，寻找散列 table 中的值（平均 O(1)）。整个操作平均为 O(n+m)。
这个blog post analyses set intersection，实现方式非常相似。
做两次不会改变任何东西，所以总体时间复杂度保持为 O(n+m)。
寻找 O(mn)
使该算法成为 O(mn) 的一种方法是完全禁用散列方法。没有理由这样做，只是为了证明这是一个非常糟糕的主意。
有 10_000 个 KeyObjects :
class KeyObject < Object
end
集合比较不到1秒
有 10_000 个 KeyObjects :
class KeyObject < Object
def hash
1
end
end
集合比较需要超过 14 分钟！
2 个不同的随机 Ruby 对象具有相同哈希值的概率约为 1E-20。严格来说，这个算法的最坏情况是 O(mn)，但如果你不去寻找它，它 永远不会 发生。找到与 2 个元素的碰撞并非易事，找到与 1E6 个元素的碰撞不会偶然发生。