将列表克隆到现有列表并最小化内存重新分配的最有效方法？

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

你为什么不直接使用

destination = source.ToList();

ToList() 创建列表的副本，之前在目标中的所有内容将在分配后立即准备好进行垃圾回收。

Answer 2

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

这可能是错误的...source.Capacity 可能比需要的大...

而你"copying"把destination中已经包含的元素变成了"new"destination"buffer"。此副本是不必要的，因为 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 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 这样的并行循环，但不确定。

将列表克隆到现有列表并最小化内存重新分配的最有效方法？

Most efficient way to clone a list into an existing list, minimizing memory reallocation?

c#

performance

list

memory-management

clone