如何加速在大型词典中的搜索

Question

我有一个非常庞大的词典，其中的内容看起来像这样：
（字典中不包括标题）

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

我有超过150K行这种字典中的匹配对。

用户输入是关键词（诊断名称），我无法通过关键词搜索字典。

这是代码:

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毫秒，这对我来说已经足够快了。

- Franva

---

大家好，请不要在没有告诉我原因的情况下给我的问题投反对票。我已经查看了其他类似的问题，但是它们都没有真正解决我的问题。 - Franva

如果你的代码中包含字符，那么将它们全部转换为Int64会很困难... - Mark Peters

术语是“延迟执行”。然而，在“Where”和“Select”之间发出额外的ToList不太可能在这种情况下提高性能。如果您多次迭代最终结果（我假设您是这样做的），那么您主要从最终 ToList中受益。尝试将代码从dic.Where(...).ToList().Select(...).ToList()更改为dic.Where(...).Select(...).ToList()-您几乎不会观察到性能上的任何变化。 - Douglas

Answer 1

您的方法有误。字典适用于在您知道键而不是值的情况下进行高效查找。

提高性能的简单方法是构建一个反向字典，模仿全文索引的方式对您的内容进行索引：

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

构建全文索引需要花费较长时间；不过，这是一次性的成本，并且将通过后续查找节省的时间来摊销。

- Douglas

---

谢谢，我正在努力 :) - Franva

嗨，道格拉斯，我发现问题隐藏在我的代码中。但无论如何，我还是喜欢你的方法，谢谢 :) - Franva

Answer 2

你的问题在于，通过迭代字典的值，你失去了字典所有速度优势。字典是针对键查找进行优化的。

我会使用不同的数据类型来处理，并将其优化为关键字查找。

以下是一个使用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"]));

请注意，这假定您正在查找整个关键字（您最初的示例可以查找部分关键字）。

- Mark Peters