C# · 12月 23, 2021

哪种C#数据结构允许最有效地搜索一对字符串用于子字符串?

我有一个由成对的值组成的数据结构,第一个是整数,第二个是字母数字字符串(可以用数字开头): +——–+—————–+| Number | Name |+——–+—————–+| 15 | APPLES || 16 | APPLE COMPUTER || 17 | ORANGE || 21 | TWENTY-1 || 291 | 156TH ELEMENT |+——–+—————–+

这些表格最多包含100,000行.

我想提供一个查找功能,用户可以在其中查找数字(就像它是一个字符串)或字符串片段.理想情况下,查找将在用户输入时“实时”;在每次击键之后(或者在短暂延迟~250-500 ms之后),将进行新的搜索以找到最可能的候选者.所以,例如搜索

> 1将返回15 APPLES,16 APPLE COMPUTER,17 ORANGE和
291第156个元素
> 15将搜索范围缩小到15 APPLES,291 156TH ELEMENT
> AP将返回15 APPLES和16 APPLE COMPUTER
>(理想情况下,但不是必需的)ELEM将返回291第156个元素.

我正在考虑使用两个Dictionary< string,string> s,因为最终将int作为字符串进行比较 – 一个将由整数部分索引,另一个将由字符串部分索引.

但实际上通过子串搜索不应该使用哈希函数,使用两倍于我认为我应该需要的内存似乎是浪费.

最终的问题是,是否有任何表现良好的方法可以同时搜索两个大型列表中的子串?

如果不这样,SortedDictionary怎么样?可能会提高性能,但仍然无法解决哈希问题.

考虑在飞行中创建一个正则表达式,但我认为这会表现得非常糟糕.

我是C#的新手(来自Java世界)所以我还没有考虑过LINQ;是答案吗?

编辑18:21 EST:“名称”字段中的所有字符串都不会超过12-15个字符,如果这会影响您的潜在解决方案.

解决方法 我考虑使用 Trie数据结构.

怎么实现呢?叶子代表你的“行”,但你会有“两条路径”到“行”的每个内存实例(一个用于数字,另一个用于名称).

然后你可以牺牲自己的条件:

(ideally,but not required) ELEM will return 291 156TH ELEMENT.

或者为行实例提供更多路径.