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

发布时间：2020-12-15 04:24:05 所属栏目：百科来源：网络整理

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

我有一个由成对的值组成的数据结构,第一个是整数,第二个是字母数字字符串(可以用数字开头)：

+--------+-----------------+
| 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.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!