python - 如果列表项在另一个列表中同时保持顺序，如何将它们移到前面

Question

我有两个示例列表，

vals = ["a", "c", "d", "e", "f", "g"]
xor  = ["c", "g"] 

我想根据 xor 列表对 vals 列表进行排序，即，xor 中的值应该按准确顺序放在 vals 列表的第一位。 vals 中存在的其余值应保持相同的顺序。

此外，在这些情况下，xor 中的值可能不在 vals 中，只是忽略这些值。而且，在重复的情况下，我只需要一个值。

期望的输出:

vals = ["c", "g", "a", "d", "e", "f"]
# here a, d, e, f are not in xor so we keep them in same order as found in vals.

我的方法:

new_list = []
for x in vals:
    for y in xor:
        if x == y:
            new_list.append(x)
            
for x in vals:
    if x not in xor:
        new_list.append(x)

vals 列表目前有大约 80 万个单词或短语。 xor 列表有 30 万个单词或短语，但以后可能会增加。有些短语也有点长。解决问题的最有效方法是什么？

Answer 1

在xor中构建一个索引字典并将其用作排序键:

order = {n: i for i, n in enumerate(xor)}

sorted(vals, key=lambda x: order.get(x, len(xor)))
# ['c', 'g', 'a', 'd', 'e', 'f']

使用 len(vals) 作为默认值确保所有不在 xor 中的值都将在后面结束。这当然假设，您希望 在 xor 中的值根据它们在 xor 中的顺序进行排序(使过程 O(M+NlogN))。否则你可以更快(O(M+N)):

from operator import contains
from functools import partial
s = set(xor)
result = list(filter(partial(contains, s), vals))
result.extend(v for v in vals if v not in s)

或者以更具可读性的方式:

s = set(xor)
result = [v for v in vals if v in s]
result += (v for v in vals if v not in s)