5

リストを各項目の桁で並べ替えたい。

例：

myCmpItem = '511'
myList = ['111','222','333','444','555','123']

(some magic)

mySortedList = ['111', '222', '333', '123', '444', '555']

アルゴリズムの仕組み:

  • myList の現在のアイテムの各桁を myCmpItem と比較します
    • リストの最初の項目は次のようになります。
    • 5 と 1 の差は 4
    • 1 と 1 の差は 0
    • 1 と 1 の差は 0
    • これらの 2 つの数値の差は 4 です (桁比較の合計)
  • 他のすべてのアイテムについても同じことを行います
  • この計算された類似度でリストを並べ替える

多くの for ループを使用してこれをコーディングすることもできますが、実際にはこれを行うためのより高速な方法を探しています。そのようなことをするアルゴリズムはありますか？速い？

その他の制限

  • 私の例では、すべてのアイテムの長さは 3 ですが、実際のシナリオでは長さは 25 です。
  • すべての項目の長さは同じです。len(myList[x])==25 は常に true です。
  • アイテムは、文字列、int、float、またはアルゴリズムにより適したものにすることができます
  • 1から5までの数字しかない

バックグラウンド

すべての項目の数字は質問に対する回答であり、特定の回答セットに最も類似した回答セットを見つけたいと考えています。したがって、「123」は、ユーザーが質問 1 = 回答 1、質問 2 = 回答 2、質問 3 = 回答 3 に回答したことを意味します。これらは、合計 25 の質問 (= 25 の長さ) を持つ多肢選択式の質問であり、常に 5 つの異なる質問があります。回答する可能性があります (これらは 1 ～ 5 の数字です)。

PS: これは私が Stackoverflow で行った最初の質問です。よろしくお願いします。すでに何時間もグーグル検索しましたが、解決策が見つからなかったので、ここで質問しました。うまくいくことを願っています。また、英語は私の母国語ではありません。

答え（参加者の皆様、ありがとうございました！）

@larsmans の回答 ( https://stackoverflow.com/a/10790714/511484 ) は、これを合理的な速度で解決する方法を非常によく説明しています。@gnibbler の投稿 ( https://stackoverflow.com/a/10791838/511484 ) を参照してください。他のすべての回答も適切で正しいものでしたが、私はそれを発見しました@larsmans が最良の説明をしてくれました。助けてくれてありがとう！

4

5 に答える 5

7

まず、からの整数のリストをmyCmpItem作成して、減算を可能にします。

myCmpItem = map(int, myCmpItem)

次に、アイテムと。の間の距離を計算する関数を定義しますmyCmpItem。アイテムを整数のリストにもマップする必要があります。残りは、L1距離（計算している「差」の数学名）のバニラ式です。

def dist(item):
    item = map(int, item)
    return sum(abs(item[i] - myCmpItem[i]) for i in xrange(len(item)))

次に、この関数keyをソートの関数として使用します。

sorted(myList, key=dist)

（追記：このアプリケーションではL1距離が理にかなっていますか？これを使用すると、回答1は回答3よりも回答2に似ているという仮定が表されます。そうでない場合は、ハミング距離の方が適切な場合があります。）

于 2012-05-28T21:43:30.913 に答える
5

lambdaリスト内包表記：

sorted(myList, key=lambda item: sum([abs(int(x) - int(y)) for x, y in zip(item, myCmpItem)])
于 2012-05-28T21:46:26.920 に答える
4 
def cmpWith(num):
    def compare(item):
        """ calculate the difference between num and item """
        return sum(
            abs(int(n) - int(x)) # cast to int to make the substraction possible
            for x,n in zip(item, num) # zip makes pairs from both lists 
        )

    return compare

lst = ['111','222','333','444','555','123']
print sorted(lst, key=cmpWith('511'))
于 2012-05-28T21:41:38.960 に答える
2

これはどう？

myCmpItem = '511'
myList = ['111','222','333','444','555','123']

def make_key(x):
    diff = 0
    for a, b in zip(x, myCmpItem):
        diff += abs(int(a)-int(b))
    return diff

mySortedList = sorted(myList, key=make_key)

print mySortedList
于 2012-05-28T21:44:39.853 に答える
2

距離の表を事前に計算すると、すべての桁をint

myCmpItem = '511'
myList = ['111','222','333','444','555','123']

# only need to compute this dict once
dists = {(i,j):abs(int(i)-int(j)) for i in '12345' for j in '12345'}

print sorted(myList, key=lambda j: sum(dists[i] for i in zip(j, myCmpItem)))

私のコンピューターでは、100000 x 25 文字列に対する larsmans の回答よりも 2.9 倍高速です。

于 2012-05-29T00:40:47.870 に答える