前置到 C# 数组

Prepend to a C# Array

提问by cytinus

Given a populated byte[] valuesin C#, I want to prepend the value (byte)0x00to 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?

鉴于byte[] values在 C# 中填充，我想将值添加(byte)0x00到数组中。我认为这需要创建一个新数组并添加旧数组的内容。速度是我的应用程序的一个重要方面。做这个的最好方式是什么？

-- 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.

所述byte[]用于存储DSA（数字签名算法）的参数。每个数组只需要执行一次该操作，但速度很重要，因为我可能会在许多不同的byte[]s上执行此操作。

采纳答案by Servy

If you are only going to perform this operation once then there isn't a whole lot of choices. The code provided by Monroe's answershould do just fine.

如果您只打算执行一次此操作，则没有太多选择。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

If, however, you're going to be performing this operation multiple times you have some more choices. There is a fundamental problem that prepending data to an array isn't an efficient operation, so you could choose to use an alternate data structure.

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

A LinkedListcan efficiently prepend data, but it's less efficient in general for most tasks as it involves a lot more memory allocation/deallocation and also looses memory locallity, so it may not be a net win.

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

A double ended queue (known as a deque) would be a fantastic data structure for you. You can efficiently add to the start or the end, and efficiently access data anywhere in the structure (but you can't efficiently insert somewhere other than the start or end). The major problem here is that .NET doesn't provide an implementation of a deque. You'd need to find a 3rd party library with an implementation.

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

You can also save yourself a lot when copying by keeping track of "data that I need to prepend" (using a List/Queue/etc.) and then waiting to actually prepend the data as long as possible, so that you minimize the creation of new arrays as much as possible, as well as limiting the number of copies of existing elements.

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

You could also consider whether you could adjust the structure so that you're adding to the end, rather than the start (even if you know that you'll need to reverse it later). If you are appending a lot in a short space of time it may be worth storing the data in a List(which can efficiently add to the end) and adding to the end. Depending on your needs, it may even be worth making a class that is a wrapper for a List and that hides the fact that it is reversed. You could make an indexer that maps ito Count-i, etc. so that it appears, from the outside, as though your data is stored normally, even though the internal Listactually holds the data backwards.

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

回答by Monroe Thomas

As you surmised, the fastest way to do this is to create new array of length + 1 and copy all the old values over.

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

If you are going to be doing this many times, then I suggest using a List<byte>instead of byte[], as the cost of reallocating and copying while growing the underlying storage is amortized more effectively; in the usual case, the underlying vector in the Listis grown by a factor of two each time an addition or insertion is made to the Listthat would exceed its current capacity.

如果您打算多次这样做，那么我建议使用 aList<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

回答by Sean U

The best choice depends on what you're going to be doing with this collection later on down the line. If that's the only length-changing edit that will ever be made, then your best bet is to create a new array with one additional slot and use Array.Copy()to do the rest. No need to initialize the first value, since new C# arrays are always zeroed out:

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

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

If there are going to be other length-changing edits that might happen, the most performant option might be to use a List<byte>all along, as long as the additions aren't always to the beginning. (If that's the case, even a linked list might not be an option that you can dismiss out of hand.):

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

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

回答by Andre Calil

Ok guys, let's take a look at the perfomance issue regarding this question. This is not an answer, just a microbenchmark to see which option is more efficient.

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

So, let's set the scenario:

所以，让我们设置场景：

• A byte array of 1,000,000 items, randomly populated
• We need to prepend item 0x00

• 一个包含 1,000,000 个项目的字节数组，随机填充
• 我们需要在项目 0x00 前面加上

We have 3 options:

我们有3个选择：

1. Manually creating and populating the new array
2. Manually creating the new array and using Array.Copy (@Monroe)
3. Creating a list, loading the array, inserting the item and converting the list to an array

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

Here's the code:

这是代码：

    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();

And the results are:

结果是：

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

I've run it multiple times and I got different numbers, but the proportion is always the same: #2 is always the most efficient choice.

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

Myconclusion: arrays are more efficient then Lists (although they provide less functionality), and somehow Array.Copyis really optmized (would like to understand that, though).

我的结论是：数组比列表更有效（尽管它们提供的功能较少），并且在某种程度上Array.Copy确实是经过优化的（不过我想了解一下）。

Any feedback will be appreciated.

任何反馈将不胜感激。

Best regards.

此致。

PS: this is not a swordfight post, we are at a Q&A site to learn and teach. And learn.

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

回答by Erik Eidt

When I need to append data frequently but also want O(1) random access to individual elements, I'll use an array that is over allocated by some amount of padding for quickly adding new values. This means you need to store the actual content length in another variable, as the array.length will indicate the length + the padding. A new value gets appended by using one slot of the padding, no allocation & copy are necessary until you run out of padding. In effect, allocation is amortized over several append operations. There are speed space trade offs, as if you have many of these data structures you could have a fair amount of padding in use at any one time in the program.

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

This same technique can be used in prepending. Just as with appending, you can introduce an interface or abstraction between the users and the implementation: you can have several slots of padding so that new memory allocation is only necessary occasionally. As some above suggested, you can also implement a prepending interface with an appending data structure that reverses the indexes.

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

I'd package the data structure as an implementation of some generic collection interface, so that the interface appears fairly normal to the user (such as an array list or something).

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

(Also, if removal is supported, it's probably useful to clear elements as soon as they are removed to help reduce gc load.)

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

The main point is to consider the implementation and the interface separately, as decoupling them gives you the flexibility to choose varied implementations or to hide implementation details using a minimal interface.

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

There are many other data structures you could use depending on the applicability to your domain. Ropes or Gap Buffer; see What is best data structure suitable to implement editor like notepad?; Trie's do some useful things, too.

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

回答by Margus

I am aware this is over 4-year-old accepted post, but for those who this might be relevant Buffer.BlockCopywould be faster.

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

回答by Desmond Cassidy

I know this is a VERY old post but I actually like using lambda. Sure my code may NOT be the most efficient way but its readable and in one line. I use a combination of .Concat and ArraySegment.

我知道这是一篇很老的帖子，但我实际上喜欢使用 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();

回答by aloisdg moving to codidact.com

The easiest and cleanest way for .NET 4.7.1 and newer is to use the side-effect free Prepend().

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

Adds a value to the beginning of the sequence.

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

Example

例子

// 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 ));