6

现在我有一个在数组上动态分配内存的算法：

  • 如果数组已满，我创建一个两倍大小的新数组，并复制项目。
  • 如果数组是四分之一满，我创建一个一半大小的新数组，并复制项目。

尽管将元素复制到新分配的数组需要额外的开销，但这是用于动态内存分配的相当快的算法。

  1. List<T>基于数组的更快或这样的算法是什么？你会推荐使用什么？

  2. List<T>使用简单数组作为内部数据结构吗？

4

6 回答 6

9

回答你的问题：

确实，C# 的List<T>实现使用了一个内部数组，即

  1. 可序列化
  2. 线程安全
  3. 实现IEnumerable<T>（这意味着它可以被 LINQ 查询、foreach编辑等）
  4. 二进制搜索

等等

因此，我会要求您使用List<T>而不是您自己的列表。

哦，顺便说一句，如果你想要来自 Microsoft的源代码List<T>，那么这里就是

列表.cs

编辑

EnsureCapacityin的源代码List<T>是：

    // Ensures that the capacity of this list is at least the given minimum
    // value. If the currect capacity of the list is less than min, the
    // capacity is increased to twice the current capacity or to min,
    // whichever is larger.
    private void EnsureCapacity(int min) {
        if (_items.Length < min) {
            int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }
于 2013-02-16T18:38:41.103 回答
6

除非您有特定的理由不相信，否则使用 C# 附带的提供的库几乎是一个普遍的好主意。这些实现都得到了很好的实现、很好的调试和很好的测试。

您描述的数据结构是动态数组数据结构的标准实现，大多数语言都将其用作默认列表实现。查看文档List<T>，似乎List<T>使用了这个实现，因为它的文档引用了内部容量并保证 O(1) 附加，只要大小小于容量。

简而言之，除非必须，否则避免重新发明轮子。

希望这可以帮助！

于 2013-02-16T18:35:31.913 回答
4

List<T>在内部使用数组，并且它使用与您类似的策略 - 如果长度超过数组的长度，它会将数组的大小加倍。但是，如果尺寸更小，它不会变小。

中的相关方法mscorlib：

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

数组的大小调整实际上发生在List<T>.Capacity.

于 2013-02-16T18:35:23.187 回答
2

无需重新发明轮子。

来自 MSDN：

容量是在需要调整大小之前 List<(Of <(T>)>) 可以存储的元素数，而 Count 是实际在 List<(Of <(T>)>) 中的元素数。

容量始终大于或等于 Count。如果在添加元素时 Count 超过了容量，则通过在复制旧元素和添加新元素之前自动重新分配内部数组来增加容量。

可以通过调用 TrimExcess 方法或显式设置容量属性来减少容量。当显式设置容量的值时，内部数组也会重新分配以容纳指定的容量，并复制所有元素。

检索此属性的值是 O(1) 操作；设置属性是一个 O(n) 操作，其中 n 是新容量。

于 2013-02-18T04:08:26.470 回答
2

是的，在内部List<T>使用 aT[]来保存您的对象。

据我记得 .NET 4.0 源代码，在添加新对象之前，它确保数组有足够的容量来容纳新数量的对象。如果现有数组不能容纳新数量的对象，则将其替换为两倍大小的新数组，并将所有对象和所有现有引用复制到新数组中。

于 2013-02-16T18:35:30.653 回答
0

这基本上也是List<T>（以及许多其他语言的动态数组）所做的。调整大小的因素可能不同，我认为在删除元素时它不会自行缩小支持数组 - 但是TrimToSize你可以设置Capacity自己，如果客户端代码很好地使用了这个特性，这可能会允许更有效的策略。但基本上，它是渐近等价的。

至于使用哪一个：除非您拥有List<T>对您的用例而言不是最佳的冷硬数据并且差异很重要（您显然还没有这方面的知识），否则您应该使用它。您自己的实现将是错误的，功能较少（参见IEnumerable<T>，，IList<T>许多方法），优化较少，不太容易识别，不被其他库接受（因此您可能必须创建昂贵的副本，或者至少比使用List<T>互动）等，而且很可能绝对没有任何收获。

于 2013-02-16T18:36:10.127 回答