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
    • 这两个数字之间的差是 4（数字比较的总和）
  • 对所有其他项目执行相同操作
  • 按此计算的相似度对列表进行排序

我可以用很多 for 循环对此进行编码，但我实际上正在寻找一种更快的方法来做到这一点。有没有类似的算法？快速地？

进一步的限制

  • 在我的示例中，所有项目的长度为 3，在实际场景中，它们的长度为 25
  • 所有项目的长度相同，len(myList[x])==25 始终为真
  • 项目可以是字符串、整数、浮点数或任何更适合算法的东西
  • 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)

（PS：你确定 L1 距离对这个应用有意义吗？使用它表示假设答案 1 与答案 2 比答案 3 更相似，等等。如果不是这样，汉明距离可能更合适。）

于 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)))

在我的电脑上，这比 larsmans 回答 100000 x 25 个字符串的速度快 2.9 倍

于 2012-05-29T00:40:47.870 回答