10

我有一个选择。

我有许多需要存储和访问的已排序字符串。看起来我可以选择使用：

  1. 一个 TStringList

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

  3. 字符串的链接列表（单链接）

    艾伦在他的评论中建议我也添加选择：

  4. TList<string>

在什么情况下，这些中的每一个都比其他的更好？

哪个最适合小型列表（10 项以下）？

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

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

哪种方法可以最大程度地减少内存使用？

哪个是最好的，以最大限度地减少加载时间以在最后添加额外的项目？

从头到尾访问整个列表的访问时间最小化是什么？

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

作为参考，我使用的是 Delphi 2009。

Dimitry 在评论中说：

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

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

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

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

希望这能让您了解我要完成的工作。

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

我刚刚在这个 StackOverflow 问题中找到了一些优化 TList 的绝佳建议： 是否有更快的 TList 实现？

4

7 回答 7

10

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

另一方面，出于特殊需要，如果你需要做很多插入和删除，那么更接近链表的东西会更好。但随后搜索变得更慢，而且它确实是一个很少需要搜索的字符串集合。在这种情况下，通常会使用某种类型的散列，例如从字符串的前 2 个字节创建散列（预分配长度为 65536 的数组，并将字符串的前 2 个字节直接转换为散列）该范围内的索引），然后在该哈希位置存储一个链表，其中每个项目键由字符串中的剩余字节组成（为了节省空间——哈希索引已经包含前两个字节）。然后，初始哈希查找是 O(1)，随后的插入和删除是链表快速的。

于 2010-04-21T06:42:52.897 回答
6

  1. 一个 TStringList。优点：具有扩展功能，允许动态增长、排序、保存、加载、搜索等。缺点：在通过索引对项目进行大量访问时，Strings[Index] 引入了明显的性能损失（百分之几），比较要访问数组，每个项目单元格的内存开销。

  2. 字符串的动态数组。优点：结合动态增长的能力，作为 TStrings，索引访问速度最快，其他内存使用量最少。缺点：有限的标准“字符串列表”功能。

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

  4. TList<字符串>。如上。

  5. 字符串生成器。我没有一个好主意，如何使用 TStringBuilder 作为多个字符串的存储。

其实还有很多方法：

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

最好的方法将取决于任务。

哪个最适合小型列表（10 项以下）？

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

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

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

哪种方法可以最大程度地减少内存使用？

动态数组会消耗更少的内存。但问题不在于开销，而在于开销在哪些项目上变得合理。然后如何正确处理这个数量的项目。

哪个是最好的，以最大限度地减少加载时间以在最后添加额外的项目？

动态数组可能会动态增长，但在真正大量的项目上，内存管理器可能找不到连续的内存区域。虽然链表将一直工作，直到至少有一个单元格的内存，但每个项目的内存分配成本。混合方法 - 动态数组的链表应该可以工作。

从头到尾访问整个列表的访问时间最小化是什么？

动态数组。

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

为哪个任务？

于 2010-04-21T06:54:58.720 回答
2

如果您的既定目标是将您的程序改进到可以加载包含数百万人的家谱文件，那么在您的问题中的四种数据结构之间做出决定并不能真正让您实现目标。

算一下 - 您当前正在加载一个 25 MB 的文件，其中包含大约 100000 人，这会导致您的应用程序消耗 175 MB 的内存。如果您希望加载包含数百万人的文件，您可以估计，如果不对程序进行重大更改，您还需要将内存需求乘以n * 10。没有办法在 32 位进程中做到这一点，同时以您当前的方式将所有内容保存在内存中。

你基本上有两个选择：

  1. 不要一次将所有内容都保存在内存中，而是使用数据库或基于文件的解决方案，您可以在需要时从中加载数据。我记得你已经对此有其他问题，并且可能决定反对它，所以我会留下它。

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

如果您选择第二种选择，那么您需要更积极地减少内存消耗：

  • 使用字符串实习。程序中包含相同数据但包含在不同字符串中的每个加载的数据元素基本上都是浪费内存。我知道您的程序是查看器，而不是编辑器，因此您可能只需将字符串添加到您的实习字符串池即可。用数百万个字符串做字符串实习仍然很困难， SmartInspect 博客上的“使用字符串池优化内存消耗”博客帖子可能会给您一些好主意。这些人经常处理庞大的数据文件，并且必须使其在您面临的相同限制下工作。
    这也应该将此答案与您的问题联系起来 - 如果您使用字符串实习，则不需要在数据结构中保留字符串列表，而是保留字符串池索引列表。
    使用多个字符串池也可能是有益的，例如一个用于名称，但另一个用于城市或国家等位置。这应该加快插入池的速度。

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

于 2010-04-22T07:20:59.713 回答
1

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

TList存储一个指针数组。

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

调整动态数组的大小很慢，因此甚至不要将其视为一种选择。

我会TList<string>在你的所有场景中使用 Delphi 的泛型。它存储一个字符串数组（不是字符串指针）。由于没有（取消）装箱，它应该在所有情况下都可以更快地访问。

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

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

于 2010-04-21T06:33:00.607 回答
1

一个问题：您如何查询：您是否匹配字符串或查询列表中的 ID 或位置？

最适合小#字符串：

无论什么使您的程序易于理解。程序的可读性非常重要，您应该只在应用程序的实际热点中牺牲它以提高速度。

最适合内存（如果这是最大的约束）和加载时间：

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

这只有在字符串是静态的并且不改变的情况下才能正常工作。

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

我会做什么：

如果 < 1000 个项目并且性能不是最重要的：使用 TStringList 或 dyn 数组对您来说最简单。else if static：使用上面的技巧。这将为您提供 O(lgN) 查询时间、最少使用的内存和非常快的加载时间（只需将其吞入或使用内存映射文件）

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

于 2010-04-21T06:46:41.350 回答
1

根据您的描述，我不完全确定它是否适合您的设计，但您可以在不遭受巨大性能损失的情况下改善内存使用的一种方法是使用trie。

相对于二叉搜索树的优势

以下是尝试优于二叉搜索树 (BST) 的主要优势：

  • 查找密钥更快。查找长度为 m 的密钥需要最坏情况 O(m) 时间。BST 对键执行 O(log(n)) 比较，其中 n 是树中元素的数量，因为查找取决于树的深度，如果树是平衡的，则它与键的数量成对数。因此，在最坏的情况下，BST 需要 O(m log n) 时间。此外，在最坏的情况下，log(n) 将接近 m。此外，在查找过程中尝试使用的简单操作（例如使用字符的数组索引）在真实机器上速度很快。

  • 当 Tries 包含大量短字符串时，它们可能需要更少的空间，因为键没有显式存储，并且节点在具有公共初始子序列的键之间共享。

  • 尝试促进最长前缀匹配，帮助找到共享所有唯一字符的最长可能前缀的密钥。
于 2010-04-22T14:13:15.680 回答
1

可能的替代方案：

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

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

很简单：

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

bigtable.Add（数据，ID）

和

bigtable.Get(aId, 数据)

一个catch，索引必须是唯一的，更新的成本有点高（先删除，再重新插入）

于 2010-06-11T07:57:27.603 回答