再帰Rangeをメモ化する

C++ Boost.Range
  • 前回のfibonacciは20番目くらいでシステムに支障を来たしてしまうほど遅い
  • メモ化するといい
  • メモ化の実装であるmulti_passは、デフォルトで、メモ用のコンテナに参照カウントを使うのだが、見てのとおり循環参照が起きてリークする
  • first_ownerというポリシークラスがちゃんと用意されていた
  • これで一瞬で終わるようになった (実装)

[]typedef[] []any_range[][]< [][]int[][], [][]recursive[][]<> > [][]range_t[][];[]


[]memo_table[] []to_table[][];[]

[]range_t[] []fibs[][];[]

[]int[] []const[] []start[][][] = { [][]1[][], [][]1[][] };[]

[]fibs[][] =[]

    []start[][]|[][]transformed[][]([][]pstade[][]::[][]as_value[][])|[]

        []jointed[][]([]

            []boost[][]::[][]make_tuple[][]([][]recursion[][]([][]fibs[][]), [][]recursion[][]([][]fibs[][])|[][]dropped[][]([][]1[][]))|[]

            []zipped_with[][]([][]regular[][]([][]lambda[][]::[][]_1[][] + [][]lambda[][]::[][]_2[][]))[]

[]        )[]

[]         | [][]memoized[][]([][]to_table[][])[]

[];[]
[]std[][]::[][]cout[][] << ([][]fibs[][]|[][]taken[][]([][]30[][]));[]