將列表克隆到現有列表中的最有效方法是最小化內存重新分配？

Question

我需要將現有列表克隆到另一個現有列表中。由於環境需要非常高的性能，我需要消除不必要的內存重新分配。

我能想到的最有效的算法如下，它會增加目的地列表的容量，以便根據需要匹配源列表，但不會減少它自己的數量。 （這是該項目的可接受行爲。）

public static void CloneInto(this List<T> source, List<T> destination) 
    { 
     if (destination.Capacity < source.Capacity) 
     { 
      /* Increase capacity in destination */ 
      destination.Capacity = source.Capacity; 
     } 

     /* Direct copy of items within the limit of both counts */ 
     for (var i = 0; i < source.Count && i < destination.Count; i++) 
     { 
      destination[i] = source[i]; 
     } 

     if (source.Count > destination.Count) 
     { 
      /* Append any extra items from source */ 
      for (var i = destination.Count; i < source.Count; i++) 
      { 
       destination.Add(source[i]); 
      } 
     } 
     else if (source.Count < destination.Count) 
     { 
      /* Trim off any extra items from destination */ 
      while (destination.Count > source.Count) 
      { 
       destination.RemoveAt(destination.Count - 1); 
      } 
     } 
    } 

但是，這似乎有很多代碼，邏輯和循環。

是否有一種更有效的方法將列表克隆到現有列表中，同時避免不必要的內存分配？

Answer 1

if (destination.Capacity < source.Capacity) 
{ 
    /* Increase capacity in destination */ 
    destination.Capacity = source.Capacity; 
} 

這可能是錯誤的...的source.Capacity可能比需要的更大......

而你是「複製」到一個「新」 destination「緩衝」已經包含在destination的元素。這個副本是不必要的，因爲隨後的destination的元素被丟棄

所以，你應該至少爲：

if (destination.Capacity < source.Count) 
{ 
    /* Increase capacity in destination */ 
    destination.Clear(); 
    destination.Capacity = source.Capacity; 
} 

這樣，如果Capacity改變，沒有元素需要被複制（請注意，我使用Capacity = Count，因爲雖然這將在短期內節省內存，但從長遠來看，它可能會導致多次內存分配）。請注意，我正在檢查source.Count，但對於Capacity的分配，我正在使用相同的source.Capacity。如果該方法被多次調用，這將最大限度地減少destination的重新分配。

小的優化：

if (destination.Capacity < source.Count) 
{ 
    /* Increase capacity in destination */ 
    destination.Capacity = 0; 
    destination.Capacity = source.Capacity; 
} 

這是因爲List.Clear()使用Array.Clear()，所以它真正歸零的內部元件，同時destination.Capacity = 0進行了優化，簡單地重新分配內部數組到static _emptyArray。

你甚至可以嘗試：

public static void CloneInto(this List<T> source, List<T> destination) 
{ 
    destination.Capacity = 0; // or destination.Clear(); 
    destination.AddRange(source); 
} 

，但通過看source code，我覺得它比必要慢（因爲它首先複製元素T[] itemsToInsert = new T[count];，它確實是這樣的元素的兩個副本.. 。

然後：

while (destination.Count > source.Count) 
{ 
    destination.RemoveAt(destination.Count - 1); 
} 

可以被優化爲：

destination.RemoveRange(source.Count, destination.Count - source.Count); 

Answer 2

你爲什麼不只是使用

destination = source.ToList(); 

ToList（）創建列表的副本，這是在目的地之前的一切，將立即準備好分配後的垃圾收集。

Answer 3

小測試上性能比較：

public static List<T> CloneInto<T>(List<T> source, List<T> destination) 
{ 
    if (destination.Capacity < source.Capacity) 
    { 
     /* Increase capacity in destination */ 
     destination.Capacity = source.Capacity; 
    } 

    /* Direct copy of items within the limit of both counts */ 
    for (var i = 0; i < source.Count && i < destination.Count; i++) 
    { 
     destination[i] = source[i]; 
    } 

    if (source.Count > destination.Count) 
    { 
     /* Append any extra items from source */ 
     for (var i = destination.Count; i < source.Count; i++) 
     { 
      destination.Add(source[i]); 
     } 
    } 
    else if (source.Count < destination.Count) 
    { 
     /* Trim off any extra items from destination */ 
     while (destination.Count > source.Count) 
     { 
      destination.RemoveAt(destination.Count - 1); 
     } 
    } 

    return destination; 
} 


static void Main(string[] args) 
{ 
    List<string> list1 = new List<string>(); 
    List<string> list2 = new List<string>(); 

    for (int i = 0; i < 100000; i++) 
    { 
     list1.Add(Guid.NewGuid().ToString());     
    } 

    Stopwatch s = new Stopwatch(); 

    s.Start(); 
    CloneInto(list1, list2); 

    s.Stop(); 

    Console.WriteLine("Your Method: " + s.Elapsed.Ticks); 

    s.Reset(); 
    s.Start(); 

    list2 = list1.ToList(); 

    s.Stop(); 

    Console.WriteLine("ToList() Method: " + s.Elapsed.Ticks); 

    Console.ReadKey(); 

結果：

但是，如果僅僅是關於內存 - 你的方法比.ToList（）更好，並且你可以做的更多的事情來提高性能。也許你可以使用像parallel.for並行循環，但不知道這一點。