在Delphi中，TStringList、动态数组或链表哪个更好？

Question

我需要选择一种存储和访问已排序字符串的方式，有以下几种选择：

1. TStringList

2. 字符串动态数组

3. 字符串单向链表

4. TList<string>

在什么情况下，每种方法都比其他方法更好？

哪个适合小列表（少于10个项目）？

哪个适合大列表（超过1000个项目）？

哪个适合超大列表（超过1,000,000个项目）？

哪个可用于最小化内存使用？

哪个可用于添加额外项目到末尾的最短加载时间？

哪个可用于最小化从头到尾访问整个列表所需的访问时间？

基于这些条件或其他条件，哪种数据结构更好？

参考资料：我正在使用 Delphi 2009。

---

Dimitry 在评论中说：

描述你的任务和数据访问模式，然后就可以给你一个确切的答案了

好的。我的家谱程序有很多数据。

对于每个人，我有许多事件和属性。我把它们存储为短文本字符串，但对于每个人，这些事件和属性有很多，数量从0到几百不等。而且我有成千上万的人。我不需要随机访问它们。我只需要将它们作为已知顺序的一些字符串与每个人相关联。这是我的数千个“小列表”情况。它们需要时间来加载和使用内存，并且如果我需要全部访问它们（例如导出整个生成的报告），则需要时间来访问。

我有几个更大的列表，例如“虚拟”树视图部分名称的所有名称，可以有数十万个名称。再次强调，我只需要一个按索引访问的列表。为了提高效率，这些信息被单独存储于树视图之外，只有在需要时才会检索。这需要一段时间来加载，并且对我的程序非常消耗内存。但是由于每次仅访问其中的几个，所以我不必担心访问时间。

希望这能让您了解我试图实现什么。

p.s. 我在StackOverflow上发布了很多关于优化Delphi的问题。我的程序可以在8秒钟内读取100,000人的25 MB文件，并为他们创建数据结构、报告和树视图，但使用了175 MB的RAM。我正在努力减少它，因为我的目标是在32位Windows中加载几百万人的文件。

---

我刚刚在这个StackOverflow问题中找到了一些优化TList的绝佳建议：

Is there a faster TList implementation?

- lkessler

---

还有两个选项：TList<string> 和 TStringBuilder。 - Alan Clark

一个哈希列表并不适合这种情况，因为我们只是在处理一组字符串列表，并不需要通过键来访问它们。 - lkessler

TStringBuilder主要用于字符串的拼接，而不是用于字符串列表。 - lkessler

Answer 1

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

另一方面，对于特殊需要的目的，如果您需要执行许多插入和删除，则更适合使用类似于链接列表的东西。 但是搜索会变慢，而且确实很少有字符串集合不需要搜索的情况。 在这种情况下，通常会使用某种类型的哈希表，其中哈希表由字符串的前两个字节创建（预先分配长度为65536的数组，并将字符串的前两个字节直接转换为该范围内的哈希索引），然后在该哈希位置存储一个链接列表，其中每个项键都由字符串中剩余的字节组成（为了节省空间-哈希索引已经包含了前两个字节）。 然后，初始哈希查找为O(1)，后续的插入和删除均为链接列表快速。 这是一种可以操纵的权衡，应该清楚使用的杠杆。

- Caleb Hattingh

Answer 2

1. 一个TStringList。优点：具有扩展功能，允许动态增长、排序、保存、加载、搜索等。缺点：在通过索引访问大量项目时，Strings[Index]会导致敏感的性能损失（几个百分点），与数组访问相比，每个项目单元的内存开销。

2. 字符串的动态数组。优点：结合了动态增长的能力，如TStrings，以及通过索引的最快访问，来自其他人的最小内存使用。缺点：标准的“字符串列表”功能有限。

3. 字符串（单向链接）的链表。优点：将项添加到列表末尾的线性速度。缺点：通过索引和搜索的访问速度最慢，标准的“字符串列表”功能有限，“下一个项”指针的内存开销，每个项内存分配的速度开销。

