C# 移动数组的最快方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2381245/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C# quickest way to shift array
提问by Dested
How can I quickly shift all the items in an array one to the left, padding the end with null?
如何快速将数组中的所有项目向左移动一个，并用 null 填充末尾？
For example, [0,1,2,3,4,5,6] would become [1,2,3,4,5,6,null]
例如， [0,1,2,3,4,5,6] 将变为 [1,2,3,4,5,6,null]
Edit: I said quickly but I guess I meant efficiently. I need to do this without creating a List or some other data structure. This is something I need to do several hundred thousand times in as short amount of time as possible.
编辑：我说得很快，但我想我的意思是有效。我需要在不创建 List 或其他一些数据结构的情况下执行此操作。这是我需要在尽可能短的时间内做几十万次的事情。
回答by Aaron
You might do it like this:
你可以这样做：
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
Of course, it would be more efficient to get rid of the array entirely and just use a List<>. You could then forget the first line and last line and do it like this:
当然，完全摆脱数组并只使用 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
回答by Stan R.
Incorrect and slightly amusing answer (thanks, i'll be here all night !)
不正确且有点有趣的答案（谢谢，我会整晚都在这里！）
int?[] test = new int?[] {0,1,2,3,4,5,6 };
int?[] t = new int?[test.Length];
t = test.Skip(1).ToArray();
t[t.Length - 1] = null;
In the spirit of still using Skip (dont ask me, i know worst usage of LINQ extension methods ever), the only way I thought of rewriting it would be
本着仍然使用 Skip 的精神（别问我，我知道 LINQ 扩展方法最糟糕的用法），我想重写它的唯一方法是
int?[] test = new int?[] { 0, 1, 2, 3, 4, 5, 6 };
int?[] t = new int?[test.Length];
Array.Copy(test.Skip(1).ToArray(), t, t.Length - 1);
But it's in NO WAY faster than the other options.
但它绝不比其他选项快。
回答by Seb
Couldn't you use a System.Collections.Generic.Queue instead of an array ?
您不能使用 System.Collections.Generic.Queue 而不是数组吗？
I feel like you need to perform actions on your value the discard it, thus using a queue seems to be more appropriate :
我觉得您需要对您的价值执行操作并丢弃它，因此使用队列似乎更合适：
// 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
回答by Ben M
The quickestway to do this is to use Array.Copy, which in the final implementation uses a bulk memory transfer operation (similar to memcpy):
执行此操作的最快方法是使用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 }
Edited: according to the documentation:
编辑：根据文档：
If sourceArray and destinationArray overlap, this method behaves as if the original values of sourceArray were preserved in a temporary location before destinationArray is overwritten.
如果 sourceArray 和 destinationArray 重叠，则此方法的行为就像在覆盖 destinationArray 之前将 sourceArray 的原始值保留在临时位置一样。
So if you don't want to allocate a new array, you can pass in the original array for both source and destination--although I imagine the tradeoff will be a somewhat slower performance since the values go through a temporary holding position.
因此，如果您不想分配新数组，则可以为源和目标传入原始数组——尽管我认为权衡会导致性能稍慢，因为这些值会经过临时持有位置。
I suppose, as in any investigation of this kind, you should do some quick benchmarking.
我想，就像在任何此类调查中一样，您应该进行一些快速的基准测试。
回答by MartinStettner
Use the Array.Copy()method as in
使用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
The Array.Copyis probably the way, Microsoft wanted us to copy array elements...
在Array.Copy可能的方式，微软希望我们能够复制数组元素...
回答by Jason Punyon
Here's my test harness...
这是我的测试工具...
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);
Here are the performance results for 1 million iterations of each solution (8 Core Intel Xeon E5450 @ 3.00GHz)
以下是每个解决方案（8 核 Intel Xeon E5450 @ 3.00GHz）的 100 万次迭代的性能结果
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
Make the choice for yourself :)
为自己做出选择:)
回答by Jeffrey L Whitledge
If it absolutely hasto be in an array, then I would recommend the most obvious code possible.
如果这是绝对有是在一个数组，那么我会推荐最明显的代码可能。
for (int index = startIndex; index + 1 < values.Length; index++)
values[index] = values[index + 1];
values[values.Length - 1] = null;
This gives the optimizer the most opportunities to find the best way on whatever target platform the program is installed on.
这使优化器有最多的机会在安装程序的任何目标平台上找到最佳方式。
EDIT:
编辑：
I just borrowed Jason Punyon's test code, and I'm afraid he's right. Array.Copy wins!
我刚刚借用了 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 takes between 103 and 150 ms on my machine.
Array.Copy 在我的机器上需要 103 到 150 毫秒。
for loop takes between 269 and 338 ms on my machine.
for 循环在我的机器上需要 269 到 338 毫秒。
回答by Task
Array copying is an O(n) operation and creates a new array. While array copying can certainly be done quickly and efficiently, the problem you've stated can actually be solved in an entirely different way without (as you've requested) creating a new array/data structure and only creating one small wrapping object instance per array:
数组复制是一个 O(n) 操作并创建一个新数组。虽然数组复制当然可以快速有效地完成，但您所说的问题实际上可以以完全不同的方式解决，而无需（按照您的要求）创建新的数组/数据结构，并且每个只创建一个小的包装对象实例大批：
using System;
using System.Text;
public class ArrayReindexer
{
private Array reindexed;
private int location, offset;
public ArrayReindexer( Array source )
{
reindexed = source;
}
public object this[int index]
{
get
{
if (offset > 0 && index >= location)
{
int adjustedIndex = index + offset;
return adjustedIndex >= reindexed.Length ? "null" : reindexed.GetValue( adjustedIndex );
}
return reindexed.GetValue( index );
}
}
public void Reindex( int position, int shiftAmount )
{
location = position;
offset = shiftAmount;
}
public override string ToString()
{
StringBuilder output = new StringBuilder( "[ " );
for (int i = 0; i < reindexed.Length; ++i)
{
output.Append( this[i] );
if (i == reindexed.Length - 1)
{
output.Append( " ]" );
}
else
{
output.Append( ", " );
}
}
return output.ToString();
}
}
By wrapping and controlling access to the array in this manner, we can now demonstrate how the problem was solved with an O(1) method call...
通过以这种方式包装和控制对数组的访问，我们现在可以演示如何使用 O(1) 方法调用解决问题...
ArrayReindexer original = new ArrayReindexer( SourceArray );
Console.WriteLine( " Base array: {0}", original.ToString() );
ArrayReindexer reindexed = new ArrayReindexer( SourceArray );
reindexed.Reindex( 1, 1 );
Console.WriteLine( "Shifted array: {0}", reindexed.ToString() );
Will produce the output:
将产生输出：
Base array: [ 0, 1, 2, 3, 4, 5, 6 ]
Shifted array: [ 0, 2, 3, 4, 5, 6, null ]
基本数组：[ 0, 1, 2, 3, 4, 5, 6 ]
移位数组： [ 0, 2, 3, 4, 5, 6, null ]
I'm willing to bet that there will be a reason that such a solution won't work for you, but I believe this does match your initial stated requirements. 8 )
我敢打赌，这样的解决方案对您不起作用是有原因的，但我相信这确实符合您最初提出的要求。8)
It's often helpful to think about all the different kindsof solutions to a problem before implementing a specific one, and perhaps that might be the most important thing that this example can demonstrate.
在实现一个特定的解决方案之前考虑所有不同类型的问题解决方案通常很有帮助，也许这可能是这个例子可以展示的最重要的事情。
Hope this helps!
希望这可以帮助！
回答by Task
You can use the same array as source and destination for fast in-place copy:
您可以使用与源和目标相同的数组进行快速就地复制：
static void Main(string[] args)
{
int[] array = {0, 1, 2, 3, 4, 5, 6, 7};
Array.ConstrainedCopy(array, 1, array, 0, array.Length - 1);
array[array.Length - 1] = 0;
}
回答by tdaines
Here is my solution, similar to Task's in that it is a simple Array wrapper and that it takes O(1) time to shift the array to the left.
这是我的解决方案，类似于 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; } }
}
Running it through Jason Punyon's test code...
通过 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);
Takes ~29ms, regardless of the array size.
无论数组大小如何，都需要大约 29 毫秒。
