www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.algorithm issue

reply Brian Myers <bmyers harryanddavid.com> writes:
Hi,

I send Andrei a suggestion a while back for improving the map! template in
std.algorithm. The change was, when map! is supplied a function alias, its
return type should be a range of the return type of the function. This is much
like Python's map statement and lets you do things like this:

string[] string_list = //integer strings from somewhere
auto intrange = map!(atoi)(split(string_list, ","));

That has worked out well. This time I have a question about both the reduce!
and map! templates. I would like to do something like this:

reduce!(Merge)(/*string[] list of files*/);

but where Merge is a member function of a class. When I try this I get:

c:\dmd\bin\..\src\phobos\std\algorithm.d(185): Error: need 'this' to access
member Merge

When I try

reduce!(this.Merge)(/*same string[]*/);

I get:

d_dedup.d(153): template std.algorithm.reduce(F...) cannot deduce template
function from argument types !(this.Merge)(i
variant(char)[],invariant(char)[][])

Is it possible to map! or reduce! a member function or delegate against a
range? If so how would I do that?

Thanx,

Brian
May 21 2008
next sibling parent BCS <ao pathlink.com> writes:
Reply to Brian,


 Is it possible to map! or reduce! a member function or delegate
 against a range? If so how would I do that?
 
I think not because the context pointer "this" must be carried somehow at runtime. It might, however, be possible to make a version of map! that takes a delegate and uses that.
May 21 2008
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Brian Myers:
 Is it possible to map! or reduce! a member function or delegate against a
 range? If so how would I do that?
Do you mean something like this? import d.func: map, xrange, putr; class Foo { int sqr(int x) { return x * x; } } class Baz { float div2(int x) { return x / 2; } } void main() { auto f1 = new Foo; putr( map(&f1.sqr, xrange(10)) ); auto b1 = new Baz; putr( map(&b1.div2, xrange(10)) ); } Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0] Bye, bearophile
May 21 2008
next sibling parent Dee Girl <deegirl noreply.com> writes:
bearophile Wrote:

 Brian Myers:
 Is it possible to map! or reduce! a member function or delegate against a
 range? If so how would I do that?
Do you mean something like this? import d.func: map, xrange, putr; class Foo { int sqr(int x) { return x * x; } } class Baz { float div2(int x) { return x / 2; } } void main() { auto f1 = new Foo; putr( map(&f1.sqr, xrange(10)) ); auto b1 = new Baz; putr( map(&b1.div2, xrange(10)) ); } Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0] Bye, bearophile
import std.algorithm; struct A { int Merge(int) { return 0; } } void main(string[] args) { A a; map!((int x) { return a.Merge(x); })([1, 2, 3]); } I did not install bearophile library. It would be interesting to see what the speed is of std.algorithm and d.func. Dee Girl
May 21 2008
prev sibling parent reply Brian Myers <bmyers harryanddavid.com> writes:
I think this is exactly what I wanted. I needed to use the address of operator
along with the instance reference.

Wow some of the things you can do in D (like Dee Girl's post) are almost as
esoteric and obscure as Felix!

Thanx everyone,

Brian

bearophile Wrote:

 Brian Myers:
 Is it possible to map! or reduce! a member function or delegate against a
 range? If so how would I do that?
Do you mean something like this? import d.func: map, xrange, putr; class Foo { int sqr(int x) { return x * x; } } class Baz { float div2(int x) { return x / 2; } } void main() { auto f1 = new Foo; putr( map(&f1.sqr, xrange(10)) ); auto b1 = new Baz; putr( map(&b1.div2, xrange(10)) ); } Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] [0.0, 0.0, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0] Bye, bearophile
May 22 2008
parent reply Dee Girl <deegirl noreply.com> writes:
Brian Myers Wrote:

 I think this is exactly what I wanted. I needed to use the address of operator
