高效比较两个列表，并记住每个唯一元素的来源

Question

考虑到这个示例，它可以找到唯一的元素，同时可以告诉元素的来源

source_list = ["one", "two", "three", "four", "five"]
diff_list = ["zero", "one", "two", "three", "four", "six", "seven"]

source_unique = []
diff_unique = []

for entry in source_list:
    if entry not in diff_list:
        source_unique.append(entry)

for entry in diff_list:
    if entry not in source_list:
        diff_unique.append(entry)

print("Unique elements in source_list: {0}".format(source_unique))
print("Unique elements in diff_list: {0}".format(diff_unique))

###
# Unique elements in source_list: ['five']
# Unique elements in diff_list: ['zero', 'six', 'seven']

在使用额外两个列表和所有这些东西的情况下，是否有更有效的方法来完成这项任务？主要任务是能够确定元素的来源。

- user5164080

Answer 1

通过使用set并取它们的差集，其复杂度为O(len(set_object))：

>>> s1, s2 = set(source_list), set(diff_list)
>>> s1.difference(s2)
{'five'}
>>> s2.difference(s1)
{'seven', 'six', 'zero'}

这也可以写成：

>>> s1 - s2 
{'five'}
>>> s2 - s1
{'seven', 'six', 'zero'}    

在这种情况下，如果需要，您可能需要事后转换为list，相应地使用list(s1 - s2)和list(s2 - s1)。

或者，您可以使用list推导式做同样的事情，并使用source_list和diff_list集进行快速成员测试，使用in运算符：

对于uniques列表：

source_unique = [v1 for v1 in source_list if v1 not in set(diff_list)]
source_unique
['five']

对于diff_unique列表：

diff_unique = [v1 for v1 in diff_list if v1 not in set(source_list)]
diff_unique
['zero', 'six', 'seven']

除非我错了时间复杂度，否则这又是 O(len(list))。

- Dimitris Fasarakis Hilliard

---

如果您在之前将列表转换为集合（set-ified），则可以获得更好的运行时间（in操作的O(1)查找时间）。 - inspectorG4dget

Answer 2

你可以使用集合（sets）：

source_list = ["one", "two", "three", "four", "five"]
diff_list = ["zero", "one", "two", "three", "four", "six", "seven"]


print("Unique elements in source_list: {0}".format(set(source_list)-set(diff_list)))
print("Unique elements in diff_list: {0}".format(set(diff_list)-set(source_list)))

打印输出：

Unique elements in source_list: set(['five'])
Unique elements in diff_list: set(['seven', 'six', 'zero'])

- Heval

---

哦，使用集合看起来非常简单！我找到了相同的问题，但只是关于差异。没想到我能够在两个方向上找到集合的差异！谢谢。 - user5164080

很高兴它有帮助 :) - Heval

但是出于内容的完整性考虑，如果您不介意的话，我会接受Jim的答案，以防其他用户遇到相同的问题。 - user5164080

Answer 3

你可以使用集合来完成它。

source_list = ["one", "two", "three", "four", "five"]
diff_list = ["zero", "one", "two", "three", "four", "six", "seven"]

source_unique = list(set(source_list) -  set(diff_list))
diff_unique =  list(set(diff_list) -  set(source_list))

- Prasanna