在Ruby中将大型哈希划分为N个较小哈希的最有效方法是什么？
问题
我正在研究涉及分片的问题。 作为问题的一部分，我需要找到以两个或更多部分划分大型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] 更好的解决方案
马克和迈克非常友好地提出方法。 我不得不承认Mark的方法感觉不对 – 它完全按照我不想要的方式 – 它循环了所有的成员并评估了有条件的情况 – 但是因为他花时间去做评估，我想我应该尝试类似的方法和基准测试。 这是我的方法的改编版本（我的密钥不是数字所以我不能逐字逐句采用他的方法）
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代码的数量（无循环，无条件） – 运行时间超过9秒
马克的方法运行时间超过5秒
这是一个重大的胜利
带走
不要被’直觉’所迷惑 – 衡量竞争算法的表现
不要担心Ruby作为一种语言的性能 – 我最初担心的是，如果我做了一千万次这样的操作，可能需要花费大量的时间在Ruby上，但事实并非如此。
感谢Mark和Mike，他们都得到了我的帮助。
谢谢！
这可能不足以满足您的需求（听起来他们需要在C中进行扩展），但也许您可以使用Hash #select？
我同意Mike Woodhouse的想法。 您是否可以在构建原始200k项哈希的相同位置构建分片？ 如果项目来自数据库，您可以根据密钥的某些方面或通过重复使用LIMIT 10000等内容一次抓取一个块来将查询拆分为多个不相交的查询。
额外
嗨，Chris，我刚刚比较了你使用Hash＃select的方法：
要求’基准’
s = {} 1.upto(200_000) { |i| s[i] = i} Benchmark.bm do |x| x.report { pivot = s.size / 2 slices = s.each_slice(pivot) s1 = Hash[*slices.entries[0].flatten] s2 = Hash[*slices.entries[1].flatten] } x.report { s1 = {} s2 = {} s.each_pair do |k,v| if k < 100_001 s1[k] = v else s2[k] = v end end } end
它看起来像Hash #select要快得多，即使它遍历每个子哈希的整个大哈希：
# ruby test.rb user system total real 0.560000 0.010000 0.570000 ( 0.571401) 0.320000 0.000000 0.320000 ( 0.323099)
希望这可以帮助。
我不知道如何使用未经修改的“vanilla”哈希来实现这一点 – 我希望您需要进入内部以便将分区划分为某种大容量内存复制操作。 你的C有多好？
我更倾向于考虑分区而不是首先创建Hash，特别是如果首先存在200K项Hash的唯一原因是要细分。
编辑：在健身房考虑之后……
找到一些现有解决方案的问题在于，其他人需要（a）经历过痛苦，（b）具有解决它的技术能力，以及（c）感觉社区友好到足以将其释放到野外。 哦，还有你的操作系统平台。
那么使用B-Tree而不是Hash呢？ 保持按键排序的数据，memcpy（）可以遍历它。 B树检索是O（log N），在大多数情况下对Hash的影响不大。
我在这里找到了一些可能会有所帮助的东西，而且我希望只有一个小鸭子打字包装才能让它像哈希那样嘎嘎叫。
但是，仍然需要那些C / C ++技能。 （我无可救药地生锈了）。