如何更快地克隆阵列？

Question

在国际象棋AI程序中，我有一个必须执行的功能，然后撤消了一步。

为了做到这一点，我需要保存一堆包含有关板上当前情况的数据的备份（例如碎片所在的位置，哪些碎片正在受到攻击，或者如果国王受到检查），然后进行移动，最后重置数组。

我使用的代码是这样的：

int[] piecesBackup = pieces.Clone() as int[];

MakeMove();

pieces = piecesBackup.Clone() as int[];



// I've also tried this



int[] piecesBackup = new int[pieces.Length];
pieces.CopyTo(piecesBackup, 0);

MakeMove();

pieces = new int[piecesBackup.Length];
piecesBackup.CopyTo(pieces, 0);

此代码重复了数千次，并且需要很长时间。我怀疑这里的耗时操作是克隆/复制操作。

我想不出任何更好的方法来解决这个问题：这真的是复制数组内容的唯一方法吗？有什么办法可以简单地使用int [] potebackup = picts然后pipter = potebackup？

Answer 1

我想您的大部分时间都花在分配物体或清理垃圾中。尽管GC处理大多数方案，但很高的频率分配可能会出现问题。但是，与往常一样，我建议一些分析以确认实际上是这种情况。关于性能，很容易猜测错误。

我会尝试将董事会状态适应不变的结构。由于这是一种值类型，因此您可以完全删除任何堆的分配。

我的国际象棋知识有点生锈，但是如果我没记错的话，随时可以发挥最大的32件作用，每件零件都有64个可能的位置。因此，我们应该能够用32个字节代表整个板，并剩下一些可能的用途。 32字节对于结构而言并不是不合理的大小，应该非常快地创建副本。

使用结构可能需要添加所有32件作为单独的字段，这可能是更多的编写代码，但是优化的代码通常并不漂亮。我还建议您阅读生活的文章对游戏状态优化的一些观点。

Answer 2

考虑每次执行副本时重复使用阵列而不是分配新阵列。分配一个新数组需要时间，然后还有一些垃圾收集将在某个时候出现，以清除不再使用的旧数组。

阵列重复使用是我使用的方法，其性能结果良好。这是示例代码，该代码演示了代码重复使用的时间约为分配新数组的时间。

var stopwatch = new System.Diagnostics.Stopwatch();
var innerIterations = 1000000;

int[] pieces = new int[32];
for (int i = 0; i < pieces.Length; i++)
{
    // Put some fake data in the array
    pieces[i] = i * 3;
}

int[] piecesReuse = new int[32];
for (int i = 0; i < piecesReuse.Length; i++)
{
    // Put some fake data in the array
    piecesReuse[i] = i * 3;
}

for (int j = 0; j < 10; j++)
{ 
    Console.WriteLine($"Begin newAllocate round {j} ...");
    stopwatch.Restart();
    for (int i = 0; i < innerIterations; i++)
    {
        int[] piecesBackup = new int[pieces.Length];
        pieces.CopyTo(piecesBackup, 0);

        MakeMove();

        pieces = new int[piecesBackup.Length];
        piecesBackup.CopyTo(pieces, 0);
    }
    stopwatch.Stop();
    Console.WriteLine($"...completed newAllocate round {j} at {stopwatch.ElapsedMilliseconds} ms.");

    Console.WriteLine($"Begin reusedArray round {j} ...");
    stopwatch.Restart();
    int[] piecesBackupReused = new int[piecesReuse.Length];
    for (int i = 0; i < innerIterations; i++)
    {
        piecesReuse.CopyTo(piecesBackupReused, 0);

        MakeMove();

        piecesBackupReused.CopyTo(piecesReuse, 0);
    }
    stopwatch.Stop();
    Console.WriteLine($"...completed reusedArray round {j} at {stopwatch.ElapsedMilliseconds} ms.");
}

void MakeMove()
{
    // Make some change to the arrays
    pieces[0] = 100;
    piecesReuse[0] = 200;
}

我的机器（YMMV）产生的输出。

Begin newAllocate round 0 ...
...completed newAllocate round 0 at 98 ms.
Begin reusedArray round 0 ...
...completed reusedArray round 0 at 28 ms.
Begin newAllocate round 1 ...
...completed newAllocate round 1 at 54 ms.
Begin reusedArray round 1 ...
...completed reusedArray round 1 at 27 ms.
Begin newAllocate round 2 ...
...completed newAllocate round 2 at 50 ms.
Begin reusedArray round 2 ...
...completed reusedArray round 2 at 27 ms.
Begin newAllocate round 3 ...
...completed newAllocate round 3 at 51 ms.
Begin reusedArray round 3 ...
...completed reusedArray round 3 at 30 ms.
Begin newAllocate round 4 ...
...completed newAllocate round 4 at 50 ms.
Begin reusedArray round 4 ...
...completed reusedArray round 4 at 26 ms.
Begin newAllocate round 5 ...
...completed newAllocate round 5 at 49 ms.
Begin reusedArray round 5 ...
...completed reusedArray round 5 at 24 ms.
Begin newAllocate round 6 ...
...completed newAllocate round 6 at 47 ms.
Begin reusedArray round 6 ...
...completed reusedArray round 6 at 23 ms.
Begin newAllocate round 7 ...
...completed newAllocate round 7 at 45 ms.
Begin reusedArray round 7 ...
...completed reusedArray round 7 at 24 ms.
Begin newAllocate round 8 ...
...completed newAllocate round 8 at 48 ms.
Begin reusedArray round 8 ...
...completed reusedArray round 8 at 32 ms.
Begin newAllocate round 9 ...
...completed newAllocate round 9 at 40 ms.
Begin reusedArray round 9 ...
...completed reusedArray round 9 at 22 ms.

Answer 3

我怀疑这里的耗时操作是克隆/复制操作。

您才是正确的，因为您使用了国际象棋板的天文差代表。您可能需要在国际象棋游戏中存储一系列可以高达40亿个整数的原因？您有64个正方形，总共有32件。

至于您的分析，最多的时间可能是通过分配和释放（GC）所有这些巨大的阵列来获取的时间。您应该使用arraypool＆lt;＆gt;或MemoryPool＆lt;＆gt;，或者只是具有正确尺寸的普通旧结构。