str.replace(..).replace(..)ad nauseam是Python中的标准习惯用法吗?

您是否有一个应用程序运行太慢,并且您对它进行了分析,发现像这段代码这样的行导致了它的运行速度变慢?瓶颈发生在意想不到的地方。

当前代码段遍历字符串5次,每次执行一项操作。您建议遍历它一次,可能每次做五件事(或者至少每次做一件事)。现在还不清楚这会自动对我起到更好的作用。目前使用的算法是o(n m)(假设字符串的长度比规则中的内容长),其中n是字符串的长度,m是替换规则的数量。我认为,你可以把算法的复杂性降低到O(n 日志(m)),在特定情况下,我们处于“_”中,原始内容仅为一个字符(但在多次调用 replace 一般来说)o(n),但这并不重要,因为 M是5 但是 n是无界的 .

如果m保持不变,那么两个解的复杂度实际上都变为o(n)。我不清楚试图把五个简单的传球变成一个复杂的传球,这将是一个有价值的任务,而我目前还不能猜到实际的时间。如果有什么东西可以使它的规模更好,我会认为这是更值得的任务。

一次通过而不是连续通过也需要回答关于如何处理冲突规则以及如何应用这些规则的问题。这些问题的解决是通过一系列 代替 .

如果我们只是测试各种方法,看看哪种方法能更快地出来(假设我们只关心最快的方法)。

