5 ms·
Hidden treasure in the D standard library
- pyed 12y agoHaskell has treasures.
- Shorel 12y agoMemoization is one the most useful things I learned about in Common Lisp. Glad to see it in D. It allows the program to have recursive algorithms with the performance of optimized for loops.
- blt 12y agoMemoization is pretty easy to implement yourself without any special language support. It's cool to make it part of the standard library but it's not like some magic sauce. Especially given that D always uses hash tables. In the Fibonacci example given, a simple array would have much, much better performance.
- repsilat 12y ago> In the Fibonacci example given, a simple array would have much, much better performance. When I looked at the output of the hash function in Python for integers a few weeks ago it looked like the identity function was being used. You'll still have greater complexity than an array, but I'm not sure how much greater.
- Shorel 12y agoIt was dead easy in Common Lisp. That's the most impressive thing about it.
- jacobwcarlson 12y agoTail call optimization is necessary as well (or at least extremely beneficial). I don't know enough about D compilers to say whether or not they do this, but this discussion gives a strong "perhaps?": http://forum.dlang.org/thread/jk5jc0$25cd$1@digitalmars.com http://forum.dlang.org/thread/jk5jc0$25cd$1@digitalmars.com
- yoklov 12y agoNot really. Only if a hash table lookup is the first part of every iteration of the for loop. It does allow some recursive algorithms to reduce their algorithmic complexity significantly, however.
- thinkpad20 12y agoI'm curious how D implements memoizing an arbitrary function. To memoize something, you need to be able to check if it's being called with the same arguments. But to do that, you need a definition of "same" (i.e., an equivalence relation). For example, if the argument is a dictionary, is it considered the same argument only if the pointer is the same, or if the keys and values are the same, assuming a recursive definition of "same"? Also, you need a way to store computed values, using the arguments as keys, which for efficiency would require either an ordering (for a tree) or hashing (for a hash table) on the arguments. Multiple arguments would further complicate things. How does this get automated? And for some things, memoization wouldn't make sense (for example, with function arguments in higher-order functions). Sensible defaults would take care of most of these things, but it makes me wonder how they chose to address these things. And is the memo recreated each time the (outer) function is called, or is it stored for the duration of the program? Also, how does the type system play with this? What's the type of `memoize!`?
- jnetterf 12y agoThe standard library (Phobos) is open source. You can find the implementation of memoize at https://github.com/D-Programming-Language/phobos/blob/6cd2e43eab2b0e4c5c6cc7bbfd30cbd5e132735d/std/functional.d#L680 https://github.com/D-Programming-Language/phobos/blob/6cd2e4... memoize is a template (http://dlang.org/template.html http://dlang.org/template.html). In this case, a template is used to create a "version" of "memoize" with the right parameters and return value (i.e., `fn` and `memoize!fn` are the same type). Each of these "versions" has a hash table from argument tuples to results. I believe the hash is computed by calling a toHash function for each item in the tuple. Tuples and type tuples (http://dlang.org/tuple.html http://dlang.org/tuple.html) in D are really quite powerful.
- Zardoz84 12y agoI recommend try std.parallelism. I did a test with a n Body simulator and runs very well on a 15 core machine with a speed up around x13-14 over the serial version. https://github.com/Zardoz89/nBodySim https://github.com/Zardoz89/nBodySim
- tonysuper 12y agoThe "flag" example could be easily replaced with named parameters. Seems a bit unnecisary to add a new type for that purpose, unless I'm missing something.
- asterite 12y agoYou are not missing anything: named parameters would have been a much nicer choice, but I think they don't want to make the language more complex.
- EvenThisAcronym 12y agoAre there any plans to add named arguments a la C# or Python in the future?
- renox 12y agoCurrently 'the plate is full': D is full of features and many of them are not finished/polished so I doubt that they will add such kind of feature in the near future..