digitalmars.D.learn - Intrinsics, std.bind problems, list comphrensions, recursivity test
- bearophile (219/219) Aug 24 2007 Some time ago I have tried to improve the Shootout nsieve-bits test, but...
- Downs (36/53) Aug 24 2007 -----BEGIN PGP SIGNED MESSAGE-----
- Henning Hasemann (27/27) Aug 24 2007 This is untested:
- Tom S (42/90) Aug 24 2007 Yup, because Bind extracts type info from the passed delegate /
Some time ago I have tried to improve the Shootout nsieve-bits test, but I have failed: http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=nsievebits&lang=all On my PC that version that uses intrinsics is faster, but on the PC used by the Shootout the version that uses local functions seems faster. Do you know how is this possibile? BTW, now that I know D a bit better I think my version of the program can be improved some more with: uint[] flags = void; But probably the speed difference isn't enough to make it go up in the time rank. --------------------------------- import std.stdio, std.bind, std.traits, std.random; int randInt(int min, int max) { int k, n; n = (max - min) + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k + min - 1 : k + min; } int randInt(int max) { int k, n; n = max + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k - 1 : k; } void main() { // This line: // auto rnd = bind(&randInt, 100); // Raises: // ...\std\bind.d(395): static assert is false // Line 394-395 of std.bind.d: // // make sure we'll copy all args the function is going to need // static assert (res >= minFuncArgs); auto rnd100 = bind(&randInt, 0, 99); writefln( typeid(typeof(rnd100)) , '\n'); // Prints: // std.bind.BoundFunc!(int(*)(int min, int max),NullAlias,Tuple!(int,int) ).BoundFunc writefln(rnd100(), ' ', rnd100(), '\n'); // OK // This line: // ReturnType!(typeof(rnd100)) x; // Raises: // ...\std\traits.d(34): alias std.traits.ReturnType!(BoundFunc).ReturnType recursive alias declaration static if (is(rnd100 TyOut == return)) { TyOut x; writefln(typeid(typeof(x))); } else writefln("No return"); // Prints this } (In the end I have simply solved the problem without std.bind, defining a lambda function.) --------------------------------- I think D developers can take a look at ShedSkin, its type inferencing is among the most powerful you can see around (but it's slow too, partially because it's written in Python). It shows how some Python can be compiled to C++. Python list comphrensions are a quite easy syntax to build various arrays (the latest Javascript of Mozilla has them too), this is a little Python code that shows few usages of LCs: print [x*x for x in xrange(16) if x & 1] print [x+y for x in xrange(5) if x & 1 for y in xrange(5)] print [[x+y for x in xrange(3)] for y in xrange(3)] def odds(): x = 0 while x < 36: yield x x += 1 print [x*x for x in odds() if x > 30] This is how ShedSkin translates them to C++ (this is most of the produced code): str *__name__; int __12; static inline list<int> *list_comp_0() { int x, __1, __0; list<int> *result = new list<int>(); FAST_FOR(x,0,16,1,0,1) if ((x&1)) { result->append((x*x)); } END_FOR return result; } static inline list<int> *list_comp_1() { int __5, __4, __3, __2, y, x; list<int> *result = new list<int>(); FAST_FOR(x,0,5,1,2,3) if ((x&1)) { FAST_FOR(y,0,5,1,4,5) result->append((x+y)); END_FOR } END_FOR return result; } static inline list<int> *list_comp_2(int y) { int x, __9, __8; list<int> *result = new list<int>(); FAST_FOR(x,0,3,1,8,9) result->append((x+y)); END_FOR return result; } static inline list<list<int> *> *list_comp_3() { int y, __7, __6; list<list<int> *> *result = new list<list<int> *>(); FAST_FOR(y,0,3,1,6,7) result->append(list_comp_2(y)); END_FOR return result; } static inline list<int> *list_comp_4(__iter<int> *__13) { __iter<int> *__11, *__10; int x; list<int> *result = new list<int>(); FOR_IN(x,__13,11) if ((x>30)) { result->append((x*x)); } END_FOR return result; } class __gen_odds : public __iter<int> { public: int x; int __last_yield; __gen_odds() { __last_yield = -1; } int next() { switch(__last_yield) { case 0: goto __after_yield_0; default: break; } x = 0; while((x<36)) { __last_yield = 0; return x; __after_yield_0:; x = (x+1); } throw new StopIteration(); } }; __iter<int> *odds() { return new __gen_odds(); } void __init() { // the main program __name__ = new str("__main__"); print("%s\n", list_comp_0()); print("%s\n", list_comp_1()); print("%s\n", list_comp_3()); print("%s\n", list_comp_4(odds())); } The list_comp_0 shows a small function and an if too. list_comp_1 shows that LCs can be attached too. list_comp_2 and list_comp_3 are nested, and list_comp_4 shows a case where you don't know how much long the resulting array will become, so it is built with successive appends. ------------------------------- In one of my recent emails I have tried to show some code that D executes relatively slowly, but Walter has spotted a stupid error of mine. So I try again (it's a bit of code that comes from the Shootout): First D version: import std.conv; int ack(int m, int n) { if (m == 0) return n+1; if (n == 0) return ack(m-1, 1); return ack(m-1, ack(m, n-1)); } void main(string[] args) { int n = args.length > 1 ? toInt(args[1]) : 11; printf("ack(3,%d): %d\n", n, ack(3, n)); } Second D version (nested function): import std.conv; void main(string[] args) { int ack(int m, int n) { if (m == 0) return n+1; if (n == 0) return ack(m-1, 1); return ack(m-1, ack(m, n-1)); } int n = args.length > 1 ? toInt(args[1]) : 11; printf("ack(3,%d): %d\n", n, ack(3, n)); } C version: #include <stdio.h> #include <stdlib.h> int ack(int m, int n) { if (m == 0) return n+1; if (n == 0) return ack(m-1, 1); return ack(m-1, ack(m, n-1)); } int main(int argc, char *argv[]) { int n = argc > 1 ? atoi(argv[1]) : 11; printf("Ack(3,%d): %d\n", n, ack(3, n)); return 0; } Object Pascal version: *{$APPTYPE CONSOLE} uses SysUtils; // integer is signed 32-bit function ack(m: integer; n: integer): integer; begin if m = 0 then ack := n+1 else if n = 0 then ack := ack(m-1, 1) else ack := ack(m-1, ack(m, n-1)); end; var n, code: Integer; begin if ParamCount > 0 then Val(ParamStr(1), n, code) else n := 6; writeln('ack(3,', n, '): ', ack(3, n)); end. Running time, input n = 11 (Pentium3 CPU): C 1: 2.91 seconds C 2: 4.61 s ObjectPascal: 6.78 s D 1: 8.15 s D 2: 16.36 s Compilers used and settings: C 1: MinGW -O3 -fomit-frame-pointer C 2: MinGW -O3 (same code as C 1). ObjectPascal: Delphi 5, runtime errors disabled D 1: dmd -O -inline -release D 2: dmd -O -inline -release, nested function Bye, bearophile
Aug 24 2007
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 FWIW, you can express those in D in a similar fashion using the tools.iter module I posted over in d.D .. bearophile wrote:print [x*x for x in xrange(16) if x & 1]writefln(Integers[0..16]~filters!("_&1")~maps!("_*_")~toArray);print [x+y for x in xrange(5) if x & 1 for y in xrange(5)]The code for doing this (tscross) only exists on my local version, and looks too ugly to post. But it works. writefln(Integers[0..5]~filters!("_&1") ~tscross({return Integers[0..5]; }) ~maps!("_.values[0]+_.values[1]")~toArray);print [[x+y for x in xrange(3)] for y in xrange(3)]// Can't use simplified syntax for this one. Dangit. writefln(Integers[0..3]~map((int e) { return Integers[0..3]~map((int f) { return f+e; })~toArray; })~toArray);def odds(): x = 0 while x < 36: yield x x += 1 print [x*x for x in odds() if x > 30]// I admit this isn't nearly as neat as the python version. // We really need to come up with a way to do yield. // StackThreads, anyone? class odds : Iterator!(int) { int x=0; bool next(ref int foo) { if (x!<36) return false; foo=x; x+=1; return true; } } writefln((new odds)~filters!("_>30")~maps!("_*_")~toArray);Still, despite the ugliness D is actually not that far off. --downs -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGzp1KpEPJRr05fBERAjdNAJ9BLWgjjz/fiSMkZQm21ul8LPezOACfcwNr z3oUu+mF/ojlx2gkLIccSjg= =dpId -----END PGP SIGNATURE-----
Aug 24 2007
This is untested: /** * Resembles pythons list comprehensions * Read as * returns *apply* applied to each *iter* in *collection* where *where* * * for example: * * int i; * select(toString(i), i, [1,2,3,4,5,6,7], i % 2 == 0) * * would return: * ["2", "4", "6"] */ R[] select(R, I, C)(lazy R apply, ref I iter, C collection, lazy bool where) { R[] r; foreach(x; collection) { iter = x; if(where()) r ~= apply(); } return r; } -- GPG Public Key: http://keyserver.ganneff.de:11371/pks/lookup?op=get&search=0xDDD6D36D41911851 Fingerprint: 344F 4072 F038 BB9E B35D E6AB DDD6 D36D 4191 1851
Aug 24 2007
bearophile wrote:import std.stdio, std.bind, std.traits, std.random; int randInt(int min, int max) { int k, n; n = (max - min) + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k + min - 1 : k + min; } int randInt(int max) { int k, n; n = max + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k - 1 : k; } void main() { // This line: // auto rnd = bind(&randInt, 100); // Raises: // ...\std\bind.d(395): static assert is falseYup, because Bind extracts type info from the passed delegate / function, and in this case it has two options. I'll try to see if I could somehow make it 'guess', basing on the number of parameters, which type to expect, but there might be problems with it. Anyway, the solution is to tell it which function pointer to choose, by using a cast.// Line 394-395 of std.bind.d: // // make sure we'll copy all args the function is going to need // static assert (res >= minFuncArgs); auto rnd100 = bind(&randInt, 0, 99); writefln( typeid(typeof(rnd100)) , '\n'); // Prints: // std.bind.BoundFunc!(int(*)(int min, int max),NullAlias,Tuple!(int,int) ).BoundFuncbind() doesn't return a delegate, it returns a BoundFunc object. Access the delegate by using .ptr(). Otherwise, opCall can be used on the object, but traits doesn't work on itwritefln(rnd100(), ' ', rnd100(), '\n'); // OK // This line: // ReturnType!(typeof(rnd100)) x; // Raises: // ...\std\traits.d(34): alias std.traits.ReturnType!(BoundFunc).ReturnType recursive alias declaration static if (is(rnd100 TyOut == return)) { TyOut x; writefln(typeid(typeof(x))); } else writefln("No return"); // Prints this } (In the end I have simply solved the problem without std.bind, defining a lambda function.)And here's the solution with Bind: // ---- import std.stdio, std.bind, std.traits, std.random; int randInt(int min, int max) { writefln(`rand1`); int k, n; n = (max - min) + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k + min - 1 : k + min; } int randInt(int max) { writefln(`rand2`); int k, n; n = max + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k - 1 : k; } void main() { // This line: auto rnd = bind(cast(int function(int))&randInt, 100).ptr(); rnd(); auto rnd100 = bind(&randInt, 0, 99).ptr(); writefln( typeid(typeof(rnd100)) , '\n'); writefln(rnd100(), ' ', rnd100(), '\n'); // OK ReturnType!(typeof(rnd100)) x; writefln(typeid(typeof(x))); } // ---- Cheers! -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Aug 24 2007