最快到阵列的一部分移到正确的方式

问题描述

我需要给定的指标在一小阵插入的元素。即，1个地点移动的所有元素具有更大的索引到右侧。什么是做，在.NET最快的方法？

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

请注意：我说我自己的答案，但我仍然在寻找一个解释和更快的替代品

NOTE: I added my own answer, but I am still looking for an explanation and faster alternatives.

编辑：我确实需要一个数组，而不是一个列表＆LT; T＆GT; ，而不是一个链表

I do need an array, not a List<T> and not a linked list.

更新：由于我没有得到奇怪的性能结果的解释，我问过单独的问题：Why正在复制引用字符串长度超过整数复制（但反之为Array.Copy（））？

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

推荐答案

有两个明显的方法：使用 Array.Copy 和一个复制的元素之一：

There are two obvious approaches: use Array.Copy and copy 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];            
}

在一方面，列表＆LT; T＆GT; 插入使用 Array.Copy 。另一方面， Array.Copy 是不通用的，可以做的额外工作的很多的：的

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

我的预期 Array.Copy 要快。然而，这MiniBench测试的结果让我吃惊。

I expected Array.Copy to 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];            
    }
}

下面是来自两个运行结果：

Here are the results from 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

也就是说，对于 INT 和的DateTime ElementByElement 是显著速度更快;而字符串 BuiltInCopy 结束快 ElementByElement 两次（两次一样慢 ElementByElement 为 INT ）。我期望为 INT 的结果和字符串是一个32位的机器上非常相似，因为参考到字符串在堆栈上的大小相同的 INT ，比读，写堆栈内存应该是其他任何操作参与其中。

That is, for int and DateTime ElementByElement is significantly faster; while for string BuiltInCopy is over twice as fast as ElementByElement (and twice as slow as ElementByElement for int). I'd expect the results for int and string to be very similar on a 32-bit machine, since a reference to string on the stack is the same size as an int and no operations other than reading and writing stack memory should be involved.

这篇关于最快到阵列的一部分移到正确的方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！