www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Reducing an array

reply Tim Holzschuh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
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?

Thank you,
     Tim
Apr 17 2014
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Apr 18 2014
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Apr 18 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Apr 18 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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 :)
Apr 19 2014
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Apr 19 2014
prev sibling parent Tim Holzschuh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
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
Apr 19 2014
prev sibling parent reply "MattCoder" <idonthaveany mail.com> writes:
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


with alias. I'll try later!

Matheus.
Apr 19 2014
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Apr 19 2014
parent "MattCoder" <idonthaveany mail.com> writes:
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 

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.
Apr 19 2014