Python 中小集合的性能

Question

我正在寻找在 Python 中表示给定范围（例如 0-10）内的小整数集的最有效方法。在这种情况下，效率意味着快速构造（从未排序的列表）、快速查询（每个集合上几个查询）以及相当快速地构造排序版本（可能每十个集合一次左右）。先验候选人是：

• 使用Python内置的

  set

  类型（快速查询）
• 使用排序数组（也许构建起来更快？）
• 使用位数组（如果我使用 C 语言，一切都会很快……但我怀疑 Python 是否会那么高效（？））。

对于选择哪一个有什么建议吗？

Answer 1

我会使用位图并将“集合”的成员存储在

int

中...在这种情况下，实际上可能比内置

set

类型更快 - 尽管我还没有测试过。它肯定会需要更少的存储空间。

更新

我现在没有时间做一个完整的类似实现并针对 Python 的内置类对其进行基准测试，但我认为这是一个说明我的建议的工作示例。正如我认为您会同意的那样，代码看起来相当快并且内存效率很高。

鉴于 Python 几乎透明的“无限”长整数功能，所编写的内容将自动处理比您需要的范围大得多的整数值，尽管这样做可能会减慢速度。 ;)

class BitSet(object):
    def __init__(self, *bitlist):
        self._bitmap = 0
        for bitnum in bitlist:
            self._bitmap |= (1 << bitnum)

    def add(self, bitnum):
        self._bitmap |= (1 << bitnum)

    def remove(self, bitnum):
        if self._bitmap & (1 << bitnum):
            self._bitmap &= ~(1 << bitnum)
        else:
            raise KeyError

    def discard(self, bitnum):
       self._bitmap &= ~(1 << bitnum)

    def clear(self):
        self._bitmap = 0

    def __contains__(self, bitnum):
        return bool(self._bitmap & (1 << bitnum))

    def __int__(self):
        return self._bitmap

if __name__ == '__main__':

    bs = BitSet()

    print '28 in bs:', 28 in bs
    print 'bs.add(28)'
    bs.add(28)
    print '28 in bs:', 28 in bs

    print
    print '5 in bs:', 5 in bs
    print 'bs.add(5)'
    bs.add(5)
    print '5 in bs:', 5 in bs

    print
    print 'bs.remove(28)'
    bs.remove(28)
    print '28 in bs:', 28 in bs

Answer 2

在这种情况下，您可能只使用 True/False 值列表。

set

使用的哈希表将执行相同的操作，但它将包括哈希、存储桶分配和冲突检测的开销。

myset = [False] * 11
for i in values:
    myset[i] = True
mysorted = [i for i in range(11) if myset[i]]

一如既往，您需要自己计时，以了解它在您的情况下如何发挥作用。

Answer 3

我的建议是坚持使用内置的

set()

。编写在性能上击败内置 C 代码的 Python 代码将非常困难。如果您依赖内置的 C 代码，构建速度和查找速度将是最快的。

对于排序列表，最好的选择是使用内置排序功能：

x = set(seq) # build set from some sequence
lst = sorted(x)  # get sorted list from set

一般来说，在Python中，编写的代码越少，速度就越快。您越能依赖 Python 的内置 C 基础，速度就越快。在许多情况下，解释型 Python 比 C 代码慢 20 倍到 100 倍，并且与仅按预期使用内置功能相比，要聪明到领先是极其困难的。

如果保证您的集合始终是 [0, 10] 范围内的整数，并且您希望确保内存占用尽可能小，那么整数内的位标志将是最佳选择。

pow2 = [2**i for i in range(32)]

x = 0  # set with no values
def add_to_int_set(x, n):
    return x | pow2[n]

def in_int_set(x, n):
    return x & pow2[n]

def list_from_int_set(x):
    return [i for i in range(32) if x & pow2[i]]

我敢打赌这实际上比使用内置

set()

函数要慢，但你知道每个集合只是一个

int

对象：4 个字节，加上 Python 对象的开销。

如果您确实需要数十亿个列表，则可以使用 NumPy

array

而不是 Python 列表来节省空间； NumPy

array

将仅存储裸整数。事实上，NumPy 具有 16 位整数类型，因此如果您的集合实际上仅在 [0, 10] 范围内，您可以使用 NumPy 将存储大小减少到每个字节

array

。

http://www.scipy.org/FAQ#head-16a621f03792969969e44df8a9eb360918ce9613

Answer 4

即使对于小型集合，使用集合进行“包含”检查也会更快。

>>> Timer("3 in values", 'values = [range(10)]').timeit(number = 10**7)
0.5200109481811523
>>> Timer("3 in values", 'values = set(range(10))').timeit(number = 10**7)
0.2755239009857178

另一方面，正如您所指出的，构建集合需要更长的时间。

>>> Timer("set(range(10))").timeit(number = 10**7)
5.87517786026001
>>> Timer("list(range(10))").timeit(number = 10**7)
4.129410028457642

排序时也有一些差异：

>>> Timer("sorted(values)", 'values = set(range(10, 0, -1))').timeit(number = 10**7)
5.277467966079712
>>> Timer("sorted(values)", 'values = list(range(10, 0, -1))').timeit(number = 10**7)
4.3836448192596436
>>> Timer("values.sort()", 'values = list(range(10, 0, -1))').timeit(number = 10**7)
2.073429822921753

就地排序速度明显更快，并且仅适用于列表。

因此，如果您只对每个集合执行少量查询，则列表的性能更高。当进行大量查询时，我会使用集合。
无论哪种情况，小集合之间的差异都很小。

不建议在 Python 中构建自己的集合类型以获得更好的性能。