如何在C#中初始化整数数组

5

可能重复的问题:
C#:初始化int数组的更简洁方法

基本上,我想知道是否有比下面显示的代码更有效的代码。

    private static int[] GetDefaultSeriesArray(int size, int value)
    {
        int[] result = new int[size];
        for (int i = 0; i < size; i++)
        {
            result[i] = value;
        }
        return result;
    }

数组大小可能从10到150000不等。对于小数组来说,这不是问题,但应该有更好的方法来执行上述操作。我使用的是VS2010(.NET 4.0)。


1
无论你如何操作,在C#中使用非默认值初始化数组都是O(N)的操作。 - Maciej
是的,@Maciej,但毫无疑问,有些聪明的人会以某种方式微调for循环(尽管我看不到任何微调)。 - Paul Sullivan
@Maciej 是的,但并非所有 O(n) 方法都相同。在其中仍存在显著的变异空间。 - Servy
1
在编程中,只有微小的优化是在for循环中使用++i。 - Paul Sullivan
如果您决定删除此问题:请注意,本文讨论了初始化非常大的数组所采取的几种方法。在删除之前,请考虑与重复内容合并。 - Alexei Levenkov
显示剩余4条评论
6个回答

8

C#/CLR没有内置的方法来使用非默认值初始化数组。

如果以每个元素的操作数作为衡量标准,您的代码已经尽可能高效。

如果并行初始化大型数组的块,可以获得潜在更快的初始化速度。但是,这种方法需要仔细调整,因为多线程操作的成本并不简单。

通过分析您的需求并有可能完全删除整个初始化,可获得更好的结果。例如,如果数组通常包含常量值,则可以实现某种COW(写时复制)方法,其中对象最初没有支持数组,并返回常量值,当要对元素进行写入时,它将创建(可能是部分)支持修改段的备份数组。

较慢但更紧凑的代码(可能更易于阅读)是使用Enumerable.Repeat。请注意,对于大型数组,ToArray将导致分配大量内存(这也可能导致LOH上的分配)- 参见使用Enumerable.Range时内存消耗高吗?

 var result = Enumerable.Repeat(value, size).ToArray();

5
这将会相当不高效,而不是更高效。 - Servy
@Servy:这可能就是为什么Alexei在回答之前说“你的代码已经尽可能高效”的原因。 - Honza Brestan
@HonzaBrestan 嗯,我不同意那个说法。除此之外,问题是要求更好的选择。如果你没有更好的选择,那就不要回答,而不是提供你知道更糟糕的东西。 - Servy
@AlexeiLevenkov 对于小型数组来说,情况会更糟,但对于小型数组来说,稍微高一点的开销不应该是一个大问题,特别是考虑到 OP 显然正在处理足够大以从并行化中受益的数组。我还没有提供答案,因为这是一个非平凡的问题,如果并行化没有做得完全正确,它很容易使问题变得更糟。再次强调,如果你的答案只是“那就是你能做到的最好”,那么情况就不会那么糟糕,但是建议使用你知道更糟的东西就不好了。 - Servy
@AlexeiLevenkov,我终于想出了一种方法,在我的几个测试中,它比OP的代码(对于大数据集)运行得更快,足以可能产生影响(即不仅仅是微小的优化)。 - Servy
显示剩余3条评论

4

你可以通过使用Array.Copy来提高速度。它能够在更低的层次上工作,批量分配更大的内存空间。

通过批处理分配,你最终可以将数组从一个部分复制到自身。

此外,这些批次本身可以非常有效地并行化。

以下是我的初始代码。在我的机器上(只有两个核心),使用大小为1000万项的样本数组,我获得了约15%的加速。你需要调整批处理大小(尝试保持在页面大小的倍数以保持效率),以将其调整到你所拥有的项目大小。对于较小的数组,它几乎与你的代码相同,因为它不会超过填充第一个批次,但在这些情况下也不会更糟糕(明显)。

