Replace a given value in array with values from second array in C#

Question

I have an array of ints which has a number of negative values in:

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

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

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

Is there a truly efficient way of doing this?

What I have currently is:

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

It's fairly quick. The arrays in question are only about 15 integers in length, and this might go up, but unlikely to exceed 100. The problem is that I have to do this over a quarter of a million times for my moderate test system, and the realistic system I am considering will involve about 10e10 iterations of this code!

Can you build up a list of negative indexes as you create or populate the existing array initially? — TVOHM
– TVOHM, Commented Jan 14, 2016 at 17:54
Not to be picky but you say the array can have 'negative values' but your code snip-it is only checking for -1.. — pnm
– pnm, Commented Jan 14, 2016 at 17:55
Yes I can build the list of negative indices up front. I have posted another answer below with some benchmarking — MikeW
– MikeW, Commented Jan 15, 2016 at 13:02

Joey Ciechanowicz · Accepted Answer · 2016-01-14 17:55:59Z

I would use a for loop and replace values in your 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 the overhead creating a new array. If you need to create a new array you can create a new int[arrayExisting.Length]

Running a quick benchmark it seems that the for loop is ~4x faster, even in the worst case where you have to replace every single time and you construct a new array to hold the replacements.

Select: 12672
For: 3386

Here's the benchmark if you're intrested.

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

dcidral · Accepted Answer · 2016-01-15 12:03:41Z

Try with 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 to have the exact same ammount of replacements and -1 To work on every scenario 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++;
    }
}

Running the same test as Joey the results are:

Select: 17378
For: 2172
Pointer: 1780
EDIT: My mistake, I forgot to iterate my code 1000000. Still faster tho.

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

Can You provide full test code? According to my testing this unsafe code is only 35% faster than the for loop that does not create new array every time.
I realized my mistake, I forgot to loop the code 1000000 times, I'm going to change it and test again
Thank You. As a tip, You can make pointer like int* replaceEnd = replace + arrayReplacements.Length; and test against that replace < replaceEnd. You save the i iterator.

MikeW · Accepted Answer · 2016-01-15 13:16:11Z

Using a comment on the original question by @TVOHM, I have 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 benchmarked this using 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 it apperas that knowledge of where we have missing values (where the -1s are) is the key to it being fast.

incidentally if I loop each call to the relevant method 10000 times and check the times I get:

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

here the effect is even greater

Collectives™ on Stack Overflow

Replace a given value in array with values from second array in C#

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related