def escape1(input):
        return input.replace('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace("'", '&#39;').replace('"', '&quot;')

translation_table = {
    '&': '&amp;',
    '<': '&lt;',
    '>': '&gt;',
    "'": '&#39;',
    '"': '&quot;',
}

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

数字基本相同。在第一种情况下,它们实际上更加一致,因为直接字符串替换现在是最快的。

我喜欢干净的东西,比如:

substitutions = [
    ('<', '&lt;'),
    ('>', '&gt;'),
    ...]

for search, replacement in substitutions:
    string = string.replace(search, replacement)

就是这样 Django does :

def escape(html):
    """Returns the given HTML with ampersands, quotes and carets encoded."""
    return mark_safe(force_unicode(html).replace('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace('"', '&quot;').replace("'", '&#39;'))

您可以使用Reduce:

reduce(lambda s,r: s.replace(*r),
       [('&', '&'),
        ('<', '&lt;'),
        ('>', '&gt;'),
        ("'", '&#39;'),
        ('"', '&quot;')],
       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({'<': '&lt;', '>': '&gt;', "'": '&#39;', '"': '&quot;'})
    return replace_multi(string.replace('&', '&amp;'), 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('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace("'", '&#39;').replace('"', '&quot;')

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({'<': '&lt;', '>': '&gt;', "'": '&#39;', '"': '&quot;'})
    return replace_multi(string.replace('&', '&amp;'), 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

为此付出了很多。

显然,通过regex实现这一点很常见。您可以在以下位置找到此示例: ASPN 和 here .

如果您使用的是非Unicode字符串和python<3.0,请尝试使用其他字符串 translate 方法:

# Python < 3.0
import itertools

def escape(a_string):
    replacer= dict( (chr(c),chr(c)) for c in xrange(256))
    replacer.update(
        {'&': '&amp;',
         '<': '&lt;',
         '>': '&gt;',
         '"': '&quot;',
         "'": '&#39;'}
    )
    return ''.join(itertools.imap(replacer.__getitem__, a_string))

if __name__ == "__main__":
    print escape('''"Hello"<i> to George's friend&co.''')

$ python so2484156.py 
&quot;Hello&quot;&lt;i&gt; to George&#39;s friend&amp;co.

根据您的意愿,这更接近于输入字符串的“单次扫描”。

编辑

我的目的是创造一个 unicode.translate 等效的,不限于单个字符替换,所以我想到了上面的答案;我得到了一个用户“流”的注释,几乎完全脱离上下文,只有一个正确的点:上面的代码,和原来一样,是用来处理的 字节串 而不是 Unicode字符串 . 有一个明显的更新(即unichr()xrange(sys.maxunicode+1)),我非常不喜欢,因此我想出了另一个同时在unicode和字节字符串上工作的函数,前提是python保证:

all( (chr(i)==unichr(i) and hash(chr(i))==hash(unichr(i)))
    for i in xrange(128)) is True

新功能如下:

def escape(a_string):
    replacer= {
        '&': '&',
        '<': '&lt;',
        '>': '&gt;',
        '"': '&quot;',
        "'": '&#39;',
    }
    return ''.join(
        itertools.starmap(
            replacer.get, # .setdefault *might* be faster
            itertools.izip(a_string, a_string)
        )
    )

请注意,使用带有元组序列的星图:对于任何不在replacer dict中的字符,返回所述字符。

好吧,所以我坐下来做了数学。请不要生我的气,我的回答是专门讨论的解决方案,但这将是有点难以在评论内吹嘘,所以让我这样做。事实上,我还将阐述一些与OP_问题相关的考虑因素。

首先,我一直在讨论他的方法的优雅性、正确性和可行性。结果发现,它看起来像一个建议,虽然它确实使用(本质上无序的)字典作为寄存器来存储替换对,但事实上,它始终返回正确的结果,在我声称不会返回的地方。这是因为调用 itertools.starmap() 在下面的第11行中,第二个参数是一个迭代器,它覆盖了一对单个字符/字节(稍后将详细介绍),如下所示 [ ( 'h', 'h', ), ( 'e', 'e', ), ( 'l', 'l', ), ... ] . 这对字符/字节是第一个参数, replacer.get ,用重复调用。没有机会遇到这样的情况 '>' 转化为 '>' 然后在不经意间又变成 '>' ,因为每个字符/字节只考虑一次替换。所以这部分原则上是很好的,算法上是正确的。

下一个问题是生存能力,这将包括对性能的研究。如果一个重要的任务在0.01秒内用一个笨拙的代码正确完成,但1使用令人敬畏的代码,那么在实践中,笨拙可能被认为是更好的选择(但只有在1秒的损失实际上是不可容忍的情况下)。这是我用于测试的代码;它包括许多不同的实现。它是用python 3.1编写的,所以我们可以使用unicode希腊字母作为标识符,这本身就非常棒。( zip 在py3k中返回与相同的 itertools.izip 在PY2)中:

import itertools                                                                  #01
                                                                                  #02
_replacements = {                                                                 #03
  '&': '&',                                                                   #04
  '<': '&lt;',                                                                    #05
  '>': '&gt;',                                                                    #06
  '"': '&quot;',                                                                  #07
  "'": '&#39;', }                                                                 #08
                                                                                  #09
def escape_ΤΖΩΤΖΙΟΥ( a_string ):                                                  #10
  return ''.join(                                                                 #11
    itertools.starmap(                                                            #12
      _replacements.get,                                                          #13
      zip( a_string, a_string ) ) )                                               #14
                                                                                  #15
def escape_SIMPLE( text ):                                                        #16
  return ''.join( _replacements.get( chr, chr ) for chr in text )                 #17
                                                                                  #18
def escape_SIMPLE_optimized( text ):                                              #19
  get = _replacements.get                                                         #20
  return ''.join( get( chr, chr ) for chr in text )                               #21
                                                                                  #22
def escape_TRADITIONAL( text ):                                                   #23
  return text.replace('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;')\    #24
    .replace("'", '&#39;').replace('"', '&quot;')                                 #25

这些是计时结果:

escaping with SIMPLE            took 5.74664253sec for 100000 items
escaping with SIMPLE_optimized  took 5.11457801sec for 100000 items
escaping TRADITIONAL in-situ    took 0.57543013sec for 100000 items
escaping with TRADITIONAL       took 0.62347413sec for 100000 items
escaping a la ΤΖΩΤΖΙΟΥ          took 2.66592320sec for 100000 items

原来的海报关注的是,传统方法很快变得难看,似乎算法性能较差在放入此上下文时,部分没有必要。实际上,它的性能最好;当隐藏在函数调用中时,我们会看到8%的性能损失(调用方法很昂贵,但一般情况下,您仍然应该这样做)。相比之下,_______实现所需的时间大约是传统方法的5倍,鉴于传统方法具有较高的复杂性,因此必须与python__浼浼浼浼浼浼浼浼浼浼

这里还有另一个算法,简单的算法。据我所见,这非常符合_ _ _ _ _ _的方法:它迭代文本中的字符/字节,并对每个字符/字节执行查找,然后将所有字符/字节联接在一起,并返回生成的转义文本。您可以看到,当一种方法涉及到相当冗长和模糊的公式时,简单的实现一眼就能理解。

然而,真正让我困惑的是,简单的方法在性能上有多糟糕:它的速度是传统方法的10倍左右,也是传统方法的两倍。我在这里完全不知所措,也许有人能想出一个主意,为什么会这样。它只使用了Python最基本的构建块,并使用了两个隐式迭代,因此它避免了构建丢弃列表和所有内容,但它仍然很慢,我不知道为什么。

让我以对_________解决方案优点的评论来结束此代码审查。我已经非常清楚了,我发现代码很难阅读,而且对于手头的任务来说过于夸张了。然而,比这更为关键的是,我发现他对待字符的方式,并确保对于给定的一小部分字符,它们的行为会像字节一样有点恼人。当然,它适用于手头的任务,但一旦我迭代(例如,在字节串“_”上),我所做的就是迭代表示单个字符的相邻字节。在大多数情况下,这正是您应该避免的;这正是为什么在py3k_字符串_中,字符串__现在是旧的unicode对象_,旧的字符串___变为_______。如果我提名PY3K的一个特性,它可以保证代码从2系列迁移到3系列的成本可能很高,那么它就是PY3K的一个特性。从那时起,我所有的编码问题中有98%都刚刚解决,而且没有聪明的黑客能让我严重怀疑我的行动。所说的算法不是概念上的8bit干净和Unicode安全算法,这对我来说是一个严重的缺点,因为这是2010年。