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