Re: *** GMX Spamverdacht *** Re: Reducing an array
Am 18.04.2014 22:27, schrieb Steven Schveighoffer via Digitalmars-d-learn: arr.sort(); arr = arr.uniq.array(); -Steve Thanks, also for the explanation! - Tim
Re: Reducing an array
On Friday, 18 April 2014 at 22:11:17 UTC, bearophile wrote:
monarch_dodra:
Out of curiosity, if the requirement was to *also* preserve
ordering (eg: remove all non-first elements), how would you go
at it?
[2, 1, 1, 3, 2, 3] = [2, 1, 3];
Maybe std.algorithm's `makeIndex` would help here?
Bonus points for doing it inplace.
This preserves ordering and it's in-place. Not tested much:
void main() {
import std.stdio, std.traits;
auto data = [2, 1, 1, 3, 2, 3];
bool[ForeachType!(typeof(data))] seen;
size_t pos = 0;
foreach (immutable i; 0 .. data.length)
if (data[i] !in seen) {
if (pos != i)
data[pos] = data[i];
seen[data[i]] = true;
pos++;
}
data.length = pos;
data.writeln;
}
Bye,
bearophile
I thought of an approach somewhere along these lines. I was
wondering if there was a UFCS approach too. Or an in-place
approach.
Well, the inplace is easy of you accept N² performance :)
Re: Reducing an array
On Friday, 18 April 2014 at 20:02:41 UTC, Tim Holzschuh via
Digitalmars-d-learn wrote:
Hi there,
I try to remove all equal elements of an array, thus [2,2] --
[2].
I thought this maybe would be possible with
std.algorithm.reduce, but at least the way I tried it doesn't
work:
arr.reduce( (a,b) = a != b );
Is there a simple solution using Phobos-functions?
Not too fancy, since I'm new in D, but I created this:
import std.stdio;
import std.array;
import std.algorithm;
static if (!is(typeof(writeln)))
alias writefln writeln;
void main(){
int myfilter(int a){
static int[] b;
if(b.find(a) == []){
b.insertInPlace(b.length, a);
return a;
}
return -1;
}
auto arr = [1,1,2,3,2,2,4,5,5,1];
auto arrFiltered = arr.filter!(a = myfilter(a) 0);
writeln(arrFiltered);
}
Tested: http://dpaste.dzfl.pl/97a1307c7fec
I'm looking for creating something like C# extensions, maybe
with alias. I'll try later!
Matheus.
Re: Reducing an array
On 04/19/2014 09:55 AM, MattCoder wrote:
On Friday, 18 April 2014 at 20:02:41 UTC, Tim Holzschuh via
Digitalmars-d-learn wrote:
void main(){
int myfilter(int a){
static int[] b;
That static variable makes this solution non-reentrant. To see an effect
of this, replace the arrFiltered line with the following:
import std.range;
auto arr2 = [1,1,5,2,3];
auto arrFiltered = zip(arr.filter!(a = myfilter(a) 0),
arr2.filter!(a = myfilter(a) 0));
Now the two filter operations get in each other's way and the output
becomes:
[Tuple!(int, int)(1, 5), Tuple!(int, int)(2, 3)]
I wonder what happened to 4. (?) :)
if(b.find(a) == []){
There is a more explicit way of saying that:
if(!b.canFind(a)){
Ali
Re: Reducing an array
On Friday, 18 April 2014 at 22:11:17 UTC, bearophile wrote:
This preserves ordering and it's in-place. Not tested much:
void main() {
import std.stdio, std.traits;
auto data = [2, 1, 1, 3, 2, 3];
bool[ForeachType!(typeof(data))] seen;
size_t pos = 0;
foreach (immutable i; 0 .. data.length)
if (data[i] !in seen) {
if (pos != i)
data[pos] = data[i];
seen[data[i]] = true;
pos++;
}
data.length = pos;
data.writeln;
}
Bye,
bearophile
If you replace that = with a swap, then you can also preserve
the duplicate elements at the end (although in no specific
ordering):
import std.stdio : writefln;
import std.algorithm : canFind, swap;
//
void main()
{
auto arr = [1,1,5,2,3,2,2,4,5,5,1];
size_t pos = 0;
foreach(ref e; arr)
if (!arr[0 .. pos].canFind(e))
swap(arr[pos++], e);
writefln(uniques: %s, arr[0 .. pos]);
writefln(dupes: %s, arr[pos .. $]);
}
//
I was trying a 100% inplace solution, but I found nothing
better than N². It's basically still what you submitted though.
Re: Reducing an array
On Saturday, 19 April 2014 at 17:12:10 UTC, Ali Çehreli wrote:
On 04/19/2014 09:55 AM, MattCoder wrote:
On Friday, 18 April 2014 at 20:02:41 UTC, Tim Holzschuh via
Digitalmars-d-learn wrote:
void main(){
int myfilter(int a){
static int[] b;
That static variable makes this solution non-reentrant...
Yes, you're completely right and I already knew that. But
remember Like I said previously, I would like to convert that
code to something close to extensions in C#, in that case I can
take the address of the array to check if it's a new Filter or
not. for example, current in D I can do this:
import std.stdio;
import std.array;
import std.range;
import std.algorithm;
void main(){
int myfilter(int[] *addr, int a){
static int[] b;
static int[] *address;
if(address != addr){
address = addr;
b.clear();
}
if(!b.canFind(a)){
b.insertInPlace(b.length, a);
return a;
}
return -1;
}
auto arr = [1,1,2,3,2,2,4,5,5,1];
auto arr2 = [3,4,3,9,9,7,4,4,4,7];
auto arrFiltered = arr.filter!(a = myfilter(arr, a) = 0);
writeln(arrFiltered);
auto arrFiltered2 = arr2.filter!(a = myfilter(arr2, a) = 0);
writeln(arrFiltered2);
}
But with extensions, the argument address (i.e: arr) on the
calling of myfilter can be avoided!
Matheus.
Re: Reducing an array
On Thu, 17 Apr 2014 09:46:25 -0400, Tim Holzschuh via Digitalmars-d-learn digitalmars-d-learn@puremagic.com wrote: Hi there, I try to remove all equal elements of an array, thus [2,2] -- [2]. I thought this maybe would be possible with std.algorithm.reduce, but at least the way I tried it doesn't work: arr.reduce( (a,b) = a != b ); reduce doesn't do what you think it does. It applies a function to all elements, keeping track of the result of each function call, and passing it to the next one. In other words, reduce!fn(a, range) is like doing this: fn(range[5], fn(range[4], fn(range[3], fn(range[2], fn(range[1], fn(range[0], a)); What you want is probably uniq: http://dlang.org/library/std/algorithm/uniq.html Note that it works on a SORTED range, so you want to sort first. Note also that what it returns is not an array, but a lazily iterated range over the array. If you want another array, this is the code I would use: arr.sort(); arr = arr.uniq.array(); -Steve
Re: Reducing an array
On Friday, 18 April 2014 at 20:27:20 UTC, Steven Schveighoffer wrote: Note also that what it returns is not an array, but a lazily iterated range over the array. If you want another array, this is the code I would use: arr.sort(); arr = arr.uniq.array(); -Steve Out of curiosity, if the requirement was to *also* preserve ordering (eg: remove all non-first elements), how would you go at it? [2, 1, 1, 3, 2, 3] = [2, 1, 3]; Maybe std.algorithm's `makeIndex` would help here? Bonus points for doing it inplace.
Re: Reducing an array
monarch_dodra:
Out of curiosity, if the requirement was to *also* preserve
ordering (eg: remove all non-first elements), how would you go
at it?
[2, 1, 1, 3, 2, 3] = [2, 1, 3];
Maybe std.algorithm's `makeIndex` would help here?
Bonus points for doing it inplace.
This preserves ordering and it's in-place. Not tested much:
void main() {
import std.stdio, std.traits;
auto data = [2, 1, 1, 3, 2, 3];
bool[ForeachType!(typeof(data))] seen;
size_t pos = 0;
foreach (immutable i; 0 .. data.length)
if (data[i] !in seen) {
if (pos != i)
data[pos] = data[i];
seen[data[i]] = true;
pos++;
}
data.length = pos;
data.writeln;
}
Bye,
bearophile
