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

Reply via email to