鉴于此算法，我想知道是否存在迭代版本。 另外，我想知道迭代版本是否可以更快。
这是一种伪python ...
该算法返回对树的根的引用
make_tree(array a) if len(a) == 0 return None; node = pick a random point from the array calculate distances of the point against the others calculate median of such distances node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances) node.right = make_tree(subset, such the distance is greater or equal to the median) return nodeGiven this algorithm, I would like to know if there exists an iterative version. Also, I want to know if the iterative version can be faster.
This some kind of pseudo-python...
the algorithm returns a reference to root of the tree
make_tree(array a) if len(a) == 0 return None; node = pick a random point from the array calculate distances of the point against the others calculate median of such distances node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances) node.right = make_tree(subset, such the distance is greater or equal to the median) return node最满意答案
只有一次递归调用的递归函数通常可以转化为尾递归函数，而不需要太多努力，然后将其转换为迭代函数是微不足道的。 这里的典型例子是阶乘：
# naïve recursion def fac(n): if n <= 1: return 1 else: return n * fac(n - 1) # tail-recursive with accumulator def fac(n): def fac_helper(m, k): if m <= 1: return k else: return fac_helper(m - 1, m * k) return fac_helper(n, 1) # iterative with accumulator def fac(n): k = 1 while n > 1: n, k = n - 1, n * k return k但是，您的情况涉及两个递归调用，除非您重新修改算法，否则需要保留堆栈。 管理自己的堆栈可能比使用Python的函数调用堆栈快一点，但增加的速度和深度可能不值得这样复杂。 这里的典型例子是斐波那契数列：
# naïve recursion def fib(n): if n <= 1: return 1 else: return fib(n - 1) + fib(n - 2) # tail-recursive with accumulator and stack def fib(n): def fib_helper(m, k, stack): if m <= 1: if stack: m = stack.pop() return fib_helper(m, k + 1, stack) else: return k + 1 else: stack.append(m - 2) return fib_helper(m - 1, k, stack) return fib_helper(n, 0, []) # iterative with accumulator and stack def fib(n): k, stack = 0, [] while 1: if n <= 1: k = k + 1 if stack: n = stack.pop() else: break else: stack.append(n - 2) n = n - 1 return k现在，你的情况比这更艰难：一个简单的累加器将难以表达一个指向需要生成子树的指针的部分构建的树。 你会需要一个拉链 - 不容易在Python这样的非真正功能的语言中实现。
A recursive function with only one recursive call can usually be turned into a tail-recursive function without too much effort, and then it's trivial to convert it into an iterative function. The canonical example here is factorial:
# naïve recursion def fac(n): if n <= 1: return 1 else: return n * fac(n - 1) # tail-recursive with accumulator def fac(n): def fac_helper(m, k): if m <= 1: return k else: return fac_helper(m - 1, m * k) return fac_helper(n, 1) # iterative with accumulator def fac(n): k = 1 while n > 1: n, k = n - 1, n * k return kHowever, your case here involves two recursive calls, and unless you significantly rework your algorithm, you need to keep a stack. Managing your own stack may be a little faster than using Python's function call stack, but the added speed and depth will probably not be worth the complexity. The canonical example here would be the Fibonacci sequence:
# naïve recursion def fib(n): if n <= 1: return 1 else: return fib(n - 1) + fib(n - 2) # tail-recursive with accumulator and stack def fib(n): def fib_helper(m, k, stack): if m <= 1: if stack: m = stack.pop() return fib_helper(m, k + 1, stack) else: return k + 1 else: stack.append(m - 2) return fib_helper(m - 1, k, stack) return fib_helper(n, 0, []) # iterative with accumulator and stack def fib(n): k, stack = 0, [] while 1: if n <= 1: k = k + 1 if stack: n = stack.pop() else: break else: stack.append(n - 2) n = n - 1 return kNow, your case is a lot tougher than this: a simple accumulator will have difficulties expressing a partly-built tree with a pointer to where a subtree needs to be generated. You'll want a zipper -- not easy to implement in a not-really-functional language like Python.
更多推荐
发布评论