C＃最快的方法来移动数组

如何快速将数组中的所有项目向左移动，并用空值填充结尾？

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

编辑：我说很快，但我想我的意思是有效的。 我需要这样做，而不创build一个列表或其他数据结构。 这是我需要在尽可能短的时间内完成数十万次的事情。

Answer 1

这是我的testing设备…

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); 

以下是每种解决scheme100万次迭代的性能结果（8核英特尔®至强®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 

为自己做出select:)

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重叠，则此方法的行为就像在sourceArray被覆盖之前，sourceArray的原始值保存在临时位置中一样。

所以，如果你不想分配一个新的数组，你可以传入源数据和目标数据的原始数组 – 尽pipe我想这个折衷的性能会稍微慢一些，因为这些数值会经过一个临时的持有位置。

我想，就像在这种调查中一样，你应该做一些快速的基准testing。

Answer 3

这是我的解决scheme，类似于任务的，它是一个简单的数组包装，并需要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的testing代码运行

 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); 

无论arrays大小如何，都需要约29ms。

Answer 4

使用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 5

难道你不能使用一个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 6

如果绝对必须在一个数组中，那么我会推荐最明显的代码。

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

这为优化程序提供了大多数机会，可以在安装该程序的任何目标平台上find最佳方法。

编辑：

我只是借用了Jason Punyon的testing代码，恐怕他是对的。 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

对于任何倾向的灵魂find这个线程，即将实施一个高度评价的答案。 他们都是垃圾，我不知道这是为什么。 也许Dested首先要求一个新的数组实现或者现在已经被删除的问题。 那么如果你只是想改变数组而不需要一个新的数组，就可以看到类似tdaines的答案。 并阅读循环缓冲区/环形缓冲区的内容： http ： //en.wikipedia.org/wiki/Circular_buffer 。 不需要移动实际的数据。 移动数组的性能不应该与数组的大小相关联。

Answer 8

你不能

• 用一个额外的1000个元素分配数组

• 有一个整数variablesint base = 0

• 而不是访问a[i]访问a[base+i]

• 做你的转变，只要说base++

然后，你完成了这1000次后，把它复制下来，重新开始。
那样的话，你只能每1000class做一次。

---

老笑话：
问：将一个寄存器移位一位需要多less个IBM 360？
答：33. 32位保存，1位移动寄存器。 （或一些这样的…）

Answer 9

你可以这样做：

 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 

Answer 10

您可以使用与原始和目的地相同的arrays进行快速就地复制：

 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; } 

Answer 11

尝试这个！ 使用Linq。 不需要第二个数组。

  var i_array = new int?[] {0, 1, 2, 3, 4, 5, 6 }; i_array = i_array.Select((v, k) => new { v = v, k = k }). Where(i => ik > 0).Select(i => iv).ToArray(); Array.Resize(ref i_array, i_array.Length + 1); 

输出：[0,1,2,3,4,5,6]将变成[1,2,3,4,5,6，null]

Answer 12

如果你拥有的内存，你可以考虑使用不安全的代码和老式的指针。

让自己成为一个内存stream并locking它，或者使用Marshal.AllocHGlobal在开始和结束时用一些填充来构造你的所有数组。 一次增加或减less所有的数组指针。 你仍然需要循环返回并设置你的空值。

如果你需要有select地增加或减less数组，你将不得不在它们之间添加填充。

数组是非常低级的数据结构，如果你以低级别的方式对待它们，你可以从中获得巨大的性能。

这样做可能会超过杰森的所有复制8核心英特尔至强E5450 @ 3.00GHz

Answer 13

没有testing过这个代码，但是它应该把所有的值都右移一位。 请注意，最后三行代码是您有效移动数组所需的全部内容。

 public class Shift : MonoBehaviour { //Initialize Array public int[] queue; void Start () { //Create Array Rows queue = new int[5]; //Set Values to 1,2,3,4,5 for (int i=0; i<5;i++) { queue[i] = i + 1; } //Get the integer at the first index int prev = queue[0]; //Copy the array to the new array. System.Array.Copy(queue, 1, queue, 0, queue.Length - 1); //Set the last shifted value to the previously first value. queue[queue.Length - 1] = prev; 

Answer 14

数组复制是O（n）操作并创build一个新的数组。 虽然数组复制当然可以快速高效地完成，但是你所说的问题实际上可以用一种完全不同的方式来解决（没有要求）创build一个新的数组/数据结构，并且只创build一个小的包装对象实例数组：

 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(); } } 

