将变量存储为单个位
Storing variables as single bits
在过去的几周里，我一直致力于制作一个程序，使素数螺旋尽可能高效。我研究了多线程以提高程序的速度，现在我 运行 遇到了一个新问题。我的素数列表有 6400 万个零和一的长度，这个列表占用 240MB 的内存。因为我使用多处理（总共5个进程）我的脚本最多使用总共1.1GB的ram，如果达到这一点它returns内存错误。
关于我如何存储素数的一些背景信息：素数存储在一个列表中，每次我找到一个素数，我都会将值设置为 1（例如：Primes[13] = 1（因为它是素数）和素数 [14] = 0）。对我来说，这似乎是最好的解决方案，因为列表不会使用大量内存
经过一些基本的数学运算后，我得出结论，我的素数列表中的每个零或一个都占用 4 个字节（32 位）的信息。这似乎合乎逻辑，但我想知道是否有办法将零和一存储为单个位，这样它就不会占用那么多内存。
提前感谢您的任何回答，
问候，伤害
如果每个 0 或 1 占用 32 位，则表示它是字符（也许是整数？）数组。您应该改用布尔类型 (bool)。最简单的方法是使用位数组。实现之一：
这里有一些 Python2 代码，它创建一个打包成字节的质数文件，每个字节编码 30 个数字块的质数，利用所有大于 5 的质数与 30 互质的事实，并且因此与 (1, 7, 11, 13, 17, 19, 23, 29) mod 30.
中的一个一致
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
'''
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
'''
#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 对象本身的少量开销（28 个字节在 32位机）。
该程序的 main 函数使用 isprime 函数创建一个素数列表。这比使用筛子慢 4 倍，但它的内存开销要少 far。它可能会加快一点，但此类优化将留作 reader 的练习。 :)
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
'''
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()
在我有 2GB RAM 的旧单核 2GHz 机器上，sieve_bin.py 需要大约 26 秒才能为 < 64000020 的数字创建一个 primebits 文件（文件大小 = 2133334 字节）；大约一半的时间花在筛选素数上。 isprime_bin.py 大约需要 124 秒才能从该文件生成素数列表（将输出发送到 /dev/null）。
通过将输出与传统埃拉托色尼筛法程序生成的输出进行比较来验证输出。
isprime_bin.py中的代码旨在测试任意正整数的素数。要简单地生成一个素数列表，它可以大大加快，因为前两个 if 测试仅适用于数字 <= 5。这是一个 mod 化版本，需要大约 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()
在过去的几周里，我一直致力于制作一个程序，使素数螺旋尽可能高效。我研究了多线程以提高程序的速度，现在我 运行 遇到了一个新问题。我的素数列表有 6400 万个零和一的长度，这个列表占用 240MB 的内存。因为我使用多处理（总共5个进程）我的脚本最多使用总共1.1GB的ram，如果达到这一点它returns内存错误。
关于我如何存储素数的一些背景信息：素数存储在一个列表中，每次我找到一个素数，我都会将值设置为 1（例如：Primes[13] = 1（因为它是素数）和素数 [14] = 0）。对我来说，这似乎是最好的解决方案，因为列表不会使用大量内存
经过一些基本的数学运算后，我得出结论，我的素数列表中的每个零或一个都占用 4 个字节（32 位）的信息。这似乎合乎逻辑，但我想知道是否有办法将零和一存储为单个位，这样它就不会占用那么多内存。
提前感谢您的任何回答， 问候，伤害
如果每个 0 或 1 占用 32 位，则表示它是字符（也许是整数？）数组。您应该改用布尔类型 (bool)。最简单的方法是使用位数组。实现之一：
这里有一些 Python2 代码，它创建一个打包成字节的质数文件，每个字节编码 30 个数字块的质数，利用所有大于 5 的质数与 30 互质的事实，并且因此与 (1, 7, 11, 13, 17, 19, 23, 29) mod 30.
中的一个一致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
'''
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
'''
#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 对象本身的少量开销（28 个字节在 32位机）。
该程序的 main 函数使用 isprime 函数创建一个素数列表。这比使用筛子慢 4 倍，但它的内存开销要少 far。它可能会加快一点，但此类优化将留作 reader 的练习。 :)
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
'''
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()
在我有 2GB RAM 的旧单核 2GHz 机器上，sieve_bin.py 需要大约 26 秒才能为 < 64000020 的数字创建一个 primebits 文件（文件大小 = 2133334 字节）；大约一半的时间花在筛选素数上。 isprime_bin.py 大约需要 124 秒才能从该文件生成素数列表（将输出发送到 /dev/null）。
通过将输出与传统埃拉托色尼筛法程序生成的输出进行比较来验证输出。
isprime_bin.py中的代码旨在测试任意正整数的素数。要简单地生成一个素数列表，它可以大大加快，因为前两个 if 测试仅适用于数字 <= 5。这是一个 mod 化版本，需要大约 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()