Changeset 2271

Show
Ignore:
Timestamp:
01/03/11 22:46:01 (4 years ago)
Author:
andrei
Message:

Added memoize

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved
  • trunk/phobos/std/functional.d

    r2195 r2271  
    99 
    1010Copyright: Copyright Andrei Alexandrescu 2008 - 2009. 
    11 License:   <a href="http://www.boost.org/LICENSE_1_0.txt">Boost License 1.0</a>
     11License:   $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0)
    1212Authors:   $(WEB erdani.org, Andrei Alexandrescu) 
    1313*/ 
     
    501501---- 
    502502 */ 
    503  
    504503template pipe(fun...) 
    505504{ 
     
    509508unittest 
    510509{ 
    511     // string foo(int a) { return to!(string)(a); } 
    512     // int bar(string a) { return to!(int)(a) + 1; } 
    513     // double baz(int a) { return a + 0.5; } 
    514     // assert(compose!(baz, bar, foo)(1) == 2.5); 
    515     // assert(pipe!(foo, bar, baz)(1) == 2.5); 
    516  
    517     // assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5); 
    518     // assert(compose!(baz, bar)("1"[]) == 2.5); 
    519  
    520     // @@@BUG@@@ 
    521     //assert(compose!(baz, bar)("1") == 2.5); 
     510    string foo(int a) { return to!(string)(a); } 
     511    int bar(string a) { return to!(int)(a) + 1; } 
     512    double baz(int a) { return a + 0.5; } 
     513    assert(compose!(baz, bar, foo)(1) == 2.5); 
     514    assert(pipe!(foo, bar, baz)(1) == 2.5); 
     515 
     516    assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5); 
     517    assert(compose!(baz, bar)("1"[]) == 2.5); 
     518 
     519    assert(compose!(baz, bar)("1") == 2.5); 
    522520 
    523521    // @@@BUG@@@ 
    524522    //assert(compose!(`a + 0.5`, `to!(int)(a) + 1`, foo)(1) == 2.5); 
     523} 
     524 
     525/** 
     526 * $(LUCKY Memoizes) a function so as to avoid repeated 
     527 * computation. The memoization structure is a hash table keyed by a 
     528 * tuple of the function's arguments. There is a speed gain if the 
     529 * function is repeatedly called with the same arguments and is more 
     530 * expensive than a hash table lookup. 
     531 
     532Example: 
     533---- 
     534double transmogrify(int a, string b) 
     535{ 
     536   ... expensive computation ... 
     537} 
     538alias memoize!transmogrify fastTransmogrify; 
     539unittest 
     540{ 
     541    auto slow = transmogrify(2, "hello"); 
     542    auto fast = fastTransmogrify(2, "hello"); 
     543    assert(slow == fast); 
     544} 
     545---- 
     546 
     547Technically the memoized function should be pure because $(D memoize) assumes it will 
     548always return the same result for a given tuple of arguments. However, $(D memoize) does not 
     549enforce that because sometimes it 
     550is useful to memoize an impure function, too. 
     551   
     552To _memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call. 
     553For example, to transform the exponential-time Fibonacci implementation into a linear-time computation: 
     554 
     555Example: 
     556---- 
     557ulong fib(ulong n) 
     558{ 
     559    alias memoize!fib mfib; 
     560    return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1); 
     561} 
     562... 
     563assert(fib(10) == 89); 
     564---- 
     565 
     566To improve the speed of the factorial function,  
     567 
     568Example: 
     569---- 
     570ulong fact(ulong n) 
     571{ 
     572    alias memoize!fact mfact; 
     573    return n < 2 ? 1 : n * mfact(n - 1); 
     574} 
     575... 
     576assert(fact(10) == 3628800); 
     577---- 
     578 
     579This memoizes all values of $(D fact) up to the largest argument. To only cache the final 
     580result, move $(D memoize) outside the function as shown below. 
     581 
     582Example: 
     583---- 
     584ulong factImpl(ulong n) 
     585{ 
     586    return n < 2 ? 1 : n * mfact(n - 1); 
     587} 
     588alias memoize!factImpl fact; 
     589... 
     590assert(fact(10) == 3628800); 
     591---- 
     592 
     593The $(D maxSize) parameter is a cutoff for the cache size. If upon a miss the length of the hash 
     594table is found to be $(D maxSize), the table is simply cleared. 
     595 
     596Example: 
     597---- 
     598// Memoize no more than 128 values of transmogrify 
     599alias memoize!(transmogrify, 128) fastTransmogrify; 
     600---- 
     601*/ 
     602template memoize(alias fun, uint maxSize = uint.max) 
     603{ 
     604    ReturnType!fun memoize(ParameterTypeTuple!fun args) 
     605    { 
     606        static ReturnType!fun[Tuple!(typeof(args))] memo; 
     607        auto t = tuple(args); 
     608        auto p = t in memo; 
     609        if (p) return *p; 
     610        static if (maxSize != uint.max) 
     611        { 
     612            if (memo.length >= maxSize) memo = null; 
     613        } 
     614        auto r = fun(args); 
     615        //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for parameters ", t); 
     616        memo[t] = r; 
     617        return r; 
     618    } 
     619} 
     620 
     621unittest 
     622{ 
     623    alias memoize!(function double(double x) { return sqrt(x); }) msqrt; 
     624    auto y = msqrt(2.0); 
     625    assert(y == msqrt(2.0)); 
     626    y = msqrt(4.0); 
     627    assert(y == sqrt(4.0)); 
     628     
     629    // alias memoize!rgb2cmyk mrgb2cmyk; 
     630    // auto z = mrgb2cmyk([43, 56, 76]); 
     631    // assert(z == mrgb2cmyk([43, 56, 76])); 
     632 
     633    //alias memoize!fib mfib; 
     634 
     635    static ulong fib(ulong n) 
     636    { 
     637        alias memoize!fib mfib; 
     638        return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1); 
     639    } 
     640 
     641    auto z = fib(10); 
     642    assert(z == 89); 
     643 
     644    static ulong fact(ulong n) 
     645    { 
     646        alias memoize!fact mfact; 
     647        return n < 2 ? 1 : n * mfact(n - 1); 
     648    } 
     649    assert(fact(10) == 3628800); 
    525650} 
    526651 
     
    571696} 
    572697 
    573 /**Convert a callable to a delegate with the same parameter list and 
     698/** 
     699 * Convert a callable to a delegate with the same parameter list and 
    574700 * return type, avoiding heap allocations and use of auxiliary storage. 
    575701 * 
    576702 * Examples: 
    577  * --- 
     703 * ---- 
    578704 * void doStuff() { 
    579705 *     writeln("Hello, world."); 
     
    586712 * auto delegateToPass = toDelegate(&doStuff); 
    587713 * runDelegate(delegateToPass);  // Calls doStuff, prints "Hello, world." 
    588  * --- 
     714 * ---- 
    589715 * 
    590716 * BUGS: 
     
    594720 * ) 
    595721 */ 
    596 auto toDelegate(F)(auto ref F fp) if (isCallable!(F)) { 
    597  
     722auto toDelegate(F)(auto ref F fp) if (isCallable!(F)) 
     723
    598724    static if (is(F == delegate)) 
    599725    { 
     
    727853    } 
    728854} 
     855