Я изучаю алгоритмы ранжирования и хотел бы, учитывая отсортированный список и некоторую перестановку этого списка, вычислить некоторое расстояние между двумя перестановками. Для случая расстояния Левенштейна это соответствует вычислению расстояния между последовательностью и отсортированной копией этой последовательности. Существует также, например, «расстояние инверсии», алгоритм линейного времени которого подробно описан здесь , над которым я работаю.
Кто-нибудь знает о существующей реализации Python расстояния инверсии и / или оптимизации расстояния Левенштейна? Я рассчитываю это для последовательности от 50 000 до 200 000 элементов, поэтому O (n ^ 2) слишком медленный, но O (n log (n)) или лучше должно быть достаточно.
Также будут оценены другие метрики для подобия перестановок.
Редактировать для людей из будущего:
На основании ответ Раймона Хеттингера ; это не Левенштейн или расстояние инверсии, а скорее «соответствие гештальт-паттерну»: P
from difflib import SequenceMatcher
import random
ratings = [random.gauss(1200, 200) for i in range(100000)]
SequenceMatcher(None, ratings, sorted(ratings)).ratio()
работает на ~ 6 секундах на ужасном рабочем столе.
Edit2: Если вы можете привести свою последовательность к перестановке [1 .. n], то изменение метрики Манхэттена чрезвычайно быстро и дает некоторые интересные результаты.
manhattan = lambda l: sum(abs(a - i) for i, a in enumerate(l)) / (0.5 * len(l) ** 2)
rankings = list(range(100000))
random.shuffle(rankings)
manhattan(rankings) # ~ 0.6665, < 1 second
Коэффициент нормализации технически является приблизительным; это верно для списков четного размера, но должно быть (0.5 * (len(l) ** 2 - 1)) для списков нечетного размера.
Edit3: Существует несколько других алгоритмов проверки сходства списков! Ранговый коэффициент Кендалла Тау и ранговый коэффициент Спирмена . Их реализации доступны в библиотеке SciPy как scipy.stats.kendalltau и scipy.stats.rspearman и будут возвращать ранги вместе со связанными p-значениями.