长表达式崩溃SymPy

我正在使用64位Python 3.3.1，pylab和32GB系统内存。这个功能：长表达式崩溃SymPy

def sqrt2Expansion(limit): 
    x = Symbol('x') 
    term = 1+1/x 
    for _ in range(limit): 
     term = term.subs({x: (2+1/x)}) 
    return term.subs({x: 2})

生产这种表达：1 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + 1/(...))))))。当被调用时：sqrt2Expansion(100)返回有效结果，但sqrt2Expansion(200)产生RuntimeError带有许多追溯页面，并挂起pylab/IPython解释器，留下大量未使用的系统内存。任何想法如何更有效地实施它？我想打电话sqrt2Expansion(1000)，仍然可以得到结果。

来源

2013-05-06 Paul Jurczak

将term = term.subs（{x：（2 + 1/x）}）'改为term = term.subs {x：（2 + 1/x）}）。factor（）'应该做的。你能解释一下你在做什么的目的吗？ – Krastanov 2013-05-06 11:29:12

@Krastanov谢谢，它的确适用于'sqrt2Expansion（1000）'。我的目的是在解决[Euler问题57]（http://projecteuler.net/problem=57）的同时学习SymPy。我知道更优雅的解决方案，但我希望看到，如果在这种情况下强力可行。如果你喜欢张贴你的评论作为答案，我会upvote它并选择它作为一个接受的答案。 – 2013-05-06 16:14:36

我试着在下面更广泛地回答。希望对你有帮助。 – Krastanov 2013-05-06 19:34:01

我会试着详细说明我上面发布的评论。

Sympy表达式是树。每个操作都是一个节点，它的操作数作为分支。例如x+y看起来像Add(x, y)和x*(y+z)，如Mul(x, Add(y, z))。

通常这些表情会自动变平，就像Add(x, Add(y, z))变成Add(x, y, z)一样，但对于更复杂的情况，可以得到很深的树。

深层树木可能会造成问题，尤其是当解释程序或库自身限制允许的递归深度（作为防止无限递归和爆炸内存使用）时。很可能这是你的原因RuntimeError：每个subs使得树更深，并且随着树越来越深，递归subs必须多次调用自身直到它到达最深的节点。

通过使用factor方法，您可以将树简化为polynomial/polynomial，它具有恒定的深度。只需将term = term.subs({x: (2+1/x)})更改为term = term.subs({x: (2+1/x)}).factor()即可。

来源

2013-05-06 19:30:25 Krastanov

我怀疑递归的深度是一个问题，但如果SymPy生成适当的错误消息而不是挂断，那将会很好。再次感谢你的帮助。 – 2013-05-06 22:38:39

我认为（我可能错了），这个错误是由解释器控制的，它通常很难在代码中捕获（它不是执行'raise RuntimeError'的SymPy）。所以SymPy对消息没有太多的控制权。另一方面，如果一些志愿者重构略有“subs”，所以它不使用递归，错误和限制将消失。 – Krastanov 2013-05-07 07:49:26

'取消'将比因子更有效。如果您不担心取消常见因素，“expr.as_numer_denom”效率最高，但在某些情况下可能会导致非常大的表达式增长。 – asmeurer 2013-05-12 22:18:47

是否有一个原因，你需要象征性地做到这一点？从2开始，从那里开始工作。你将永远不会遇到递归错误，因为这个分数将在每个阶段变平坦

In [10]: def sqrt2(limit): 
    ....:  expr = Rational(1, 2) 
    ....:  for i in range(limit): 
    ....:   expr = 1/(2 + expr) 
    ....:  return 1 + expr 
    ....: 

In [11]: sqrt2(100) 
Out[11]: 
552191743651117350907374866615429308899 
─────────────────────────────────────── 
390458526450928779826062879981346977190 

In [12]: sqrt2(100).evalf() 
Out[12]: 1.41421356237310 

In [13]: sqrt(2).evalf() 
Out[13]: 1.41421356237310 

In [15]: print sqrt2(1000) 
173862817361510048113392732063287518809190824104684245763570072944177841306522186007881248757647526155598965224342185265607829530599877063992267115274300302346065892232737657351612082318884085720085755135975481584205200521472790368849847501114423133808690827279667023048950325351004049478273731369644053281603356987998498457434883570613383878936628838144874794543267245536801570068899/122939577152521961584762100253767379068957010866562498780385985503882964809611193975682098617378531179669585936977443997763999765977165585582873799618452910919591841027248057559735534272951945685362378851460989224784933532517808336113862600995844634542449976278852113745996406252046638163909206307472156724372191132577490597501908825040117098606797865940229949194369495682751575387690

来源

2013-05-12 22:17:37 asmeurer

由于您正在解决Project Euler问题，因此您可能需要修改算法以检查每个阶段的结果，而不是重新计算整个事件1000次（尽管如此，即使这样做会在几秒钟内完成）。 – asmeurer 2013-05-12 22:20:43

“Rational”需要什么导入？ – 2013-05-13 02:12:13

我用'Fraction'替换'Rational'使它在Python3.3中工作。你的是迄今为止我见过的最优雅的声明式解决方案。我开始朝这个方向发展，但我陷入了困境 - 我是一个Python新手。我使用SymPy主要用于未来的应用程序 - 我知道这是对这个问题的矫枉过正。谢谢你的帮助。 – 2013-05-13 02:51:57

长表达式崩溃SymPy

回答

相关问题