Replace the given value in the array with values ​​from the second array in C #

Question

I have an ints array that has several negative values ​​in:

var arrayExisting = new int[]{1,2,-1,3,5,-1,0,0,-1}; 

And another array with the corresponding set of values ​​that I want to insert into the first array:

 var replacements = new int[]{7,6,5}; 

Is there any really effective way to do this?

I currently have:

 var newArray = arrayExisting.Select(val => { if (val != -1) return val; var ret = replacements[i]; i++; return ret; }).ToArray(); 

This is pretty fast. The arrays in question are only about 15 integers, and this can increase, but it is unlikely to exceed 100. The problem is that I have to do this more than a quarter of a million times for my moderate test system, and a realistic system I'm considering involve about 10e10 iterations of this code!

Answer 1

Using the comment on the original question from @TVOHM, I implemented the following code

 public static int[] ReplaceUsingLinq(IEnumerable<int> arrayFromExisting, IEnumerable<int> x) { var indices = x.ToArray(); var i = 0; var newArray = arrayFromExisting.Select(val => { if (val != -1) return val; var ret = indices[i]; i++; return ret; }).ToArray(); return newArray; } public static int[] ReplceUsingForLoop(int[] arrayExisting, IEnumerable<int> x) { var arrayReplacements = x.ToArray(); var replaced = new int[arrayExisting.Length]; var replacementIndex = 0; for (var i = 0; i < arrayExisting.Length; i++) { if (arrayExisting[i] < 0) { replaced[i] = arrayReplacements[replacementIndex++]; } else { replaced[i] = arrayExisting[i]; } } return replaced; } public static unsafe int[] ReplaceUsingPointers(int[] arrayExisting, IEnumerable<int> reps) { var arrayReplacements = reps.ToArray(); int replacementsLength = arrayReplacements.Length; var replaced = new int[arrayExisting.Length]; Array.Copy(arrayExisting, replaced, arrayExisting.Length); int existingLength = replaced.Length; fixed (int* existing = replaced, replacements = arrayReplacements) { int* exist = existing; int* replace = replacements; int i = 0; int x = 0; while (i < replacementsLength && x < existingLength) { if (*exist == -1) { *exist = *replace; i++; replace++; } exist++; x++; } } return replaced; } public static int[] ReplaceUsingLoopWithMissingArray(int[] arrayExisting, IEnumerable<int> x, int[] missingIndices) { var arrayReplacements = x.ToArray(); var replaced = new int[arrayExisting.Length]; Array.Copy(arrayExisting, replaced, arrayExisting.Length); var replacementIndex = 0; foreach (var index in missingIndices) { replaced[index] = arrayReplacements[replacementIndex]; replacementIndex++; } return replaced; } 

and compared this with the following code:

 public void BenchmarkArrayItemReplacements() { var rand = new Random(); var arrayExisting = Enumerable.Repeat(2, 1000).ToArray(); var arrayReplacements = Enumerable.Repeat(1, 100); var toReplace = Enumerable.Range(0, 100).Select(x => rand.Next(100)).ToList(); toReplace.ForEach(x => arrayExisting[x] = -1); var misisngIndices = toReplace.ToArray(); var sw = Stopwatch.StartNew(); var result = ArrayReplacement.ReplceUsingForLoop(arrayExisting, arrayReplacements); Console.WriteLine($"for loop took {sw.ElapsedTicks}"); sw.Restart(); result = ArrayReplacement.ReplaceUsingLinq(arrayExisting, arrayReplacements); Console.WriteLine($"linq took {sw.ElapsedTicks}"); sw.Restart(); result = ArrayReplacement.ReplaceUsingLoopWithMissingArray(arrayExisting, arrayReplacements, misisngIndices); Console.WriteLine($"with missing took {sw.ElapsedTicks}"); sw.Restart(); result = ArrayReplacement.ReplaceUsingPointers(arrayExisting, arrayReplacements); Console.WriteLine($"Pointers took {sw.ElapsedTicks}"); } 

This gives the results:

 for loop took 848 linq took 2879 with missing took 584 Pointers took 722 

So this means that knowing where we have no values ​​(where -1 s) is the key to fast.

by the way, if I loop every call to the corresponding method 10,000 times and check the time I get:

 for loop took 190988 linq took 489052 with missing took 69198 Pointers took 159102 

here the effect is even greater

Answer 2

I would use a for loop and replace the values ​​in the original array in place.

 int replacementIndex = 0; for (var i = 0; i < arrayExisting.Length; i++) { if (arrayExisting[i] < 0) { arrayExisting[i] = replacements[replacementIndex++]; } } 

