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); |
---|
| 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 | |
---|
| 532 | Example: |
---|
| 533 | ---- |
---|
| 534 | double transmogrify(int a, string b) |
---|
| 535 | { |
---|
| 536 | ... expensive computation ... |
---|
| 537 | } |
---|
| 538 | alias memoize!transmogrify fastTransmogrify; |
---|
| 539 | unittest |
---|
| 540 | { |
---|
| 541 | auto slow = transmogrify(2, "hello"); |
---|
| 542 | auto fast = fastTransmogrify(2, "hello"); |
---|
| 543 | assert(slow == fast); |
---|
| 544 | } |
---|
| 545 | ---- |
---|
| 546 | |
---|
| 547 | Technically the memoized function should be pure because $(D memoize) assumes it will |
---|
| 548 | always return the same result for a given tuple of arguments. However, $(D memoize) does not |
---|
| 549 | enforce that because sometimes it |
---|
| 550 | is useful to memoize an impure function, too. |
---|
| 551 | |
---|
| 552 | To _memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call. |
---|
| 553 | For example, to transform the exponential-time Fibonacci implementation into a linear-time computation: |
---|
| 554 | |
---|
| 555 | Example: |
---|
| 556 | ---- |
---|
| 557 | ulong fib(ulong n) |
---|
| 558 | { |
---|
| 559 | alias memoize!fib mfib; |
---|
| 560 | return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1); |
---|
| 561 | } |
---|
| 562 | ... |
---|
| 563 | assert(fib(10) == 89); |
---|
| 564 | ---- |
---|
| 565 | |
---|
| 566 | To improve the speed of the factorial function, |
---|
| 567 | |
---|
| 568 | Example: |
---|
| 569 | ---- |
---|
| 570 | ulong fact(ulong n) |
---|
| 571 | { |
---|
| 572 | alias memoize!fact mfact; |
---|
| 573 | return n < 2 ? 1 : n * mfact(n - 1); |
---|
| 574 | } |
---|
| 575 | ... |
---|
| 576 | assert(fact(10) == 3628800); |
---|
| 577 | ---- |
---|
| 578 | |
---|
| 579 | This memoizes all values of $(D fact) up to the largest argument. To only cache the final |
---|
| 580 | result, move $(D memoize) outside the function as shown below. |
---|
| 581 | |
---|
| 582 | Example: |
---|
| 583 | ---- |
---|
| 584 | ulong factImpl(ulong n) |
---|
| 585 | { |
---|
| 586 | return n < 2 ? 1 : n * mfact(n - 1); |
---|
| 587 | } |
---|
| 588 | alias memoize!factImpl fact; |
---|
| 589 | ... |
---|
| 590 | assert(fact(10) == 3628800); |
---|
| 591 | ---- |
---|
| 592 | |
---|
| 593 | The $(D maxSize) parameter is a cutoff for the cache size. If upon a miss the length of the hash |
---|
| 594 | table is found to be $(D maxSize), the table is simply cleared. |
---|
| 595 | |
---|
| 596 | Example: |
---|
| 597 | ---- |
---|
| 598 | // Memoize no more than 128 values of transmogrify |
---|
| 599 | alias memoize!(transmogrify, 128) fastTransmogrify; |
---|
| 600 | ---- |
---|
| 601 | */ |
---|
| 602 | template 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 | |
---|
| 621 | unittest |
---|
| 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); |
---|