将变量以单比特存储

Question

在过去的几周里，我一直在努力制作一个能够尽可能高效地生成素数螺旋图的程序。我研究了多线程以增加程序的速度，但现在我遇到了一个新问题。我的素数列表有6400万个0和1，这个列表占用了240MB的内存。因为我使用了多进程（总共5个进程），所以我的脚本最多使用1.1GB的内存，如果达到这个点就会返回内存错误。

关于我如何存储素数的一些背景信息：素数存储在一个列表中，每次找到一个素数时，我将该值设置为1（例如：Primes[13] = 1（因为它是素数），而Primes[14] = 0）。对我来说，这似乎是最好的解决方案，因为列表不会使用太多的内存。

经过一些基本的数学计算，我得出结论，我的素数列表中的每个0或1占用4个字节（32位）的信息。这似乎很合理，但我想知道是否有一种方法可以将0和1存储为单个位，这样就不会占用太多的内存。

提前感谢任何答案， 问候，Harm

- user5887651

---

顺便说一下，您可以进一步压缩素数表。每个大于30的质数都与{±1, ±7, ±11, ±13} mod 30之一同余。也就是说，在每个30个数字的块中，只有8个数字（最多）可能是质数，并且质数只能在这些位置上。因此，一个字节的位可以保存30个数字块的质数数据。您可以使用字节数组（https://docs.python.org/2/library/array.html）在Python中高效地保存该信息。 - PM 2Ring

我不太明白你的意思，能否提供一个链接或者澄清一下？ - user5887651

看一下这个质数表，它有30列。注意到所有大于5的质数都在8列中吗？因此，为了压缩我们的质数表，我们只需要为这8列保存位。 - PM 2Ring

只发送这些列相当复杂，但我使用了这些信息使计算过程更加高效（现在仅使用了75%的时间）。谢谢 :) - user5887651

当然，仅使用这8列确实会使代码变得有点复杂。在Python中进行位操作不像在C中那样高效，但正如下面我的代码所示，它并不是太糟糕。顺便说一句，我已经在我的答案中添加了一个更快的“isprime_bin.py”版本。 - PM 2Ring

我明白了，我已经使用stackoverflow很长一段时间，但这是我第一次发帖。谢谢你告诉我 :) - user5887651

Answer 1

如果每个0或1占用32位，这意味着它是字符（或整数？）数组。你应该使用布尔类型（bool）。最简单的方法是使用bitarray，有一个实现方式： https://pypi.python.org/pypi/bitarray/0.8.1。

- Flash Thunder

---

谢谢，这正是我在寻找的，我只是找不到它。我确实使用整数来存储零和一，这显然不是正确的解决方案。 - user5887651

Answer 2

以下是一些Python 2代码，它创建了一个包含质数的文件，并将其打包成字节，每个字节编码30个数字块的素性，利用所有大于5的质数都与30互质的事实，因此它们与模30中的(1,7,11,13,17,19,23,29)之一同余。

sieve_bin.py

#! /usr/bin/env python

''' Prime sieve.

    Save primes to a file with the primes in each block of 30 numbers 
    packed into a byte, utilising the fact that all primes > 5 are
    coprime to 30 and hence are congruent to one of 
    (1, 7, 11, 13, 17, 19, 23, 29) mod 30

    Written by PM 2Ring 2016.02.06
    Prime sieve by Robert William Hanks
    See https://dev59.com/EJPfa4cB1Zd3GeqPHseH
'''

import sys
from array import array

