使用太多内存的大规模Python整数集

Question

建立

• Python 2.6
• Ubuntu x64

我有一组独特的整数,其值介于1到5千万之间.随机添加新的整数,例如numberset.add(random.randint(1, 50000000)).我需要能够快速添加新的整数并快速检查是否已存在整数.

问题

过了一会儿,这套装置对我的低内存系统来说变得太大了,我体验到了MemoryError.

题

如何在使用更少内存的同时实现这一目标？使用磁盘而不重新配置系统(例如交换文件)的最快方法是什么？我应该使用像sqlite这样的数据库文件吗？是否有一个库可以压缩内存中的整数？

Answer 1

使用位数组.这将减少对巨大空间需求的需求.

实现了SO问题:

• Python相当于Java的BitSet

Answer 2

您可以通过自己编写来避免对第三方位阵列模块的依赖 - 所需的功能相当小:

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