前置到C#数组

Question

给定byte[] valuesC#中的填充,我想将值添加(byte)0x00到数组之前.我假设这将需要创建一个新数组并添加旧数组的内容.速度是我的应用程序的一个重要方面.做这个的最好方式是什么？

- 编辑 -

所述byte[]用于存储DSA(数字签名算法)的参数.每个阵列只需执行一次操作,但速度很重要,因为我可能在许多不同的byte[]s 上执行此操作.

Answer 1

如果您只打算执行此操作,那么就没有很多选择.门罗答案提供的代码应该没问题.

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

但是,如果您要多次执行此操作,则可以选择更多选项.存在一个基本问题,即将数据添加到数组不是一种有效的操作,因此您可以选择使用备用数据结构.

A LinkedList可以有效地预先添加数据,但是对于大多数任务来说它通常效率较低,因为它涉及更多的内存分配/释放并且还会丢失内存的本地性,因此它可能不是一个净赢.

双端队列(称为双端队列)对您来说是一个很棒的数据结构.您可以有效地添加到开头或结尾,并有效地访问结构中的任何位置(但您无法有效地插入除开头或结尾之外的某个位置).这里的主要问题是.NET不提供deque的实现.您需要找到带有实现的第三方库.

您还可以通过跟踪"我需要预先添加的数据"(使用List/Queue /等)然后等待尽可能长时间地实际预先添加数据来为复制时节省很多时间,以便最大限度地减少创建尽可能多地使用新数组,以及限制现有元素的副本数量.

您还可以考虑是否可以调整结构,以便添加到结尾,而不是开始(即使您知道以后需要将其反转).如果你在很短的时间内追加很多东西,可能值得将数据存储在一个List(可以有效地添加到最后)并添加到最后.根据您的需要,甚至可能值得创建一个类,它是List的包装器,并且隐藏了它被颠倒的事实.您可以从外部创建一个映射i到Count-i等等的索引器,就好像您的数据正常存储一样,即使内部List实际上向后保存数据也是如此.

Answer 2

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

那么,让我们设置场景:

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

我们有3个选择:

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

这是代码:

    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:这不是一个剑术,我们在Q&A网站上学习和教学.并学习.

Answer 3

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

如果您要多次这样做,那么我建议使用a List<byte>而不是byte[],因为重新分配和复制的成本,同时增长底层存储更有效地摊销; 在通常情况下,List每次添加或插入List超过其当前容量时,其中的基础矢量增长2倍.

...

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

Answer 4

对于 .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 ));