进化一: LinkedList vs List
因为我最早是学C++的,而对象池只关注每次取出来的对象,而不关注内部结构。第一反应就是使用C++的链表,类比成C#的LinkedList,后来有些好奇,就对C#的LinkedList和List的添加和删除效率做了一个对比, List的速度竟然是LinkedList的17倍。原因很简单,List内部就是用数组来保存对应的泛型对象,而LinkedList是先将泛型对象封装到LinkedListNode,然后再实现链表的操作。有点类似于C#的装箱和拆箱,在对象池这种频繁操作的数据结构里就会很耗时了,GC也会很吃力。LinkedList封装对象的代码:
public sealed class LinkedListNode<T>
{
public LinkedListNode(T value);
public LinkedListNode<T> Next { get; }
public LinkedListNode<T> Previous { get; }
public T Value { get; set; }`
}
List数据的代码:
public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
{
public T this[int index] { get; set; }`
}
进化一: LinkedList vs List 因为我最早是学C++的,而对象池只关注每次取出来的对象,而不关注内部结构。第一反应就是使用C++的链表,类比成C#的LinkedList,后来有些好奇,就对C#的LinkedList和List的添加和删除效率做了一个对比, List的速度竟然是LinkedList的17倍。原因很简单,List内部就是用数组来保存对应的泛型对象,而LinkedList是先将泛型对象封装到LinkedListNode,然后再实现链表的操作。有点类似于C#的装箱和拆箱,在对象池这种频繁操作的数据结构里就会很耗时了,GC也会很吃力。LinkedList封装对象的代码:
List数据的代码:
一个是原生,一个还需要封装,List必然更快。
进化二: List内部进化 最早用List写的时候,每次获取对象的写法都是这样:
但是这种写法吧,每次Remove一个对象时,都会导致其他对象往前移一位,仍然是N的时间复杂度。于是,Remove的时候,从最后开始Remove,就不会导致其他对象的前移,时间复杂度就变成1了。新的代码如下:
进化三: List vs Stack 在进化二的最终形式, 其实就是Stack的标准用法啊,先进后出, 而且接口简单。更不会出现数组下标越界的情况。最终代码如下: