Python 整数集合占用内存过大

5 投票

6 回答

2491 浏览

提问于 2025-04-16 06:47

设置

Python 2.6
Ubuntu x64

我有一组独特的整数，值在1到50000000之间。新的整数会随机添加，比如说用 numberset.add(random.randint(1, 50000000)) 这个方法。我需要能够快速添加新的整数，并且快速检查某个整数是否已经存在。

问题

过了一段时间，这个集合变得太大，超出了我这个内存较小的系统的承受能力，导致出现了 MemoryError 错误。

疑问

我该如何在使用更少内存的情况下实现这个功能？有没有什么快速的方法可以利用磁盘，而不需要重新配置系统，比如说交换文件？我是否应该使用像sqlite这样的数据库文件？有没有库可以在内存中压缩这些整数？

数据库数据结构数据压缩内存优化磁盘存储唯一性检查整数集合交换文件

6 个回答

可以用一个比特数组来为每个整数设置标志，这样只需要大约5000万比特的内存（大约6MB）。有一些模块可以帮助实现这个功能。这个例子使用了bitstring，另外一个选择是bitarray：

from bitstring import BitArray
i = BitArray(50000000) # initialise 50 million zero bits
for x in xrange(100):
    v = random.randint(1, 50000000)
    if not i[v]: # Test if it's already present
        i.set(1, v) # Set a single bit

设置和检查这些比特的速度非常快，而且占用的内存也很少。

回答于 2025-04-16 由 Python大师

分享举报

使用一个位数组。这样可以减少对大量空间的需求。

相关的StackOverflow问题：

Python中相当于Java的BitSet

回答于 2025-04-16 由 Python大师

分享举报

你可以通过自己编写代码来避免依赖第三方的位数组模块，因为所需的功能其实很简单：

import array

BITS_PER_ITEM = array.array('I').itemsize * 8

def make_bit_array(num_bits, initially=0):
    num_items = (num_bits + BITS_PER_ITEM - 1) // BITS_PER_ITEM
    return array.array('I', [initially]) * num_items

def set_bit(bit_array, offset):
    item_index = offset // BITS_PER_ITEM
    bit_index = offset % BITS_PER_ITEM
    bit_array[item_index] |= 1 << bit_index

def clear_bit(bit_array, offset):
    item_index = offset // BITS_PER_ITEM
    bit_index = offset % BITS_PER_ITEM
    bit_array[item_index] &= ~(1 << bit_index)

def get_bit(bit_array, offset):
    item_index = offset // BITS_PER_ITEM
    bit_index = offset % BITS_PER_ITEM
    return (bit_array[item_index] >> bit_index) & 1

回答于 2025-04-16 由 Python大师

分享举报

Python 整数集合占用内存过大

6 个回答

撰写回答