Dan*_*Tao 9 .net performance big-o list clear
该方法是O(n)操作,其中n是Count.
为什么O(n)？我问,因为我认为List<T>只需在T[]内部分配一个新数组即可完成清除.没有其他类可以引用这个数组,所以我没有看到这种方法的危害.
现在,也许这是一个愚蠢的问题......正在分配一个T[]数组本身O(n)？出于某种原因,我不会这么想; 但也许是(我现在缺少CS学位吗？).如果是这样,我想这可以解释它,因为根据上面引用的相同文档,列表的容量保持不变,这意味着需要构建一个相同大小的数组.
(然后,这似乎不是正确的解释,因为文档应该说"其中n是容量 " - 而不是 Count*).
我只是怀疑这个方法,而不是分配一个新的数组,将当前的所有元素归零; 而且我很想知道为什么会这样.
*Hans Passant在对LukeH的回答中指出,文档是正确的.Clear只将已设置的元素清零List<T>; 它不需要将所有元素"重新归零".
据我所知,当前的实现只调用Array.Clear其内部T[]数组,并且Array.Clear是一个O(n)进程.(正如Hans在评论中指出的那样,MSDN文档是正确的,n在这种情况下是列表Count,而不是它Capacity.)
但是,即使它只是在T[]内部分配一个新数组,那仍然是一个O(n)进程,因为分配一个大小的数组n涉及将所有n元素初始化为零/ null /默认状态.
当然,没有什么可以阻止某种内部技巧,其中阵列可以用0或42或其他任何长度进行初始化,然后根据需要在运行中再次自动扩展,从而分摊整体O(n)成本.