python - 这个算法优化了吗？还有其他用途吗？

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
我正在研究一个欧拉问题（on-topic）。我已经用另一种方法解决了这个问题，但是我很好奇如何优化我最初试图解决这个问题的算法，因为它增长得非常快，并且对实际需要多长时间感到有点惊讶所以我真的很想学习如何分析和继续优化算法。
此算法的方法是使用角点作为点-(0,0)在左上角，(2,2)在左下角为2x2网格从顶点开始，路径将仅为x+1或y+1。因此，我通过检查网格中的点空间是否存在下一个允许的移动来迭代地形成这些路径。
我最初是从左上角开始的，但发现从底部向后走，去掉一些冗余，开始只将有价值的数据存储在内存中会更有效。所以我现在就在那里能否进一步优化？还有其他类型的应用程序呢？
(x+1, y+1)是网格中所有点的列表，存储为字符串-iegivenPoints算法存储唯一路径的最新点，而不是整个路径，最后列表中的条目数与唯一路径数相等。

def calcPaths4(givenPoints):
    paths = []
    paths.append(givenPoints[-1])
    dims = int(math.sqrt(len(givenPoints))) - 1
    numMoves = 2*dims
    numPaths = 0

    for x in range(0,numMoves):
        t0= time.clock()
        newPaths = []
        for i in paths:
            origin = int(i)
            dest1 = origin - 1
            dest3 = origin - 100
            if ('%04d' % dest1) in givenPoints:
                newPaths.append(('%04d' % dest1))
                numPaths +=1
            if ('%04d' % dest3) in givenPoints:
                newPaths.append(('%04d' % dest3))
                numPaths +=1
        t= time.clock() - t0
        paths = newPaths
        print(str(x)+": " +str(t)+": " +str(len(paths)) )
    return(paths)

最佳答案

你的方法不对从左上角开始到右下角需要向右移动20步，向下移动20步。
因此，您可以将任何路径看作一个长度为20的序列，其中有10个元素right和10个元素down你只需计算一下有多少欠款。
一旦你修正了，比如说，right移动了down移动，那么整个问题就减少到：你可以从20个位置中选择10个位置的方法有多少？
这可以通过binomial coefficient简单地解决。
因此，解决方案是：

from math import factorial

def number_of_paths(k):
    """Number of paths from the top left and bottom right corner in a kxk grid."""
    return factorial(2*k)//(factorial(k)**2)

通过注意以下几点可以提高效率：

import operator as op
from functools import reduce

def number_of_paths(k):
    """Number of paths from the top left and bottom right corner in a kxk grid."""
    return reduce(op.mul, range(2*k, k, -1), 1)//factorial(k)

注意，路径的数量增长很快，这意味着通过创建不同路径来工作的任何算法都将很慢认真“优化”的唯一方法是改变方法，避免创建路径，而只计算路径。
我要指出另一种更通用的方法：递归和记忆/动态编程。
当路径位于某个位置时，它可以直接转到n!/(k!*k!) = (n·(n-1)···(k+1))/k!或向下转到(x,y)因此，从该点到右下角的路径数是从(x-1,y)到达右下角的路径数和从(x, y-1)到达右下角的路径数之和：
基本情况是当您处于边缘时，即(x-1,y)或(x, y-1)。

def number_of_paths(x, y):
    if not x or not y:
        return 1
    return number_of_paths(x-1, y) + number_of_paths(x, y-1)

这个解决方案遵循您的推理，但它只跟踪路径的数量你可以再次看到这是非常低效的。
问题是当我们试图计算x==0
我们最终执行以下步骤：
计算y==0
这是通过计算number_of_paths(x, y)和number_of_paths(x-1, y)
计算number_of_paths(x-2, y)
这是通过计算number_of_paths(x-1, y-1)和number_of_paths(x, y-1)
注意如何计算两次number_of_paths(x-1, y-1)但结果显然是一样的因此，我们可以在第一次计算时，在下一次看到调用时，返回已知的结果：

def number_of_paths(x, y, table=None):
    table = table if table is not None else {(0,0):1}
    try:
        # first look if we already computed this:
        return table[x,y]
    except KeyError:
        # okay we didn't compute it, so we do it now:
        if not x or not y:
            result = table[x,y] = 1
        else:
            result = table[x,y] = number_of_paths(x-1, y, table) + number_of_paths(x, y-1, table)
        return result

现在它执行得相当快：

>>> number_of_paths(20,20)
137846528820

你可以认为“执行两次呼叫，没什么大不了的”，但你必须考虑到，如果对number_of_paths(x, y-2)的呼叫计算两次，那么每次对number_of_paths(x-1, y-1)进行两次呼叫，就会导致计算4次然后(x-1,y-1)八次，…然后(x-2, y-2)1048576次！
或者，我们可以构建一个(x-2, y-2)矩阵并从右下角填充它：

def number_of_paths(x, y):
    table = [[0]*(x+1) for _ in range(y+1)]
    table[-1][-1] = 1
    for i in reversed(range(x+1)):
        for j in reversed(range(y+1)):
            if i == x or j == y:
                table[i][j] = 1
            else:
                table[i][j] = table[i+1][j] + table[i][j+1]
    return table[0][0]

请注意，这里的表表示交叉点，因此在大小上以a(x-3, y-3)结束。
这种记忆以前的调用以在以后重用它们的技术称为记忆。一个更普遍的原则是动态编程，在这里你基本上把问题减少到填充一个表格数据结构，就像我们在这里所做的那样，使用递归和记忆，然后你通过使用之前填充的指针来“回溯”单元格，以获得原始问题的解决方案。