可控增长线段数组-BigList
浏览数：21 /
时间：2015年06月08日
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 else 107 { 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 Capacity 130 { 131 get { return m_capacity; } 132 set 133 { 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 == null) 149 return false; 150 return IndexOf((T)value) >= 0; 151 } 152 153 public int IndexOf(object value) 154 { 155 if (value == 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 IsFixedSize 166 { 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 get 178 { 179 return this[index]; 180 } 181 set 182 { 183 this[index] = (T)value; 184 } 185 } 186 187 #endregion 188 189 #region ICollection 成员 190 191 public void CopyTo(Array array, int index) 192 { 193 this.CopyTo((T[])array, index); 194 } 195 196 public bool IsSynchronized 197 { 198 get { return false; } 199 } 200 201 public object SyncRoot 202 { 203 get { return this; } 204 } 205 206 #endregion 207 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 get 222 { 223 return m_segments[index >> BIT_OFFSET][index & OFFSET_MASK]; 224 } 225 set 226 { 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 else 250 { 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 else 264 { 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 #endregion 312 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 IsReadOnly 333 { 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 #endregion 349 350 #region IEnumerable<int> 成员 351 352 public IEnumerator<T> GetEnumerator() 353 { 354 return new ListEnumerator<BigList<T>, T>(this); 355 } 356 357 #endregion 358 359 #region IEnumerable 成员 360 361 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 362 { 363 return new ListEnumerator<BigList<T>, T>(this); 364 } 365 366 #endregion 367 368 #region Enumerator 369 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 Current 384 { 385 get { return m_list[m_pos]; } 386 } 387 388 #endregion 389 390 #region IDisposable 成员 391 392 public void Dispose() 393 { 394 } 395 396 #endregion 397 398 #region IEnumerator 成员 399 400 object System.Collections.IEnumerator.Current 401 { 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 #endregion 416 } 417 #endregion 418 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
