私はランキングアルゴリズムについていくつかの研究を行っており、ソートされたリストとそのリストのいくつかの順列が与えられた場合、2 つの順列間の距離を計算したいと考えています。レーベンシュタイン距離の場合、これはシーケンスとそのシーケンスのソートされたコピーとの間の距離を計算することに対応します。たとえば、「反転距離」もあり、その線形時間アルゴリズムはこちらで詳しく説明されており、実装に取り組んでいます。
反転距離の既存の 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:リストの類似性をチェックするアルゴリズムは他にもいくつかあります! Kendall Tauランキング係数とSpearmanランキング係数。これらの実装はSciPyライブラリでscipy.stats.kendalltauおよびとして利用できscipy.stats.rspearman、関連する p 値とともにランクを返します。