4. TList< string >。同上。

5. TStringBuilder。我不知道如何将TStringBuilder用作多个字符串的存储。

实际上，还有更多方法：

• 动态数组的链表
• 哈希表
• 数据库
• 二叉树
• 等等

最佳方法取决于任务。

哪种最适合小列表（少于10个项目）？

任何人，甚至是具有总项目计数变量的静态数组。

哪种最适合大列表（超过1000个项目）？哪种最适合巨大列表（超过1,000,000个项目）？

对于大型列表，我会选择： - 动态数组，如果需要大量通过索引访问或搜索特定项 - 哈希表，如果需要按键搜索 - 动态数组的链表，如果需要许多项附加和不需要通过索引访问

哪种最适合最小化内存使用？

动态数组将占用更少的内存。但问题不在于开销，而在于这种开销在哪个项目数量上变得敏感。然后如何正确处理这些项目。

哪种最适合最小化加载时间以添加额外的项目到末尾？

动态数组可以动态增长，但在真正大量的项目中，内存管理器可能找不到连续的内存区域。而链表将一直工作，直到至少有一个单元的内存，但是要付出每个项内存分配的代价。混合方法-动态数组的链表应该可以工作。

哪种最适合最小化从头到尾访问整个列表的访问时间？

动态数组。

基于此（或任何其他原因），哪种数据结构更可取？

用于哪个任务？

- da-soft

---

你可能认为小列表不值得优化，但如果我有10,000个不同的小列表呢？它们的总性能将是显著的，所以我应该为它们使用最优化的数据结构。 - lkessler

不，我不这么认为。我真正认为的是，我们在谈论“真空中的立方马”<g> 描述你的任务和数据访问模式，那么就有可能给你一个确切的答案... - da-soft

Answer 3

如果你的目标是将程序改进到能够加载包含数百万人的家谱文件，那么在这个问题中选择四种数据结构并不会真正帮到你。

算一下吧 - 你现在正在加载一个25 MB的文件，其中大约有100000个人，这导致你的应用程序消耗了175 MB的内存。如果你希望加载包含数百万人的文件，则可以估计，除非对程序进行 drasitc 改变，否则你需要将内存需求乘以 n * 10 量级。在当前保持所有东西都在内存中的情况下，没有办法在32位进程中做到这一点。

基本上你有两个选项：

1. 不同时将所有内容放在内存中，而是使用数据库或基于文件的解决方案，在需要时从中加载数据。我记得你之前已经问过其他相关问题，并可能决定反对它，所以就暂且不提了。

2. 将所有内容都放在内存中，但是以最节省空间的方式。只要没有64位Delphi，这应该允许几百万人，具体取决于每个人的数据量。重新编译为64位也将消除这个限制。

如果你选择第二个选项，那么你需要更加积极地减少内存消耗：

使用字符串池技术（string interning）。如果你的程序中包含了许多相同的数据，但是这些数据被存储在不同的字符串中，那么这些字符串就会浪费内存。我知道你的程序是一个查看器而不是编辑器，所以你可能只需要将字符串添加到你的字符串池中。对于拥有数百万个字符串的程序来说，实现字符串池仍然很困难，但是SmartInspect博客上的"Optimizing Memory Consumption with String Pools"文章可能会给你一些好的想法。这些人经常处理大型数据文件，并且必须在面临与你相同的限制时使其正常工作。
这也可以回答你的问题——如果你使用字符串池技术，就不需要在你的数据结构中保存字符串列表，而是需要保存字符串池索引列表。
使用多个字符串池也可能会有益处，比如一个用于名称，另一个用于城市或国家等位置信息。这应该可以加快插入操作的速度。

