如何加快在一個巨大的字典搜索

我有一個非常龐大的詞典，裏面的內容，它看起來像：
（在字典中不包括標題）如何加快在一個巨大的字典搜索

(code)  (names) 
------------------------------ 
910235487  Diabetes, tumors, sugar sick, .....

我有超過15萬線這種對在字典中。

用戶輸入是關鍵字（診斷名稱），我無法通過鍵搜索字典。

下面是代碼：

var relevantIDs = this.dic.Where(ele => ele.Value.Contains(keyword)).Select(n => Convert.ToUInt64(n.Key));

字典是Dictionary<string, string>和我必須使用字符串作爲密鑰的數據類型，這是因爲代碼可以有時含有的字符。名稱列包含相關診斷名稱的列表。所以我也不能改變這種數據類型。

我認爲這個問題是對的每個值，我做了Contains操作並會減慢誰處理，但我不能找到一個替代辦法做下去......

這是我做過什麼以找到匹配的代碼。
但是，這段代碼的性能很糟糕（完成這一行代碼大約需要5分鐘）。

有人可以幫忙嗎？

更新和簡單的解決方案：

我終於找到了賽季爲什麼搜索是如此緩慢，並通過這樣做解決了這個問題：

var relevantStringIDs = this.dic.Where(ele => ele.Value.Contains(keyword)).Tolist(); 
var relevantUlongIDs = relevantStringIDs.Select(n => Convert.ToUInt64(n.Key)).Tolist();

之所以說它是慢是this.dic.Where(ele => ele.Value.Contains(keyword))，每執行一次查詢的第二部分就會執行（這是IEnumberable<T>的功能，我忘記了它的用語（可能是延遲執行））。因此，我使用ToList()將延遲查詢轉換爲內存中的具體列表，以便在將字符串轉換爲ulongs時可以重新使用結果，而不是爲每次轉換再次執行查詢。
如果您在此解釋中發現錯誤，請糾正我。

順便說一句，雖然這可能不是最好的解決方案，但改變後的代碼的性能很安靜。代碼的第一個聲明只需169 ms，對我來說足夠快。

來源

2013-07-16 Franva

嗨，大家好，請不要downvote我的問題沒有告訴我的原因。我查了其他類似的問題，但沒有一個真正解決了我的問題。 – Franva

如果您的代碼可以包含字符，您將很難將它們全部轉換爲Int64 ... –

術語是「[延期執行]」（http://msdn.microsoft.com/en-us/library /bb943859.aspx）」。然而，在Where和Select之間發佈一個額外的ToList在這種情況下不太可能有助於提高性能。如果你多次迭代最終結果（我假設你是），那麼你主要從* final *'ToList'中受益。嘗試從'dic.Where（...）。ToList（）。選擇（...）。ToList（）'到'dic.Where（...）。Select。（...）。ToList ）' - 你會發現性能幾乎沒有變化。 – Douglas

你這樣做是錯誤的。當您知道密鑰時，字典允許高效查找，而不是數值。

固定性能將構建一個反向字典在你的內容模仿全文索引的一個簡單的方法：

var dic = new Dictionary<string, string>(); 
dic.Add("910235487", "Diabetes, tumors, sugar sick"); 
dic.Add("120391052", "Fever, diabetes"); 

char[] delimiters = new char[] { ' ', ',' }; 

var wordCodes = 
    from kvp in dic 
    from word in kvp.Value.Split(delimiters, StringSplitOptions.RemoveEmptyEntries) 
    let code = long.Parse(kvp.Key) 
    select new { Word = word, Code = code }; 

var fullTextIndex = 
    wordCodes.ToLookup(wc => wc.Word, wc => wc.Code, StringComparer.OrdinalIgnoreCase); 

long[] test1 = fullTextIndex["sugar"].ToArray();  // Gives 910235487 
long[] test2 = fullTextIndex["diabetes"].ToArray(); // Gives 910235487, 120391052

全文索引將需要很長時間的建設;然而，這是一次性成本，並且將通過隨後查找節省的時間來攤銷。

來源

2013-07-16 00:50:15 Douglas

+1比我的一點清潔，我認爲 –

謝謝，我在嘗試:) – Franva

嗨，道格拉斯，我發現隱藏在我的代碼中的問題。但是，無論如何，我喜歡你的方式，謝謝:) – Franva

您的問題是您通過迭代它的值而失去了字典的所有速度優勢。字典針對密鑰查找進行了優化。

我會用不同的數據類型來處理它，併爲你的關鍵字查找進行優化。

下面是使用LINQ從類似於您的數據創建Lookup的示例。在這種情況下，我直接從字符串數據構建它，這完全避免了字典。

這種類型的查找應該更好。

string [] lines = { 
"123 A, B, C, D", 
"456 E, F, G", 
"321 A, E, H, I", 
"654 B, G", 
"789 A, J, K, L", 
"987 A, M, L, E" 
}; 

var lookup = lines.SelectMany (
    l => (l.Split(new char[]{' '},2)[1]).Split(',').Select (v => v.Trim().ToLower()).ToArray(), 
    (l,o) => new{ 
    keyword = o, 
    code = Convert.ToInt64(l.Split(' ')[0]) 
}).ToLookup(k => k.keyword, v => v.code).Dump(); 

Console.WriteLine(String.Join(",",lookup["a"])); 
Console.WriteLine(String.Join(",",lookup["l"])); 
Console.WriteLine(String.Join(",",lookup["b"]));

注意，這裏假設你正在尋找一個個完整的關鍵字（您最初的例子中可以查找局部關鍵字）

來源

2013-07-16 00:59:07

謝謝馬克:)我現在就試試 – Franva

+1使用LookUp :)乾杯 – Franva

如何加快在一個巨大的字典搜索

回答

相關問題