您拥有的结构类型一旦变大就会导致查找速度缓慢。如果您的数据集将会很大,并且您没有后端数据库将索引字段与索引字段一起存储以进行搜索,那么您可以通过预先创建一个值并搜索它而不是迭代数组并查看哈希值。做一次,当散列数组已经创建并且稳定。
vals.include?('a') #=> true
vals.include?('z') #=> false
如果你将有很多的:如果你要反复做查找
vals = pages.inject([]){ |m,h| m += h.values; m } #=> ["a", "d", "b", "e", "c", "f"]
将其赋值给一个变量会加快,如果你有问题的价值看的任务重复您的散列值,这可能是值得使用一套,而不是一个数组。
require 'set'
pages.inject([].to_set){ |m,h| m += h.values; m } #=> #<Set: {"a", "d", "b", "e", "c", "f"}>
到一个集的优点是它仅保持任何特定元件的一个副本;重复被忽略,保持您的搜索列表尽可能小。缺点是Set在创建时会有更多的开销,从而减慢其创建时间。集虽然基于哈希,所以它们比顺序搜索更快。为了说明在数组上迭代的速度有多慢,下面是一个搜索52个哈希的基准,分别寻找'A'或'z',第一个或最后一个元素。第二个建立值的列表然后测试列入。最后两个做同样的只使用集而不是阵列。
require 'benchmark'
require 'set'
puts "RUBY_VERSION=#{ RUBY_VERSION }"
# build a 52-element array.
pages = (('A'..'Z').to_a + ('a'..'z').to_a).each_slice(2).inject([]) { |m,a| m << { uri:a[0], page:a[1] }; m }
n = 500_000
Benchmark.bm(20) do |x|
x.report("AoH traversal A") { n.times { pages.any?{ |h| h.has_value?('A') } } }
x.report("AoH traversal z") { n.times { pages.any?{ |h| h.has_value?('z') } } }
x.report("array inclusion A") { vals = pages.inject([]){ |m,h| m += h.values; m }; n.times { vals.include?('A') } }
x.report("array inclusion z") { vals = pages.inject([]){ |m,h| m += h.values; m }; n.times { vals.include?('z') } }
x.report("set inclusion A") { vals = pages.inject([].to_set){ |m,h| m += h.values; m }; n.times { vals.include?('A') } }
x.report("set inclusion z") { vals = pages.inject([].to_set){ |m,h| m += h.values; m }; n.times { vals.include?('z') } }
end
# >> RUBY_VERSION=1.9.2
# >> user system total real
# >> AoH traversal A 1.140000 0.000000 1.140000 ( 1.140952)
# >> AoH traversal z 19.130000 0.010000 19.140000 (19.135050)
# >> array inclusion A 0.450000 0.000000 0.450000 ( 0.443042)
# >> array inclusion z 5.600000 0.010000 5.610000 ( 5.605876)
# >> set inclusion A 0.490000 0.000000 0.490000 ( 0.492484)
# >> set inclusion z 0.480000 0.000000 0.480000 ( 0.479374)
编辑:
每次我做一个插入时
,我首先需要做一次检查。这是网络蜘蛛的一部分。我将在未来考虑分贝。
看看基准的结果。
您选择的答案和假定实施的解决方案平均比使用Set进行查找要慢20倍。你可以维护一个Set,并且你的结构仍然遥遥领先,因为Set的查找速度会降低得更慢。单独维护数组的速度大约快10倍。
例如,检查Set for a hit or miss。如果这是一个转移到下一页的命中。如果错误push
将信息放入你的哈希数组中,则将必要的命中信息添加到下一个循环的Set中。不要每次都完全重建Set,只添加新的信息。
在一个快速而肮脏的蜘蛛,我会使用一个哈希,其中的键是我扫描的URL。我会通过剥离所有查询,会话和其他数据来标准化它们,只留下页面的基本URL。通过这种方式,我可以跟踪是否已经看到该页面并跳过它,否则当查询更改时,最终可能会多次触击同一页面。哈希键指向包含从扫描页面搜集的所有信息的结构,因此,在处理结束时,我可以通过散列哈希键来转储每个页面的结果。
当使用数据库时,同样的策略适用,否则您可以使用冗余页面扫描来填充表格,而不是实际查看唯一页面。
@锡铁人。 +1我真的很喜欢这个答案,但是每次我插入时,都需要先进行检查。这是网络蜘蛛的一部分。我将在未来考虑分贝。 – bluekeys 2011-03-19 16:44:03
@dsjbirch,请参阅我的答案中的编辑。 – 2011-03-19 19:04:18
@锡锡人。感谢您的建议。 – bluekeys 2011-03-19 20:27:03