解决方案

我最近写了一堆解决方案，都是基于templatetypedef提到的那篇论文。许多使用生成器，每个m值一个，产生n = 0，n = 1，n = 2等的值。这一个可能是我最喜欢的：

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))

说明

考虑生成器a(m)。它产生A（m，0）、A（m，1）、A（m，2）等。A（m，n）的定义使用A（m-1，A（m，n-1））。因此a(m)在其索引n处产生A（m，n），计算如下：

• A（m，n-1）由a(m)生成器本身在索引n-1处产生。它就是这个生成器产生的前一个值（x）。
• A（m-1，A（m，n-1））= A（m-1，x）由a(m-1)生成器在索引x处产生。因此a(m)生成器迭代a(m-1)生成器，并获取索引i == x处的值。

基准测试

以下是计算所有A（m，n）的时间，其中m ≤ 3且n ≤ 17，也包括templatetypedef的解：

1325 ms  A_Stefan_row_class
 1228 ms  A_Stefan_row_lists
  544 ms  A_Stefan_generators
 1363 ms  A_Stefan_paper
  459 ms  A_Stefan_generators_2
  866 ms  A_Stefan_m_recursion
  704 ms  A_Stefan_function_stack
  468 ms  A_Stefan_generator_stack
  945 ms  A_Stefan_generator_stack2
  582 ms  A_Stefan_generator_stack3
  467 ms  A_Stefan_generator_stack4
 1652 ms  A_templatetypedef

注意：使用数学见解/公式的解决方案甚至更快（* 快得多 *）是可能的，请参阅我的评论和pts's answer。我故意没有这样做，因为我对 * 编码 * 技术感兴趣，以避免深度递归和避免 * 重新 * 计算。我得到的印象是，这也是问题/OP想要的，他们现在证实了这一点（在删除的答案下，如果你有足够的声誉，可见）。

代码

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]

funcs = [
    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.1f} ms ', f.__name__)
    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()

v0基本上就是你的代码：

def ack(m, n):
  if m == 0: return n + 1
  return ack(m - 1, 1) if n == 0 else ack(m - 1, ack(m, n - 1))

这在2.49s内计算ack（3，9）。ack（）被调用11164370次。当然，我们可以缓存已经计算的值，从而节省对函数的大量调用。
v1对缓存使用dict，并且仅当结果不在该高速缓存中时才进行计算：

c = {}

def ack(m, n):
  global c

  if "{}-{}".format(m, n) in c: return c["{}-{}".format(m, n)]
  else:
    if m == 0: ret = n + 1
    else: ret = ack(m - 1, 1) if n == 0 else ack(m - 1, ack(m, n - 1))

    c["{}-{}".format(m, n)] = ret
    return ret

这在0.03s内计算ack（3，9），并且ack（3，9）不再适合于测量执行时间。这次ack（）被调用了12294次，节省了大量的时间。但我们可以做得更好。从现在开始，我们使用ack（3，13），目前运行时间为0.23s。
v2只关心其中m > 0的高速缓存，因为m == 0的情况是微不足道的。这样，空间复杂度就有所降低：

c = {}

def ack(m, n):
  global c

  if m == 0: return n + 1
  else:
    if "{}-{}".format(m, n) in c: return c["{}-{}".format(m, n)]
    else: ret = ack(m - 1, 1) if n == 0 else ack(m - 1, ack(m, n - 1))

    c["{}-{}".format(m, n)] = ret
    return ret

这在0.18s内完成ack（3，13）。但我们可以做得更好。
v3通过每次迭代只计算一次该高速缓存中的键来节省一点时间：

c = {}

def ack(m, n):
  global c

  if m == 0: return n + 1
  else:
    key = "{}-{}".format(m, n)
    if key in c: return c[key]
    else: ret = ack(m - 1, 1) if n == 0 else ack(m - 1, ack(m, n - 1))

    c[key] = ret
    return ret

这一次它运行0.14s。我肯定不能在午夜前后做更多的事情，但我会再考虑一下。Ez jómulatság，férfi munka volt -对于那些知道这意味着什么的人来说。

下面是我对Grossman-Zeitman algorithm的Python实现的尝试，它在O（A（i，n））时间内迭代计算A（i，n）。有关此算法如何工作的描述，请检查链接的问题。

def ackermann(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]

考虑到内部循环非常紧密，并且没有递归，我怀疑这可能会优于您最初发布的基本递归解决方案。然而，我还没有对这个实现进行正确性或时间测试;它基于我在链接问题中编写的Java代码。

但令人惊讶的是，缓存根本没有帮助：

In [9]: %timeit Ackermann = cache(A); Ackermann(3, 4)
1.3 ms ± 10.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

那是因为你做错了只有您的Ackermann被备忘录化，而不是您的A。递归调用都转到A。
m的次数，n = 3，8，包括正确记忆的版本B：

