高效地按序列排序列表

Question

假设我有两个列表：

sequence = [25, 15, 20, 15, 25, 25]
l = [(25, 'banana'), 
     (25, 'apple'), 
     (25, 'pine'), 
     (20, 'soap'), 
     (15, 'rug'), 
     (15, 'cloud')]

我希望对第二个列表 l 进行按序列排序。在这个例子中，数字 25 出现了多次，这种情况下，只要元组的值为 25，它所在的位置并不重要。两个列表长度总是相同的。

我目前的方法是：

r = list(range(len(sequence)))

for i, v in enumerate(sequence):
    for e in l:
        if e[0] == v:
            r[i] = e
            l.remove(e)
print(r)

可能的输出：

[(25, '香蕉'), (15, '地毯'), (20, '肥皂'), (15, '云'), (25, '苹果'), (25, '松果')]

您是否有更好的方法？

感谢您的帮助！

Muff

- Raggamuffin

---

l 中是否可能存在重复的元组？ - Jared Goguen

不，名称是唯一的。只有数字可以重复。 - Raggamuffin

Answer 1

是的。首先创建一个默认字典，以数字为键，并将每个键的名称作为值（作为列表）。

sequence = [25, 15, 20, 15, 25, 25]
l = [(25, 'banana'),
     (25, 'apple'),
     (25, 'pine'),
     (20, 'soap'),
     (15, 'rug'),
     (15, 'cloud')]

from collections import defaultdict

d = defaultdict(list)
for i,n in l:
    d[i].append(n)

然后，迭代序列并使用list.pop从相关列表中删除（匹配数字）一个项（每个列表中必须有足够的项和键，否则你将得到Python异常（空列表/键错误））：

result = [(i,d[i].pop()) for i in sequence]
print(result)

结果：

[(25, 'pine'), (15, 'cloud'), (20, 'soap'), (15, 'rug'), (25, 'apple'), (25, 'banana')]

顺序与预期输出不同，但数字与名称相匹配，这就是重点。如果您想要相同的顺序，只需删除第一个项目即可（在列表中性能较差，因此如果可以选择，请通过最后一个项目插入和删除项目，这样更快）：

result = [(i,d[i].pop(0)) for i in sequence]

提供：

[(25, 'banana'), (15, 'rug'), (20, 'soap'), (15, 'cloud'), (25, 'apple'), (25, 'pine')]

- Jean-François Fabre

---

@JaredGoguen，是的。我的回答提出了pop()和pop(0)，只要数字/名称匹配，似乎就没有关系。 - Jean-François Fabre

如果使用 pop(0) 时性能成为问题，可以考虑使用 collections.deque 和 popleft() 来代替 list 和 pop(0)。 - SethMMorton

Answer 2

另一种选项是使用关键函数进行排序，该函数将从“序列”中删除已使用的元素（此方法会修改“序列”，因此如果稍后需要“序列”，则应创建副本）：

sequence = [25, 15, 20, 15, 25, 25]
l = [(25, 'banana'), 
     (25, 'apple'), 
     (25, 'pine'), 
     (20, 'soap'), 
     (15, 'rug'), 
     (15, 'cloud')]

def key_func(_tuple):
    idx = sequence.index(_tuple[0])
    sequence[idx] = None
    return idx

l.sort(key=key_func)

正如Jared Goguen所说，如果您需要保留“sequence”（序列），下一个包装器将会有所帮助：

def get_key_func(sequence):
    sequence_copy = sequence[:]
    def key_func(_tuple):
        idx = sequence_copy.index(_tuple[0])
        sequence_copy[idx] = None
        return idx
    return key_func

l.sort(key=get_key_func(sequence))

- Vsevolod Kulaga

---

或者使用 sorted(l, key=key_func)，它不会就地修改。 - Wondercricket

你可以将 key_func 包装在一个外部函数中，该函数接受一个序列作为参数，复制它，并返回引用复制序列的内部函数。 - Jared Goguen

将排序键中的列表元素设置为None是很聪明的。然而，由于list.index的时间复杂度为O(n)，所以复杂度将为O(n^2 * log(n))。 - timgeb

Answer 3

我的想法与Jean的类似，但我使用的是列表迭代器而不是pop方法(如果您从前面弹出，则运行时间为O(n)，但如果您从末尾弹出，则运行时间为O(1))。

>>> from collections import defaultdict
>>> supply = defaultdict(list)
>>> for k, v in l:
...     supply[k].append(v)
... 
>>> supply_iter = {k:iter(v) for k,v in supply.items()}
>>> [(k, next(supply_iter[k])) for k in sequence]
[(25, 'banana'), (15, 'rug'), (20, 'soap'), (15, 'cloud'), (25, 'apple'), (25, 'pine')]

< p > next 方法还允许将第二个参数作为可选的默认值（在这里选择 None 是一个不错的选择）。

- timgeb

---

感谢您提供这个简洁明了的解决方案 - 您能否解释一下 supply_iter 赋值语句中的 k:iter(v) 部分？我知道这是一个字典推导式，但我从未使用过这个 iter 对象。 - Raggamuffin

@Raggamuffin 没问题。你提到的那一行代码创建了一个字典，就像 supply 一样，但是所有的值都是 list_iterator 对象。这个想法是迭代器每次调用 next 时都会产生一个新的项。尝试 myiter = iter([1,2,3]); next(myiter); next(myiter); - timgeb

谢谢！我选择了你的解决方案，因为我学到了最多，并且它似乎是最有效的。 - Raggamuffin

Answer 4

您可以在循环之前不设置数组并且不使用enumerate来完成它。我认为这样做可能不会更快，但可能更容易理解。

r =[]

for val in sequence:
    for key, elem in l:
        if key == val:
            temp = (val, elem)
            r.append(temp)
            l.remove(temp)
            break # break the loop thru element to avoid having 2 elements of the same "key"
print(r)

- Nicolas M.

---

双重循环？O(n**2)复杂度，而且你正在迭代时从l中删除项目。这不是一个好主意。 - Jean-François Fabre

O(n*2) 是最小可能的吗？使用 defaultdict 的解决方案使用 O(n) 填充 supply dict 和 O(n) 用于 supply_iter，再加上 O(n) 用于最终数组。使用 sort + index 的解决方案是 O(nlog(n)) + O(n)。我是对的吗？此外，使用 pop，l 中的循环在每次转换时都会减少。感谢您的反馈。 - Nicolas M.

没有问题；当你有一个双层循环时，复杂度是O(n**2)。此外：当你不得不在某个地方放置一个break时，那大多数情况下是因为你没找到非线性搜索方式。而最烦人的是在迭代过程中修改l。在循环中比较key会揭示出key并不是真正的“关键”。 - Jean-François Fabre

Answer 5

另一种方法，

sequence = [25, 15, 20, 15, 25, 25]
list1 = [(25, 'banana'), 
     (25, 'apple'), 
     (25, 'pine'), 
     (20, 'soap'), 
     (15, 'rug'), 
     (15, 'cloud')]
     
_dict = {}

# organised duplicates into dict
for a, b in list1 :
    _dict.setdefault(a, []).append(b)

print(_dict)

index_list = []

# append based on sequence using pop to avoid duplicates 
for key in sequence:
    next_in_line = _dict[key].pop(0)
    index_list.append((key, next_in_line))
   
print(index_list)

提供

{25: ['banana', 'apple', 'pine'], 20: ['soap'], 15: ['rug', 'cloud']}
[(25, 'banana'), (15, 'rug'), (20, 'soap'), (15, 'cloud'), (25, 'apple'), (25, 'pine')]

[Program finished]

- Subham