C#最快的移位阵列方式

Question

如何快速将数组中的所有项目向左移动,用null填充结尾？

例如,[0,1,2,3,4,5,6]将成为[1,2,3,4,5,6,null]

编辑:我很快说,但我想我的意思是有效率.我需要在不创建List或其他数据结构的情况下执行此操作.这是我需要在尽可能短的时间内做几十万次的事情.

Answer 1

这是我的测试工具......

var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
var destination = new int?[source.Length];

var s = new Stopwatch();
s.Start();
for (int i = 0; i < 1000000;i++)
{
    Array.Copy(source, 1, destination, 0, source.Length - 1);
}
s.Stop();
Console.WriteLine(s.Elapsed);

以下是每个解决方案100万次迭代的性能结果(8 Core Intel Xeon E5450 @ 3.00GHz)

                       100 elements  10000 elements
For Loop                     0.390s         31.839s 
Array.Copy()                 0.177s         12.496s
Aaron 1                      3.789s         84.082s
Array.ConstrainedCopy()      0.197s         17.658s

自己做出选择:)

Answer 2

该最快要做到这一点的方法是使用Array.Copy,这在最终实现使用(类似的memcpy)大容量存储器传输操作:

var oldArray = new int?[] { 1, 2, 3, 4, 5, 6 };
var newArray = new int?[oldArray.Length];
Array.Copy(oldArray, 1, newArray, 0, oldArray.Length - 1);
// newArray is now { 2, 3, 4, 5, 6, null }

编辑:根据文件:

如果sourceArray和destinationArray重叠,则此方法的行为就像在覆盖destinationArray之前将sourceArray的原始值保留在临时位置中一样.

因此,如果您不想分配新数组,则可以为源和目标传递原始数组 - 尽管我认为权衡会稍微慢一点,因为值会通过临时保持位置.

我想,就像在任何此类调查中一样,你应该做一些快速的基准测试.

Answer 3

这是我的解决方案,类似于Task,因为它是一个简单的数组包装器,并且需要花费O(1)时间将数组移到左侧.

public class ShiftyArray<T>
{
    private readonly T[] array;
    private int front;

    public ShiftyArray(T[] array)
    {
        this.array = array;
        front = 0;
    }

    public void ShiftLeft()
    {
        array[front++] = default(T);
        if(front > array.Length - 1)
        {
            front = 0;
        }
    }

    public void ShiftLeft(int count)
    {
        for(int i = 0; i < count; i++)
        {
            ShiftLeft();
        }
    }

    public T this[int index]
    {
        get
        {
            if(index > array.Length - 1)
            {
                throw new IndexOutOfRangeException();
            }

            return array[(front + index) % array.Length];
        }
    }

    public int Length { get { return array.Length; } }
}

通过Jason Punyon的测试代码运行它......

int?[] intData = Enumerable.Range(1, 100).Cast<int?>().ToArray();
ShiftyArray<int?> array = new ShiftyArray<int?>(intData);

Stopwatch watch = new Stopwatch();
watch.Start();

for(int i = 0; i < 1000000; i++)
{
    array.ShiftLeft();
}

watch.Stop();

Console.WriteLine(watch.ElapsedMilliseconds);

无论阵列大小如何,都需要~29ms.

Answer 4

难道你不能使用System.Collections.Generic.Queue而不是数组？

我觉得你需要对丢弃它的值执行操作,因此使用队列似乎更合适:

// dummy initialization
        System.Collections.Generic.Queue<int> queue = new Queue<int>();
        for (int i = 0; i < 7; ++i ) { queue.Enqueue(i); }// add each element at the end of the container

        // working thread
        if (queue.Count > 0)
            doSomething(queue.Dequeue());// removes the last element of the container and calls doSomething on it

Answer 5

使用Array.Copy()方法,如

int?[] myArray = new int?[]{0,1,2,3,4};
Array.Copy(myArray, 1, myArray, 0, myArray.Length - 1);
myArray[myArray.Length - 1] = null

在Array.Copy可能的方式,微软希望我们能够复制数组元素...

Answer 6

如果这是绝对有是在一个数组,那么我会推荐最明显的代码可能.

for (int index = startIndex; index + 1 < values.Length; index++)
     values[index] = values[index + 1];
values[values.Length - 1] = null;

这为优化器提供了在安装程序的任何目标平台上找到最佳方法的最大机会.

编辑:

我刚刚借用了Jason Punyon的测试代码,我担心他是对的.Array.Copy赢了!

    var source = Enumerable.Range(1, 100).Cast<int?>().ToArray();
    int indexToRemove = 4;

    var s = new Stopwatch();
    s.Start();
    for (int i = 0; i < 1000000; i++)
    {
        Array.Copy(source, indexToRemove + 1, source, indexToRemove, source.Length - indexToRemove - 1);
        //for (int index = indexToRemove; index + 1 < source.Length; index++)
        //    source[index] = source[index + 1]; 
    }
    s.Stop();
    Console.WriteLine(s.Elapsed);

Array.Copy在我的机器上需要103到150毫秒.

for循环在我的机器上需要269到338毫秒.

Answer 7

任何倾注的灵魂找到这个线程,并即将实施一个评价很高的答案.所有这些都是垃圾,我不知道为什么会这样.也许Dested首先要求新的阵列实现,或者现在已经从问题中删除了.好吧,如果您只是想移动数组而不需要新数组,请参阅tdaines的答案之类的答案.并阅读循环缓冲区/环形缓冲区等内容:http://en.wikipedia.org/wiki/Circular_buffer.不需要移动实际数据.移位数组的性能不应该与数组的大小相关联.

Answer 8

你可以这样做：

var items = new int?[] { 0, 1, 2, 3, 4, 5, 6 };  // Your array
var itemList = new List<int?>(items);  // Put the items in a List<>
itemList.RemoveAt(1); // Remove the item at index 1
itemList.Add(null); // Add a null to the end of the list
items = itemList.ToArray(); // Turn the list back into an array

当然，完全摆脱数组并仅使用 List<> 会更有效。然后你可以忘记第一行和最后一行，然后这样做：

var itemList = new List<int?> { 0, 1, 2, 3, 4, 5, 6 };
itemList.RemoveAt(1); // Remove the item at index 1
itemList.Add(null); // Add a null to the end of the list