数据结构分析
原文链接：https://www.nv5geospatialsoftware.com/Learn/Blogs/Blog-Details/data-structure-analysis
10157 为本文评分：
暂无评分
数据结构分析
匿名作者 2015年2月12日 星期四
使用任何编程语言时，开发者都需要面对的一个核心问题是：“我应该使用何种数据结构？”这是一个复杂且困难的问题，因为需要权衡诸多因素。若需要动态数据类型，IDL 提供了多种选择。在本次分析中，我们将考察动态数组、列表、哈希表及有序哈希表在插入和删除元素方面的性能。首先，我们来回顾这些数据结构。动态数组基于 IDL 数组能够自我调整大小的特性，例如：
array = [1,2,3,4] ; 声明
array = [array, 5] ; 插入
array = [array[0:1],array[3:*]] ; 删除
列表使用 IDL 对象 LIST：
list = LIST(1,2,3,4) ; 声明
list.add,5 ; 插入
list.remove, 2 ; 删除
哈希表使用 IDL 对象 HASH：
hash = HASH([1,2,3,4],[1,2,3,4]) ; 声明
hash[5] = 5 ; 插入
hash.remove, 2 ; 删除
有序哈希表使用 IDL 对象 ORDEREDHASH：
ohash = ORDEREDHASH([1,2,3,4],[1,2,3,4]) ; 声明
ohash[5] = 5 ; 插入
ohash.remove, 2 ; 删除
针对每种数据结构，我们将计算插入和删除 n 个元素所需的时间（注：插入/删除操作在 FOR 循环内执行，每次迭代进行一次插入/删除。这是为了模拟数据使用高度不稳定的应用场景。但由于 IDL 是向量化语言，始终建议将多个操作合并为单次调用）。请查看随附的图表以获取运行结果。结果符合我们基于简单大 O 分析（big-O analysis）的预期。对于少量输入，动态数组表现尚可；但一旦输入规模增大，使用哈希表（任一类型）或列表会快得多。就任意输入规模下的绝对速度而言，列表是最快的。然而，如果已知输入元素数量有限，所有提及的数据结构都能提供相近的性能。
注：在本次分析中，所有数据结构在元素数量达到 10,000 之前性能相近。这并非全面测试，结果可能因系统而异。但我遵循的经验法则是：若输入元素少于 10,000，请选择您最易使用的数据结构。