4

我需要维护字符串和整数之间的对应关系，然后查找字符串值并返回整数。满足以下要求的存储此信息的最佳结构是什么：

  • 速度和内存大小按顺序很重要。

  • 我不想重新发明轮子并编写自己的排序程序。调用 Sort(CompareFunction) 当然可以。

条件：

  • 整数不保证是连续的，也没有像 0 或 1 这样的“起始值”

  • 数据对的数量可以从 100 到 100000

  • 数据都是一开始就读入的，没有后续的增删改

  • FWIW 字符串是 Outlook（MAPI？）用来识别条目的十六进制条目 ID。示例：00000000FE42AA0A18C71A10E8850B651C24000003000000040000000000000018000000000000001E7FDF4152B0E944BA66DFBF2C6A6416E4F52000487F22

有很多选项（TStringList（带有对象或名称/值对），TObjectList，TDictionary，...），我最好先征求意见...

我已阅读如何在 Delphi TStringList 中更快地搜索名称/值对？它建议字符串/字符串对的 TDictionary，以及Delphi 2007 中的多维数组排序，它建议字符串/整数的 TStringlist 对象，但对整数进行排序。

4

2 回答 2

7

您在问题中包含的第二个链接不适用。这是一个关于排序而不是有效查找的问题。尽管您在问题中多次讨论排序，但您不需要排序。您的要求只是一个字典，也称为关联数组。当然，您可以通过对数组进行排序并使用二进制搜索进行查找来实现这一点，但排序不是必需的。你只需要一本高效的字典。

开箱即用，对您的问题最有效和最方便的数据结构是TDictionary<string, Integer>. 这具有 O(1) 的查找复杂性，因此可以很好地扩展到大型集合。对于较小的集合，具有 O(log n) 查找复杂度的基于二分查找的查找可能具有竞争力，并且确实可以胜过字典。

Cosmin Prund在 SO 上写了一个很好的答案，他将字典查找的性能与基于二进制搜索的查找进行了比较。我建议你读一读。我想说，对于小型容器，性能对您来说可能不是那么大的问题。因此，即使二进制搜索可能更快，也可能无关紧要，因为无论哪种方式你的性能都很好。但是对于较大的容器，性能可能会成为一个问题，而这正是字典总是更强大的地方。对于足够大的容器，二分查找的性能可能会变得无法接受。

我确信可以产生比 Embarcadero 更有效的字典实现，但我还要说 Embarcadero 实现非常可靠。它使用了一个不错的哈希函数，并且没有任何明显的弱点。

就内存复杂性而言，字典和排序数组之间几乎没有选择余地。不可能改进排序数组以供内存使用。

我建议您从TDictionary<string, Integer>不满足性能要求的情况下开始，并且只关注它。

于 2013-04-22T16:54:36.493 回答
0

看来您要查找长的均匀分布的字符串。这类问题最快的数据结构之一是Trie。

但是您的数据集大小相当小，并且像 THashedStringList 或 TDictionary（更方便）这样的即用型 Delphi 解决方案将提供相当高的速度。

于 2013-04-22T17:22:36.007 回答