def rwh_primes(n):
    ''' Returns a boolean list of odd primes < n
        Adapted from code by Robert William Hanks
        See https://dev59.com/snI95IYBdhLWcg3w-DH0#3035188
    '''
    #Each `sieve` item represents an odd number, starting at 1
    sieve = [True] * (n//2)
    for i in xrange(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return sieve

def main():
    if len(sys.argv) != 2:
        print '''Generate a file of primes packed into bits.
Usage:
%s hi
to generate a file of primes < `hi`
If `hi` isn't a multiple of 30 it will be rounded down to the nearest multiple of 30
''' % sys.argv[0]
        exit()

    hi = int(sys.argv[1]) // 30 * 30
    fname = 'primebits'

    print 'Generating primes less than %d...' % hi
    odd_primes = rwh_primes(hi)

    print 'Packing primes into bytes...'
    prime_residues = (1, 7, 11, 13, 17, 19, 23, 29)
    bitmasks = [(1<<j, (u - 1) // 2) for j, u in enumerate(prime_residues)]
    packer = (sum(mask for mask, r in bitmasks if odd_primes[i + r])
        for i in xrange(0, hi//2, 15))

    primebytes = array('B', packer)
    with open(fname, 'wb') as f:
        primebytes.tofile(f)
    print 'Saved to', fname


if __name__ == '__main__':
    main()

这里有一个程序，它读取由 sieve_bin.py 创建的 primebits 文件。该文件被读入一个无符号字节数组 array 中，因此在 RAM 使用方面非常高效：每个从文件中读取的数据字节占用一个字节加上 array 对象本身的一些开销（在 32 位机器上为 28 字节）。

该程序的 main 函数使用 isprime 函数创建了一个质数列表。这比使用筛法慢大约 4 倍，但内存开销要小得多。它可能可以稍微加速，但这样的优化将留给读者作为练习。 :)

isprime_bin.py

#! /usr/bin/env python

''' Test if a number is prime, using a table read from disk
    The table contains the primes packed into bytes, with
    each byte encoding the primality of a block of 30 numbers,
    utilising the fact that all primes > 5 are coprime to 30 and
    hence are congruent to one of (1, 7, 11, 13, 17, 19, 23, 29) mod 30

    See https://dev59.com/EJPfa4cB1Zd3GeqPHseH
'''

import sys
import os.path
from array import array

def load_primes(fname):
    primebytes = array('B')
    filesize = os.path.getsize(fname)  
    with open(fname, 'rb') as f:
        primebytes.fromfile(f, filesize)

    return primebytes

prime_residues = (1, 7, 11, 13, 17, 19, 23, 29)
#Build a dict for fast conversion of residue to bitmask
bitmasks = dict((v, 1<<i) for i, v in enumerate(prime_residues))

def isprime(n, primebytes):
    if n < 2:
        return False
    if n in (2, 3, 5):
        return True
    r = n % 30
    if r not in bitmasks:
        return False
    b = primebytes[n // 30]
    return b & bitmasks[r]

#Test
def main():
    m = int(sys.argv[1]) if len(sys.argv) > 1 else 300

    fname = 'primebits'
    primebytes = load_primes(fname)
    primes = [i for i in xrange(m) if isprime(i, primebytes)]
    print primes


if __name__ == '__main__':
    main()

在我的旧单核2GHz机器上，配备2GB的RAM，sieve_bin.py创建一个primebits文件来处理小于64000020的数字（文件大小=2133334字节）需要大约26秒；其中大约一半的时间用于筛选素数。isprime_bin.py从该文件中生成素数列表需要大约124秒（将输出发送到/dev/null）。

通过与传统的Eratosthenes筛程序生成的输出进行比较，已验证输出。

---

isprime_bin.py中的代码旨在测试任意正整数是否为质数。要简单生成素数列表，可以大大加快速度，因为前两个if测试仅适用于数字<= 5。这是一个修改后的版本，它需要约47秒才能从2133334字节的primebits文件中生成所有质数列表。

#! /usr/bin/env python

import sys
import os.path
from array import array

def load_primes(fname):
    primebytes = array('B')
    filesize = os.path.getsize(fname)  
    with open(fname, 'rb') as f:
        primebytes.fromfile(f, filesize)

    return primebytes

prime_residues = (1, 7, 11, 13, 17, 19, 23, 29)
#Build a dict for fast conversion of residue to bitmask
bitmasks = dict((v, 1<<i) for i, v in enumerate(prime_residues))

def isprime(n, primebytes):
    r = n % 30
    if r not in bitmasks:
        return False
    b = primebytes[n // 30]
    return b & bitmasks[r]

def primes(primebytes):
    s = (2, 3, 5) + prime_residues[1:]
    for i in s:
        yield i
    s = prime_residues
    j = 30
    while True:
        try:
            for i in s:
                p = j + i
                if isprime(p, primebytes):
                    yield p
            j += 30
        except IndexError:
            return

#Test
def main():
    m = int(sys.argv[1]) if len(sys.argv) > 1 else 300

    fname = 'primebits'
    primebytes = load_primes(fname)
    primelist = []
    for p in primes(primebytes):
        if p > m:
            break
        primelist.append(p)
    print primelist


if __name__ == '__main__':
    main()

- PM 2Ring