This way you avoid overhead by creating a new array. If you need to create a new array, you can create new int[arrayExisting.Length]

Running a quick test seems that the for ~ ~ cycle is 4 times faster, even in the worst case, when you have to replace every time and you create a new array for storing notes.

 Select: 12672 For: 3386 

In this test, if you are interested.

 var loops = 1000000; var arrayExisting = Enumerable.Repeat(-1, 1000).ToArray(); var replacements = Enumerable.Repeat(1, 1000).ToArray(); var selectTimer = Stopwatch.StartNew(); for (var j = 0; j < loops; j++) { var i = 0; var newArray = arrayExisting.Select(val => { if (val != -1) return val; var ret = replacements[i]; i++; return ret; }).ToArray(); } selectTimer.Stop(); var forTimer = Stopwatch.StartNew(); for (var j = 0; j < loops; j++) { var replaced = new int[arrayExisting.Length]; int replacementIndex = 0; for (var i = 0; i < arrayExisting.Length; i++) { if (arrayExisting[i] < 0) { replaced[i] = replacements[replacementIndex++]; } else { replaced[i] = arrayExisting[i]; } } } forTimer.Stop(); Console.WriteLine("Select: " + selectTimer.ElapsedMilliseconds); Console.WriteLine("For: " + forTimer.ElapsedMilliseconds); 

Answer 3

Try to indicate pointers:

 int replacementsLength = arrayReplacements.Length; fixed (int* existing = arrayExisting, replacements = arrayReplacements) { int* exist = existing; int* replace = replacements; int i = 0; while (i < replacementsLength) { if (*exist == -1) { *exist = *replace; i++; replace++; } exist++; //edit: forgot to put exist++ outside the if block } } 

EDIT: this code only works if you are sure you have the same supply of substitutions and -1. To work on each script, use this code:

 int replacementsLength = arrayReplacements.Length; int existingLength = arrayExisting.Length; fixed (int* existing = copy, replacements = arrayReplacements) { int* exist = existing; int* replace = replacements; int i = 0; int x = 0; while (i < replacementsLength && x < existingLength) { if (*exist == -1) { *exist = *replace; i++; replace++; } exist++; x++; } } 

Performing the same test as Joey, do the following:

Select: 17378
For: 2172
Pointer: 1780
EDIT: My mistake, I forgot to repeat my code 1,000,000. Tho is even faster.

Here is the test code:

 private unsafe static void test() { var loops = 1000000; var arrayExisting = Enumerable.Repeat(-1, 1000).ToArray(); var arrayReplacements = Enumerable.Repeat(1, 1000).ToArray(); int[] newArray = null; var selectTimer = Stopwatch.StartNew(); for (var j = 0; j < loops; j++) { var i = 0; newArray = arrayExisting.Select(val => { if (val != -1) return val; var ret = arrayReplacements[i]; i++; return ret; }).ToArray(); } selectTimer.Stop(); printResult("linQ", newArray); arrayExisting = Enumerable.Repeat(-1, 1000).ToArray(); arrayReplacements = Enumerable.Repeat(1, 1000).ToArray(); int[] replaced = null; var forTimer = Stopwatch.StartNew(); for (var j = 0; j < loops; j++) { replaced = new int[arrayExisting.Length]; int replacementIndex = 0; for (var i = 0; i < arrayExisting.Length; i++) { if (arrayExisting[i] < 0) { replaced[i] = arrayReplacements[replacementIndex++]; } else { replaced[i] = arrayExisting[i]; } } } forTimer.Stop(); printResult("for", replaced); arrayExisting = Enumerable.Repeat(-1, 1000).ToArray(); arrayReplacements = Enumerable.Repeat(1, 1000).ToArray(); int[] copy = null; var pointerTimer = Stopwatch.StartNew(); //EDIT: fixed the test code for (int j = 0; j < loops; j++) { copy = new int[arrayExisting.Length]; Array.Copy(arrayExisting, copy, arrayExisting.Length); int replacementsLength = arrayReplacements.Length; int existingLength = arrayExisting.Length; fixed (int* existing = copy, replacements = arrayReplacements) { int* exist = existing; int* replace = replacements; int i = 0; int x = 0; while (i < replacementsLength && x < existingLength) { if (*exist == -1) { *exist = *replace; i++; replace++; } exist++; x++; } } } pointerTimer.Stop(); printResult("pointer", copy); File.AppendAllText(@"E:\dev\test.txt", "\r\n" + "Select: " + selectTimer.ElapsedMilliseconds + "\r\n" + "For: " + forTimer.ElapsedMilliseconds + "\r\n" + "Pointer: " + pointerTimer.ElapsedMilliseconds); }