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.
In C you'd need to write (or get a library of) replacement functions for all the strxxx() functions. What the "rope" would do to prepend a string to another string is simply insert a new begin,end pair pointing at the new piece of string. It might also have to copy the new piece of string, if it's a temporary pointer.
How to append one string to the end of another. In C, the strcat() function is used to concatenate two strings. It concatenates one string (the source) to the end of another string (the destination). The pointer of the source string is appended to the end of the destination string, thus concatenating both strings.
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 answer should do just fine.
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 LinkedList
can 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.
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.
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 i
to Count-i
, etc. so that it appears, from the outside, as though your data is stored normally, even though the internal List
actually holds the data backwards.
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:
We have 3 options:
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.
My conclusion: arrays are more efficient then Lists (although they provide less functionality), and somehow Array.Copy
is really optmized (would like to understand that, though).
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With