Ruby Hashes vs. Arrays：找到一件物品的最快方法？

我正在使用紅寶石將大型TXT文件加載到數組或散列中。輸入文件包含超過1'000'000個MD5散列值，按字母順序排序，無重複。Ruby Hashes vs. Arrays：找到一件物品的最快方法？

什麼是Ruby中最快的方法，以查明某個散列值是否存在於我的數組或散列中？目前我使用數組和「include？」。

def loadhashlist 
@all_hash_values = Array.new 
    f = File.readlines("inputmd5.txt").each do |row| 
    @all_hash_values.push(row.gsub("\n","")) 
    end 
end 

loadhashlist 

def hashlookup(file) 
md5 = file.getMd5 
    if @all_hash_values.include? md5 
    #code goes here 
    end 
end

來源

2017-09-20 Roman77

除了答案，您還可以使用'@all_hash_values = File.foreach（「inputmd5.txt」）清理負載。 row.chomp}'。 'File＃foreach'返回一個'Enumerator'，然後'Enumerator＃map'將根據塊中的返回值返回一個新的'Array'，'String＃chomp'將刪除尾隨的新行字符。現在，您正在使用'File＃readlines'創建'Array'，以將值放入另一個'Array'（'@ all_hash_values'），這也會對性能產生影響。 – engineersmnky

@engineersmnky謝謝你幫我解決這個問題！巨大的差異！用10'000'000行加載inputmd5.txt，過去需要大約40秒。使用你的代碼，我在9秒內完成！ – Roman77

是的，你可以使用一個數組，最好是O(logN)，但它使用一個集合更快且語義更好。

require 'set' 

hashes = Set.new 
hashes << 'foo' 
hashes << 'bar' 
hashes.include?('bar') # => true

在紅寶石集與哈希表實現的，因此查找是O(1)。

來源

2017-09-20 06:00:57

謝謝塞爾吉奧。在第一步中，我在一個集合或一個數組中加載了數千個哈希值，它們的速度幾乎相同。總的來說它非常快：我在10秒內將10'000'000 MD5散列值加載到一個集合/數組中！在腳本的查找部分中使用一個集合，我詢問IF中是否存在某個哈希值，這已經被證明比使用數組快一點。謝謝！ – Roman77

Array#include?是O（N）。

相反，由於數組已經排序，所以可以使用Array#bsearch，它是O（lgN）。

來源

2017-09-20 05:56:47

沒有檢查Ruby中實現細節（如果你完全依賴它，你將不得不基準），但是從我在CS類瞭解到這應該歸結爲：

陣列：基於方法爲O（n）或O（log n）的使用
哈希（假設MD5是關鍵）：O（1）

所以我想利用哈希去。

來源

2017-09-20 06:00:07 ulferts

對於散列而言，「O（1）」顯然是由key_搜索的，而不是由value來搜索的。 – mudasobwa

我至少想寫出它需要md5作爲關鍵。 – ulferts

你有什麼建議作爲價值？如果沒有，那麼塞爾吉奧在最佳答案中將[正確]建議。 – mudasobwa

Ruby Hashes vs. Arrays：找到一件物品的最快方法？

回答

相關問題