logo标签列表

使用另一个列表对元组列表进行排序

pythonlistsortingtuples
13

我有一个元组列表to_order，例如：

to_order = [(0, 1), (1, 3), (2, 2), (3,2)]

给出一个列表，它指定了对 to_order 每个元组的第二个元素应用的顺序：

order = [2, 1, 3]

所以我正在寻找一种方法来获得这个输出:

ordered_list = [(2, 2), (3,2), (0, 1), (1, 3)]

有什么想法吗？

2
"tie-breaker" 策略？ - Ma0
默认的平局处理方式是稳定排序吗？ - Reblochon Masque
1
这个问题不是重复的，至少不是与被提出的那个问题重复。链接的问题有相等长度的列表。在上面的问题中，一个order索引有多个to_order对。所谓重复的高效方法（使用“mapping”）在这种情况下不适用。 - Eric Duminil
@EricDuminil 没关系。如果其他相关的问题不适用，它应该解释为什么不适用。每个读者都不应该去做所有的研究工作。 - jpmc26
@jpmc26 你说得对。抱歉，我无法抵制寻找替代的、更有效的编写方式，即使是针对不太清晰的问题。 - Eric Duminil
显示剩余3条评论
4个回答
23

您可以提供一个key，它将检查在order中第二个元素的索引，并基于其进行排序：

to_order = [(0, 1), (1, 3), (2, 2), (3,2)]
order = [2, 1, 3]
print(sorted(to_order, key=lambda item: order.index(item[1]))) # [(2, 2), (3, 2), (0, 1), (1, 3)]

编辑

既然讨论了时间复杂度，以下算法在使用Eric的输入示例时运行时间为O(n+m):

N = 5
to_order = [(randrange(N), randrange(N)) for _ in range(10*N)]
order = list(set(pair[1] for pair in to_order))
shuffle(order)


def eric_sort(to_order, order):
    bins = {}

    for pair in to_order:
        bins.setdefault(pair[1], []).append(pair)

    return [pair for i in order for pair in bins[i]]


def alfasin_new_sort(to_order, order):
    arr = [[] for i in range(len(order))]
    d = {k:v for v, k in enumerate(order)}
    for item in to_order:
        arr[d[item[1]]].append(item) 
    return [item for sublist in arr for item in sublist]


from timeit import timeit
print("eric_sort", timeit("eric_sort(to_order, order)", setup=setup, number=1000))
print("alfasin_new_sort", timeit("alfasin_new_sort(to_order, order)", setup=setup, number=1000))

输出:

eric_sort 59.282021682999584
alfasin_new_sort 44.28244407700004
评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Andy
我如何对元组的第一和第二项进行排序，而不仅仅是第二项？ - user3352632
@user3352632 如果我理解正确，您正在询问“词典顺序”（首先按第一项排序，然后按第二项排序）。如果这是您要求的，您可以尝试：sorted(to_order, key=lambda x: (x[0], x[1])) 但是我IRC那是默认行为，所以您也可以简单地执行：sorted(to_order)。 - Nir Alfasi
20

算法

你可以根据第二个元素将元组分发到一个列表的字典中，并迭代 order 索引以获取排序后的列表：

from collections import defaultdict
to_order = [(0, 1), (1, 3), (2, 2), (3, 2)]
order = [2, 1, 3]

bins = defaultdict(list)

for pair in to_order:
    bins[pair[1]].append(pair)

print(bins)
# defaultdict(<class 'list'>, {1: [(0, 1)], 3: [(1, 3)], 2: [(2, 2), (3, 2)]})

print([pair for i in order for pair in bins[i]])
# [(2, 2), (3, 2), (0, 1), (1, 3)]

sort或index不需要，输出是稳定的。

这个算法类似于所谓的重复中提到的mapping。这个链接的答案只适用于to_order和order具有相同的长度，这在OP的问题中并不是情况。

性能

该算法对to_order的每个元素进行两次迭代。复杂度为O(n)。@alfasin的第一个算法要慢得多（O(n * m * log n)），但他的第二个算法也是O(n)。

