2

我正在寻找最有效的方法来表示 Python 中给定范围（比如 0-10）内的一小组整数。在这种情况下，效率意味着快速构建（来自未排序的列表）、快速查询（每个集合上的几个查询）和合理快速构建排序版本（可能每十个集合一次左右）。先验的候选人正在使用 Python 的内置集合类型（快速查询），使用排序数组（可能更快地构造？），或使用位数组（如果我在 C 中，一切都快......但我怀疑 Python 会高效（？））。关于选择哪一个有什么建议吗？

谢谢。

4

4 回答 4

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
于 2012-06-13T22:02:32.077 回答
0

在这种情况下，您可能只使用 True/False 值列表。使用的哈希表set将做同样的事情，但它将包括哈希、桶分配和冲突检测的开销。

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

与往常一样，您需要自己计时，以了解它在您的情况下是如何工作的。

于 2012-06-13T22:12:04.540 回答
0

我的建议是坚持使用内置的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 对象的开销。

如果你真的需要数十亿个，你可以通过使用 NumPyarray而不是 Python 列表来节省空间；NumPyarray将只存储裸整数。事实上，NumPy 有一个 16 位整数类型，所以如果你的集合真的只在 [0, 10] 的范围内，你可以使用 NumPy 将存储大小缩小到每个字节array。

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

于 2012-06-13T21:57:26.010 回答
0

即使对于小型集合，“包含”检查对集合的结果也相当快。

>>> 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 中构建自己的集合类型以获得更好的性能。

于 2020-09-03T13:11:02.443 回答