Python естественное сравнение между строками?

Question

Есть ли в Python быстрая функция для естественной сортировки между двумя строками?Не обязательно сортировать, просто функция сравнения, которая возвращает 0, -1 или 1 в зависимости от того, что впереди в естественном порядке или то же самое.

РЕДАКТИРОВАТЬ: предложенная функция верна, но она слишком медленная.Как это можно быстро сделать в Python?

ПРИМЕЧАНИЕ Это не дубликат поста, который многие люди предлагают - поскольку эти другие темы не затрагивают проблему эффективности.Текущие решения работают и являются правильными, но делают вызов регулярного выражения для каждой строки, что непомерно дорого.Мне бы хотелось, чтобы решение было эффективным и могло использоваться для миллионов сравнений.

Answer 1

Адаптировано из ответа на этот вопрос: Имеет ли 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 lib, по сравнению с чистым Python-кодом.Чтобы продемонстрировать, я взял ключевую функцию (часть с re) и переписал ее несколько раз на чистом 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

Теперь я уверен, что есть вещи, которые я мог бы сделатьчтобы ускорить реализацию ключевых функций, но если мне не хватает чего-то огромного, будет сложно получить такую ​​же быструю работу, как код re.split (то есть с использованием чистого python).

Answer 2

cmp - это встроенная функция для этого.

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

РЕДАКТИРОВАТЬ: с "естественная сортировка" Вы относитесь к сортировке чисел, как люди?Если это так, то это возможный рецепт.

Answer 3

Это позволит вам естественным образом отсортировать список строк:

import re

unsorted_list = ["a1", "a2", "a11", "b1", "b2", "b11"]

def natural_key(s):
    return [ int(c) if c.isdigit() else c for c in re.split(r'(\d+)', s) ]

sorted_list = sorted(unsorted_list, key = lambda x : natural_key(x))

print sorted_list

---

. Это вернет -1, 0 или 1, в зависимости от того, х> у

def natural_key(x, y):
     x = [int(c) if c.isdigit() else c for c in re.split(r'(\d+)', x)]
     y = [int(c) if c.isdigit() else c for c in re.split(r'(\d+)', y)]
     if x == y:
          return 0
     elif x > y:
          return 1
     else:
          return -1

Это работает в python 2.X и 3.X