List 中使用哪种算法来动态分配内存?
现在我有一个动态分配数组内存的算法:
这是用于动态内存分配的相当快的算法,尽管将元素复制到新分配的数组的额外开销。
-
什么是更快,
List
或基于数组的这种算法? 你会建议使用什么? -
List
使用简单数组作为内部数据结构吗?
回答你的问题:
确实,C#的List
实现使用了一个内部数组
- 序列化
- 线程安全
- 实现
IEnumerable
(这意味着它可以是LINQ查询,foreach
ed等) - 二进制搜索
等等
因此,我会要求您使用List
而不是您自己的List。
哦,顺便说一句,如果你想要微软的List
的源代码 ,那么就在这里
List.cs
编辑
List
中EnsureCapacity
的源代码是:
// 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; } }
除非你有特别的理由相信,否则使用C#附带提供的库几乎是一个好主意。 这些实现经过良好实施,调试良好且经过良好测试。
您描述的数据结构是动态数组数据结构的标准实现,大多数语言将此作为默认列表实现。 查看List
的文档 ,似乎List
使用此实现,因为其文档引用了内部容量,并且只要大小小于容量,就保证O(1)追加。
简而言之,除非必须,否则请避免重新发明轮子。
希望这可以帮助!
List
在内部使用一个数组,它使用与你类似的策略 – 如果长度超过数组的长度,它会使数组的大小加倍。 但是,如果尺寸变小,它就不会变小。
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
的setter中。
是的, List
在内部使用T[]
来保存您的对象。
据我记得.NET 4.0源代码,在添加新对象之前,它确保了数组有足够的容量来容纳新的对象数。 如果现有数组不能容纳新数量的对象,则将其替换为大小加倍的新数组,并将所有对象和所有现有引用复制到新数组。
无需重新发明轮子。
来自MSDN:
容量是List <(Of <(T>)>)在需要resize之前可以存储的元素数,而Count是实际位于List <(Of <(T>)>)中的元素数。
容量始终大于或等于Count。 如果Count在添加元素时超出容量,则在复制旧元素和添加新元素之前,通过自动重新分配内部数组来增加容量。
可以通过调用TrimExcess方法或显式设置Capacity属性来减少容量。 当显式设置Capacity的值时,还会重新分配内部数组以容纳指定的容量,并复制所有元素。
检索此属性的值是O(1)操作; 设置属性是O(n)操作,其中n是新容量。
这基本上就是List
(以及许多其他语言的动态数组)。 resize因素可能不同,我认为在删除元素时它不会自行缩小后备数组 – 但是有TrimToSize
并且您可以自己设置Capacity
,如果客户端代码很好地使用此function,则可能允许更有效的策略。 但基本上,它是渐近等价的。
至于使用哪一个:除非你有冷,硬数据, List
对你的用例来说不是最理想的,并且差异很重要(你显然还没有这方面的知识),你应该使用它。 您自己的实现将是错误的,function较少(参见IEnumerable
, IList
,众多方法),优化程度较低,识别率较低,不被其他库接受(因此您可能需要创建昂贵的副本,或者至少比List
做更多的工作来进行交互)等等,并且很可能绝对没有任何好处。
上述就是C#学习教程:List 中使用哪种算法来动态分配内存?分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1004852.html