我正在编写一个程序来计算 Python 中的 Levenshtein 距离。我实现了记忆化，因为我递归地运行算法。我的原始函数在函数本身中实现了内存。这是它的样子:
# Memoization table mapping from a tuple of two strings to their Levenshtein distance
dp = {}
# Levenshtein distance algorithm
def lev(s, t):
# If the strings are 0, return length of other
if not s:
return len(t)
if not t:
return len(s)
# If the last two characters are the same, no cost. Otherwise, cost of 1
if s[-1] is t[-1]:
cost = 0
else:
cost = 1
# Save in dictionary if never calculated before
if not (s[:-1], t) in dp:
dp[(s[:-1], t)] = lev(s[:-1], t)
if not (s, t[:-1]) in dp:
dp[(s, t[:-1])] = lev(s, t[:-1])
if not (s[:-1], t[:-1]) in dp:
dp[(s[:-1], t[:-1])] = lev(s[:-1], t[:-1])
# Returns minimum chars to delete from s, t, and both
return min(dp[(s[:-1], t)] + 1,
dp[(s, t[:-1])] + 1,
dp[(s[:-1], t[:-1])] + cost)
这行得通!但是，我找到了一种方法来内存 using decorators .我尝试将此技术应用到我的算法中:
# Memoization table mapping from a tuple of two strings to their Levenshtein distance
def memoize(func):
memo = {}
def wrap(s, t):
if (s, t) not in memo:
memo[(s, t)] = func(s, t)
return memo[(s, t)]
return wrap
# Levenshtein distance algorithm
@memoize # lev = memoize(lev)
def lev(s, t):
# If the strings are 0, return length of other
if not s:
return len(t)
if not t:
return len(s)
# If the last two characters are the same, no cost. Otherwise, cost of 1
if s[-1] is t[-1]:
cost = 0
else:
cost = 1
# Returns minimum chars to delete from s, t, and both
return min(lev(s[:-1], t) + 1,
lev(s, t[:-1]) + 1,
lev(s[:-1], t[:-1]) + cost)
对我来说，这看起来更清晰，也更容易混淆。我以为这两者在功能上是等价的，但是当我运行带有装饰器的版本时，我惊讶地发现我得到了一个RecursionError: maximum recursion depth exceeded。
我到底错过了什么？使用装饰器在功能上不等价吗？我尝试通过添加 sys.setrecursionlimit(1500) 进行修复，这很有效，但这是一个 hack，并没有解释为什么两者的功能不同。
注意:我使用一段 lorem ipsum 作为维基百科中 s 和 t 的测试字符串:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est labour.
我知道对于更长的字符串，我的第一个函数将失败。我只想知道为什么装饰的首先失败。谢谢!
最佳答案
考虑原始代码中发生的堆栈帧(函数调用)。它们看起来像:
lev(s, t)
-> lev(..., ...)
-> lev(..., ...)
-> lev(..., ...)
-> lev(..., ...)
在您的内存版本中，它们显示为:
wraps(s, t)
-> lev(..., ...)
-> wraps(s, t)
-> lev(..., ...)
-> wraps(s, t)
-> lev(..., ...)
-> wraps(s, t)
-> lev(..., ...)
-> wraps(s, t)
-> lev(..., ...)
也就是说，您的堆栈帧将是原来的两倍大，因为每个“调用”实际上调用了两个函数。因此，您将更早地耗尽堆栈帧限制。
关于python - 超出最大递归深度，但仅在使用装饰器时，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38624852/
我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc
很好奇，就使用rubyonrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提
假设我做了一个模块如下:m=Module.newdoclassCendend三个问题:除了对m的引用之外，还有什么方法可以访问C和m中的其他内容？我可以在创建匿名模块后为其命名吗(就像我输入“module...”一样)？如何在使用完匿名模块后将其删除，使其定义的常量不再存在？ 最佳答案 三个答案:是的，使用ObjectSpace.此代码使c引用你的类(class)C不引用m:c=nilObjectSpace.each_object{|obj|c=objif(Class===objandobj.name=~/::C$/)}当然这取决于
我正在尝试使用ruby和Savon来使用网络服务。测试服务为http://www.webservicex.net/WS/WSDetails.aspx?WSID=9&CATID=2require'rubygems'require'savon'client=Savon::Client.new"http://www.webservicex.net/stockquote.asmx?WSDL"client.get_quotedo|soap|soap.body={:symbol=>"AAPL"}end返回SOAP异常。检查soap信封，在我看来soap请求没有正确的命名空间。任何人都可以建议我
关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。
我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po