使用最小化内存表示的字符串编码。将所有内容都存储为本地 Windows Unicode 字符串可能会消耗更多的空间，除非你经常处理包含大量需要三个或更多字节的 UTF-8 编码字符的字符串。
由于必要的字符集转换，你的程序需要更多的 CPU 周期来显示字符串，但是在处理如此大量的数据时，这是一个值得权衡的选择，因为内存访问将成为瓶颈，而更小的数据大小有助于减少内存访问负载。

- mghie

---

感谢@mghie提供的周到答案。是的，我计划使用数据库（我在SO上已经问过相关问题），并且在将我的程序从查看器转换为编辑器之前实现它。我所有的优化都是以编辑器概念为基础的。您提供的字符串池参考非常好，我以前没有见过，但是数据库实现可能会减少我对此的需求。将文本存储为UTF8是我最后留下的选择，因为它会偏离国际用户的性能。我正在采取许多措施来减少175 MB，这个问题就是其中之一。 - lkessler

@lkessler：国际用户的性能为什么会更差？我知道祖先的名字可能（根据它们的起源）包含各种非ASCII字符，但根据http://en.wikipedia.org/wiki/UTF-8，您有2048个字符与等效宽字符相同或更小，并且这些字符包括希腊语、西里尔语、希伯来语和阿拉伯语，因此已经涵盖了相当多的字符。而且由于字符串携带其编码，您甚至可以在同一池中使用不同的编码。 - mghie

@mghie：从内存使用及其相关的分配和释放来定义的“性能”会更糟，因为他们的文本将占用更多的内存。西方文字每个字符占用1个字节，希腊、西里尔等字符占用2个字节，中文等语言则需要3个或更多字节。而直接使用Unicode对于所有语言都是2个字节。 - lkessler

@lkessler：当然，你必须决定大多数用户的大部分数据是否确实是使用CJK脚本或克林贡语编写的。;-) - mghie

显然，nobugleftbehind博客已经不存在了。有关“使用字符串池优化内存消耗”的文章仍然可以在互联网档案馆中找到，网址为http://web.archive.org/web/20090220130903/http://nobugleftbehind.com/optimizing-memory-consumption-with-string-pools-part-i/。 - dummzeuch

Answer 4

TStringList 存储一个指向（字符串，TObject）记录的指针数组。

TList 存储一个指针数组。

TStringBuilder 不能存储字符串集合。它类似于 .NET 的 StringBuilder，只应用于连接（许多）字符串。

调整动态数组大小很慢，因此不要考虑它作为选项。

我会在所有情况下使用 Delphi 的通用 TList<string>。它存储字符串数组（而不是字符串指针）。由于没有（取消）装箱，它在所有情况下都应该具有更快的访问速度。

如果您只需要顺序访问，则可以找到或实现稍微更好的链表解决方案。请参见 Delphi 算法和数据结构。

Delphi推广其TList和TList<>。内部数组实现经过高度优化，我在使用它时从未遇到性能/内存问题。请参见TList和TStringList的效率。

- carlmon

---

TStringList 在很大程度上等同于 TList<string>，除了 TStringList 还可以为每个条目存储一个对象引用。TList<string> 和 TStringList 都将字符串存储在字符串数组中，该数组实现为指向堆的引用计数指针。它们之间不应该有显著的性能差异。 - Barry Kelly

我相信Marcu Cantu在他的Delphi 2009书中写到了TList<string>使用动态数组。如果是这样的话，我不知道你怎么能说动态数组很慢但TList更快。 - lkessler

@lkessler：你说得对。我看了一下TList<T>的实现，它使用动态数组。当手动管理动态数组时，常见的瓶颈是调整大小的策略：每次插入都扩展数组大小1很慢，但是TList<T>通过在达到限制时将动态数组大小加倍来解决这个问题。我不确定TList和TList<T>之间哪个更快...我会针对大量数据编写一个快速的基准测试，以测试速度/内存使用情况。 - carlmon

Answer 5

一个问题：你如何查询：是匹配字符串还是按照列表中的ID或位置进行查询？

