c# - Prepend to a C# Array

Question

Given a populated byte[] values in C#, I want to prepend the value (byte)0x00 to the array. I assume this will require making a new array and adding the contents of the old array. Speed is an important aspect of my application. What is the best way to do this?

-- EDIT --

The byte[] is used to store DSA (Digital Signature Algorithm) parameters. The operation will only need to be performed once per array, but speed is important because I am potentially performing this operation on many different byte[]s.

score 47 · Accepted Answer

如果您只打算执行此操作一次，那么没有很多选择。Monroe's answer提供的代码应该没问题。

byte[] newValues = new byte[values.Length + 1];
newValues[0] = 0x00;                                // set the prepended value
Array.Copy(values, 0, newValues, 1, values.Length); // copy the old values

但是，如果您要多次执行此操作，您就有更多选择。有一个基本问题是，将数据添加到数组不是一种有效的操作，因此您可以选择使用替代数据结构。

ALinkedList可以有效地预置数据，但对于大多数任务来说，它的效率通常较低，因为它涉及更多的内存分配/释放，并且还失去了内存局部性，因此它可能不是一个净赢。

双端队列（称为双端队列）对您来说将是一个很棒的数据结构。您可以有效地添加到开头或结尾，并有效地访问结构中任何位置的数据（但您不能有效地插入除开头或结尾之外的其他位置）。这里的主要问题是.NET 没有提供双端队列的实现。您需要找到一个带有实现的 3rd 方库。

您还可以通过跟踪“我需要预先添加的数据”（使用列表/队列/等）然后尽可能长时间地等待实际预先添加数据来在复制时节省很多，这样您就可以最大限度地减少创建尽可能多的新数组，以及限制现有元素的副本数量。

您还可以考虑是否可以调整结构，以便添加到结尾而不是开头（即使您知道以后需要反转它）。如果您在短时间内追加很多内容，则可能值得将数据存储在 a 中List（可以有效地添加到末尾）并添加到末尾。根据您的需要，甚至可能值得创建一个作为 List 包装器的类，并隐藏它被反转的事实。您可以制作一个映射i到Count-i等的索引器，以便它从外部显示，就好像您的数据正常存储一样，即使内部List实际上是向后保存数据。

score 20 · Accepted Answer

好的，让我们来看看关于这个问题的性能问题。这不是一个答案，只是一个微基准，看看哪个选项更有效。

所以，让我们设置场景：

包含 1,000,000 个项目的字节数组，随机填充
我们需要添加项目 0x00

我们有 3 个选项：

手动创建和填充新数组
手动创建新数组并使用 Array.Copy (@Monroe)
创建列表、加载数组、插入项目并将列表转换为数组

这是代码：

    byte[] byteArray = new byte[1000000];

    for (int i = 0; i < byteArray.Length; i++)
    {
        byteArray[i] = Convert.ToByte(DateTime.Now.Second);
    }

    Stopwatch stopWatch = new Stopwatch();

    //#1 Manually creating and populating a new array;

    stopWatch.Start();

    byte[] extendedByteArray1 = new byte[byteArray.Length + 1];

    extendedByteArray1[0] = 0x00;

    for (int i = 0; i < byteArray.Length; i++)
    {
        extendedByteArray1[i + 1] = byteArray[i];
    }

    stopWatch.Stop();
    Console.WriteLine(string.Format("#1: {0} ms", stopWatch.ElapsedMilliseconds));
    stopWatch.Reset();

    //#2 Using a new array and Array.Copy

    stopWatch.Start();

    byte[] extendedByteArray2 = new byte[byteArray.Length + 1];
    extendedByteArray2[0] = 0x00;                                
    Array.Copy(byteArray, 0, extendedByteArray2, 1, byteArray.Length);

    stopWatch.Stop();
    Console.WriteLine(string.Format("#2: {0} ms", stopWatch.ElapsedMilliseconds));
    stopWatch.Reset();

    //#3 Using a List

    stopWatch.Start();

    List<byte> byteList = new List<byte>();
    byteList.AddRange(byteArray);
    byteList.Insert(0, 0x00);

    byte[] extendedByteArray3 = byteList.ToArray();

    stopWatch.Stop();
    Console.WriteLine(string.Format("#3: {0} ms", stopWatch.ElapsedMilliseconds));
    stopWatch.Reset();

    Console.ReadLine();

结果是：

#1: 9 ms
#2: 1 ms
#3: 6 ms

我已经运行了多次，得到的数字不同，但比例始终相同：#2 始终是最有效的选择。

我的结论：数组比列表更有效（尽管它们提供的功能较少），并且以某种方式Array.Copy真正优化了（尽管想理解这一点）。

