首页 > 代码库 > 可控增长线段数组-BigList
可控增长线段数组-BigList
List<T>恐怕是日常代码里最常用的集合类型之一了，此子大多数情况下工作情况良好，但凡事都有例外了。
加入你正在写一个服务端项目，对稳定性有着极高的要求，这时就要多考虑一些因素了，就拿这个List<T>来说吧。
一、先说说List<T>的内部机理
其实很简单，内部就是一个数组，当添加一个新元素T时，首先判断数组是否都已经填满数据，如果已经填满，即空间不够时，就分配一个新的数组代替，新数组大小以当前数组大小的2倍增长，然后加入新数据。
二、来说说问题
问题出在2倍增长这个逻辑，通用情况下这个逻辑是合理的，但实际应用中，如果我们是用来存储大量数据的话就会产生一个问题：
试想，数组现在大小是1000,0000，那么下次，增长就是2000,0000, 但可能我们增长后只用了很小很小的一部分，比如1000,0000 + 1个元素，那末就会有999,0000个元素的冗余空闲，更大的问题在于数据增长到2000,00000要很长时间也许一个月、一年甚至几年。这段时间里这么大空间的冗余浪费在服务端当然是一个极大的问题，另外如果这是个临时对象，产生的大对象对GC又是个极大的压力。
三、来说说笔者在项目的方案（代码已调整）
其实很简单，把整个的大数组划分为多个固定大小子数组，以T[][]代替T[]，这样，每次增长仅限于子数组的大小，更重要的，固定大小的子数组具有很强的重用性，写多服务端的朋友一定喜欢这点了。话不多说，直接上代码（说明：代码使用的大小仍是大对象范畴，如需减小，请自定调整代码）：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Collections; 6 using System.Diagnostics; 7 using System.Security.Permissions; 8 9 [Serializable] 10 [DebuggerDisplay("Count = { Count }"), DebuggerTypeProxy(typeof(CollectionDebugView<>)), HostProtection(SecurityAction.LinkDemand, MayLeakOnAbort = true)] 11 public class BigList<T> : IList<T>, IList 12 { 13 protected int m_count; 14 protected int m_capacity; 15 protected T[][] m_segments; 16 protected IComparer<T> m_comparer; 17 18 const int OFFSET_MASK = 0xffff; 19 const int SEG_SIZE = 0xffff + 1; 20 const int DEFAULT_CAPACITY = 4; 21 const int BIT_OFFSET = 16; 22 23 public BigList() 24 : this(0) 25 { 26 } 27 28 public BigList(int iCapacity) 29 : this(iCapacity, Comparer<T>.Default) 30 { 31 32 } 33 34 public BigList(int iCapacity, IComparer<T> comparer) 35 { 36 if (iCapacity < 0) 37 return; 38 if (iCapacity == 0) iCapacity = DEFAULT_CAPACITY; 39 m_comparer = comparer; 40 EnsureCapacity(iCapacity); 41 } 42 43 public void EnsureCapacity(int capacity) 44 { 45 if (m_capacity >= capacity) 46 return; 47 48 int offset; 49 if (m_capacity == 0) offset = DEFAULT_CAPACITY; 50 else 51 { 52 int mod = m_capacity & OFFSET_MASK; 53 if (mod == 0) offset = DEFAULT_CAPACITY; 54 else offset = Math.Min(mod * 2, SEG_SIZE) - mod; 55 } 56 57 capacity = Math.Max(capacity, m_capacity + offset); 58 59 int nSeg = capacity / SEG_SIZE; 60 int nCap = capacity % SEG_SIZE; 61 if (nCap != 0) ++nSeg; 62 int last; 63 if (m_segments == null) 64 { 65 m_segments = new T[nSeg][]; 66 last = m_segments.Length - 1; 67 if (last >= 0) 68 { 69 for (int i = 0; i < last; ++i) 70 m_segments[i] = new T[SEG_SIZE]; 71 //segments[len - 1] = new T[nCap]; 72 if (nCap == 0) nCap = SEG_SIZE; 73 m_segments[last] = new T[nCap];// new T[nCap]; 74 } 75 } 76 else if (nSeg > m_segments.Length) 77 { 78 T[][] nSegments = new T[nSeg][]; 79 if (m_segments.Length > 1) 80 { 81 Array.Copy(m_segments, 0, nSegments, 0, m_segments.Length - 1); 82 //T[] nArr = new T[SEG_SIZE]; 83 } 84 last = m_segments.Length - 1; 85 //int big = nSegments.Length - 1; 86 int big = nSegments.Length - 1; 87 for (int i = m_segments.Length; i < big; ++i) 88 nSegments[i] = new T[SEG_SIZE]; 89 90 if (m_segments[last].Length < SEG_SIZE) 91 { 92 nSegments[last] = new T[SEG_SIZE]; 93 Array.Copy(m_segments[last], 0, nSegments[last], 0, m_segments[last].Length); 94 } 95 else 96 { 97 nSegments[last] = m_segments[last]; 98 } 99 100 if (nCap == 0) nCap = SEG_SIZE;101 nSegments[big] = new T[nCap];// new T[nCap];102 103 m_segments = nSegments;104 105 }106 else107 {108 last = m_segments.Length - 1;109 //if (nCap > 0)110 //{111 if (nCap == 0) nCap = SEG_SIZE;112 T[] nArr = new T[nCap];113 T[] arr = m_segments[last];114 if (arr != null)115 Array.Copy(arr, 0, nArr, 0, arr.Length);116 117 m_segments[last] = nArr;118 //}119 }120 121 m_capacity = capacity;122 }123 124 public void Trim(int count)125 {126 m_count = count;127 }128 129 public int Capacity130 {131 get { return m_capacity; }132 set133 {134 EnsureCapacity(value);135 }136 }137 138 #region IList 成员139 140 public int Add(object value)141 {142 this.Add((T)value);143 return m_count - 1;144 }145 146 public bool Contains(object value)147 {148 if (value =http://www.mamicode.com/= null)149 return false;150 return IndexOf((T)value) >= 0;151 }152 153 public int IndexOf(object value)154 {155 if (value =http://www.mamicode.com/= null)156 return -1;157 return IndexOf((T)value);158 }159 160 public void Insert(int index, object value)161 {162 this.Insert(index, (T)value);163 }164 165 public bool IsFixedSize166 {167 get { return false; }168 }169 170 public void Remove(object value)171 {172 this.Remove((T)value);173 }174 175 object IList.this[int index]176 {177 get178 {179 return this[index];180 }181 set182 {183 this[index] = (T)value;184 }185 }186 187 #endregion188 189 #region ICollection 成员190 191 public void CopyTo(Array array, int index)192 {193 this.CopyTo((T[])array, index);194 }195 196 public bool IsSynchronized197 {198 get { return false; }199 }200 201 public object SyncRoot202 {203 get { return this; }204 }205 206 #endregion207 208 #region IList<int> 成员209 210 public void Add(T value)211 {212 if (m_count == m_capacity)213 EnsureCapacity(m_count + 1);214 m_segments[m_count >> BIT_OFFSET][m_count & OFFSET_MASK] = value;215 216 ++m_count;217 }218 219 public T this[int index]220 {221 get222 {223 return m_segments[index >> BIT_OFFSET][index & OFFSET_MASK];224 }225 set226 {227 m_segments[index >> BIT_OFFSET][index & OFFSET_MASK] = value;228 }229 }230 231 public int IndexOf(T item)232 {233 int i;234 int iFound = -1;235 for (i = 0; i < m_segments.Length; ++i)236 if ((iFound = Array.IndexOf<T>(m_segments[i], item)) >= 0)237 break;238 239 if (iFound != -1)240 return i * SEG_SIZE + iFound;241 return -1;242 }243 244 public void Insert(int index, T item)245 {246 if (m_count == m_capacity) EnsureCapacity(m_count + 1);247 if (index == m_count)248 m_segments[index >> BIT_OFFSET][index & OFFSET_MASK] = item;249 else250 {251 int eSeg = (m_count - 1) >> BIT_OFFSET;252 int eSiz = (m_count - 1) & OFFSET_MASK;253 T[] arr;254 int sSeg = index >> BIT_OFFSET;255 if (eSeg > sSeg)256 {257 arr = m_segments[eSeg];258 if (eSiz == SEG_SIZE - 1)259 {260 m_segments[eSeg + 1][0] = arr[arr.Length - 1];261 Array.Copy(arr, 0, arr, 1, eSiz);262 }263 else264 {265 Array.Copy(arr, 0, arr, 1, eSiz);266 //if (eSeg > 0)267 // arr[0] = segments[eSeg - 1][SEG_SIZE - 1];268 }269 arr[0] = m_segments[eSeg - 1][SEG_SIZE - 1];270 271 for (int i = eSeg - 1; i > sSeg; --i)272 {273 arr = m_segments[i];274 Array.Copy(arr, 0, arr, 1, SEG_SIZE - 1);275 arr[0] = m_segments[i - 1][SEG_SIZE - 1];276 }277 }278 279 arr = m_segments[sSeg];280 int offset = index & OFFSET_MASK;281 if (offset < SEG_SIZE - 1)282 Array.Copy(arr, offset, arr, offset + 1, arr.Length - offset - 1);283 m_segments[index >> BIT_OFFSET][index & OFFSET_MASK] = item;284 }285 ++m_count;286 }287 288 public void RemoveAt(int index)289 {290 int seg = index / SEG_SIZE;291 int mod = index % SEG_SIZE;292 T[] arr = m_segments[seg];293 if (mod > 0 && mod != OFFSET_MASK)294 {295 Array.Copy(arr, mod + 1, arr, mod, arr.Length - mod - 1);296 ++seg;297 }298 if (seg > 0)299 for (int i = seg; i < m_segments.Length; ++i)300 {301 arr = m_segments[i];302 if (arr == null || arr.Length == 0) return;303 m_segments[i - 1][SEG_SIZE - 1] = arr[0];304 if (arr.Length > 1)305 Array.Copy(arr, 1, arr, 0, arr.Length - 1);306 307 }308 --m_count;309 }310 311 #endregion312 313 #region ICollection<int> 成员314 public int Count { get { return m_count; } }315 316 public void Clear()317 {318 m_count = 0;319 }320 321 public bool Contains(T item)322 {323 return IndexOf(item) >= 0;324 }325 326 public void CopyTo(T[] array, int arrayIndex)327 {328 for (int i = 0; i < this.Count && arrayIndex < array.Length; ++i, ++arrayIndex)329 array[arrayIndex] = this[i];330 }331 332 public bool IsReadOnly333 {334 get { return false; }335 }336 337 public bool Remove(T item)338 {339 int index = IndexOf(item);340 if (index >= 0)341 {342 RemoveAt(index);343 return true;344 }345 return false;346 }347 348 #endregion349 350 #region IEnumerable<int> 成员351 352 public IEnumerator<T> GetEnumerator()353 {354 return new ListEnumerator<BigList<T>, T>(this);355 }356 357 #endregion358 359 #region IEnumerable 成员360 361 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()362 {363 return new ListEnumerator<BigList<T>, T>(this);364 }365 366 #endregion367 368 #region Enumerator369 public struct ListEnumerator<TList, TValue> : IEnumerator<TValue>370 where TList : IList<TValue>371 {372 int m_pos;373 TList m_list;374 375 public ListEnumerator(TList list)376 {377 m_pos = -1;378 m_list = list;379 }380 381 #region IEnumerator<int> 成员382 383 public TValue Current384 {385 get { return m_list[m_pos]; }386 }387 388 #endregion389 390 #region IDisposable 成员391 392 public void Dispose()393 {394 }395 396 #endregion397 398 #region IEnumerator 成员399 400 object System.Collections.IEnumerator.Current401 {402 get { return m_list[m_pos]; }403 }404 405 public bool MoveNext()406 {407 return ++m_pos < m_list.Count;408 }409 410 public void Reset()411 {412 m_pos = -1;413 }414 415 #endregion416 }417 #endregion418 }
可控增长线段数组-BigList
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。