abh*_*hek 5 c# linked-list list sortedlist
在我看来,List基本上是使用实现的LinkedList,而普通Array是作为连续的块实现的.我一直使用,List因为它在Generic命名空间中,因为我认为它使用了动态内存分配 - 但我错了.
昨天我看到了List使用Reflector 的实现,发现它实际上是一个T(T[])数组.Array.Copy在操纵每个元素的同时有很多List.例如,当您使用时Insert,它将创建一个新内存并复制插入元素之前/之后的所有元素.所以在我看来,使用List非常昂贵.
我也看到了SortedList.我不知道为什么SortedList还在其中实现了一个数组.难道你认为SortedList使用数组会不会很糟糕,因为你需要在每次微调操作时对列表进行排序List？
我也想知道为什么List这么受欢迎,因为大多数人使用它而不是去LinkedList.是否只是因为索引器的灵活性？
Han*_*ant 14
是的,SortedList对于插入是O(n).小心使用.
最大的原因是现代计算机设计.CPU缓存非常重要,因为RAM太慢了.内存总线设计无法跟上CPU时钟速度的快速提升.使高频数字信号传输超过一英寸是非常困难的.
数组具有无与伦比的缓存性能,当您迭代它时,下一个元素很可能已经在缓存中.链接列表给出非常小的几率,这是下一个项目基本上是随机地址.这是昂贵的,它会使处理器停滞不前,等待RAM赶上来.可以是数百个周期.