4
\$\begingroup\$

I wrote a method that takes an array T[] array (T is a type parameter) and a second array int[] indices. The method should remove those entries from array, whose indices are stored in indices. Then, the resulting array will be "returned" as an out-parameter T[] rest. Finally, there is a second out parameter T[] removed that contains the removed items.

public static void RemoveViaIndex<T>(this T[] array, int[] indices, out T[] rest, out T[] removed)
{
    int arrayLength = array.Length;
    int indicesLength = indices.Length;

    if (indicesLength == 0 || arrayLength == 0)
    {
        rest = array;
        removed = new T[0];
        return;
    }

    rest = new T[arrayLength - indicesLength];
    removed = new T[indicesLength];

    int copyBegin = 0;
    int copyEnd = -1;

    // We will only iterate over the index-array once
    // Therefore, the indices have to be in ascending order
    Array.Sort(indices);

    for (int indexForIndices = 0; indexForIndices < indicesLength; indexForIndices++)
    {
        // Copying elements in a chunk that ends at the 
        // next index that has to be removed
        copyEnd = indices[indexForIndices];
        Array.Copy(sourceArray: array, sourceIndex: copyBegin,
            destinationArray: rest, destinationIndex: copyBegin - indexForIndices, 
            length: copyEnd - copyBegin);
        removed[indexForIndices] = array[copyEnd];
        copyBegin = copyEnd + 1;
    }

    if (copyEnd < arrayLength - 1)
    {
        // Copy the final chunk that the loop did not take (if there is one)
        Array.Copy(array, copyBegin, rest, copyEnd - indicesLength + 1, arrayLength - copyBegin);
    }
}

I am assuming that all the indices in same-named array are valid indices for array. Are there any further border cases that I did not cover?

Furthermore, I wonder if this way is faster than an if statement that is contained within a for loop that iterates over the source array since the if-currentIndex-in-indices-then-remove branch disappears:

for (*every index in source*)
{
    if (*current-index-in-indices-to-remove*)
    {
        *remove-and-put-to-target-array*
    }
}
\$\endgroup\$
2
\$\begingroup\$

You can make you method really short if you use a HashSet<int> for the indicies.

The only thing you need to do is to loop over the array and check if the hash-set contains the current i. If yes, you add the array's value to removed and otherwise to the rest. For both arrays (rest and removed) you use two additional indexes to know where to put the elements.

As far as the code itself is concerned I think it looks good. Clear names, clean code. Just fine.

public static void RemoveViaIndex2<T>(this T[] array, HashSet<int> indices, out T[] rest, out T[] removed)
{
    if (array.Length == 0 || indices.Count == 0)
    {
        rest = array;
        removed = new T[0];
        return;
    }

    rest = new T[array.Length - indices.Count];
    removed = new T[indices.Count];

    for (int i = 0, restIndex = 0, removedIndex = 0; i < array.Length; i++)
    {
        if (indices.Contains(i))
        {
            removed[removedIndex++] = array[i];
        }
        else
        {
            rest[restIndex++] = array[i];
        }
    }
}

EDIT-1

I didn't measure it but I'm pretty sure it will be much faster than all the sorting and copying.

I did measure it at your implementation needs only 4ms whereas mine 40ms :O

Test code:

// create some random test data
var elementCount = 1000000;
var arr = Enumerable.Range(0, elementCount).ToArray();

var indexCount = 10000;
var rnd = new Random(DateTime.Now.Millisecond);
var indicies = new HashSet<int>(Enumerable.Range(0, indexCount).Select(x => rnd.Next(elementCount))).ToArray();

var sw1 = new Stopwatch();
sw1.Start();
int[] rest;
int[] removed;
arr.RemoveViaIndex(indicies, out rest, out removed);
sw1.Stop();

// just a helper variable for a Q&D test
var indiciesHashSet = new HashSet<int>(indicies);
var sw2 = new Stopwatch();
sw2.Start();
int[] rest2;
int[] removed2;
arr.RemoveViaIndex2(indicies, out rest2, out removed2, indiciesHashSet);
sw2.Stop();

Console.WriteLine("Original: {0} ms", sw1.ElapsedMilliseconds);
Console.WriteLine("      My: {0} ms", sw2.ElapsedMilliseconds);

And the R# Profiler results to answer your question about which version would be faster:

enter image description here enter image description here

The if-contains is a real bottleneck here.

@ziddarth's ZRemoveIndex

enter image description here

All three outside of Visual Studio context which made the third test inaccurate:

enter image description here


EDIT-2

Measuring performance isn't as easy as I thought and it's not enough to simply measure a method execution time with the Stopwatch. I run a few more tests and came to the same conclusion as @HerpDerpington. All the tests were very unreliable and I got different results each time I run the tests.

I modified them so I call the garbage collector before each measurement with GD.Collect();. After implementing this the last tested method wasn't the slowest one anymore and running the same test several times in a row didn't result in alternating fast/slow times.

