python - 哪种方法更适合组合多个不重复的列表？

Question

给定一个社交网络，我将返回 friend 关系的 friend 列表。例如，如果 A -> B 且 B -> [C, D] ，则 fxn(A) = [C, D]

假设我已经使用名为“get_connections”的函数收集了用户 A 的 friend 列表 ([B,...,n])(实际上只是返回给定用户的 friend 列表)。我用来执行此过程的原始方法使用两个 For 循环:

return_list = []

for friend in friends_list:
    second_friends_list = get_connections(network, friend)

    # Go through each friend's friend list
    for friends in second_friends_list:
        # Check for duplicates
        if friends not in return_list:
            return_list.append(friends)

return return_list

我通过 Stackoverflow 确定的第二种方法如下:

for friends in friends_list:
    return_list = list(set(return_list) | set(get_connections(network, friends)))

这两种方法有显着差异吗？我对算法的了解很有限，我知道for循环方法是O^2，但我不知道set到底是如何工作的，以便更好地评估它的优势。

Answer 1

集合可以很好地完成此操作 - 使用 list 在这里特别糟糕，因为成员资格测试(in 运算符)发生在 O(N) 中(您必须查看每一个元素，直到找到您正在寻找的元素)。假设好友列表中的好友是可哈希的:

>>> class Friend(object):
...   def __init__(self, friend_list):
...     self.friend_list = list(friend_list)
... 
>>> f1 = Friend('ABCD')
>>> f2 = Friend('CDEF')
>>> f3 = Friend('AGHIJKLMN')
>>> my_friends = [f1, f2, f3]
>>> set().union(*(f.friend_list for f in my_friends))
set(['A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'K', 'J', 'M', 'L', 'N'])

这是一个小演示，其中我使用了 set.union 而不是联合运算符 (|)。不同之处在于方法版本将接受非设置参数，因此您可以避免对集合进行两次迭代。如果您愿意，我们也可以使用常规 set 构造函数和 itertools¹ 来完成此操作:

>>> import itertools
>>> all_friends = itertools.chain.from_iterable(f.friend_list for f in my_friends)
>>> set(all_friends)
set(['A', 'C', 'B', 'E', 'D', 'G', 'F', 'I', 'H', 'K', 'J', 'M', 'L', 'N'])

这两个操作都是 O(M) 操作(其中 M 是所有 friend 列表中的总数或“ friend ”)。

<小时/>

^{1...或者嵌套理解 -- 但我从来不喜欢这些...}