www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - best way to memoize a range?

reply "Laeeth Isharc" <spamnolaeeth nospamlaeeth.com> writes:
obviously it's trivial to do with a little aa cache.  and I know 
I can memoize a function, and turn the memoized version into an 
infinite range.  but suppose I have a lazy function that returns 
a finite range, and its expensive to calculate.

can I use Phobos to produce a memoized range?  So it will 
calculate on access to an element if it needs to, but will return 
the cached value if it has been calculated before.
Sep 11 2015
next sibling parent "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Friday, 11 September 2015 at 13:09:33 UTC, Laeeth Isharc wrote:
 obviously it's trivial to do with a little aa cache.  and I 
 know I can memoize a function, and turn the memoized version 
 into an infinite range.  but suppose I have a lazy function 
 that returns a finite range, and its expensive to calculate.

 can I use Phobos to produce a memoized range?  So it will 
 calculate on access to an element if it needs to, but will 
 return the cached value if it has been calculated before.
Is your range random access? If not, `cache` should do the trick. [1] http://dlang.org/phobos/std_algorithm_iteration.html#cache
Sep 11 2015
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 11 September 2015 at 13:09:33 UTC, Laeeth Isharc wrote:
 obviously it's trivial to do with a little aa cache.  and I 
 know I can memoize a function, and turn the memoized version 
 into an infinite range.  but suppose I have a lazy function 
 that returns a finite range, and its expensive to calculate.

 can I use Phobos to produce a memoized range?  So it will 
 calculate on access to an element if it needs to, but will 
 return the cached value if it has been calculated before.
perhaps http://dlang.org/phobos/std_algorithm_iteration.html#.cache would do what you need. An AA based cache (with a normal range interface if you want) is probably the sensible way to get true random-access here, unless you have reasonably dense and monotonic accesses in which case an appender-based linear cache could work, either using Nullable!T or a separate list of bools (or bits) marking whether a result is cached yet.
Sep 11 2015
parent "Laeeth Isharc" <spamnolaeeth nospamlaeeth.com> writes:
On Friday, 11 September 2015 at 13:31:06 UTC, John Colvin wrote:
 On Friday, 11 September 2015 at 13:09:33 UTC, Laeeth Isharc 
 wrote:
 obviously it's trivial to do with a little aa cache.  and I 
 know I can memoize a function, and turn the memoized version 
 into an infinite range.  but suppose I have a lazy function 
 that returns a finite range, and its expensive to calculate.

 can I use Phobos to produce a memoized range?  So it will 
 calculate on access to an element if it needs to, but will 
 return the cached value if it has been calculated before.
perhaps http://dlang.org/phobos/std_algorithm_iteration.html#.cache would do what you need. An AA based cache (with a normal range interface if you want) is probably the sensible way to get true random-access here, unless you have reasonably dense and monotonic accesses in which case an appender-based linear cache could work, either using Nullable!T or a separate list of bools (or bits) marking whether a result is cached yet.
Thanks, John and Jacob. Laeeth.
Sep 11 2015