440.30 ms  A(m, n)
431.11 ms  Ackermann = cache(A); Ackermann(m, n)
  1.74 ms  B.cache_clear(); B(m, n)

关于B：

• 然后打印B.cache_info())，看看该高速缓存效果如何：所以B有5，119个“真实的的”调用（它必须工作的地方）和1，029个从缓存中应答的调用。如果没有备忘录，它被调用了2，785，999次。
• 对于m，n = 3，12，花费约32ms。
• 对于m，n = 3，13，它由于深度递归而崩溃。

代码：

from timeit import repeat
import sys

sys.setrecursionlimit(999999)

setup = '''
from functools import cache

def A(m, n):
    if not m:
        return n + 1
    return A(m - 1, A(m, n - 1)) if n else A(m - 1, 1)

@cache
def B(m, n):
    if not m:
        return n + 1
    return B(m - 1, B(m, n - 1)) if n else B(m - 1, 1)

m, n = 3, 8
'''

codes = [
    'A(m, n)',
    'Ackermann = cache(A); Ackermann(m, n)',
    'B.cache_clear(); B(m, n)',
]

for code in codes:
    t = min(repeat(code, setup, number=1))
    print(f'{t*1e3:6.2f} ms ', code)

TL;DR阿克曼函数增长如此之快，以至于对于（m >= 4且n >= 3），结果将不适合RAM。对于较小的m或n值，直接（无需递归）快速计算值非常容易。

我知道这个答案无助于优化递归函数调用，但它提供了一个在真实的的当代计算机上计算Ackermann函数值的快速解决方案（通过分析），并且它提供了问题第一段的直接答案。
我们希望将结果存储在计算机上的无符号二进制大整数变量中。为了存储值2B，我们需要（b + 1）位的数据，以及（c1 + c2 * ceil（log 2（b）））位的报头用于存储长度b本身。（c1是非负整数，c2是正整数。）因此，我们需要多于B位的RAM来存储2b。
具有大量RAM的计算机：

• 到2023年，消费级PC将拥有高达128 GiB的RAM，而市面上的服务器将拥有2 TiB的RAM（https://ramforyou.com/is-it-possible-for-a-computer-have-1tb-ram）。
• 在2020年，构建了具有6 TiB RAM的单机架服务器（https://www.youtube.com/watch?v=uHAfTty9UWY）。
• 2017年，构建了一个具有160 TiB RAM的大型服务器（https://www.forbes.com/sites/aarontilley/2017/05/16/hpe-160-terabytes-memory/）。
• 因此，我们可以说，在2023年建造一台具有1 PiB == 1024 TiB RAM的计算机是不可行的，而1 EiB == 1024 PiB == 1048576 TiB ==（2**63）位在2023年和不久的将来是完全不可能的。
• 目前宇宙中的原子数量估计为1082 == 10 * 1081 < 16 * 2270 < 2274。
• 让我们想象一下最大的计算机。即使有更多的原子，比如说2300个，我们可以在一台计算机中使用所有这些原子，我们可以在一个原子中存储1 EiB的数据，因此我们有2363位的内存;它仍然太小，无法存储 Big 值2**（2**363）。

让我们看看Knuth的向上箭头符号（https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation）中哪些值小于 Big：

• 2 ^ B == 2b：它适用于1 <= B <=（2363 - 1）。

2 ^（2363）== 2（2**363）==大>=大。

• 2 ^^ B：它适用于1 <= b <= 5。

2 ^^ 1 == 2;
2 ^^ 2 == 22 == 4;
2 ^^ 3 == 2（22）== 16;
2 ^^ 4 == 2（2**（22））== 65536;
2 ^^ 5 == 2（2**（22））== 265536 == 2**（216）<大;
2 ^^ 6 == 2（2**（2**（22）））== 2（2**65536）>=大。

• 2 ^^^ B：它适用于1 <= b <= 3。

2 ^^^ 1 == 2;
2 ^^^ 2 == 2 ^^ 2 == 4;
2 ^^^ 3 == 2 ^^（2 ^^ 2）== 65536;
2 ^^^ 4 == 2 ^^（2 ^^（2 ^^ 2））== 2 ^^ 65536 >= 2 ^^ 6 >=大。

• 2 ^^^^ B：它适用于1 <= b <= 2。

2 ^^^^ 1 == 2;
2 ^^^^ 2 == 2 ^^^ 2 == 4;
2 ^^^^ 3 == 2 ^^^（2 ^^^ 2）== 2 ^^^ 4 == 2 ^^ 65536 >= 2 ^^ 6 >=大。

• 2 ^^^^^ B和更多箭头：它适用于1 <= B <= 2。值至少为2 ^^^^ B，请参见此处。

下面是如何在Python中计算可行值：

