31

例如,假设我想要一个函数来转义用于 HTML 的字符串(如在 Django 的转义过滤器中):

    def escape(string):
        """
        Returns the given string with ampersands, quotes and angle 
        brackets encoded.
        """
        return string.replace('&', '&amp;').replace('<', '&lt;').replace('>', '&gt;').replace("'", '&#39;').replace('"', '&quot;')

这行得通,但它很快就会变得丑陋,而且算法性能似乎很差(在这个例子中,字符串被重复遍历了 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('&', '&amp;'),
                             {'<': '&lt;', '>': '&gt;', 
                              "'": '&#39;', '"': '&quot;'})

是否存在这样的函数,或者是使用我之前编写的标准 Python 习语?

4

9 回答 9

24

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

当前代码段遍历字符串 5 次,每次做一件事。你建议遍历一次,可能每次做五件事(或者至少每次做一些事情)。目前尚不清楚这是否会自动对我做得更好。目前使用的算法是 O(n*m)(假设字符串的长度比规则中的内容长),其中 n 是字符串的长度,m 是替换规则的数量。我认为,您可以将算法复杂性降低到像 O(n*log(m)) 之类的东西,并且在我们所处的特定情况下,原始事物都只有一个字符(但在多次调用的情况下则不然到replace一般)—O(n),但这并不重要,因为m 是 5n 是无界的

如果 m 保持不变,那么这两种解决方案的复杂度实际上都会达到 O(n)。我不清楚尝试将五个简单的通行证变成一个复杂的通行证是否是一项有价值的任务,我目前无法猜测其实际时间。如果有什么东西可以让它更好地扩展,我会认为这是更有价值的任务。

一次通过而不是连续通过也需要回答有关如何处理冲突规则以及如何应用它们的问题。这些问题的解决方案很清楚,有一个链replace

于 2010-03-20T19:17:05.963 回答
17

不如我们测试一下各种方法,看看哪种方法更快(假设我们只关心最快的方法)。

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

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

于 2010-03-20T19:50:11.500 回答
13

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

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

for search, replacement in substitutions:
    string = string.replace(search, replacement)
于 2010-03-20T18:40:44.687 回答
9

您可以使用减少:

reduce(lambda s,r: s.replace(*r),
       [('&', '&amp;'),
        ('<', '&lt;'),
        ('>', '&gt;'),
        ("'", '&#39;'),
        ('"', '&quot;')],
       string)
于 2010-03-20T19:29:22.743 回答
7

这就是Django 所做的:

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;'))
于 2010-03-20T18:16:07.703 回答
5

根据 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

这么多。

于 2010-03-20T19:04:13.603 回答
3

显然,通过正则表达式实现它是很常见的。您可以在ASPN此处找到这方面的示例。

于 2010-03-20T18:17:13.050 回答
2

好的,所以我坐下来算了算。请不要生我的气,我回答专门讨论 ΤZΩΤZΙΟΥ 的解决方案,但这在评论中有点难以硬塞,所以让我这样做。事实上,我也会提出一些与 OP 的问题相关的考虑。

首先,我一直在与 ΤZΩΤZΙΟΥ 讨论他的方法的优雅、正确和可行性。事实证明,它看起来像提案,虽然它确实使用(固有无序的)字典作为寄存器来存储替换对,但实际上确实始终返回正确的结果,而我曾声称它不会。这是因为在itertools.starmap()下面的第 11 行中的调用将一个迭代器作为其第二个参数,该迭代器对看起来像[ ( 'h', 'h', ), ( 'e', 'e', ), ( 'l', 'l', ), ... ]. 这些字符/字节对是第一个参数replacer.get, 被重复调用的内容。没有机会遇到先'>'被转化为'&gt;',然后不经意间再次转化为的情况'&amp;gt;',因为每个字符/字节只被考虑一次用于替换。所以这部分原则上是好的并且在算法上是正确的。

下一个问题是可行性,这将包括对性能的了解。如果使用笨拙的代码在 0.01 秒内正确完成一项重要任务,但使用出色的代码在 1 秒内正确完成,那么在实践中可能会认为笨拙是可取的(但前提是 1 秒的损失实际上是无法容忍的)。这是我用于测试的代码;它包括许多不同的实现。它是用 python 3.1 编写的,因此我们可以使用 unicode 希腊字母作为标识符,这本身就很棒(zip在 py3k 中返回与itertools.izip在 py2 中相同):

import itertools                                                                  #01
                                                                                  #02
_replacements = {                                                                 #03
  '&': '&amp;',                                                                   #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% 的性能损失(“调用方法很昂贵”,但通常你仍然应该这样做)。相比之下,ΤZΩΤZΙΟΥ 的实现时间大约是传统方法的 5 倍,鉴于它具有更高的复杂性,必须与 python 久经磨练的优化字符串方法竞争也就不足为奇了。

这里还有另一种算法,简单算法。据我所知,这与 ΤZΩΤZΙΟΥ 的方法所做的完全一样:它遍历文本中的字符/字节并对每个字节执行查找,然后将所有字符/字节连接在一起并返回结果转义文本。您可以看到,其中一种方法涉及相当冗长和神秘的公式,而 SIMPLE 实现实际上一目了然。

然而,真正让我感到困惑的是,SIMPLE 方法的性能有多糟糕:它的速度大约是传统方法的 10 倍,也是 ΤZΩΤZΙΟΥ 方法的两倍。我在这里完全不知所措,也许有人能想到为什么会这样。它仅使用 python 的最基本构建块并使用两个隐式迭代,因此它避免构建一次性列表和所有内容,但它仍然很慢,我不知道为什么。

让我用 ΤZΩΤZΙΟΥ 解决方案的优点来结束这个代码审查。我已经说得很清楚了,我发现代码很难阅读,而且对于手头的任务来说太过分了。然而,比这更重要的是,我发现他对待字符的方式,并确保对于给定的小范围字符,它们会以类似字节的方式表现得有点烦人。确保它适用于手头的任务,但是一旦我迭代例如字节串'ΤZΩΤZΙΟΥ',我所做的就是迭代代表单个字符的相邻字节。在大多数情况下,这正是您应该避免的;这正是为什么在 py3k 中“字符串”现在是旧的“unicode 对象”,而旧的“字符串”变成了“字节”和“字节数组”。如果我要提名 py3k 的一个特性,它可能保证将代码从 2 系列迁移到 3 系列可能代价高昂,那将是 py3k 的这个单一属性。从那以后,我 98% 的编码问题都已经解决了,而且没有任何聪明的黑客可以让我严重怀疑我的举动。说算法不是“概念上 8 位干净和 unicode 安全”,这对我来说是一个严重的缺点,因为这是 2010 年。

于 2010-05-21T17:11:36.783 回答
1

如果您使用非 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不限于单字符替换的等价物,所以我想出了上面的答案;我得到了用户“flow”的评论,几乎完全脱离了上下文,只有一个正确的点:上面的代码原样用于处理byte strings而不是unicode strings。有一个明显的更新(即 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= {
        '&': '&amp;',
        '<': '&lt;',
        '>': '&gt;',
        '"': '&quot;',
        "'": '&#39;',
    }
    return ''.join(
        itertools.starmap(
            replacer.get, # .setdefault *might* be faster
            itertools.izip(a_string, a_string)
        )
    )

注意星图与元组序列的使用:对于不在替换字典中的任何字符,返回所述字符。

于 2010-03-21T15:39:04.547 回答