Скорее всего functools.cmp_to_key() тесно связано с базовой реализацией сортировки Python. Кроме того, параметр cmp является устаревшим. Современный способ заключается в преобразовании входных элементов в объекты, которые поддерживают требуемые операции расширенного сравнения.
В CPython 2.x объекты разнородных типов можно упорядочить, даже если соответствующие операторы расширенного сравнения не были реализованы. В CPython 3.x объекты разных типов должны явно поддерживать сравнение. См. Как Python сравнивает string и int? , который ссылается на официальную документацию . Большинство ответов зависят от этого неявного порядка. Переход на Python 3.x потребует нового типа для реализации и унификации сравнений между числами и строками.
Python 2.7.12 (default, Sep 29 2016, 13:30:34)
>>> (0,"foo") < ("foo",0)
True
Python 3.5.2 (default, Oct 14 2016, 12:54:53)
>>> (0,"foo") < ("foo",0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: int() < str()
Есть три разных подхода. Первый использует вложенные классы, чтобы использовать преимущества алгоритма сравнения Iterable в Python. Второй разворачивает это вложение в один класс. Третий отказывается от подкласса str, чтобы сосредоточиться на производительности. Все рассчитано; второй в два раза быстрее, а третий почти в шесть раз быстрее. Подклассы str не требуются, и, вероятно, изначально были плохой идеей, но они имеют определенные удобства.
Символы сортировки дублируются для принудительного упорядочения по регистру и меняются регистром для принудительной сортировки букв нижнего регистра; это типичное определение «натуральный сорт». Я не мог определиться с типом группировки; некоторые могут предпочесть следующее, что также дает значительные преимущества в производительности:
d = lambda s: s.lower()+s.swapcase()
При использовании операторы сравнения устанавливаются на object, поэтому они не будут игнорироваться functools.total_ordering.
import functools
import itertools
@functools.total_ordering
class NaturalStringA(str):
def __repr__(self):
return "{}({})".format\
( type(self).__name__
, super().__repr__()
)
d = lambda c, s: [ c.NaturalStringPart("".join(v))
for k,v in
itertools.groupby(s, c.isdigit)
]
d = classmethod(d)
@functools.total_ordering
class NaturalStringPart(str):
d = lambda s: "".join(c.lower()+c.swapcase() for c in s)
d = staticmethod(d)
def __lt__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
try:
return int(self) < int(other)
except ValueError:
if self.isdigit():
return True
elif other.isdigit():
return False
else:
return self.d(self) < self.d(other)
def __eq__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
try:
return int(self) == int(other)
except ValueError:
if self.isdigit() or other.isdigit():
return False
else:
return self.d(self) == self.d(other)
__le__ = object.__le__
__ne__ = object.__ne__
__gt__ = object.__gt__
__ge__ = object.__ge__
def __lt__(self, other):
return self.d(self) < self.d(other)
def __eq__(self, other):
return self.d(self) == self.d(other)
__le__ = object.__le__
__ne__ = object.__ne__
__gt__ = object.__gt__
__ge__ = object.__ge__
import functools
import itertools
@functools.total_ordering
class NaturalStringB(str):
def __repr__(self):
return "{}({})".format\
( type(self).__name__
, super().__repr__()
)
d = lambda s: "".join(c.lower()+c.swapcase() for c in s)
d = staticmethod(d)
def __lt__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
groups = map(lambda i: itertools.groupby(i, type(self).isdigit), (self, other))
zipped = itertools.zip_longest(*groups)
for s,o in zipped:
if s is None:
return True
if o is None:
return False
s_k, s_v = s[0], "".join(s[1])
o_k, o_v = o[0], "".join(o[1])
if s_k and o_k:
s_v, o_v = int(s_v), int(o_v)
if s_v == o_v:
continue
return s_v < o_v
elif s_k:
return True
elif o_k:
return False
else:
s_v, o_v = self.d(s_v), self.d(o_v)
if s_v == o_v:
continue
return s_v < o_v
return False
def __eq__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
groups = map(lambda i: itertools.groupby(i, type(self).isdigit), (self, other))
zipped = itertools.zip_longest(*groups)
for s,o in zipped:
if s is None or o is None:
return False
s_k, s_v = s[0], "".join(s[1])
o_k, o_v = o[0], "".join(o[1])
if s_k and o_k:
s_v, o_v = int(s_v), int(o_v)
if s_v == o_v:
continue
return False
elif s_k or o_k:
return False
else:
s_v, o_v = self.d(s_v), self.d(o_v)
if s_v == o_v:
continue
return False
return True
__le__ = object.__le__
__ne__ = object.__ne__
__gt__ = object.__gt__
__ge__ = object.__ge__
import functools
import itertools
import enum
class OrderingType(enum.Enum):
PerWordSwapCase = lambda s: s.lower()+s.swapcase()
PerCharacterSwapCase = lambda s: "".join(c.lower()+c.swapcase() for c in s)
class NaturalOrdering:
@classmethod
def by(cls, ordering):
def wrapper(string):
return cls(string, ordering)
return wrapper
def __init__(self, string, ordering=OrderingType.PerCharacterSwapCase):
self.string = string
self.groups = [ (k,int("".join(v)))
if k else
(k,ordering("".join(v)))
for k,v in
itertools.groupby(string, str.isdigit)
]
def __repr__(self):
return "{}({})".format\
( type(self).__name__
, self.string
)
def __lesser(self, other, default):
if not isinstance(self, type(other)):
return NotImplemented
for s,o in itertools.zip_longest(self.groups, other.groups):
if s is None:
return True
if o is None:
return False
s_k, s_v = s
o_k, o_v = o
if s_k and o_k:
if s_v == o_v:
continue
return s_v < o_v
elif s_k:
return True
elif o_k:
return False
else:
if s_v == o_v:
continue
return s_v < o_v
return default
def __lt__(self, other):
return self.__lesser(other, default=False)
def __le__(self, other):
return self.__lesser(other, default=True)
def __eq__(self, other):
if not isinstance(self, type(other)):
return NotImplemented
for s,o in itertools.zip_longest(self.groups, other.groups):
if s is None or o is None:
return False
s_k, s_v = s
o_k, o_v = o
if s_k and o_k:
if s_v == o_v:
continue
return False
elif s_k or o_k:
return False
else:
if s_v == o_v:
continue
return False
return True
# functools.total_ordering doesn't create single-call wrappers if both
# __le__ and __lt__ exist, so do it manually.
def __gt__(self, other):
op_result = self.__le__(other)
if op_result is NotImplemented:
return op_result
return not op_result
def __ge__(self, other):
op_result = self.__lt__(other)
if op_result is NotImplemented:
return op_result
return not op_result
# __ne__ is the only implied ordering relationship, it automatically
# delegates to __eq__
>>> import natsort
>>> import timeit
>>> l1 = ['Apple', 'corn', 'apPlE', 'arbour', 'Corn', 'Banana', 'apple', 'banana']
>>> l2 = list(map(str, range(30)))
>>> l3 = ["{} {}".format(x,y) for x in l1 for y in l2]
>>> print(timeit.timeit('sorted(l3+["0"], key=NaturalStringA)', number=10000, globals=globals()))
362.4729259099986
>>> print(timeit.timeit('sorted(l3+["0"], key=NaturalStringB)', number=10000, globals=globals()))
189.7340817489967
>>> print(timeit.timeit('sorted(l3+["0"], key=NaturalOrdering.by(OrderingType.PerCharacterSwapCase))', number=10000, globals=globals()))
69.34636392899847
>>> print(timeit.timeit('natsort.natsorted(l3+["0"], alg=natsort.ns.GROUPLETTERS | natsort.ns.LOWERCASEFIRST)', number=10000, globals=globals()))
98.2531585780016
Естественная сортировка довольно сложна и неопределенно определяется как проблема. Не забудьте заранее запустить unicodedata.normalize(...) и рассмотреть возможность использования str.casefold() вместо str.lower(). Возможно, есть тонкие проблемы с кодированием, которые я не рассматривал. Поэтому я рекомендую библиотеку natsort . Я быстро взглянул на репозиторий github; обслуживание кода было звездным.
Все алгоритмы, которые я видел, зависят от уловок, таких как дублирование и понижение символов, а также от случая замены. Хотя это удваивает время выполнения, альтернатива потребует полного естественного упорядочения во входном наборе символов. Я не думаю, что это является частью спецификации Unicode, и так как в Unicode намного больше цифр, чем [0-9], создание такой сортировки было бы в равной степени пугающим. Если вы хотите сравнения с учетом локали, подготовьте свои строки с locale.strxfrm для Python's Сортировка HOW TO .