问题
我正在研究一个涉及分片的问题。作为问题的一部分,我需要找到最快的方法将大型 Ruby 散列(> 200,0000 个条目)划分为两个或更多部分。
有没有非 O(n) 的方法?
是否有非 Ruby 即 C/C++ 实现?
请不要使用将哈希转换为数组并重建 N 个不同哈希的简单方法来回复示例。
我担心的是 Ruby 做这种工作太慢了。
最初的方法
这是我尝试的第一个解决方案。它的吸引力在于:
- 它不需要盲目地循环遍历哈希
- 它不需要管理计数器来在分片之间均匀分配成员。
- 它看起来又短又整洁
好吧,它不是 O(n),但它依赖于标准库中的方法,我认为这比编写我自己的 Ruby 代码更快。
pivot = s.size / 2
slices = s.each_slice(pivot)
s1 = Hash[*slices.entries[0].flatten]
s2 = Hash[*slices.entries[1].flatten]
更好的解决方案
马克和迈克很友善地提出了一些方法。我不得不承认马克的方法感觉是错误的 - 它确实做了我不想要的事情 - 它循环了所有的成员并评估了一个条件 - 但因为他花时间做了评估,我认为我应该尝试类似的方法并对其进行基准测试。这是我对其方法的改编版本(我的密钥不是数字,所以我不能逐字接受他的方法)
def split_shard(s)
shard1 = {}
shard2 = {}
t = Benchmark.measure do
n = 0
pivot = s.size / 2
s.each_pair do |k,v|
if n < pivot
shard1[k] = v
else
shard2[k] = v
end
n += 1
end
end
$b += t.real
$e += s.size
return shard1, shard2
end
结果
在这两种情况下,大量的哈希值都会被分割成碎片。测试数据集中所有散列的元素总数为 1,680,324。
我最初的解决方案 - 它必须更快,因为它使用标准库中的方法并最大限度地减少 Ruby 代码量(无循环,无条件) - 运行时间刚好超过9s
马克的方法刚刚结束5s
这是一场重大胜利
带走
不要被“直觉”愚弄 - 衡量竞争算法的性能
不要担心 Ruby 作为一种语言的性能 - 我最初担心的是,如果我要执行一千万次这样的操作,那么在 Ruby 中可能会花费大量时间,但事实并非如此。
感谢马克和迈克,他们的帮助都从我这里得到了积分。
Thanks!