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

Question

我有一个元组列表 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)]

有什么想法吗？

Answer 1

您可以提供一个 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)]

编辑

因为开始了关于时间复杂度的讨论...开始吧，以下算法在 O(n+m) 中运行，使用 Eric 的输入示例:

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