I also increased the number of runs for each method so now each one is tested a few times and the average time is then calculated as advised by this answer on Stack Overlow.

The last thing I added to the test is a warm-up where I just run all tests without considering their results.

This is the final code that I came up with:

var elementCount = 100000000;
var arr = Enumerable.Range(0, elementCount).ToArray();

var indexCount = 1000000;
var rnd = new Random(DateTime.Now.Millisecond);
var indicies = new HashSet<int>(Enumerable.Range(0, indexCount).Select(x => rnd.Next(elementCount))).ToArray();

// warm-up
Test1(arr, indicies);
Test2(arr, indicies);
Test3(arr, indicies);

var testCount = 10;

var test1Avg = Enumerable.Repeat(0, testCount).Select(x => Test1(arr, indicies).ElapsedMilliseconds).Average();
var test2Avg = Enumerable.Repeat(0, testCount).Select(x => Test2(arr, indicies).ElapsedMilliseconds).Average();
var test3Avg = Enumerable.Repeat(0, testCount).Select(x => Test3(arr, indicies).ElapsedMilliseconds).Average();

Console.WriteLine("@HerpDerpington: avg {0} ms", test1Avg);
Console.WriteLine("@ziddarth: avg {0} ms", test2Avg);
Console.WriteLine("@t3chb0t (mixed): avg {0} ms", test3Avg);

Console.ReadKey();

Measureing method:

public static Stopwatch Measure(Action measureAction, Action<Stopwatch> resultAction = null)
{
    GC.Collect();
    var stopwatch = new Stopwatch();
    stopwatch.Start();
    measureAction();
    stopwatch.Stop();
    resultAction?.Invoke(stopwatch);
    return stopwatch;
}

The OP's implementation wins all tests.

\$\endgroup\$
4
  • \$\begingroup\$ Oh, the uploaded images seem to be scaled. They aren't so weird diffrent sized. \$\endgroup\$ – t3chb0t Sep 17 '15 at 20:26
  • \$\begingroup\$ Next time I'll first measure something and then I write. I didn't expect it to be that fast. This was a good exercise and a good lesson. \$\endgroup\$ – t3chb0t Sep 17 '15 at 20:30
  • \$\begingroup\$ Yeah, but I surely did not expect that it would make such a big difference... \$\endgroup\$ – HerpDerpington Sep 17 '15 at 20:38
  • 1
    \$\begingroup\$ @HerpDerpington I edited my answer (EDIT-2) and added a new test code that seems to be quite reliable now. \$\endgroup\$ – t3chb0t Sep 18 '15 at 10:44
3
\$\begingroup\$

So far my tests indicate that the performance is slightly better in the larger test cases because there is no hashing involved when accessing elements in deleteStatusArray. There are also no array copy operations.

public static void ZRemoveIndex<T>(this T[] array, int[] indices, out T[] rest, out T[] removed)
{
    int arrayLength = array.Length;
    int indicesLength = indices.Length;

    if (indicesLength == 0 || arrayLength == 0)
    {
        rest = array;
        removed = new T[0];
        return;
    }

    rest = new T[arrayLength - indicesLength];
    removed = new T[indicesLength];
    //memo to remember which array indices are removed
    //all elements will be false by default
    var deleteStatusArray = new bool[array.Length];

    foreach (var removeIndex in indices)
    {
        //mark index that should be considered deleted
        deleteStatusArray[removeIndex] = true;
    }

    var notRemovedCounter = 0;
    var removedCounter = 0;
    for (int i = 0; i < array.Length; i++)
    {
        if(!deleteStatusArray[i])
            rest[notRemovedCounter++]= array[i];
        else
            removed[removedCounter++] = array[i];
    }
}
\$\endgroup\$
10
  • \$\begingroup\$ I tested your method and it's two times slower then the original :-) it needed 8ms. But still way faster then the hashset. \$\endgroup\$ – t3chb0t Sep 18 '15 at 5:00
  • \$\begingroup\$ Ok, wait... I did another test and it's even 1ms better then the original. There was some overhead when testing inside Visual Studio. \$\endgroup\$ – t3chb0t Sep 18 '15 at 5:05
  • \$\begingroup\$ Try using an even bigger array. I tried it and at some point it flips around; this one gets slower that the original method... \$\endgroup\$ – HerpDerpington Sep 18 '15 at 7:59
  • \$\begingroup\$ @HerpDerpington I just tested the two fastest methods with an array of 100.000.000 items and this is true only if you run it inside Visual Studio (even as release). If you run the exe alone ziddrath's method is 100ms faster then the original one. \$\endgroup\$ – t3chb0t Sep 18 '15 at 8:14
  • 1
    \$\begingroup\$ @t3chb0t I just noticed that, too :D \$\endgroup\$ – HerpDerpington Sep 18 '15 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.