delphi - Delphi 中的 TStringList、动态数组还是链接列表？

Question

我有选择。

我有一些已经订购的字符串需要存储和访问。看来我可以选择使用:

1. TStringList

2. 动态字符串数组，以及

3. 字符串链接列表(单链接)

   艾伦在评论中建议我也添加选择:

4. TList<string>

在什么情况下这些方法比其他方法更好？

哪一个最适合小型列表(10 项以下)？

哪一个最适合大型列表(超过 1000 个项目)？

哪一个最适合大型列表(超过 1,000,000 项)？

哪一个最能最大限度地减少内存使用？

哪种方法最能缩短最后添加额外项目的加载时间？

哪一个最能最大限度地减少从头到尾访问整个列表的时间？

在此基础上(或任何其他)，哪种数据结构更可取？

作为引用，我使用的是 Delphi 2009。

<小时/>

迪米特里在评论中说道:

Describe your task and data access pattern, then it will be possible to give you an exact answer

好的。我有一个包含大量数据的家谱程序。

对于每个人，我都有许多事件和属性。我将它们存储为短文本字符串，但每个人都有很多，从 0 到几百个不等。我有成千上万的人。我不需要随机访问它们。我只需要将它们关联为按已知顺序附加到每个人的多个字符串。这是我的数千个“小 list ”的案例。它们需要时间来加载和使用内存，如果我需要它们，则需要时间来访问它们(例如导出整个生成的报告)。

然后我有一些更大的列表，例如我的“虚拟” TreeView 的所有部分的名称，其中可以有数十万个名称。同样，我只需要一个可以通过索引访问的列表。为了提高效率，它们与 TreeView 分开存储，并且 TreeView 仅在需要时检索它们。这需要一段时间来加载，并且对于我的程序来说内存非常昂贵。但我不必担心访问时间，因为一次只访问几个。

希望这能让您了解我正在努力实现的目标。

附:我在 StackOverflow 上发布了很多有关优化 Delphi 的问题。我的程序读取 100,000 人的 25 MB 文件，并在 8 秒内为他们创建数据结构、报告和 TreeView ，但需要使用 175 MB RAM。我正在努力减少这种情况，因为我的目标是在 32 位 Windows 中加载数百万人的文件。

<小时/>

我刚刚在这个 StackOverflow 问题中发现了一些优化 TList 的极好建议: Is there a faster TList implementation?

Answer 1

除非您有特殊需求，否则 TStringList 很难被击败，因为它提供了许多组件可以直接使用的 TStrings 接口(interface)。使用TStringList.Sorted := True，将使用二分搜索，这意味着搜索将非常快。您还可以免费获得对象映射，每个项目还可以与一个指针关联，并且您可以获得所有现有的编码、流接口(interface)、逗号文本、分隔文本等方法。

另一方面，出于特殊需要，如果需要进行多次插入和删除，那么更接近链表的东西会更好。但搜索会变得更慢，而且它确实是一个罕见的字符串集合，永远不需要搜索。在这种情况下，经常使用某种类型的哈希，例如，根据字符串的前 2 个字节创建哈希(预分配长度为 65536 的数组，并将字符串的前 2 个字节直接转换为哈希)索引在该范围内)，然后在该哈希位置，存储一个链表，其中每个项目键由字符串中的剩余字节组成(为了节省空间——哈希索引已经包含前两个字节)。然后，初始哈希查找的时间复杂度为 O(1)，后续的插入和删除都是链表快速的。这是一个可以操纵的权衡，并且杠杆应该是明确的。