0

以下に示すコードは機能します。Pythonでは再帰の使用は効果的ではないと思います。どうすればforループバージョンに変換できますか？

def fun(x1, y1, x2, y2, n, r=[]):
    if n<1 :
        return
    r.append( [[x1,y1],[x2,y2]])
    x3=(x1+x2)/2.0
    y3=(y1+y2)/2.0
    fun(x1,y1,x3,y3, n-1)
    fun(x3,y3,x2,y2,n-1)

    x4=(x2+y2-y3-x3)*0.7+x3;
    y4 = (y2 - x2 + x3 - y3)*0.7 + y3;
    fun(x3, y3, x4, y4, n - 1);

    x3 = (3* x1 + x2)/4;
    y3 = (3* y1 + y2)/4;
    x2 = (3*x2 + x1)/4;
    y2 = (3*y2 + y1)/4;
    x4 = (x2*1.7 - y2 + 2*x3 - x3*1.7 + y3)/2;
    y4 = (x2 + y2*1.7 - x3 + 2*y3 - 1.7*y3)/2;
    fun(x3, y3, x4, y4, n - 1);
    return r

print fun(200, 400, 200, 0, 9).__len__()
4

1 に答える 1

2

より多くのメモリを使用して再帰関数を高速化するために、メモ化のようなものを検討することをお勧めします。基本的に、呼び出しの結果をキャッシュに保存します。

次のコードを追加します

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

次に、このように関数を飾ります

@memoized
def fun(x1, y1, x2, y2, n, r=[]):
    ...

オプションのパラメータにも注意してください。によって作成されたリストは、r = []実際にはrを使用したfのすべての呼び出しで共有されます。毎回新しいリストが作成されるように、このようなことを行うことをお勧めします。

def fun(x1, y1, x2, y2, n, r=None):
    r = [] if r is None else r

長さを取得するためのよりPythonicな方法は次のとおりです

print len(fun(200, 400, 200, 0, 9))
于 2013-02-25T04:38:06.200 に答える