delphi - 通过快速查找字符串来实现字符串/整数对的最佳存储？

Question

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

• 速度和内存大小依次很重要。

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

条件:

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

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

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

• FWIW 字符串是 Outlook(MAPI？)用来识别条目的十六进制条目 ID。示例:00000000FE42AA0A18C71A10E8850B651C24000003000000040000000000000018000000000000001E7FDF4152B0E944BA66DFBF2C6A6416E4F52000487F2 2

有太多选项(TStringList(带有对象或名称/值对)、TObjectList、TDictionary...)，我最好先寻求建议...

我已阅读How can I search faster for name/value pairs in a Delphi TStringList?建议使用 TDictionary 来表示字符串/字符串对，以及 Sorting multidimensional array in Delphi 2007建议使用 TStringlist 对象来表示字符串/整数，但对整数进行排序。

Answer 1

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

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

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

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

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

我建议您从 TDictionary<string, Integer> 开始只有当您的性能要求未得到满足时，才需要考虑其他因素。