Mic*_*ael 28 python performance replace idioms
例如,假设我想要一个函数来转义字符串以便在HTML中使用(如在Django的转义过滤器中):
def escape(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
return string.replace('&', '&').replace('<', '<').replace('>', '>').replace("'", ''').replace('"', '"')
这样可行,但它很快变得难看并且似乎具有较差的算法性能(在此示例中,字符串重复遍历5次).更好的是这样的事情:
def escape(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
# Note that ampersands must be escaped first; the rest can be escaped in
# any order.
return replace_multi(string.replace('&', '&'),
{'<': '<', '>': '>',
"'": ''', '"': '"'})
这样的函数是否存在,或者是使用我之前编写的标准Python习惯用法？
Mik*_*ham 20
您是否有一个运行速度太慢的应用程序并且您对其进行了分析以发现像这个代码段的行导致它变慢？瓶颈发生在意想不到的地方.
当前片段遍历字符串5次,每次做一件事.你建议遍历它一次,可能每次做五件事(或者至少每次做一件事).目前尚不清楚这会自动为我做得更好.目前使用的算法是O(n m)(假设字符串的长度比规则中的东西长),其中n是字符串的长度,m是替换规则的数量.我认为,您可以将算法复杂度降低到类似O(n log(m))的范围,并且在特定情况下我们处于原始状态只有一个字符的位置(但在多次调用的情况下不会)replace通常)-O(n),但这并不重要,因为m是5但n是无界的.
如果m保持不变,则两种解决方案的复杂性实际上都是O(n).我不清楚尝试将五个简单的传递变成一个复杂的传递将是一个值得的任务,实际的时间我无法在当前时刻猜测.如果它有什么可以使它更好地扩展,我会认为这是更有价值的任务.
在一次通过而不是连续通过中执行所有操作也需要回答有关如何处理冲突规则及其应用方式的问题.这些问题的解决方案很清楚replace.
Mik*_*ers 14
我们只是测试各种方法,看看哪个更快出来(假设我们只关心最快的方式).
def escape1(input):
return input.replace('&', '&').replace('<', '<').replace('>', '>').replace("'", ''').replace('"', '"')
translation_table = {
'&': '&',
'<': '<',
'>': '>',
"'": ''',
'"': '"',
}
def escape2(input):
return ''.join(translation_table.get(char, char) for char in input)
import re
_escape3_re = re.compile(r'[&<>\'"]')
def _escape3_repl(x):
s = x.group(0)
return translation_table.get(s, s)
def escape3(x):
return _escape3_re.sub(_escape3_repl, x)
def escape4(x):
return unicode(x).translate(translation_table)
test_strings = (
'Nothing in there.',
'<this is="not" a="tag" />',
'Something & Something else',
'This one is pretty long. ' * 50
)
import time
for test_i, test_string in enumerate(test_strings):
print repr(test_string)
for func in escape1, escape2, escape3, escape4:
start_time = time.time()
for i in xrange(1000):
x = func(test_string)
print '\t%s done in %.3fms' % (func.__name__, (time.time() - start_time))
print
运行这个给你:
'Nothing in there.'
escape1 done in 0.002ms
escape2 done in 0.009ms
escape3 done in 0.001ms
escape4 done in 0.005ms
'<this is="not" a="tag" />'
escape1 done in 0.002ms
escape2 done in 0.012ms
escape3 done in 0.009ms
escape4 done in 0.007ms
'Something & Something else'
escape1 done in 0.002ms
escape2 done in 0.012ms
escape3 done in 0.003ms
escape4 done in 0.007ms
'This one is pretty long. <snip>'
escape1 done in 0.008ms
escape2 done in 0.386ms
escape3 done in 0.011ms
escape4 done in 0.310ms
看起来只是一个接一个地更换它们最快.
编辑:使用1000000次迭代再次运行测试会为前三个字符串提供以下内容(第四个字符串在我的机器上需要太长时间才能等待= P):
'Nothing in there.'
escape1 done in 0.001ms
escape2 done in 0.008ms
escape3 done in 0.002ms
escape4 done in 0.005ms
'<this is="not" a="tag" />'
escape1 done in 0.002ms
escape2 done in 0.011ms
escape3 done in 0.009ms
escape4 done in 0.007ms
'Something & Something else'
escape1 done in 0.002ms
escape2 done in 0.011ms
escape3 done in 0.003ms
escape4 done in 0.007ms
数字几乎相同.在第一种情况下,它们实际上更加一致,因为直接字符串替换现在最快.
Hte*_*hno 13
我更喜欢干净的东西:
substitutions = [
('<', '<'),
('>', '>'),
...]
for search, replacement in substitutions:
string = string.replace(search, replacement)
这就是Django的作用:
def escape(html):
"""Returns the given HTML with ampersands, quotes and carets encoded."""
return mark_safe(force_unicode(html).replace('&', '&').replace('<', '<').replace('>', '>').replace('"', '"').replace("'", '''))
你可以使用reduce:
reduce(lambda s,r: s.replace(*r),
[('&', '&'),
('<', '<'),
('>', '>'),
("'", '''),
('"', '"')],
string)
根据 bebraw 的建议，这是我最终使用的（当然是在一个单独的模块中）：
import re
class Subs(object):
"""
A container holding strings to be searched for and replaced in
replace_multi().
Holds little relation to the sandwich.
"""
def __init__(self, needles_and_replacements):
"""
Returns a new instance of the Subs class, given a dictionary holding
the keys to be searched for and the values to be used as replacements.
"""
self.lookup = needles_and_replacements
self.regex = re.compile('|'.join(map(re.escape,
needles_and_replacements)))
def replace_multi(string, subs):
"""
Replaces given items in string efficiently in a single-pass.
"string" should be the string to be searched.
"subs" can be either:
A.) a dictionary containing as its keys the items to be
searched for and as its values the items to be replaced.
or B.) a pre-compiled instance of the Subs class from this module
(which may have slightly better performance if this is
called often).
"""
if not isinstance(subs, Subs): # Assume dictionary if not our class.
subs = Subs(subs)
lookup = subs.lookup
return subs.regex.sub(lambda match: lookup[match.group(0)], string)
用法示例：
def escape(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
# Note that ampersands must be escaped first; the rest can be escaped in
# any order.
escape.subs = Subs({'<': '<', '>': '>', "'": ''', '"': '"'})
return replace_multi(string.replace('&', '&'), escape.subs)
好多了 ：）。谢谢您的帮助。
没关系，迈克格雷厄姆是对的。我对它进行了基准测试，替换结果实际上要慢得多。
代码：
from urllib2 import urlopen
import timeit
def escape1(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
return string.replace('&', '&').replace('<', '<').replace('>', '>').replace("'", ''').replace('"', '"')
def escape2(string):
"""
Returns the given string with ampersands, quotes and angle
brackets encoded.
"""
# Note that ampersands must be escaped first; the rest can be escaped in
# any order.
escape2.subs = Subs({'<': '<', '>': '>', "'": ''', '"': '"'})
return replace_multi(string.replace('&', '&'), escape2.subs)
# An example test on the stackoverflow homepage.
request = urlopen('http://stackoverflow.com')
test_string = request.read()
request.close()
test1 = timeit.Timer('escape1(test_string)',
setup='from __main__ import escape1, test_string')
test2 = timeit.Timer('escape2(test_string)',
setup='from __main__ import escape2, test_string')
print 'multi-pass:', test1.timeit(2000)
print 'single-pass:', test2.timeit(2000)
输出：
multi-pass: 15.9897229671
single-pass: 66.5422530174
这么多。