15

我正在寻找一种可以轻松添加项目而不会影响性能的数组数据类型。

  • 系统。数组-Redim Preserve将整个 RAM 从旧的复制到新的，与现有元素的数量一样慢
  • System.Collections。ArrayList - 够好吗？
  • System.Collections。IList - 够好吗？
4

5 回答 5

19

简单总结一下数据结构：

System.Collections.ArrayList：无类型数据结构已过时。请改用 List(of t)。

System.Collections.Generic.List(of t)：这表示一个可调整大小的数组。这个数据结构在幕后使用了一个内部数组。只要底层数组没有被填充，将项目添加到 List 是 O(1)，否则它是 O(n+1) 来调整内部数组的大小并复制元素。

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

添加项目仅在添加到列表末尾时才有效。在中间插入会强制数组将所有项目向前移动，这是一个 O(n) 操作。删除项目也是 O(n)，因为数组需要向后移动项目。

System.Collections.Generic.LinkedList(of t)：如果您不需要对列表中的项目进行随机或索引访问，例如您只计划添加项目并从头到尾迭代，那么 LinkedList 就是您的朋友。插入和删除是 O(1)，查找是 O(n)。

于 2009-01-05T16:28:20.023 回答
15

您应该为此使用 Generic List<> ( System.Collections.Generic.List )。它以固定的摊销时间运作。

它还与 Arrays 共享以下功能。

  • 快速随机访问（您可以在 O(1) 中访问列表中的任何元素）
  • 快速循环
  • 在开头或中间插入和删除对象很慢（因为它必须复制整个列表相信）

如果您需要在开头或结尾快速插入和删除，请使用链表或队列

于 2009-01-05T16:19:48.747 回答
3

LinkedList< T> 结构对你有用吗？它（在某些情况下）不像直接数组那样直观，但非常快。

  • AddLast 追加到末尾
  • AddBefore/AddAfter 插入到列表中
  • AddFirst 追加到开头

但是，随机访问并不是那么快，因为您必须遍历结构才能访问您的项目......但是，它具有 .ToList() 和 .ToArray() 方法来获取列表/数组形式的结构副本所以对于读取访问，你可以在紧要关头做到这一点。插入的性能提高可能超过随机访问需求的性能降低，也可能不会。这将完全取决于您的情况。

还有这个参考资料可以帮助您确定正确的方法：

何时在数组/数组列表上使用链表？

于 2009-01-05T16:20:43.767 回答
1

什么对你来说“足够好”？你到底想用那个数据结构做什么？

没有数组结构（即 O(n) 访问）允许在没有 O(n) 运行时的情况下插入中间；最后插入是 O(n) 最坏的情况，O(1) 摊销用于像 ArrayList 这样的自调整大小数组。

也许哈希表（在任何地方进行分摊的 O(1) 访问和插入，但对于插入来说是 O(n) 最坏的情况）或树（O(log(n)) 用于在任何地方进行访问和插入，保证）更适合。

于 2009-01-05T16:32:44.603 回答
1

如果速度是您的问题，我看不出所选答案比使用原始数组有什么好处，尽管它会自行调整大小，但它使用与调整数组大小完全相同的机制（并且应该只需要一点时间) 除非你总是添加到最后，在这种情况下它应该做的事情更聪明一些，因为它一次分配一个块而不是一个元素。

如果您经常在集合的开头/中间添加附近并且不经常索引到中间/结尾，您可能需要链接列表。这将具有最快的插入时间并且将具有很长的迭代时间，它只是在索引方面很糟糕（例如从末尾查看第 3 个元素或第 72 个元素）。

于 2009-01-05T17:30:50.727 回答