您擁有的結構類型一旦變大就會導致查找速度緩慢。如果您的數據集將會很大,並且您沒有後端數據庫將索引字段與索引字段一起存儲以進行搜索,那麼您可以通過預先創建一個值並搜索它而不是迭代數組並查看哈希值。做一次,當散列數組已經創建並且穩定。
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