python - 有效地找到最相似的集合(Python，数据结构)

Question

假设我在名为 my_sets 的列表中有几千个 Python 集。对于 my_sets 中的每个集合“A”，我想在 my_sets 中找到包含集合 A 成员百分比最高的五个集合(集合“B”)。

我目前正在将数据存储为集合并循环两次以计算重叠...

from random import randint
from heapq import heappush, heappop

my_sets = []

for i in range(20):
    new_set = set()

    for j in range(20):
        new_set.add(randint(0, 50))

    my_sets.append(new_set)

for i in range(len(my_sets)):
    neighbor_heap = []

    for j in range(len(my_sets)):
        if i == j:
            continue

        heappush(neighbor_heap, (1 / len(my_sets[i] & my_sets[j]), j))

    results = []

    while len(results) < 5:
        results.append(heappop(neighbor_heap)[1])

    print('Closest neighbors to set {} are sets {}'.format(i, results))

但是，这显然是一个 O(N**2) 算法，所以当 my_sets 变长时它就会爆炸。有没有更好的数据结构或算法可以在基本 Python 中实现来解决这个问题？没有理由 my_sets 必须是一个列表，或者每个单独的集合实际上都必须是一个 Python 集合。任何存储每个集合是否包含来自有限选项列表的成员的方法都可以(例如，标准化顺序中的一堆 bool 值或位)。构建一个更奇特的数据结构以节省时间也很好。

(有些人可能会指出，我当然可以将其构造为 Numpy 数组，其中行是集合，列是元素，单元格是 1/0，具体取决于该元素是否在其中设置。然后，你只需执行一些 Numpy 操作。这无疑会更快，但我根本没有真正改进我的算法，我只是将复杂性卸载到其他人的优化 C/Fortran/等等。)

编辑 经过全面测试后，我最初发布的算法在约定的测试条件下运行了约 586 秒。

Answer 1

你能不能:

1. 反转集合，为每个集合元素生成包含它的集合的列表(或集合)。

   它是 O(n*m) -- 对于 n 个集合，平均 每组 m 个元素。

2. 对于每个集合 S，考虑它的元素，并(使用 1)构造一个包含其他集合的列表(或堆)以及每个集合有多少个元素与 S 分享——选出“最好的”5 个。

   是O(n*m*a)，其中a> 是每个元素所属的集合的平均数。

离 O(n*n) 多远显然取决于 m 和 一个。

编辑:Python 中的简单实现在我的机器上运行了 103 秒...

old_time = clock()

my_sets = []

for i in range(10000):
    new_set = set()

    for j in range(200):
        new_set.add(randint(0, 999))

    my_sets.append(new_set)

my_inv_sets = [[] for i in range(1000)]

for i in range(len(my_sets)):
    for j in range(1000):
        if j in my_sets[i]:
            my_inv_sets[j].append(i)

for i in range(len(my_sets)):
    counter = Counter()

    for j in my_sets[i]:
        counter.update(my_inv_sets[j])

    print(counter.most_common(6)[1:])

print(clock() - old_time)