求交集算法

集合 — Redis 设计与实现

    求交集算法¶

    SINTER 和 SINTERSTORE 两个命令所使用的求并交集算法可以用 Python 表示如下：

    # coding: utf-8

    def sinter(*multi_set):

        # 根据集合的基数进行排序
        sorted_multi_set = sorted(multi_set, lambda x, y: len(x) - len(y))

        # 使用基数最小的集合作为基础结果集，有助于降低常数项
        result = sorted_multi_set[0].copy()

        # 剔除所有在 s[0] 中存在，但在其他集合中不存在的元素
        for elem in sorted_multi_set[0]:
            for s in sorted_multi_set[1:]:
                if (not elem in s) and (elem in result):
                    result.remove(elem)
                    break

        return result

    算法的复杂度为 O(N2) ， 执行步数为 S∗T ， 其中 S 为输入集合中基数最小的集合， 而 T 则为输入集合的数量。