along with the instance reference.
 
 Wow some of the things you can do in D (like Dee Girl's post) are almost as
esoteric and obscure as Felix!
In fact it is simpler. It is just bug in dmd. The following code works. import std.algorithm; struct A { int Merge(int) { return 0; } } void main(string[] args) { A a; auto fun = &a.Merge; map!(fun)([1, 2, 3]); } It is a problem that compiler can work with fun but not direct with &a.Merge. It is good idea to report bug to Walter. Such bug limits power of higher order functions. Thank you, Dee Girl
May 22 2008
parent reply Brian Myers <bmyers harryanddavid.com> writes:
Hmmm, for some reason this is still not working. It must be because the reduce
statement is itself within a method of the same class as Merge. Here's what
I've got.

class ExternalSorter : Sorter {
.
.
.

    string Merge(string f1, string f2) {
    .
    .
    .
    }

    override void Sort() {
    .
    .
    .
        auto mrg = &Merge;
        retfile = (chunk_list.length == 1 ? chunk_list[0] :
                   reduce!(mrg)(chunk_list[0], chunk_list[1..$]));
    .
    .
    .
    }

And here's the error message:
c:\dmd\bin\..\src\phobos\std\algorithm.d(283): template
std.algorithm.reduce(F...) is not a function template
d_dedup.d(191): template std.algorithm.reduce(F...) cannot deduce template
function from argument types !(&this.Merge)(i
nvariant(char)[],invariant(char)[][])
d_dedup.d(191): Error: incompatible types for ((this.chunk_list[cast(uint)0]) ?
((reduce(F...))((this.chunk_list[cast(ui
nt)0]),this.chunk_list[cast(uint)1..__dollar]))): 'invariant(char)[]' and 'int'

This is the closest I've gotten yet. I've tried a number of other ways with the
address of operator, etc...

Brian



Dee Girl Wrote:

 Brian Myers Wrote:
 
 I think this is exactly what I wanted. I needed to use the address of operator
along with the instance reference.
 
 Wow some of the things you can do in D (like Dee Girl's post) are almost as
esoteric and obscure as Felix!
In fact it is simpler. It is just bug in dmd. The following code works. import std.algorithm; struct A { int Merge(int) { return 0; } } void main(string[] args) { A a; auto fun = &a.Merge; map!(fun)([1, 2, 3]); } It is a problem that compiler can work with fun but not direct with &a.Merge. It is good idea to report bug to Walter. Such bug limits power of higher order functions. Thank you, Dee Girl
May 22 2008
next sibling parent Dee Girl <deegirl noreply.com> writes:
Brian Myers Wrote:

 Hmmm, for some reason this is still not working. It must be because the reduce
statement is itself within a method of the same class as Merge. Here's what
I've got.
This code does not work: import std.algorithm; class Sorter {} class ExternalSorter : Sorter { string Merge(string f1, string f2) { return f1 ~ f2; } void Sort() { string[] chunk_list = [ "a", "b" ]; auto mrg = &Merge; auto retfile = reduce!(mrg)(chunk_list[0], chunk_list[1..$]); } } void main(string[] args) { auto s = new ExternalSorter; s.Sort; } But I know how to make it work because I look at the error message. You go to std.algorithm and make NxNHelper from private to public. Then inside NxNHelper also make For from private to public. Then code works. Maybe bug report to Walter is necessary. Private should work because lookup is in correct module. It is bug in compiler not library. Can you please? Thank you, Dee Girl
May 22 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Brian Myers:
     string Merge(string f1, string f2) {
     .
     .
     .
     }
I don't exactly know what you are trying to do, but using s1~s2 to merge an array of strings is probably O(n^2) if the higher order functions you use (or the compiler) aren't smart enough. There is a join() function in std.string that is O(1), and there's a faster version of it in my libs (and probably in Tango too). Bye, bearophile
May 22 2008
parent reply Brian Myers <bmyers harryanddavid.com> writes:
I'll look into submitting a bug report to Walter. Thanx bearophile.

Dee Girl, I'm actually not merging strings. The strings are file names. Merge
is the merge phase for an external sort. In my next project I'll use map to do
something like what you're talking about. I'll have to test the difference
between map!-ing a custom function and doing join, and using reduce and a
custom function.

Thanx to both of you.

Brian

bearophile Wrote:

 Brian Myers:
     string Merge(string f1, string f2) {
     .
     .
     .
     }
I don't exactly know what you are trying to do, but using s1~s2 to merge an array of strings is probably O(n^2) if the higher order functions you use (or the compiler) aren't smart enough. There is a join() function in std.string that is O(1), and there's a faster version of it in my libs (and probably in Tango too). Bye, bearophile
May 22 2008
parent lurker <lurker lurk.com> writes:
dood u got ur credits crossed. d chick not bearophile said u should submit a
bug report. then bearophile not d chick said merging strings is bad. afaiu d
chick prolly put string concat in there as an example. peace

Brian Myers Wrote:

 I'll look into submitting a bug report to Walter. Thanx bearophile.
 
 Dee Girl, I'm actually not merging strings. The strings are file names. Merge
is the merge phase for an external sort. In my next project I'll use map to do
something like what you're talking about. I'll have to test the difference
between map!-ing a custom function and doing join, and using reduce and a
custom function.
 
 Thanx to both of you.
 
 Brian
 
 bearophile Wrote:
 
 Brian Myers:
     string Merge(string f1, string f2) {
     .
     .
     .
     }
I don't exactly know what you are trying to do, but using s1~s2 to merge an array of strings is probably O(n^2) if the higher order functions you use (or the compiler) aren't smart enough. There is a join() function in std.string that is O(1), and there's a faster version of it in my libs (and probably in Tango too). Bye, bearophile
May 22 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Dee Girl:
 I did not install bearophile library. It would be interesting to see what the
speed is of std.algorithm and d.func.
I am not using D 2.x, but I have performed some benchmarks, with quite interesting results (DMD 1.029 because my libs don't work at all with DMD 1.030, on a Core Duo, using 1 core only): import std.stdio: put = writef, putr = writefln; import d.func: map, range; import d.time: clock; import std.traits: ReturnType; import d.extra: NewVoidCArray, delVoidC, NewVoidGCArray; import std.c.stdlib: alloca; static int inv(int x) { return -x; } ReturnType!(f)[] Map2(alias f)(int[] arr) { auto result = new ReturnType!(f)[arr.length]; foreach (i, el; arr) result[i] = f(el); return result; } ReturnType!(f)[] Map3(alias f)(int[] arr) { auto result = NewVoidGCArray!(int)(arr.length); foreach (i, el; arr) result[i] = f(el); return result; } void Map4(alias f)(int[] arr) { auto result = (cast(int*)alloca(arr.length * int.sizeof))[0 .. arr.length]; if (result.ptr is null) throw new Exception("Not enough free stack"); foreach (i, el; arr) result[i] = f(el); return result; } void main() { auto data = range(6_000_000); double t; typeof(data) r; t = clock(); for (uint i; i < 100U; ++i) { r = new int[data.length]; foreach (pos, el; data) r[pos] = -el; } putr("inline: ", clock() - t, " ", r[$-1]); t = clock(); for (uint i; i < 100U; ++i) r = map(&inv, data); putr("map global func: ", clock() - t, " ", r[$-1]); t = clock(); for (uint i; i < 100U; ++i) r = map((int x) {return -x;}, data); putr("map locally defined delegate: ", clock() - t, " ", r[$-1]); t = clock(); for (uint i; i < 100U; ++i) r = map(function(int x) {return -x;}, data); putr("map locally defined function: ", clock() - t, " ", r[$-1]); t = clock(); for (uint i; i < 100U; ++i) r = Map2!(inv)(data); putr("Map2 with global function: ", clock() - t, " ", r[$-1]); t = clock(); for (uint i; i < 100U; ++i) { auto r2 = NewVoidCArray!(int)(data.length); foreach (pos, el; data) r2[pos] = -el; delVoidC(r2); } putr("inline C malloc: ", clock() - t); t = clock(); for (uint i; i < 100U; ++i) r = Map3!(inv)(data); putr("Map3 with global function: ", clock() - t, " ", r[$-1]); t = clock(); for (uint i; i < 100U; ++i) Map4!(inv)(data); putr("Map4 with global function: ", clock() - t); } Timings results, n = 6_000_000 of ints: inline: 4.59 map global func: 4.95 map locally defined delegate: 4.73 map locally defined function: 4.31 Map2 with global function: 3.97 inline C malloc: 2.01 Map3 with global function: 2.53 Map4 with global function: 2.0 I can see two surprises there, one is that putting "function" in the map avoids it to become a delegate, speeding up the code a little. The other bigger surprise is the first version (inlined) being slower than the version "map locally defined function". Bye, bearophile
May 24 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
More versions with more surprises:

    t = clock();
    for (uint i; i < 100U; ++i)
        r = Map2!((int x) {return -x;})(data);
    putr("Map2 with locally defined delegate: ", clock() - t, " ", r[$-1]);

    t = clock();
    for (uint i; i < 100U; ++i)
        r = Map2!(function(int x) {return -x;})(data);
    putr("Map2 with locally defined function: ", clock() - t, " ", r[$-1]);
}

/*

Timings:
    inline: 4.61 -5999999
    map global func: 4.968 -5999999
    map locally defined delegate: 4.782 -5999999
    map locally defined function: 4.328 -5999999
    Map2 with global function: 4 -5999999
    inline C malloc: 2.015
    Map3 with global function: 2.531 -5999999
    Map4 with global function: 1.969
    Map2 with locally defined delegate: 4.297 -5999999
    Map2 with locally defined function: 4.156 -5999999
May 24 2008
parent Dee Girl <deegirl noreply.com> writes:
bearophile Wrote:

 More versions with more surprises:
 
     t = clock();
     for (uint i; i < 100U; ++i)
         r = Map2!((int x) {return -x;})(data);
     putr("Map2 with locally defined delegate: ", clock() - t, " ", r[$-1]);
 
     t = clock();
     for (uint i; i < 100U; ++i)
         r = Map2!(function(int x) {return -x;})(data);
     putr("Map2 with locally defined function: ", clock() - t, " ", r[$-1]);
 }
 
 /*
 
 Timings:
     inline: 4.61 -5999999
     map global func: 4.968 -5999999
     map locally defined delegate: 4.782 -5999999
     map locally defined function: 4.328 -5999999
     Map2 with global function: 4 -5999999
     inline C malloc: 2.015
     Map3 with global function: 2.531 -5999999
     Map4 with global function: 1.969
     Map2 with locally defined delegate: 4.297 -5999999
     Map2 with locally defined function: 4.156 -5999999
I think you want to measure function call overhead. Then do not put dynamic allocation in function. Otherwise you measure allocate speed. That is why results are odd. Maybe if you change order results will change. Would help to put static allocation inside function, never dynamic. Then you measure loop and call overhead. Also tests should be in separate runs of program and averaged over few runs. Dee Girl
May 24 2008