对于少量字符串，最好的方法是：

无论什么方法使你的程序易于理解。程序的可读性非常重要，你应该只在应用程序的真正热点中为速度而牺牲它。

对于内存（如果这是最大的限制）和加载时间，最好的方法是：

将所有字符串保存在单个内存缓冲区（或内存映射文件）中，并仅保留指向字符串（或偏移量）的指针。每当需要一个字符串时，您可以使用两个指针剪切出一个字符串并将其作为Delphi字符串返回。这样，您就避免了字符串结构本身的开销（引用计数、长度int、代码页int以及每个字符串分配的内存管理器结构）。

如果字符串是静态的且不会更改，则此方法可以很好地工作。

TList、TList<>、字符串数组和上述解决方案都具有每个字符串一个指针的“列表”开销。链表至少有2个指针（单向链表）或3个指针（双向链表）的开销。链表解决方案没有快速的随机访问，但允许O（1）调整大小，而其他选项使用因子进行调整大小的O（lgN）或使用固定调整大小的O（N）。

我会这样做：

如果数据项<1000并且性能不是最重要的，那么使用TStringList或动态数组（无论哪个对您来说最容易）。 否则，如果是静态数据：可以使用上述技巧。这将使查询时间为O(lgN)，占用的内存最少，并且加载速度非常快（只需将其读入或使用内存映射文件）

当您处理大量1M+字符串需要在代码中动态更改时，所有在您提出问题中提到的结构都会失败。此时，我会根据我的查询类型使用平衡二叉树或哈希表。

- Ritsaert Hornstra

---

回答问题：不需要匹配。将字符串视为代表信息项的文本行，按顺序从第一项到最后一项排序。当您处理某个对象时，它可能以某种方式引用此字符串列表作为有关该对象的信息。我实际上有一个家谱程序，其中一些列表是儿童姓名、名称变体甚至整个姓名索引本身预先排序并输入到列表中。 - lkessler

Answer 6

从您的描述来看，我并不完全确定它是否适合您的设计，但是一种可以在不承受巨大性能惩罚的情况下提高内存使用率的方法是使用 trie。

相对于二叉搜索树，Trie树的主要优势有：

1. 查找键值更快。查找长度为m的键最坏情况下需要O(m)的时间。而二叉搜索树进行O(log(n))次键比较，其中n是树中元素的数量，因为查找取决于树的深度，如果树是平衡的，则树中键的数量对数级别增长。因此，在最坏的情况下，二叉搜索树需要O(m log n)的时间。此外，在最坏的情况下，log(n)将接近于m。此外，在查找期间，Trie使用的简单操作（如使用字符进行数组索引）在真实机器上非常快速。

2. 当包含大量短字符串时，Trie可能需要更少的空间，因为键不是显式存储的，并且具有共同初始子序列的键之间共享节点。

3. Trie有利于最长前缀匹配，可以帮助找到共享尽可能长的字符前缀的键。

- Lieven Keersmaekers

---

是的。实际上，@Lieven，我一直在考虑将存储需要按排序顺序和按键检索的数据结构的B*树转换为tries。这个问题是关于字符串列表的，我需要它们按顺序排列，但不需要按键检索，这就是trie（以及树和哈希表）的作用。 - lkessler

Answer 7

可能的替代方案：

我最近发现了 SynBigTable（http://blog.synopse.info/post/2010/03/16/Synopse-Big-Table），它有一个 TSynBigTableString 类，可以使用字符串索引存储大量数据。

非常简单，单层 bigtable 实现，主要使用磁盘存储，在存储数十万条记录时消耗的内存比预期少得多。

就像这样简单：

aId := UTF8String(Format('%s.%s', [name, surname]));

bigtable.Add(data, aId)

和

bigtable.Get(aId, data)

唯一的限制是索引必须是唯一的，并且更新的成本有点高（首先删除，然后重新插入）。

- Noener