def up_arrow(a, b):
  if b <= 2:
    if b < 0:
      raise ValueError
    return (1, 2, 4)[b]
  elif a == 1:
    if b >> 363:
      raise ValueError
    return 1 << b  # This may run out of memory for large b.
  elif a == 2:
    if b > 5:
      raise ValueError
    if b == 5:
      return 1 << 65536
    return (16, 65536)[b - 3]
  elif a == 3:
    if b > 3:
      raise ValueError
    return 65536
  else:
    raise ValueError

假设m >= 3，ack（m，n）== up_arrow（m - 2，n + 3）- 3（参见https：//en.wikipedia.org/wiki/Ackermann_function#Table_of_values），我们可以计算阿克曼函数的可行值：

def ack(m, n):
  if n < 0:
    raise ValueError
  if m in (0, 1):
    return n + (m + 1)  # This may run out of memory for large n.
  elif m == 2:
    return (n << 1) + 3  # This may run out of memory for large n.
  elif m == 3:
    if n >> 360:
      raise ValueError
    return (1 << (n + 3)) - 3  # This may run out of memory for large n.
  elif m == 4:
    if n > 2:
      raise ValueError
    if n == 2:
      return (1 << 65536) - 3
    return (13, 65533)[n]
  elif m == 5:
    if n > 0:
      raise ValueError
    return 65533
  else:
    raise ValueError

print([ack(m, 0) for m in range(6)])
print([ack(m, 1) for m in range(5)])
print([ack(m, 2) for m in range(5)])
print([ack(m, 3) for m in range(4)])
print([ack(m, 4) for m in range(4)])

你在经文中问这两个问题：
理论上阿克曼函数能被优化吗？
当然，你可以简单地实现它，然后用技术方法优化它（例如存储或存储中间值等）。但我认为这不是你真正要问的问题。
如果不是，是否可以肯定地证明它的时间复杂度不能降低？
优化与时间复杂度无关。“O”符号从常数乘法因子中抽象出来。你可以有两个算法，其中一个计算阿克曼函数的时间或空间是另一个的百万分之一，但它们仍然具有相同的O复杂度。
引用Wikipedia
Ackermann函数，以Wilhelm Ackermann命名，是最简单的1和最早发现的非原始递归的完全可计算函数的例子之一。
不是原始递归意味着它
比任何原始递归函数都要快。
“原始递归”基本上是...一切毫无疑问，作为一个普通的程序员，你所接触到的每一个函数，无论多么困难或庞大，都是原始递归的。你必须在real hard中搜索非原始递归函数。
是的，proven证明了Ackermann不是原始递归的。发现它实际上并非如此可能不会让你赚钱，但肯定会让你的名字在理论计算机科学社区中得到尊重。
你不能优化这种复杂性--把你的程序看作是一种不同的格式，用来证明阿克曼确实是原始递归的;你只需要把它转换回数学/逻辑术语，瞧。事实上，这并没有发生在许多年来，连同存在的“证明积极”一样，一个链接告诉你，它是，事实上，行为作为广告。
注意：最后，所有这些也必须从阿克曼函数的Angular 来看，阿克曼函数很可能被设计成具有这种属性-正如维基百科页面提到的那样，在它被发现或创建之前，有些人认为 * 所有 * 可计算函数都是原始递归的。虽然我不知道是什么驱使先生。阿克曼在20世纪20年代就开始这样做了，现在Ackerman函数确实是理论计算机科学中复杂性理论的基石;一个非常引人入胜的故事。

这个问题有Python标签，但是使用ctypes调用C++代码也是Python的一个特性。它比顶级Python答案快20000倍。如果不使用特殊情况下的数学优化，速度将提高约13- 15倍。每个m都有一个直接的数学解，但我假设您想要一个类似递归的解。
计算所有对m <= 3, n <= 17的阿克曼数的时间成本：

• 使用数学：~20微秒
• 不使用数学：约30 ms

// ackermann.cpp
#include <iostream>
#include <vector>
#include <chrono>
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];
    // special signal to clear cache
    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;
    
    // These 3 lines are kinda cheating, since it uses math formula for special case
    // Comment them out in case you dont want to use that. 
    if (m == 1) return cache[m][n] = n + 2;
    if (m == 2) return cache[m][n] = 2 * n + 3;
    if (m == 3) return cache[m][n] = (1LL << (n + 3)) - 3;

    if (n == 0) return cache[m][n] = ackermann(m - 1, 1);

    return cache[m][n] = ackermann(m - 1, ackermann(m, n - 1));        
  }
}

volatile int64_t dummy = 0;

int main()
{
  MyTimer timer;
  timer.startCounter();
    
  for (int m = 0; m <= 3; m++)
  for (int n = 0; n <= 17; n++) {
    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 answer）

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.1f} ms ', f.__name__)
    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)

输出：

0 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