Re: D idom for removing array elements

2017-01-30 Thread ag0aep6g via Digitalmars-d-learn

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

2017-01-30 Thread albert-j via Digitalmars-d-learn

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

2017-01-30 Thread albert-j via Digitalmars-d-learn

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

2017-01-30 Thread cym13 via Digitalmars-d-learn

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

2017-01-30 Thread cym13 via Digitalmars-d-learn

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

2017-01-30 Thread albert-j via Digitalmars-d-learn

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

2017-01-29 Thread albert-j via Digitalmars-d-learn

On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:

[...]


Great explanation, thank you!



Re: D idom for removing array elements

2017-01-29 Thread ag0aep6g via Digitalmars-d-learn

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

2017-01-29 Thread albert-j via Digitalmars-d-learn

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

2017-01-29 Thread Jordan Wilson via Digitalmars-d-learn

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

2017-01-29 Thread Jordan Wilson via Digitalmars-d-learn

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

2017-01-29 Thread albert-j via Digitalmars-d-learn

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

2017-01-28 Thread cym13 via Digitalmars-d-learn

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

2017-01-28 Thread cym13 via Digitalmars-d-learn

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

2017-01-28 Thread albert-j via Digitalmars-d-learn

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

2017-01-27 Thread cym13 via Digitalmars-d-learn

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

2017-01-27 Thread 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 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

2017-01-27 Thread Dukc via Digitalmars-d-learn

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

2017-01-27 Thread albert-j via Digitalmars-d-learn

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

2017-01-27 Thread Dukc via Digitalmars-d-learn

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

2017-01-27 Thread Dukc via Digitalmars-d-learn

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

2017-01-27 Thread Dukc via Digitalmars-d-learn

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

2017-01-26 Thread Stefan Koch via Digitalmars-d-learn

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

2017-01-26 Thread albert-j via Digitalmars-d-learn

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

2017-01-26 Thread Jordan Wilson via Digitalmars-d-learn

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

2017-01-26 Thread Stefan Koch via Digitalmars-d-learn
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

2017-01-26 Thread Dukc via Digitalmars-d-learn

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

2017-01-26 Thread Nicholas Wilson via Digitalmars-d-learn

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

2017-01-26 Thread albert-j via Digitalmars-d-learn
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]);