python字符串之间的自然比较？

Question

Python是否具有在两个字符串之间进行自然排序的快速功能？不一定排序,只是一个返回0,-1或1的比较函数,具体取决于自然顺序或相同的前面.

编辑:建议的功能是正确的,但它太慢了.如何在Python中快速完成？

注意这不是许多人建议的帖子的重复 - 因为这些其他线程没有解决效率问题.当前的解决方案工作正常,但是对每一行进行正则表达式调用,这非常昂贵.我想要一个有效的解决方案,可用于进行数百万次比较.

Answer 1

cmp 是内置的功能来做到这一点.

>>> a = 'hello'
>>> b = 'world'
>>> cmp(a, b)
-1

编辑:用"自然排序"你指的排序号作为人类会做什么？如果是这种情况,那么这是一个可能的配方.

Answer 2

改编自这个问题的答案:Python是否具有字符串自然排序的内置函数？

import re

def nat_cmp(a, b):
    convert = lambda text: int(text) if text.isdigit() else text.lower()
    alphanum_key = lambda key: [ convert(c) for c in re.split('([0-9]+)', key) ]

    return cmp(alphanum_key(a), alphanum_key(b))

print nat_cmp('foo10z', 'foo100z')
print cmp('foo10z', 'foo100z')  # <- notice the builtin yields a different result

输出:

-1
1

更新

使用ipython定时(使用示例输入):

In [1]: %timeit nat_cmp('foo10z', 'foo100z')
100000 loops, best of 3: 11.6 us per loop

更新2

说到性能...... re与pure-python代码相比,我不确定你理解lib实际上有多快.为了演示,我采用了关键功能(部分re),并在pure-python中重写了几次,并将它们的速度与更简单的使用方式进行了比较re.split.

import re
from itertools import groupby

def regex_key(key):
    """Traditional, regular-expression-based nat-sort key."""
    convert = lambda text: int(text) if text.isdigit() else text.lower()
    return [convert(c) for c in re.split('([0-9]+)', key)]

def fast_key(value):
    """Attempt #1 to go faster than 'slow' 're' library."""
    result = []
    for is_int, chunk in groupby(value.lower(), str.isdigit):
        if is_int:
            result.append(int(''.join(chunk)))
        else:
            result.append(tuple(chunk))
    return result

def faster_key(value):
    """Attempt #2.  'Low-level' python."""
    start_idx = 0
    is_num = None
    result = []
    for idx, c in enumerate(value.lower()):
        now_is_num = c.isdigit()
        if is_num is not None and now_is_num != is_num:
            buf = value[start_idx:idx]
            result.append(int(buf) if is_num else buf)
            start_idx = idx
            is_num = None
        is_num = now_is_num
    buf = value[start_idx:]
    result.append(int(buf) if is_num else buf)
    return result

接下来,我针对一个简单的基准运行这些:

from datetime import datetime

def benchmark(fn):
    print "Benching %s (run 1000 times)" % fn.__name__

    start = datetime.now()
    for x in xrange(1000):
        # run key function on something approx 100 chars long
        fn('asdf1234sdfg234jhd88123j2134 - 123d34123djfsk'*2)
    print "\t%s" % (datetime.now() - start)

benchmark(regex_key)
benchmark(fast_key)
benchmark(faster_key)

结果如下:

Benching regex_key (run 1000 times)
    0:00:00.025908
Benching fast_key (run 1000 times)
    0:00:00.065567
Benching faster_key (run 1000 times)
    0:00:00.042654

现在,我确信我可以做些什么来使我的key-func实现更快,但除非我遗漏了一些巨大的东西,否则很难得到与re.split代码一样快(使用pure-python,是).