python - 根据数据的特征是否相交对数据进行分组

Question

假设我们有一张 table :

id  | aliases
-------------
0   | ['a0', 'a1', 'a4', 'a11']
1   | ['a3', 'a5']
2   | ['a16', 'a18']
3   | ['a6', 'a8', 'a10']
4   | ['a7', 'a8', 'a9']
5   | ['a3', 'a12', 'a14']
6   | ['a5', 'a16', 'a17']

并且我想将映射到相同别名的所有id分组在一起；换句话说，最终结果将所有具有相交的别名的id分组在一起，并递归应用。在上述情况下，我们将:

• 0 映射到 ['a0', 'a1', 'a4', 'a11']
• 1、2、5 和 6 映射到 ['a3', ' a5', 'a12', 'a14', 'a16', 'a17', 'a18']
• 3 和 4 映射到 ['a6', 'a7', 'a8', 'a9', 'a10']

有没有有效的方法来做到这一点？在我的实际用例中，我有大约 1500 万行。

有一种简单的方法可以流式传输行并检查每个新行中的每个别名元素是否在迄今为止处理的别名中；如果是，则将具有匹配别名的所有行的 id 收集在一起，并将它们映射到匹配的 aliases 的并集。

但是，这种方法在计算上似乎不切实际。

Answer 1

要在此表上运行 O(n*len(groupcount) 复杂度代码应该不那么难，只是我的想法:

假设您将 id 作为 id 列表，将 aliases 作为列表列表，您可以执行以下操作:

bins = []
sets = []
for i in id: # Assume from (0 - n)
    alias = aliases[i]
    in_set = False
    for j in range(len(sets)):
        if len(sets[j].intersection(set(alias))) > 0:
            sets[j].update(set(alias)) # add alias to set, if any difference
            in_set = True
            bins[j].append(i) # append id to bins
            break
    if not in_set:
        bins.append([i])
        sets.append(set(alias))

bins 将包含 id 组，sets 中的相应元素将包含 alias 组，您可以使用list()将这些集合转换回list。由于所有集合操作都是基于哈希的，因此可以确保您的程序在 O(n*groupcount) 时间内运行。