如何根据另一个列表对元组列表进行排序

Question

这里有一个列表：

a = [("ax", 1), ("ec", 3), ("bk", 5)]

另一个列表：

b = ["ec", "ax", "bk"]

我想要按照b对a进行排序：

sort_it(a, b)

a = [("ec", 3), ("ax", 1), ("bk", 5)]

如何做到这一点？

- alwbtc

---

@jpp，这实际上不是https://dev59.com/PGw15IYBdhLWcg3wbbNx的重复。这个问题是关于将一个列表的顺序与另一个列表对齐，而另一个问题是关于使用第二个列表的值作为第一个列表的排序键。尝试在那里给出的解决方案，你会发现它不能产生期望的结果。同样，如果你试图将此处接受的解决方案应用于那个情况，你将会得到一个`ValueError`。 - Aryeh Leib Taurog

@AryehLeibTaurog，我很感激你的想法，所以我又重新打开了它。在我看来，它们彼此都是相互适应的。如果一个解决方案被理解了，那么另一个解决方案就显而易见了。我们不想走的路是为len-2元组、len-3元组、len-4元组等单独找出解决方案的路线。 - jpp

Answer 1

a.sort(key=lambda x: b.index(x[0]))

这将使用b中每个元组的第一个元素在a中查找其索引值，并以此为排序依据，对a进行原地排序。

另一种可能更清晰的写法是：

a.sort(key=lambda (x,y): b.index(x))

如果你有大量的项目，可能更有效率的做法是稍微改变一下方式，因为在长列表上，.index() 可能是一个昂贵的操作，而且你实际上并不需要进行完全排序，因为你已经知道了顺序。

mapping = dict(a)
a[:] = [(x,mapping[x]) for x in b]

注意，这仅适用于2元组列表。如果您希望它适用于任意长度的元组，您需要稍微修改一下：

mapping = dict((x[0], x[1:]) for x in a)
a[:] = [(x,) + mapping[x] for x in b]

- Amber

---

我得到了这个错误信息 :( TypeError: unhashable type: 'list' - Trect

我不喜欢这个答案，因为它非常专门用于按其第一个元素排序元组的目的，而且显然不知道如何将此解决方案推广到其他情况。任意长度的元组排序代码还假定每个元组都有唯一的第一个元素；如果任何两个元组具有相同的第一个元素，则其中一个元组将被悄悄地丢弃。 - Aran-Fey

Answer 2

另一种可能是对a进行排序，根据b对索引进行排序，然后根据索引对a进行排序。

a.sort(key=lambda x: x[0])
ind = [i[0] for i in sorted(enumerate(b),key=lambda x: x[1])]
a = [i[0] for i in sorted(zip(a,ind),key=lambda x: x[1])]

由于每个排序都需要n*log(n)，因此对于更大的列表仍然具有可扩展性。

- fritz-johann

---

Python的for循环不是一种好的排序方式。 - Trect

Answer 3

实际上，有一种方法可以在线性O(n)时间内完成这个操作，因为这不是真正的排序操作。列表b的存在意味着排序已经完成了；我们真正需要做的就是重新排列a中的元素以使其按照相同的顺序排列。这可以通过使用字典来高效地完成。

from collections import defaultdict

def sorted_by(seq_to_sort, desired_order, key=None):
    if key is None:
        key = lambda x: x

    # group the elements by their key
    grouped_items = defaultdict(list)
    for item in seq_to_sort:
        k = key(item)
        grouped_items[k].append(item)

    # flatten the dict of groups to a list
    return [item for key in desired_order for item in grouped_items[key]]

使用方法：

a = [("ax", 1), ("ec", 3), ("bk", 5)]
b = ["ec", "ax", "bk"]
result = sorted_by(a, b, lambda tup: tup[0])
print(result)  # output: [("ec", 3), ("ax", 1), ("bk", 5)]

最初的回答

备注：

• This is a stable sort; if two list items have the same key, their order will be preserved. Example:

  >>> sorted_by([1, 2, 3], [5], key=lambda x: 5)
  [1, 2, 3]
  

• If any list elements are mapped to keys that don't exist in desired_order, those elements are silently discarded. For example:

  >>> sorted_by([1, 2, 3], [1, 2, 3], key=lambda x: 5)
  []
  

See also:

• defaultdict

- Aran-Fey

---

这很棒，但如果元组列表比所需的顺序更长怎么办？ - Umar.H

你有没有另一种解决方案，可以处理列表 desired_order 中包含重复元素的情况？例如，sorted_by([('a', 1), ('a', 2), ('b', 3), ('c', 4)], ['a', 'b', 'c', 'a'], key=lambda tup: tup[0]) 应该返回 [('a', 1), ('b', 3), ('c', 4), ('a', 2)] 或 [('a', 2), ('b', 3), ('c', 4), ('a', 1)]，其中一个 ('a', _) 元组映射到一个 'a' 键，而另一个元组映射到另一个键。 - Stef

Answer 4

传统排序可能不是必要的。

[tup for lbl in b for tup in a if tup[0] == lbl]
# [('ec', 3), ('ax', 1), ('bk', 5)]

- pylang

---

这是由于有两个for循环，这种情况不好。在Python中，for循环并不好用。最好使用lambda函数。 - Trect

“Bad”可能并不准确。一般来说，嵌套循环可能具有O(n^2)的时间复杂度，但在Python中，列表推导式是高效的，特别是对于像OP这样的小输入。在这种情况下，“显式优于隐式”。此外，我认为Python的创造者会不同意您对lambda的看法，因为他声称"... lambda比列表推导式慢"。 - pylang