Re: D idom for removing array elements
On 01/30/2017 01:33 PM, albert-j wrote:
On Monday, 30 January 2017 at 12:31:33 UTC, albert-j wrote:
OK, got it. Can you do removal without reallocation with
std.container.array?
Array!int arr;
foreach (i; 0..10) arr ~= i;
Sorry, sent too early.
arr = arr[].remove!(x=> x > 5); //Doesn't work withouth calling
.Array!int
Looks like it can't be done in that straight-forward manner. But you can
do the `remove` and then update just `arr`'s length:
void main()
{
import std.container: Array;
import std.algorithm: equal, remove;
Array!int arr;
foreach (i; 0..10) arr ~= i;
const oldAddress = &arr[0];
arr.length = arr[].remove!(x=> x > 5).length;
assert(equal(arr[], [0, 1, 2, 3, 4, 5])); /* holds */
assert(&arr[0] is oldAddress); /* holds */
}
Maybe std.container.Array can be improved somehow to simplify this. But
I'm not sure about the details.
Re: D idom for removing array elements
On Monday, 30 January 2017 at 12:31:33 UTC, albert-j wrote: OK, got it. Can you do removal without reallocation with std.container.array? Array!int arr; foreach (i; 0..10) arr ~= i; Sorry, sent too early. arr = arr[].remove!(x=> x > 5); //Doesn't work withouth calling .Array!int
Re: D idom for removing array elements
On Monday, 30 January 2017 at 10:45:03 UTC, cym13 wrote:
Meh.
Forget that, bad memory. remove isn't working in-place. However
slapping ".array" is still asking explicitely for reallocation,
so just forget it. Here is a code that works:
import std.conv;
import std.stdio;
import std.format;
import std.algorithm;
void main(string[] args) {
int [] arr = [8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
auto before = arr.ptr;
arr = arr.remove!(x => x>5);
auto after = arr.ptr;
assert(arr == [0, 1, 2, 3, 4, 5], arr.to!string);
assert(before == after, "%s %s".format(before, after));
}
OK, got it. Can you do removal without reallocation with
std.container.array?
Array!int arr;
foreach (i; 0..10) arr ~= i;
Re: D idom for removing array elements
On Monday, 30 January 2017 at 10:30:22 UTC, cym13 wrote:
On Monday, 30 January 2017 at 08:50:14 UTC, albert-j wrote:
On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:
Removing works by overwriting the array with only the wanted
values and discarding the rest.
But then why do I get this:
import std.stdio, std.algorithm, std.array;
int[] arr;
foreach (i; 0..10) arr ~= i; // [0, 1, 2, 3, 4, 5, 6, 7,
8, 9]
writeln("&arr[0]:", &arr[0]); // prints "7F56FAE93000"
arr = arr.remove!(x => x > 5).array;
writeln("&arr[0]:", &arr[0]); // prints "7F56FAE92020"
writeln("arr:",arr); // prints: "[0, 1, 2, 3, 4, 5]"
It looks like arr.remove allocates new memory and copies the
data there.
No, remove works in-place, you are the one specifically asking
for a reallocation here: instead of
arr = arr.remove!(x => x>5).array;
write
arr.remove!(x => x>5);
Complete example:
import std.stdio;
import std.format;
import std.algorithm;
void main(string[] args) {
int [] arr = [0, 1, 2, 3, 4, 5];
auto before = arr.ptr;
arr.remove!(x => x>5);
auto after = arr.ptr;
assert(before == after, "%s %s".format(before, after));
}
Meh.
Forget that, bad memory. remove isn't working in-place. However
slapping ".array" is still asking explicitely for reallocation,
so just forget it. Here is a code that works:
import std.conv;
import std.stdio;
import std.format;
import std.algorithm;
void main(string[] args) {
int [] arr = [8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
auto before = arr.ptr;
arr = arr.remove!(x => x>5);
auto after = arr.ptr;
assert(arr == [0, 1, 2, 3, 4, 5], arr.to!string);
assert(before == after, "%s %s".format(before, after));
}
Re: D idom for removing array elements
On Monday, 30 January 2017 at 08:50:14 UTC, albert-j wrote:
On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:
Removing works by overwriting the array with only the wanted
values and discarding the rest.
But then why do I get this:
import std.stdio, std.algorithm, std.array;
int[] arr;
foreach (i; 0..10) arr ~= i; // [0, 1, 2, 3, 4, 5, 6, 7, 8,
9]
writeln("&arr[0]:", &arr[0]); // prints "7F56FAE93000"
arr = arr.remove!(x => x > 5).array;
writeln("&arr[0]:", &arr[0]); // prints "7F56FAE92020"
writeln("arr:",arr); // prints: "[0, 1, 2, 3, 4, 5]"
It looks like arr.remove allocates new memory and copies the
data there.
No, remove works in-place, you are the one specifically asking
for a reallocation here: instead of
arr = arr.remove!(x => x>5).array;
write
arr.remove!(x => x>5);
Complete example:
import std.stdio;
import std.format;
import std.algorithm;
void main(string[] args) {
int [] arr = [0, 1, 2, 3, 4, 5];
auto before = arr.ptr;
arr.remove!(x => x>5);
auto after = arr.ptr;
assert(before == after, "%s %s".format(before, after));
}
Re: D idom for removing array elements
On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:
Removing works by overwriting the array with only the wanted
values and discarding the rest.
But then why do I get this:
import std.stdio, std.algorithm, std.array;
int[] arr;
foreach (i; 0..10) arr ~= i; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
writeln("&arr[0]:", &arr[0]); // prints "7F56FAE93000"
arr = arr.remove!(x => x > 5).array;
writeln("&arr[0]:", &arr[0]); // prints "7F56FAE92020"
writeln("arr:",arr); // prints: "[0, 1, 2, 3, 4, 5]"
It looks like arr.remove allocates new memory and copies the data
there.
Re: D idom for removing array elements
On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote: [...] Great explanation, thank you!
Re: D idom for removing array elements
On Sunday, 29 January 2017 at 21:41:57 UTC, albert-j wrote:
int[] arr;
foreach (i; 0..10)
arr ~= i;
writeln("Original array: ",arr);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -- OK
auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2);
arrMap is a range. The filter and map operations only happen when
the range is iterated. The array on which arrMap operates is the
memory that is referred to by arr. If you change the values in
that memory before evaluating arrMap, the result will be affected.
However, `filter` also does something on creation: it skips to
the first element that passes the predicate. I.e., it skips to 6
in your code. Or rather, it skips to the memory location where 6
is stored at the time. Since it happens on creation, that
skipping will not be re-evaluated when you iterate over arrMap
multiple times.
writeln("arrMap: ", arrMap);
// [36, 49, 64, 81] -- OK
Note that the values are computed while printing to the screen.
They're not stored anywhere.
int[] toRemove = [1, 2, 9];
arr = arr.remove!(x => toRemove.canFind(x)).array;
Removing works by overwriting the array with only the wanted
values and discarding the rest.
The case at hand in detail:
* Look at arr[0]. It's 0. That's not in [1, 2, 9], so it's copied
to arr[0].
* Look at arr[1]. It's 1. That's in [1, 2, 9], so it's discarded.
* Look at arr[2]. It's 2. That's in [1, 2, 9], so it's discarded.
* Look at arr[3]. It's 3. That's not in [1, 2, 9], so it's copied
to arr[1].
* arr[4] through arr[8] are not in [1, 2, 9] either, so they're
copied to arr[2] through arr[6].
* arr[9] is in [1, 2, 9], so it's not copied.
Note that arr[7] through arr[9] have not been overwritten. So
you've got this in arr: [0, 3, 4, 5, 6, 7, 8, 7, 8, 9]. The last
three values are then sliced off, because three values have been
removed. Those values are still there in memory, though. The
array's new length just stops before them.
writeln("Original array after removal: ", arr);
// [0, 3, 4, 5, 6, 7, 8] -- OK
arr ~= arrMap.array;
writeln("Original array after removal and concatenation: ",
arr);
// [0, 3, 4, 5, 6, 7, 8, 64, 49, 64, 81] -- what?
Now, you've created arrMap before calling `remove`, so it still
uses the old length for its underlying array. But it sees the new
values, because `remove` has updated them in place. That means,
it sees the values mentioned above: [0, 3, 4, 5, 6, 7, 8, 7, 8,
9]. Except, `filter` has already skipped the first six elements.
So arrMap sees this: [8, 7, 8, 9]. Square those values and you
get [64, 49, 64, 81], which is what you see.
Generally, I'd say don't alter the underlying range/array between
creating and evaluating a range, nor during evaluation. `filter`
is most probably not the only range that misbehaves in that
situation.
Instead of mixing lazy ranges with the eager, in-place `remove`,
you can use filter again:
void main()
{
import std.array: array;
import std.algorithm: canFind, filter, map;
import std.range: chain;
import std.stdio: writeln;
int[] arr;
foreach (i; 0..10) arr ~= i;
immutable int[] toRemove = [1, 2, 9];
arr = chain(
arr.filter!(x => !toRemove.canFind(x)),
arr.filter!(x => x > 5).map!(x => x^^2),
).array;
writeln(arr); /* prints "[0, 3, 4, 5, 6, 7, 8, 36, 49, 64,
81]" */
}
Re: D idom for removing array elements
On Sunday, 29 January 2017 at 23:48:40 UTC, Jordan Wilson wrote: You need to do something like this: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; It's because arrMap is lazy evaluated. So does it mean that I cannot assign FilterResult and MapResult to a variable and safely use it later, because underlying array may change meanwhile? Since I am dealing with large arrays, I thought I'd save some memory by not calling .array on MapResult.
Re: D idom for removing array elements
On Sunday, 29 January 2017 at 23:42:40 UTC, Jordan Wilson wrote: On Sunday, 29 January 2017 at 21:41:57 UTC, albert-j wrote: On Saturday, 28 January 2017 at 11:54:58 UTC, cym13 wrote: [...] I am trying to wrap my head around lazy evaluation during filtering/mapping, but there's something I don't understand. I want to create an array, square some elements, remove some elements from original array and add the squared ones to the original array: [...] You need to do something like this: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; It's because arrMap is lazy evaluated. Specifically: arr ~= arrMap.array; will cause arrMap to be evaluated again using whatever arr is. So instead of: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2); // mutate arr arr ~= arrMap.array; you would want: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; // mutate arr arr ~= arrMap;
Re: D idom for removing array elements
On Sunday, 29 January 2017 at 21:41:57 UTC, albert-j wrote: On Saturday, 28 January 2017 at 11:54:58 UTC, cym13 wrote: [...] I am trying to wrap my head around lazy evaluation during filtering/mapping, but there's something I don't understand. I want to create an array, square some elements, remove some elements from original array and add the squared ones to the original array: [...] You need to do something like this: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; It's because arrMap is lazy evaluated.
Re: D idom for removing array elements
On Saturday, 28 January 2017 at 11:54:58 UTC, cym13 wrote:
I am trying to wrap my head around lazy evaluation during
filtering/mapping, but there's something I don't understand.
I want to create an array, square some elements, remove some
elements from original array and add the squared ones to the
original array:
import std.stdio, std.algorithm, std.array;
int[] arr;
foreach (i; 0..10)
arr ~= i;
writeln("Original array: ",arr);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -- OK
auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2);
writeln("arrMap: ", arrMap);
// [36, 49, 64, 81] -- OK
int[] toRemove = [1, 2, 9];
arr = arr.remove!(x => toRemove.canFind(x)).array;
writeln("Original array after removal: ", arr);
// [0, 3, 4, 5, 6, 7, 8] -- OK
arr ~= arrMap.array;
writeln("Original array after removal and concatenation: ",
arr);
// [0, 3, 4, 5, 6, 7, 8, 64, 49, 64, 81] -- what?
The last result is not what I wanted. I would expect [0, 3, 4, 5,
6, 7, 8] and [36, 49, 64, 81] concatenated into [0, 3, 4, 5, 6,
7, 8, 36, 49, 64, 81], but something else is happening here.
It looks like arr = arr.remove! is messing things up, but
why?
Re: D idom for removing array elements
On Saturday, 28 January 2017 at 10:46:29 UTC, albert-j wrote:
On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:
void main()
{ import std.stdio, std.algorithm, std.range, std.array,
std.datetime;
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array;
int[] b = [3, 4, 6].cycle.take(2000).array;
void originalMethod()
{ auto c = a.remove!(x => b.canFind(x));
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void WilsonMethod()
{ auto c = a.filter!(x => !b.canFind(x)).array;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void myMethod()
{ auto sortedB = sort(b.dup);
auto c = a
. filter!(i => !sortedB.contains(i))
. array
;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
auto r = benchmark!(originalMethod, WilsonMethod,
myMethod)(1);
foreach(result; r) result.writeln;
}
How to make it work with std.container.array?
Here is an example:
import std.container.array;
alias ArrI = Array!int;
auto removeAll(ArrI a, ArrI b) {
import std.array;
import std.range;
import std.algorithm;
auto sortedB = sort(b[]).uniq.array;
auto c = a[].partition!(v => sortedB.assumeSorted.contains(v),
SwapStrategy.stable);
return ArrI(c);
}
void main() {
import std.stdio;
auto a = ArrI(1, 2, 3, 4, 5, 6, 7, 4);
auto b = ArrI(3, 4, 6);
a.removeAll(b)[].writeln;
}
Note especially how you slice an Array to access its data.
Re: D idom for removing array elements
On Friday, 27 January 2017 at 11:56:02 UTC, Dukc wrote:
On Friday, 27 January 2017 at 10:20:19 UTC, albert-j wrote:
I am also wondering why the standard library doesn't have
convenience functions for this, e.g. like Java's removeAll?
Now there's more typing than necessary for a relatively common
task.
That might be a good addition considering how well it can be
optimized compared to a naive implementation. Of course, D
version of that would accept ranges as input, not only
collections.
Just to follow up, I've been playing a bit and the fastest I've
got so far is:
#!/usr/bin/env rdmd
import std.conv;
import std.stdio;
import std.array;
import std.range;
import std.datetime;
import std.algorithm;
void main() {
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array;
int[] b = [3, 4, 6].cycle.take(2000).array;
void originalMethod()
{ auto c = a.remove!(x => b.canFind(x));
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void WilsonMethod()
{ auto c = a.filter!(x => !b.canFind(x)).array;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void myMethod()
{ auto sortedB = sort(b.dup);
auto c = a
. filter!(i => !sortedB.contains(i))
. array
;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
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]);
}
void newPartitionMethod()
{ auto sortedB = sort(b.dup).uniq.array;
auto c = a.partition!(v =>
sortedB.assumeSorted.contains(v));
assert(c[0 .. 4] == [1, 2, 5, 7], c[0..4].to!string);
}
void newStablePartitionMethod()
{ auto sortedB = sort(b.dup).uniq.array;
auto c = a.partition!(v =>
sortedB.assumeSorted.contains(v),
SwapStrategy.stable);
assert(c[0 .. 4] == [1, 2, 5, 7], c[0..4].to!string);
}
benchmark!(originalMethod,
WilsonMethod,
myMethod,
partitionMethod,
stablePartitionMethod,
newPartitionMethod,
newStablePartitionMethod)(1)
.each!writeln;
}
/* Results (one of many runs, considered characteristic):
* TickDuration(18129442) // originalMethod
* TickDuration(28536187) // WilsonMethod
* TickDuration(845396) // myMethod
* TickDuration(29936970) // partitionMethod
* TickDuration(33447345) // stablePartitionMethod
* TickDuration(548226) // newPartitionMethod
* TickDuration(597183) // newStablePartitionMethod
*/
Re: D idom for removing array elements
On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:
void main()
{ import std.stdio, std.algorithm, std.range, std.array,
std.datetime;
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array;
int[] b = [3, 4, 6].cycle.take(2000).array;
void originalMethod()
{ auto c = a.remove!(x => b.canFind(x));
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void WilsonMethod()
{ auto c = a.filter!(x => !b.canFind(x)).array;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void myMethod()
{ auto sortedB = sort(b.dup);
auto c = a
. filter!(i => !sortedB.contains(i))
. array
;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
auto r = benchmark!(originalMethod, WilsonMethod,
myMethod)(1);
foreach(result; r) result.writeln;
}
How to make it work with std.container.array?
Re: D idom for removing array elements
On Friday, 27 January 2017 at 15:39:57 UTC, cym13 wrote: On Friday, 27 January 2017 at 08:30:41 UTC, Dukc wrote: [...] 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. [...] I forgot to say that the main reason to use partition is that it's easy to use it to remove the elements of the array in place: auto r = a.partition!(v => !b.canFind(v)); a.length -= r.length; It just puts the "bad" elements at the end and changes the length of the array.
Re: D idom for removing array elements
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 40 and "b" of length 3:
/*
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(40).array;
int[] b = [3, 4, 6];
*/
TickDuration(312038) // 2nd
TickDuration(541912)
TickDuration(606883)
TickDuration(190662) // partitionMethod is way faster
TickDuration(418751) // 3rd
Re: D idom for removing array elements
On Friday, 27 January 2017 at 10:20:19 UTC, albert-j wrote: I am also wondering why the standard library doesn't have convenience functions for this, e.g. like Java's removeAll? Now there's more typing than necessary for a relatively common task. That might be a good addition considering how well it can be optimized compared to a naive implementation. Of course, D version of that would accept ranges as input, not only collections.
Re: D idom for removing array elements
On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote: TickDuration(28085) TickDuration(42868) TickDuration(1509) Thank you, this is very helpful. I am also wondering why the standard library doesn't have convenience functions for this, e.g. like Java's removeAll? Now there's more typing than necessary for a relatively common task.
Re: D idom for removing array elements
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.
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 23:10:02 UTC, albert-j wrote: Will it also work correctly and fast for arrays of custom objects? How should opCmp() be defined if objects don't have a meaningful ordering? The order of elements in the original array does not matter. Two options: either define opCmp for the custom objects, or define ordering for the sort algorithm (see std.algorithm in phobos documentation)
Re: D idom for removing array elements
On Friday, 27 January 2017 at 05:48:27 UTC, Stefan Koch wrote:
To me it looks rather slow.
please benchmark!
void main()
{ import std.stdio, std.algorithm, std.range, std.array,
std.datetime;
int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array;
int[] b = [3, 4, 6].cycle.take(2000).array;
void originalMethod()
{ auto c = a.remove!(x => b.canFind(x));
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void WilsonMethod()
{ auto c = a.filter!(x => !b.canFind(x)).array;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
void myMethod()
{ auto sortedB = sort(b.dup);
auto c = a
. filter!(i => !sortedB.contains(i))
. array
;
assert(c[0 .. 4] == [1, 2, 5, 7]);
}
auto r = benchmark!(originalMethod, WilsonMethod,
myMethod)(1);
foreach(result; r) result.writeln;
}
resulted in:
TickDuration(28085)
TickDuration(42868)
TickDuration(1509)
So, you were correct that the original method is better than
Wilsons filter. My method is much better for large arrays I
tested here. But what I think you were afraid of is that it
needlessly wastes performance by allocating a new array, and I
agree.
Also, as I said, it could be made O(n).
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 23:10:02 UTC, albert-j wrote: On Thursday, 26 January 2017 at 13:21:38 UTC, Dukc wrote: import std.stdio, std.algorithm, std.range, std.array; int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto sortedB = sort(b.dup); auto c = a . filter!(i => !sortedB.contains(i)) . array ; assert(c == [1, 2, 5, 7]); If arrays get large, this should be more efficient since it performs O(n * n.log) instead of O(n * n). It does look much faster than my solution. Will it also work correctly and fast for arrays of custom objects? How should opCmp() be defined if objects don't have a meaningful ordering? The order of elements in the original array does not matter. To me it looks rather slow. please benchmark!
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 13:21:38 UTC, Dukc wrote: import std.stdio, std.algorithm, std.range, std.array; int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto sortedB = sort(b.dup); auto c = a . filter!(i => !sortedB.contains(i)) . array ; assert(c == [1, 2, 5, 7]); If arrays get large, this should be more efficient since it performs O(n * n.log) instead of O(n * n). It does look much faster than my solution. Will it also work correctly and fast for arrays of custom objects? How should opCmp() be defined if objects don't have a meaningful ordering? The order of elements in the original array does not matter.
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 08:22:09 UTC, albert-j wrote: What is the D idiom for removing array elements that are present in another array? Is this the right/fastest way? int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto c = a.remove!(x => b.canFind(x)); assert(c == [1, 2, 5, 7]); If you don't care about array a being mutated, then I think what you have is best (although I would suggest that if you don't care about a being mutated, just reassign the results back to a again). Otherwise, I think you need to allocate a new array, so the other answers using filter are good.
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 11:44:27 UTC, Nicholas Wilson wrote: On Thursday, 26 January 2017 at 08:22:09 UTC, albert-j wrote: What is the D idiom for removing array elements that are present in another array? Is this the right/fastest way? int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto c = a.remove!(x => b.canFind(x)); assert(c == [1, 2, 5, 7]); filter. auto c = a.filter!(x => !b.canFind(x)).array; He wanted to remove elements. This will allocate a freaking new array. And do N function calls to build it. This is WORSE!
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 08:22:09 UTC, albert-j wrote: What is the D idiom for removing array elements that are present in another array? Is this the right/fastest way? int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto c = a.remove!(x => b.canFind(x)); assert(c == [1, 2, 5, 7]); import std.stdio, std.algorithm, std.range, std.array; int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto sortedB = sort(b.dup); auto c = a . filter!(i => !sortedB.contains(i)) . array ; assert(c == [1, 2, 5, 7]); If arrays get large, this should be more efficient since it performs O(n * n.log) instead of O(n * n). On the other hand you could also just use assumeSorted if b is already sorted, as in this case. But if you do, I still recommend adding an assert to check the range truly is sorted when debugging. It can be made to perform O(n) by sorting both a and b, but then you need to figure a way to return a back to normal order after filtering. I tried, and found it to be so hard I didn't bother.
Re: D idom for removing array elements
On Thursday, 26 January 2017 at 08:22:09 UTC, albert-j wrote: What is the D idiom for removing array elements that are present in another array? Is this the right/fastest way? int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto c = a.remove!(x => b.canFind(x)); assert(c == [1, 2, 5, 7]); filter. auto c = a.filter!(x => !b.canFind(x)).array;
D idom for removing array elements
What is the D idiom for removing array elements that are present in another array? Is this the right/fastest way? int[] a = [1, 2, 3, 4, 5, 6, 7, 4]; int[] b = [3, 4, 6]; auto c = a.remove!(x => b.canFind(x)); assert(c == [1, 2, 5, 7]);
