集合

REDIS_SET （集合）是 SADD  、 SRANDMEMBER  等命令的操作对象，它使用 REDIS_ENCODING_INTSET 和 REDIS_ENCODING_HT 两种方式编码：

REDIS_ENCODING_INTSET;    REDIS_SET -> REDIS_ENCODING_HT;    // datastruct 1    intset [label="intset.h/intset"];    REDIS_ENCODING_INTSET -> intset;    // datastruct 2    dict [label="dict.h/dict"];        REDIS_ENCODING_HT -> dict;}" />

编码的选择

第一个添加到集合的元素，决定了创建集合时所使用的编码：

• 如果第一个元素可以表示为 long long 类型值（也即是，它是一个整数）， 那么集合的初始编码为 REDIS_ENCODING_INTSET 。
• 否则，集合的初始编码为 REDIS_ENCODING_HT 。

编码的切换

如果一个集合使用 REDIS_ENCODING_INTSET 编码，那么当以下任何一个条件被满足时，这个集合会被转换成 REDIS_ENCODING_HT 编码：

• intset 保存的整数值个数超过 server.set_max_intset_entries （默认值为 512 ）。
• 试图往集合里添加一个新元素，并且这个元素不能被表示为 long long 类型（也即是，它不是一个整数）。

字典编码的集合

当使用 REDIS_ENCODING_HT 编码时，集合将元素保存到字典的键里面，而字典的值则统一设为 NULL 。

作为例子，以下图片展示了一个以 REDIS_ENCODING_HT 编码表示的集合，集合的成员为 elem1 、 elem2 和 elem3 ：

dictht |

集合命令的实现

Redis 集合类型命令的实现，主要是对 intset 和 dict 两个数据结构的操作函数的包装，以及一些在两种编码之间进行转换的函数，大部分都没有什么需要解释的地方，唯一比较有趣的是 SINTER [http://redis.readthedocs.org/en/latest/set/sinter.html#sinter] 、 SUNION [http://redis.readthedocs.org/en/latest/set/sunion.html#sunion] 等命令之下的算法实现，以下三个小节就分别讨论它们所使用的算法。

求交集算法

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()

    # 剔除所有在 sorted_multi_set[0] 中存在
    # 但在其他某个集合中不存在的元素
    for elem in sorted_multi_set[0]:

        for s in sorted_multi_set[1:]:

            if (not elem in s):
                result.remove(elem)
                break

    return result

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

求并集算法

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

# coding: utf-8

def sunion(*multi_set):

    result = set()

    for s in multi_set:
        for elem in s:
            # 重复的元素会被自动忽略
            result.add(elem)

    return result

算法的复杂度为 (O(N)) 。

求差集算法

Redis 为 SDIFF  和 SDIFFSTORE  两个命令准备了两种求集合差的算法。

以 Python 代码表示的算法一定义如下：

# coding: utf-8

def sdiff_1(*multi_set):

    result = multi_set[0].copy()

    sorted_multi_set = sorted(multi_set[1:], lambda x, y: len(x) - len(y))

    # 当 elem 存在于除 multi_set[0] 之外的集合时
    # 将 elem 从 result 中删除
    for elem in multi_set[0]:

        for s in sorted_multi_set:

            if elem in s:
                result.remove(elem)
                break

    return result

这个算法的复杂度为 (O(N^2)) ，执行步数为 (S*T) ，其中 (S) 为输入集合中基数最小的集合，而 (T) 则为除第一个集合之外，其他集合的数量。

以 Python 代码表示的算法二定于如下：

# coding: utf-8

def sdiff_2(*multi_set):
    # 用第一个集合作为结果集的起始值
    result = multi_set[0].copy()

    for s in multi_set[1:]:
        for elem in s:
            # 从结果集中删去其他集合中包含的元素
            if elem in result:
                result.remove(elem)

    return result

这个算法的复杂度同样为 (O(N^2)) ，执行步数为 (S) ，其中 (S) 为所有集合的基数总和。

Redis 使用一个程序决定该使用那个求差集算法，程序用 Python 表示如下：

# coding: utf-8

from sdiff_1 import sdiff_1
from sdiff_2 import sdiff_2

def sdiff(*multi_set):

    # 算法一的常数项较低，给它一点额外的优先级
    algo_one_advantage = 2 
    algo_one_weight = len(multi_set[0]) * len(multi_set[1:]) / algo_one_advantage

    algo_two_weight = sum(map(len, multi_set))

    if algo_one_weight <= algo_two_weight:
        return sdiff_1(*multi_set)
    else:
        return sdiff_2(*multi_set)

• 上一篇：列表
• 有序集：下一篇