这里是一个包含10000个随机对的列表，介于0和1000之间。我们提取唯一的第二个元素，并将它们混洗以定义order：

from random import randrange, shuffle
from collections import defaultdict
from timeit import timeit
from itertools import chain

N = 1000
to_order = [(randrange(N), randrange(N)) for _ in range(10*N)]
order = list(set(pair[1] for pair in to_order))
shuffle(order)


def eric(to_order, order):
    bins = defaultdict(list)
    for pair in to_order:
        bins[pair[1]].append(pair)
    return list(chain.from_iterable(bins[i] for i in order))


def alfasin1(to_order, order):
    arr = [[] for i in range(len(order))]
    d = {k:v for v, k in enumerate(order)}
    for item in to_order:
        arr[d[item[1]]].append(item) 
    return [item for sublist in arr for item in sublist]

def alfasin2(to_order, order):
    return sorted(to_order, key=lambda item: order.index(item[1]))

print(eric(to_order, order) == alfasin1(to_order, order))
# True
print(eric(to_order, order) == alfasin2(to_order, order))
# True

print("eric", timeit("eric(to_order, order)", globals=globals(), number=100))
# eric 0.3117517130003762
print("alfasin1", timeit("alfasin1(to_order, order)", globals=globals(), number=100))
# alfasin1 0.36100843100030033
print("alfasin2", timeit("alfasin2(to_order, order)", globals=globals(), number=100))
# alfasin2 15.031453827000405
这取决于 to_order 事先是否按第一个键进行预排序，否则您将获得不同的输出，例如 to_order = [(0, 1), (3, 2), (2, 2), (1, 3)] 将输出 [(3, 2), (2, 2), (0, 1), (1, 3)]。 - Matt
@Matt：我不确定我理解你的观点。这个算法按order排序。如果一对具有相同的第二个元素，则它们按照输入中的顺序返回。这与描述和其他答案一致。如果您想对每个子列表进行排序，可以在bins.values()中这样做。 - Eric Duminil
谢谢，我也选择使用字典方法。 - RadaKk
@Eric 对不起，我写那条评论时还没喝够咖啡。我的意思是值得注意的是，匹配项可能不会按预期顺序排序。 - Matt
@miradulo：谢谢你的评论。我尝试了你的建议，它节省了1到2个百分点，但对我来说假设有点过多。chain.from_iterable是一个很好的改进，特别是如果你可以在不将其转换为列表的情况下使用它。 - Eric Duminil
显示剩余5条评论
3
另一种解决方案: [item for key in order for item in filter(lambda x: x[1] == key, to_order)] 这个解决方案首先根据order对to_order进行过滤，对于order中的每个key，筛选出与该key相等的元素。
等价于：
ordered = []
for key in order:
    for item in filter(lambda x: x[1] == key, to_order):
        ordered.append(item)

更简洁的写法，但我不知道如何用列表推导式实现：

ordered = []
for key in order:
    ordered.extend(filter(lambda x: x[1] == key, to_order))

注意：如果to_order包含元组x，并且x [1]不在order中，则不会抛出 ValueError 。
Ev Kounis用列表推导式编写了一个类似的解决方案：[x for y in order for x in to_order if x[1] == y]。然而，它非常慢，甚至比被接受的答案还要慢。 - Eric Duminil
2

个人而言，我更喜欢使用list对象的sort函数，而不是内置的sort函数，因为后者会生成一个新列表，而不是直接改变原列表。

to_order = [(0, 1), (1, 3), (2, 2), (3,2)]
order = [2, 1, 3]
to_order.sort(key=lambda x: order.index(x[1]))
print(to_order)
>[(2, 2), (3, 2), (0, 1), (1, 3)]

在此解释一下：sort方法的key参数基本上会对列表进行预处理，并根据某个度量对所有值进行排名。在我们的情况下，order.index()查看当前处理的项的第一次出现并返回其位置。
x = [1,2,3,4,5,3,3,5]
print x.index(5)
>4
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接