Python 递归算法不适用于大值 - C 程序有效

Question

我想为 this question 编写回溯解决方案，它要求找到总和为给定 n 的最不同的奇数。

我破解了这段 Python 代码:

import sys
sys.setrecursionlimit(10000) 


stop = False
def solve(n, used, current_sum):
    global stop
    if stop:
        return

    if current_sum == n:
        print(used)
        stop = True
        return

    start = 1 if len(used) == 0 else (used[-1] + 2)
    for i in range(start, n + 1, 2):
        if current_sum + i <= n and not stop:
            used.append(i)
            solve(n, used, current_sum + i)
            used.pop()
        else:
            return

solve(100000000, [], 0)

不幸的是，它没有为我打印任何东西。据我所知，它永远不会达到 if 条件。如果我在每一步都打印 current_sum，当整个程序没有错误地退出时，它似乎只是停在 16000000 左右。

我尝试增加递归限制，但没有成功。

我在 Windows 8.1 下使用 Python 3.4、64 位在 Idle 和 Eclipse 上对其进行了测试。我有 16 GB 的 RAM。

如果我减少 n，那么我会得到一个解决方案(例如删除一个零)。

这对我来说没有意义，所以我想看看我是否在 C 中有更好的运气。我在 C 中破解了这个:

int sol[100000];
bool done = false;
void solve(int n, int k, int sum)
{
    if (done)
        return;

    if (sum == n)
    {
        done = true;
        for (int i = 0; i < k; ++i)
        {
            printf("%d ", sol[i]);
        }
        printf("\n");
        return;
    }

    int start = 1;
    if (k > 0)
        start = sol[k - 1] + 2;
    for (int i = start; i <= n; i += 2)
        if (sum + i <= n && !done)
        {
            sol[k] = i;
            solve(n, k + 1, sum + i);
        }
        else
            return;
}

int main()
{
    solve(100000000, 0, 0);

    return 0;
}

即使我再添加一个零，效果也很好!

Python 有什么问题，我怎样才能让它也适用于大值？

较低值的执行时间与 C 代码相当，它只是在我身上退出较高的值。

Answer 1

What is the deal with Python and how can I get this working for large values as well?

我重写了您的代码以使其工作。当您增加 n 参数时，您需要调整递归深度。我使用的是 Python 2.7.6。想法是按照与您编写的 C 代码相同的方式执行此操作，传递的第二个参数将是一个整数而不是列表。

import sys
sys.setrecursionlimit(100000) 

sol = []
stop = False

def solve(n, k, current_sum):
    global stop

    if stop:
        return

    if current_sum == n:
    stop = True
    for i in xrange(0, k, 1):
            print(sol[i]),
    print
        return

    start = 1 if len(sol) == 0 else (sol[k-1] + 2)
    for i in xrange(start, n + 1, 2):
        if current_sum + i <= n and not stop:
        sol.append(0)
        sol[k] = i
            solve(n, k + 1, current_sum + i)
        else:
            return

solve(100000000, 0, 0)

---

问题讨论

我试图读取您编写的 python 代码的内存使用情况。我必须设置 n = 100.000 才能获得 370 MB 的结果。添加 0 会使我的操作系统终止该程序。 (在 Mac OS X 上我收到内存错误)。

这是我在 Linux 上使用的代码:

import os
import sys

sys.setrecursionlimit(100000)


_proc_status = '/proc/%d/status' % os.getpid()

_scale = {'kB': 1024.0, 'mB': 1024.0*1024.0,
          'KB': 1024.0, 'MB': 1024.0*1024.0}

def _VmB(VmKey):
    '''Private.
    '''
    global _proc_status, _scale
     # get pseudo file  /proc/<pid>/status
    try:
        t = open(_proc_status)
        v = t.read()
        t.close()
    except:
        return 0.0  # non-Linux?
     # get VmKey line e.g. 'VmRSS:  9999  kB\n ...'
    i = v.index(VmKey)
    v = v[i:].split(None, 3)  # whitespace
    if len(v) < 3:
        return 0.0  # invalid format?
     # convert Vm value to bytes
    return float(v[1]) * _scale[v[2]]

def memory(since=0.0):
    '''Return memory usage in bytes.
    '''
    return _VmB('VmSize:') - since


stop = False
def solve(n, used, current_sum):
    global stop

    if stop:
        return

    if current_sum == n:
        print(used)
        stop = True
        return

    start = 1 if len(used) == 0 else (used[-1] + 2)
    for i in range(start, n + 1, 2):
        if current_sum + i <= n and not stop:
            used.append(i)
            solve(n, used, current_sum + i)
            used.pop()
        else:
            return

m0 = memory()
solve(100000, [], 0)
m1 = memory(m0)
print(m1/(1024*1024))

与此结果相比，我编写的改进(更正)代码仅使用 4 MB，参数 n 设置为 100.000.000 .这确实是一个巨大的差异。

我不确定这是为什么。特别是你有一个包含递归调用的循环(所以你从同一个分支多次递归调用)。

如果您坚持使用递归调用，那么也许您需要重新设计您的程序。在案例中，带内存的递归调用比循环更快。参见 this link for example .