递归闭包（函数生成器）

Question

递归闭包（函数生成器）

pythonrecursionfunctional-programmingclosurescomplexity-theory

4

我一直在学习函数式编程，想到将数学运算符组合起来。顺理成章地，我写出了最简单和最朴素的代码表达式，并且它工作得非常好！问题是我真的不知道为什么它能如此有效地处理如此庞大的输出。

问题是：这个函数的复杂度是多少？

代码是用Python编写的：

def operator(d):
        if d<=1:
                return lambda x,y:x+y
        else:
                return lambda x,y:reduce(operator(d-1),(x for i in xrange(y)))


#test 
f1 = operator(1)       #f1 is adition
print("f1",f1(50,52))  #50+52

f2 = operator(2)      #f2 is multiplication
print("f2",f2(2,20))  #2*20

f3 = operator(3)      #f3 is power, just look how long output can be
print("f3",f3(4,100)) #4**100 

f4 = operator(4)      #f4 is superpower, this one does not work that well
print("f4",f4(2,6))   #((((2**2)**2)**2)**2)**2

f5 = operator(5)      #f5 do not ask about this one, 
print("f5",f5(2,4))   #

输出（即时）：

('f1', 102)
('f2', 40)
('f3', 1606938044258990275541962092341162602522202993782792835301376L)
('f4', 4294967296L)
('f5', 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656L)

- Luka Rahne

你的代码只在递归展开时执行加法操作，因此我猜测 Python 的大数加法非常高效。 - Frédéric Hamidi

@Frederic：虽然加法的数量呈指数级增长，但是这里呈现的数字规模并不令人惊叹。我看不出有问题，更别提具体的问题了。 - Niklas B.

2

你应该尝试基准测试你的代码所执行的加法次数 - 只需稍微改变operator(1)，使其每次被调用时增加一个变量。顺便提一句，我感觉你可能会对Ackerman函数感兴趣 :)。 - hugomg

@missingno Ackerman函数的定义实际上是另一种方式。例如，operator(4)(2,3)表示为(22)2，其中ACK(4,0)等于2(22)-3。 - Luka Rahne

1

顺便提一下，http://en.wikipedia.org/wiki/Hyperoperation 是关于编程的内容。 - newacct

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niklas B. · Accepted Answer

反汇编告诉你，这里没有使用任何魔法优化，它只是在一个生成器表达式上进行了一次缩减。Python似乎可以胜任这个任务，即使这让你感到惊讶。

>>> import dis
>>> dis.dis(f3)
  5           0 LOAD_GLOBAL              0 (reduce)
              3 LOAD_GLOBAL              1 (operator)
              6 LOAD_DEREF               1 (d)
              9 LOAD_CONST               1 (1)
             12 BINARY_SUBTRACT     
             13 CALL_FUNCTION            1
             16 LOAD_CLOSURE             0 (x)
             19 BUILD_TUPLE              1
             22 LOAD_CONST               2 (<code object <genexpr> at 0x7f32d325f830, file "<stdin>", line 5>)
             25 MAKE_CLOSURE             0
             28 LOAD_GLOBAL              2 (xrange)
             31 LOAD_FAST                1 (y)
             34 CALL_FUNCTION            1
             37 GET_ITER            
             38 CALL_FUNCTION            1
             41 CALL_FUNCTION            2
             44 RETURN_VALUE

如果你仔细看一下你的 f5（2，4） 调用，它实际上并没有执行太多操作:

>>> counter = 0
>>> def adder(x, y):
...   global counter
...   counter += 1
...   return x + y
... 
>>> def op(d):
...   if d <= 1: return adder
...   return lambda x,y:reduce(op(d-1),(x for i in xrange(y)))
...
>>> op(5)(2,4)
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656L
>>> counter
65035
>>> counter = 0
>>> op(3)(4,100)
>>> counter
297

在现代的CPU中，65k的加法运算，更不用说297次幂运算，都不能称之为什么。因此，这个计算过程可以瞬间完成也就不足为奇了。尝试增加其中一个参数，你会发现它能够迅速达到快速评估的边界。

顺便提一下，operator是一个内置模块，你不应该使用这个名称作为自己的函数名。