任何反馈将不胜感激。

此致。

PS：这不是一个剑术帖子，我们在一个问答网站学习和教学。并学习。

score 15 · Accepted Answer

正如您所推测的，最快的方法是创建长度为 + 1 的新数组并复制所有旧值。

如果您要多次这样做，那么我建议使用 aList<byte>而不是byte[]，因为在增加底层存储时重新分配和复制的成本可以更有效地摊销；在通常情况下，List每次对List超过其当前容量的添加或插入进行添加或插入时，中的基础向量都会增长两倍。

...

byte[] newValues = new byte[values.Length + 1];
newValues[0] = 0x00;                                // set the prepended value
Array.Copy(values, 0, newValues, 1, values.Length); // copy the old values

score 9 · Accepted Answer

.NET 4.7.1 及更高版本最简单、最干净的方法是使用无副作用的Prepend().

在序列的开头添加一个值。

例子

// Creating an array of numbers
var numbers = new[] { 1, 2, 3 };

// Trying to prepend any value of the same type
var results = numbers.Prepend(0);

// output is 0, 1, 2, 3
Console.WriteLine(string.Join(", ", results ));

score 3 · Accepted Answer

当我需要频繁地追加数据但又希望 O(1) 随机访问单个元素时，我将使用一个由一些填充量过度分配的数组来快速添加新值。这意味着您需要将实际内容长度存储在另一个变量中，因为 array.length 将指示长度 + 填充。通过使用填充的一个插槽附加一个新值，在您用完填充之前不需要分配和复制。实际上，分配是通过几个附加操作摊销的。存在速度空间权衡，就好像你有许多这样的数据结构，你可以在程序中的任何时候使用相当数量的填充。

同样的技术可以用于前置。就像附加一样，你可以在用户和实现之间引入一个接口或抽象：你可以有几个填充槽，这样新的内存分配只是偶尔需要。正如上面的一些建议，您还可以使用反转索引的附加数据结构实现一个前置接口。

我将数据结构打包为一些通用集合接口的实现，以便该接口对用户来说显得相当正常（例如数组列表或其他东西）。

（此外，如果支持删除，则在删除元素后立即清除它们可能很有用，以帮助减少 gc 负载。）

要点是分别考虑实现和接口，因为将它们解耦使您可以灵活地选择不同的实现或使用最小接口隐藏实现细节。

根据您的域的适用性，您可以使用许多其他数据结构。绳索或间隙缓冲器；请参阅适合实现记事本等编辑器的最佳数据结构是什么？; Trie 也做了一些有用的事情。

score 3 · Accepted Answer

我知道这是一个非常古老的帖子，但我实际上喜欢使用 lambda。当然，我的代码可能不是最有效的方式，但它的可读性和一行。我使用 .Concat 和 ArraySegment 的组合。

 string[] originalStringArray = new string[] { "1", "2", "3", "5", "6" };
 int firstElementZero = 0;
 int insertAtPositionZeroBased = 3;
 string stringToPrepend = "0";
 string stringToInsert = "FOUR"; // Deliberate !!!

 originalStringArray = new string[] { stringToPrepend }
            .Concat(originalStringArray).ToArray();

 insertAtPositionZeroBased += 1; // BECAUSE we prepended !!
 originalStringArray = new ArraySegment<string>(originalStringArray, firstElementZero, insertAtPositionZeroBased)       
                .Concat(new string[] { stringToInsert })
                .Concat(new ArraySegment<string>(originalStringArray, insertAtPositionZeroBased, originalStringArray.Length - insertAtPositionZeroBased)).ToArray();

score 2 · Accepted Answer

最佳选择取决于您以后将如何处理此系列。如果这是唯一可以更改长度的编辑，那么最好的办法是创建一个带有一个额外插槽的新数组，然后Array.Copy()用来完成其余的工作。无需初始化第一个值，因为新的 C# 数组总是清零：

byte[] PrependWithZero(byte[] input)
{
    var newArray = new byte[input.Length + 1];
    Array.Copy(input, 0, newArray, 1, input.Length);
    return newArray;
}

如果可能会发生其他长度变化的编辑，那么性能最高的选项可能是一直使用 a List<byte>，只要添加的内容并不总是从头开始。（如果是这种情况，即使是链接列表也可能不是您可以立即忽略的选项。）：

var list = new List<byte>(input);
list.Insert(0, 0);

score 0 · Accepted Answer

我知道这是超过 4 年的接受帖子，但对于那些可能与Buffer.BlockCopy相关的人来说会更快。

c# - Prepend to a C# Array

8 回答 8

Related

Reference