private const int batchSize = 1048576;
private static int[] GetDefaultSeriesArray2(int size, int value)
{

    int[] result = new int[size];

    //fill the first batch normally
    int end = Math.Min(batchSize, size);
    for (int i = 0; i < end; i++)
    {
        result[i] = value;
    }

    int numBatches = size / batchSize;

    Parallel.For(1, numBatches, batch =>
    {
        Array.Copy(result, 0, result, batch * batchSize, batchSize);
    });

    //handle partial leftover batch
    for (int i = numBatches * batchSize; i < size; i++)
    {
        result[i] = value;
    }

    return result;
}

+1。好的建议。你有机会比较一下仅使用复制(不使用并行)的改进效果吗? - Alexei Levenkov
@AlexeiLevenkov 进行了几个简单的测试后,结果非常接近。这需要进行良好的调整才能从中获得更多的好处(例如,您需要拥有恰到好处的批量大小)。 - Servy

1
另一种提高性能的方法是使用一种相当基本的技术:循环展开。
我编写了一些代码来初始化一个包含2000万个项目的数组,这样做重复100次,并计算平均值。如果不展开循环,则需要大约44毫秒才能完成此过程。使用10次循环展开后,该过程在23毫秒内完成。
 private void Looper()
        {
            int repeats = 100;
            float avg = 0;

            ArrayList times = new ArrayList();

            for (int i = 0; i < repeats; i++)
                times.Add(Time()); 

            Console.WriteLine(GetAverage(times)); //44

            times.Clear();

            for (int i = 0; i < repeats; i++)            
                times.Add(TimeUnrolled()); 

            Console.WriteLine(GetAverage(times)); //22

        }

 private float GetAverage(ArrayList times)
        {
            long total = 0;
            foreach (var item in times)
            {
                total += (long)item;
            }

            return total / times.Count;
        }

        private long Time()
        {
            Stopwatch sw = new Stopwatch();
            int size = 20000000;
            int[] result = new int[size];
            sw.Start();


            for (int i = 0; i < size; i++)
            {
                result[i] = 5;
            }
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
            return sw.ElapsedMilliseconds;
        }

        private long TimeUnrolled()
        {
            Stopwatch sw = new Stopwatch();
            int size = 20000000;
            int[] result = new int[size];
            sw.Start();


            for (int i = 0; i < size; i += 10)
            {
                result[i] = 5;
                result[i + 1] = 5;
                result[i + 2] = 5;
                result[i + 3] = 5;
                result[i + 4] = 5;
                result[i + 5] = 5;
                result[i + 6] = 5;
                result[i + 7] = 5;
                result[i + 8] = 5;
                result[i + 9] = 5;
            }
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
            return sw.ElapsedMilliseconds;
        }

虽然代码不是最好的,但它能够说明我的观点。总体来说,这是一个50%的改进,如果你只做一次可能不会有太大的影响,但是多次累加起来就会很明显了。 - Mataniko

0
Enumerable.Repeat(value, size).ToArray();

0

阅读 Enumerable.Repeat 比 ops 标准循环慢 20 倍,我发现唯一可能提高其速度的方法是

private static int[] GetDefaultSeriesArray(int size, int value)
{
    int[] result = new int[size];
    for (int i = 0; i < size; ++i)
    {
        result[i] = value;
    }
    return result;
}

注意,i++ 被改为 ++i。i++ 复制 i,增加 i,并返回原始值。++i 只返回增加后的值。


-2

正如其他人已经提到的,您可以像这样利用并行处理:

int[] result = new int[size];
Parallel.ForEach(result, x => x = value);
return result;

抱歉,我没有时间在这个机器上进行性能测试(没有安装VS),但如果您可以进行测试并分享结果,那就太好了。

编辑:根据评论,虽然我仍然认为它们在性能方面是等效的,但您可以尝试使用并行for循环:

Parallel.For(0, size, i => result[i] = value);

这不是并行化的有效方式。你几乎可以肯定会更糟,因为你会失去内存局部性,而且工作单元太小了。如果你使用了Parallel.For,至少它会有更好的机会。 - Servy
@编辑:您可以很容易地测试性能,这样您就不必猜测了。 - Sam Axe
1
我刚刚对这两个进行了一些简单的测试,平行版本花费的时间大约是普通版本的5倍,这也是我预期的。 - Servy

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接