通过以这种方式包装和控制对数组的访问，现在我们可以演示如何用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() ); 

会产生输出：

基本数组：[0，1，2，3，4，5，6]
移位数组：[0，2，3，4，5，6，null]

我敢打赌，这样的解决scheme不适合你，但我相信这确实符合你的初始要求。 8）

在实现某个特定的问题之前，思考所有不同types的解决scheme通常是有帮助的，也许这可能是这个例子能够certificate的最重要的事情。

希望这可以帮助！

Answer 15

不正确和有趣的答案（谢谢，我会在这里整夜！）

 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; 

本着仍然使用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); 

但是它的速度比其他select还要快。

Answer 16

我知道这是一个古老的问题，但来自谷歌没有一个简单的例子，所以感谢这是最简单的方式重新sorting列表，你不必提供的types，它会在运行时，

  private static List<T> reorderList<T>(List<T> list){ List<T> newList = new List<T>(); list.ForEach(delegate(T item) { newList.Add(item); }); return newList; } 

Answer 17

 using System; using System.Threading; namespace ShiftMatrix { class Program { static void Main(string[] args) { MatrixOperation objMatrixOperation = new MatrixOperation(); //Create a matrix int[,] mat = new int[,] { {1, 2}, {3,4 }, {5, 6}, {7,8}, {8,9}, }; int type = 2; int counter = 0; if (type == 1) { counter = mat.GetLength(0); } else { counter = mat.GetLength(1); } while (true) { for (int i = 0; i < counter; i++) { ShowMatrix(objMatrixOperation.ShiftMatrix(mat, i, type)); Thread.Sleep(TimeSpan.FromSeconds(2)); } } } public static void ShowMatrix(int[,] matrix) { int rows = matrix.GetLength(0); int columns = matrix.GetLength(1); for (int k = 0; k < rows; k++) { for (int l = 0; l < columns; l++) { Console.Write(matrix[k, l] + " "); } Console.WriteLine(); } } } class MatrixOperation { public int[,] ShiftMatrix(int[,] origanalMatrix, int shift, int type) { int rows = origanalMatrix.GetLength(0); int cols = origanalMatrix.GetLength(1); int[,] _tmpMatrix = new int[rows, cols]; if (type == 2) { for (int x1 = 0; x1 < rows; x1++) { int y2 = 0; for (int y1 = shift; y2 < cols - shift; y1++, y2++) { _tmpMatrix[x1, y2] = origanalMatrix[x1, y1]; } y2--; for (int y1 = 0; y1 < shift; y1++, y2++) { _tmpMatrix[x1, y2] = origanalMatrix[x1, y1]; } } } else { int x2 = 0; for (int x1 = shift; x2 < rows - shift; x1++, x2++) { for (int y1 = 0; y1 < cols; y1++) { _tmpMatrix[x2, y1] = origanalMatrix[x1, y1]; } } x2--; for (int x1 = 0; x1 < shift; x1++, x2++) { for (int y1 = 0; y1 < cols; y1++) { _tmpMatrix[x2, y1] = origanalMatrix[x1, y1]; } } } return _tmpMatrix; } } } 

Answer 18

我相信最好和最有效的方法是使用Buffer.BlockCopy函数。 你将设置源和目的地到你的数组，源的偏移量是1.取决于你的数组types（我认为它是int），1 int = 4字节，所以你必须传入4作为第二个参数function。 请注意，偏移量是字节偏移量。

所以看起来像这样：

 int bytes2copy = yourArray.length - 4; Buffer.BlockCopy(yourArray, 4, yourArray, 0, bytes2copy); yourArray[yourArray.length-1] = null; 

Answer 19

请参阅下面的C＃代码以从string中删除空格。 数组中的那个移位字符。 性能是O（n）。 没有其他数组被使用。 所以没有额外的记忆。

  static void Main(string[] args) { string strIn = System.Console.ReadLine(); char[] chraryIn = strIn.ToCharArray(); int iShift = 0; char chrTemp; for (int i = 0; i < chraryIn.Length; ++i) { if (i > 0) { chrTemp = chraryIn[i]; chraryIn[i - iShift] = chrTemp; chraryIn[i] = chraryIn[i - iShift]; } if (chraryIn[i] == ' ') iShift++; if (i >= chraryIn.Length - 1 - iShift) chraryIn[i] = ' '; } System.Console.WriteLine(new string(chraryIn)); System.Console.Read(); }