问题标记为Python，但使用ctypes调用C++代码也是Python的一个特性。它包含3个版本（我测量了
result = [ackermann(m,n) for m<=3, n <= 17]的时间成本，就像在顶部答案中一样）。
- 使用int64_t和带有记忆化递归 => 32ms。它只适用于小输入（就像顶部答案中的所有算法一样）。它专注于优化递归函数。
- 使用bignum和与上述相同的算法 => 32ms。由于我使用的bignum库是使用64位基本类型实现的，如果结果适合小数，与直接使用
int64_t没有区别。我添加了这个版本，因为评论中提到比较C++的int64_t和Python的无限长度整数是不公平的。
- 使用bignum + 数学公式 => ~~0.14 ms。这个版本也适用于更大的输入。
总结：如果使用数学计算，比最优的Python答案快3000倍以上；如果不使用数学计算，快13-15倍。我使用的是这个单头文件大数库。Stackoverflow有答案长度限制，所以我无法将文件复制到这里。
#include <iostream>
#include <vector>
#include <chrono>
#include <string>
#include "num.hpp"
using namespace std;
class MyTimer {
std::chrono::time_point<std::chrono::system_clock> start;
public:
void startCounter() {
start = std::chrono::system_clock::now();
}
int64_t getCounterNs() {
return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now() - start).count();
}
int64_t getCounterMs() {
return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start).count();
}
double getCounterMsPrecise() {
return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now() - start).count()
/ 1000000.0;
}
};
extern "C" {
int64_t ackermann(int64_t m, int64_t n) {
static std::vector<int64_t> cache[4];
if (m < 0 && n < 0) {
for (int i = 0; i < 4; i++) {
cache[i].resize(0);
cache[i].shrink_to_fit();
}
return -1;
}
if (n >= cache[m].size()) {
int cur = cache[m].size();
cache[m].resize(n + 1);
for (int i = cur; i < n; i++) cache[m][i] = ackermann(m, i);
}
if (cache[m][n]) return cache[m][n];
if (m == 0) return cache[m][n] = n + 1;
if (n == 0) return cache[m][n] = ackermann(m - 1, 1);
return cache[m][n] = ackermann(m - 1, ackermann(m, n - 1));
}
Num ackermann_bignum_smallres(int64_t m, int64_t n) {
static std::vector<Num> cache[4];
if (m < 0 && n < 0) {
for (int i = 0; i < 4; i++) {
cache[i].resize(0);
cache[i].shrink_to_fit();
}
return -1;
}
if (n >= cache[m].size()) {
int cur = cache[m].size();
cache[m].resize(n + 1);
for (int i = cur; i < n; i++) cache[m][i] = ackermann(m, i);
}
if (cache[m][n] > 0) return cache[m][n];
if (m == 0) return cache[m][n] = n + 1;
if (n == 0) return cache[m][n] = ackermann(m - 1, 1);
return cache[m][n] = ackermann(m - 1, ackermann(m, n - 1));
}
Num bignum_pow(const Num& x, const Num& n) {
if (n == 0) return 1;
Num mid = bignum_pow(x, n / 2);
if (n % 2 == 0) return mid * mid;
else return mid * mid * x;
}
Num ackermann_bignum(Num m, Num n) {
if (m <= 1) return n + (m + 1);
else if (m == 2) return Num(2) * n + 3;
else if (m == 3) return bignum_pow(2, n + 3) - 3;
else {
cout << "Don't put m >= 4\n";
exit(1);
}
}
}
Num dummy = 0;
int main(int argc, char* argv[])
{
int test_type = 0;
if (argc > 1) {
try {
test_type = std::stoi(string(argv[1]));
} catch (...) {
test_type = 0;
}
}
int lim = (test_type == 0) ? 63 : 17;
MyTimer timer;
timer.startCounter();
for (int m = 0; m <= 3; m++)
for (int n = 0; n <= lim; n++) {
if (test_type == 0) {
dummy = ackermann_bignum(m, n);
} else if (test_type == 1) {
dummy = ackermann_bignum_smallres(m, n);
} else {
dummy = ackermann(m, n);
}
cout << "ackermann(" << m << ", " << n << ") = " << dummy << "\n";
}
cout << "ackermann cost = " << timer.getCounterMsPrecise() << "\n";
}
使用以下命令编译上述代码：
g++ ackermann.cpp -shared -fPIC -O3 -std=c++17 -o ackermann.so
要单独运行，请使用以下命令：
g++ -o main_cpp ackermann.cpp -O3 -std=c++17
./main_cpp
然后在同一个文件夹中运行这个脚本（修改自@Stefan Pochmann的答案）。
def A_Stefan_row_class(m, n):
class A0:
def __getitem__(self, n):
return n + 1
class A:
def __init__(self, a):
self.a = a
self.n = 0
self.value = a[1]
def __getitem__(self, n):
while self.n < n:
self.value = self.a[self.value]
self.n += 1
return self.value
a = A0()
for _ in range(m):
a = A(a)
return a[n]
from collections import defaultdict
def A_Stefan_row_lists(m, n):
memo = defaultdict(list)
def a(m, n):
if not m:
return n + 1
if m not in memo:
memo[m] = [a(m-1, 1)]
Am = memo[m]
while len(Am) <= n:
Am.append(a(m-1, Am[-1]))
return Am[n]
return a(m, n)
from itertools import count
def A_Stefan_generators(m, n):
a = count(1)
def up(a, x=1):
for i, ai in enumerate(a):
if i == x:
x = ai
yield x
for _ in range(m):
a = up(a)
return next(up(a, n))
def A_Stefan_paper(m, n):
next = [0] * (m + 1)
goal = [1] * m + [-1]
while True:
value = next[0] + 1
transferring = True
i = 0
while transferring:
if next[i] == goal[i]:
goal[i] = value
else:
transferring = False
next[i] += 1
i += 1
if next[m] == n + 1:
return value
def A_Stefan_generators_2(m, n):
def a0():
n = yield
while True:
n = yield n + 1
def up(a):
next(a)
a = a.send
i, x = -1, 1
n = yield
while True:
while i < n:
x = a(x)
i += 1
n = yield x
a = a0()
for _ in range(m):
a = up(a)
next(a)
return a.send(n)
def A_Stefan_m_recursion(m, n):
ix = [None] + [(-1, 1)] * m
def a(m, n):
if not m:
return n + 1
i, x = ix[m]
while i < n:
x = a(m-1, x)
i += 1
ix[m] = i, x
return x
return a(m, n)
def A_Stefan_function_stack(m, n):
def a(n):
return n + 1
for _ in range(m):
def a(n, a=a, ix=[-1, 1]):
i, x = ix
while i < n:
x = a(x)
i += 1
ix[:] = i, x
return x
return a(n)
from itertools import count, islice
def A_Stefan_generator_stack(m, n):
a = count(1)
for _ in range(m):
a = (
x
for a, x in [(a, 1)]
for i, ai in enumerate(a)
if i == x
for x in [ai]
)
return next(islice(a, n, None))
from itertools import count, islice
def A_Stefan_generator_stack2(m, n):
a = count(1)
def up(a):
i, x = 0, 1
while True:
i, x = x+1, next(islice(a, x-i, None))
yield x
for _ in range(m):
a = up(a)
return next(islice(a, n, None))
def A_Stefan_generator_stack3(m, n):
def a(m):
if not m:
yield from count(1)
x = 1
for i, ai in enumerate(a(m-1)):
if i == x:
x = ai
yield x
return next(islice(a(m), n, None))
def A_Stefan_generator_stack4(m, n):
def a(m):
if not m:
return count(1)
return (
x
for x in [1]
for i, ai in enumerate(a(m-1))
if i == x
for x in [ai]
)
return next(islice(a(m), n, None))
def A_templatetypedef(i, n):
positions = [-1] * (i + 1)
values = [0] + [1] * i
while positions[i] != n:
values[0] += 1
positions[0] += 1
j = 1
while j <= i and positions[j - 1] == values[j]:
values[j] = values[j - 1]
positions[j] += 1
j += 1
return values[i]
import ctypes
mylib = ctypes.CDLL('./ackermann.so')
mylib.ackermann.argtypes = [ctypes.c_int64, ctypes.c_int64]
mylib.ackermann.restype = ctypes.c_int64
def c_ackermann(m, n):
return mylib.ackermann(m,n)
funcs = [
c_ackermann,
A_Stefan_row_class,
A_Stefan_row_lists,
A_Stefan_generators,
A_Stefan_paper,
A_Stefan_generators_2,
A_Stefan_m_recursion,
A_Stefan_function_stack,
A_Stefan_generator_stack,
A_Stefan_generator_stack2,
A_Stefan_generator_stack3,
A_Stefan_generator_stack4,
A_templatetypedef
]
N = 18
args = (
[(0, n) for n in range(N)] +
[(1, n) for n in range(N)] +
[(2, n) for n in range(N)] +
[(3, n) for n in range(N)]
)
from time import time
def print(*args, print=print, file=open('out.txt', 'w')):
print(*args)
print(*args, file=file, flush=True)
expect = none = object()
for _ in range(3):
for f in funcs:
t = time()
result = [f(m, n) for m, n in args]
print(f'{(time()-t) * 1e3 :5.0f} ms ', f.__name__)
if expect is none:
expect = result
elif result != expect:
raise Exception(f'{f.__name__} failed')
del result
print()
c_ackermann(-1, -1)
输出：
32 ms c_ackermann
1897 ms A_Stefan_row_class
1427 ms A_Stefan_row_lists
437 ms A_Stefan_generators
1366 ms A_Stefan_paper
479 ms A_Stefan_generators_2
801 ms A_Stefan_m_recursion
725 ms A_Stefan_function_stack
716 ms A_Stefan_generator_stack
1113 ms A_Stefan_generator_stack2
551 ms A_Stefan_generator_stack3
682 ms A_Stefan_generator_stack4
1622 ms A_templatetypedef
print(m, n)，然后调用A(3, 2)。你会看到重复的值一次又一次地出现。例如，A(1, 5)被调用了16次。缓存肯定会使它更快。 - user2390182print(m, n)语句并调用A(3, 2)，你会看到重复的值一次又一次地出现。例如，A(1, 5)被调用了16次。缓存绝对会使其更快。 - user2390182