lke*_*ler 10 delphi linked-list tstringlist dynamic-arrays data-structures
我有一个选择.
我有许多已经排序的字符串,我需要存储和访问.看起来我可以选择使用:
字符串的链接列表(单链接)
艾伦在他的评论中建议我也加入选择:
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实现？
Cal*_*ngh 10
除非您有特殊需求,否则TStringList很难被击败,因为它提供了TStrings许多组件可以直接使用的界面.使用TStringList.Sorted := True二进制搜索,这意味着搜索将非常快.您还可以免费获得对象映射,每个项目也可以与指针关联,您可以获得编组,流接口,逗号文本,分隔文本等所有现有方法.
另一方面,出于特殊需要的目的,如果您需要进行许多插入和删除操作,那么更接近链接列表的内容会更好.但是后来搜索变慢了,这是一个罕见的字符串集合,实际上从不需要搜索.在这种情况下,通常使用某种类型的散列,其中散列是由字符串的前2个字节创建的(预分配长度为65536的数组,并且字符串的前2个字节直接转换为散列该范围内的索引),然后在该哈希位置,存储链表,每个项密钥由字符串中的剩余字节组成(为了节省空间---哈希索引已经包含前两个字节).然后,初始哈希查找是O(1),随后的插入和删除是快速链接列表.这是一个可以操纵的权衡,杠杆应该是明确的.
一个TStringList.优点:具有扩展功能,允许动态增长,排序,保存,加载,搜索等.缺点:通过索引对项目的大量访问,字符串[索引]引入了明显的性能损失(几个百分点),比较访问数组,每个项目单元格的内存开销.
动态字符串数组.优点:将作为TStrings的动态增长功能与索引的最快访问速度相结合,最大限度地减少其他内存的使用.缺点:有限的标准"字符串列表"功能.
字符串的链接列表(单链接).优点:将项目添加到列表末尾的线性速度.缺点:索引的最慢访问和搜索,有限的标准"字符串列表"功能,"下一项"指针的内存开销,每个项目内存分配的开销开销.
TList <string>.如上.
TStringBuilder.我没有一个好主意,如何使用TStringBuilder作为多个字符串的存储.
实际上,有更多的方法:
最好的方法取决于任务.
哪个最适合小清单(10项以下)？
任何人,甚至可能是具有总项数变量的静态数组.
哪个最适合大型列表(超过1000个项目)？哪个最适合大型列表(超过1,000,000个项目)？
对于大型列表,我将选择: - 动态数组,如果我需要通过索引进行大量访问或搜索特定项 - 哈希表,如果我需要按键链接列表搜索动态数组,如果我需要很多项追加并且索引无法访问
哪个最好最小化内存使用？
动态数组会占用更少的内存.但问题不在于开销,而是关于这个开销变得合理的项目数量.然后如何正确处理这些项目.
哪个最好最小化加载时间以在最后添加额外的项目？
动态数组可能会动态增长,但是在大量项目上,内存管理器可能找不到连续的内存区域.虽然链接列表将起作用,直到存在至少一个单元格的内存,但是每个项目的内存分配成本.混合方法 - 动态数组的链接列表应该有效.
哪个最好最小化从头到尾访问整个列表的访问时间？
动态数组.
在此基础上(或任何其他),哪种数据结构更可取？
为了哪个任务？