The fastest way to move part of the array to the right

Question

I need to "insert" an element at a given index into a small array. That is, to move all elements with large indices to 1 place on the right. What is the fastest way to do this in .NET?

NOTE. I added my own answer, but I'm still looking for explanations and faster alternatives.

EDIT: I need an array, not a List<T> , not a linked list.

UPDATE: Since I didn’t get an explanation of the strange performance results, I asked this question separately: Why copying links to strings is much slower than copying ints (but vice versa for Array.Copy ())?

Answer 1

There are two obvious approaches: use Array.Copy and copy the elements one by one:

 private static void ElementByElement<T>(T[] arg, int start) { for (int i = arg.Length - 1; i > start; i--) { arg[i] = arg[i - 1]; } } private static T BuiltInCopy<T>(T[] arg, int start) { Array.Copy(arg, start, arg, start + 1, arg.Length - start - 1); return arg[0]; } 

For one thing, List<T> insert uses Array.Copy . Array.Copy , Array.Copy other hand, is nonequivalent and can do a lot of extra work: http://msdn.microsoft.com/en-us/library/z50k9bft.aspx

I expected Array.Copy be faster. However, the results of this MiniBench test surprised me.

 internal class Program { private static int smallArraySize = 32; public static void Main(string[] args) { BenchArrayCopy(); } private static void BenchArrayCopy() { var smallArrayInt = new int[smallArraySize]; for (int i = 0; i < smallArraySize; i++) smallArrayInt[i] = i; var smallArrayString = new string[smallArraySize]; for (int i = 0; i < smallArraySize; i++) smallArrayString[i] = i.ToString(); var smallArrayDateTime = new DateTime[smallArraySize]; for (int i = 0; i < smallArraySize; i++) smallArrayDateTime[i] = DateTime.Now; var moveInt = new TestSuite<int[], int>("Move part of array right by 1: int") .Plus(BuiltInCopy, "Array.Copy()") .Plus(ElementByElement, "Element by element in a for loop") .RunTests(smallArrayInt, 0); var moveString = new TestSuite<string[], string>("Move part of array right by 1: string") .Plus(BuiltInCopy, "Array.Copy()") .Plus(ElementByElement, "Element by element in a for loop") .RunTests(smallArrayString, "0"); var moveDT = new TestSuite<DateTime[], DateTime>("Move part of array right by 1: DateTime") .Plus(BuiltInCopy, "Array.Copy()") .Plus(ElementByElement, "Element by element in a for loop") .RunTests(smallArrayDateTime, smallArrayDateTime[0]); moveInt.Display(ResultColumns.All, moveInt.FindBest()); moveString.Display(ResultColumns.All, moveInt.FindBest()); moveDT.Display(ResultColumns.All, moveInt.FindBest()); } private static T ElementByElement<T>(T[] arg) { int start = 8; for (int i = smallArraySize - 1; i > start; i--) { arg[i] = arg[i - 1]; } return arg[0]; } private static T BuiltInCopy<T>(T[] arg) { int start = 8; int length = smallArraySize - start - 1; Array.Copy(arg, start, arg, start + 1, length); return arg[0]; } } 

The following are the results of two runs:

 f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe ============ Move part of array right by 1: int ============ Array.Copy() 568475865 0:31.606 1,73 Element by element in a for loop 980013061 0:31.449 1,00 ============ Move part of array right by 1: string ============ Array.Copy() 478224336 0:31.618 2,06 Element by element in a for loop 220168237 0:30.926 4,38 ============ Move part of array right by 1: DateTime ============ Array.Copy() 382906030 0:27.870 2,27 Element by element in a for loop 458265102 0:29.239 1,99 f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe ============ Move part of array right by 1: int ============ Array.Copy() 500925013 0:28.514 1,76 Element by element in a for loop 988394220 0:31.967 1,00 ============ Move part of array right by 1: string ============ Array.Copy() 483178262 0:30.048 1,92 Element by element in a for loop 193092931 0:27.642 4,43 ============ Move part of array right by 1: DateTime ============ Array.Copy() 450569361 0:30.807 2,11 Element by element in a for loop 568054290 0:31.385 1,71 

That is, for int and DateTime ElementByElement is much faster; and for string BuiltInCopy , it's twice as fast as ElementByElement (and twice as slow as ElementByElement for int ). I expect that the results for int and string will be very similar on a 32-bit machine, since the link to string on the stack is the same size as int , and no operations other than reading and writing to the memory of the stack should be involved.

Answer 2

Perhaps using a linked list would be better in this case.

Answer 3

First I asked if the array is a suitable data structure choice given this requirement. However, I see a possible optimization in the code for copying "element by element":

  private static void ElementByElement2<T>(T[] arg, int start) { int i = arg.Length - 1; while (i > start) arg[i] = arg[--i]; } 

I compared this and about twice as fast as your for-loop solution.

Answer 4

As an example, consider List<T> - it uses Array.Copy , assuming that if you are limited to using an array , then this might be your best option.

Or, as Indeera notes, use a different container! Depending on the specific use, some options

• if you always paste to 0, use List<T> (or save your own array with spare capacity, but I can't figure out why), but think about it the other way around so that “insert” becomes “append”, which is cheaper (especially if you do not need to redistribute)
• linked list is an option
• as is queue / stack (depending on how and how to delete data)
• or to add and add, save the array with the reserve capacity on both sides, wrapped up with something like (but more complicated than) a List<T> - and save the offset - that is, you have an array of 100 and you know that your zero "is 50 and you used 20; pasting to “zero” then simply changes the value with an offset of 49, reduces the offset of the main zero to 49, and increases the virtual length to 21

Answer 5

If you want to add to this index, you must use the Linked List. See also: What are real-world examples of when to use Linked Lists?