D idom for removing array elements

[cym13 via Digitalmars-d-learn]

On Friday, 27 January 2017 at 08:30:41 UTC, Dukc wrote:
> On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:
>> My method is much better for large arrays I tested here.
>
> Trough, considering the size of the arrays the performance 
> difference should be even greater, like 1000X better instead of 
> 15X better so it's definitely not that great.

Note that if the set of values to be excluded isn't smaller than 
the haystack then using partition is way faster and your method 
is the slowest of all. If the order of the array matters stable 
partition can be used but is slower than the original method.

Added test cases and benchmark results:


     void partitionMethod() {
         auto c = a.partition!(v => b.canFind(v));
         // Sort to recover the order
         assert(sort(c[0..4]).array == [1, 2, 5, 7]);
     }

     void stablePartitionMethod() {
         auto c = a.partition!(v => b.canFind(v), 
SwapStrategy.stable);
         assert(c[0..4] == [1, 2, 5, 7]);
     }

     benchmark!(originalMethod,
                WilsonMethod,
                myMethod,
                partitionMethod,
                stablePartitionMethod)(1)
     .each!writeln;


With "a" of length 4000 and "b" of length 4000:

/*
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(4000).array;
int[] b = [3, 4, 6].cycle.take(4000).array;
*/

TickDuration(51482830)
TickDuration(43634792)
TickDuration(1085159)  // myMethod is faster
TickDuration(44216820) // 3rd
TickDuration(42920567) // 2nd

With "a" of length 400000 and "b" of length 3:

/*
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(400000).array;
int[] b = [3, 4, 6];
*/

TickDuration(312038) // 2nd
TickDuration(541912)
TickDuration(606883)
TickDuration(190662) // partitionMethod is way faster
TickDuration(418751) // 3rd