python - framework - tutorial django

Almacenamiento de variables como bits individuales

Question

durante las últimas semanas he estado trabajando en la creación de un programa que pueda hacer que las espirales principales sean lo más eficientes posible. Busqué en multihilo para aumentar la velocidad del programa, y ​​ahora me encontré con un nuevo problema. Mi lista de números primos tiene una longitud de 64 millones de ceros y unos, y esta lista ocupa 240 MB de ram. porque utilizo el multiprocesamiento (5 procesos en total), mi script usa un total de 1.1 GB de RAM como máximo, y si llega a este punto, devuelve un error de memoria.

Algunos antecedentes sobre cómo estoy almacenando los números primos: los números primos se almacenan en una lista, y cada vez que encuentro un número primo, establezco el valor en 1 (ejemplo: Primes [13] = 1 (porque es el principal), y Primes [14] = 0). Para mí, esta parecía ser la mejor solución, ya que la lista no usaría mucha memoria

Después de algunas matemáticas básicas, concluí que cada cero o uno en mi lista de primos tomaba 4 bytes (32 bits) de información. Esto parece lógico, pero me preguntaba si hay una forma de almacenar los ceros y los cero como bits individuales, por lo que no ocupará tanta memoria.

Gracias de antemano por cualquier respuesta, Saludos, Daño

Answer 1

Si cada 0 o 1 toma 32 bits, significa que es una matriz de caracteres (¿tal vez un número entero?). Debería usar boolean type ( bool ) en su lugar. La forma más sencilla de hacerlo es usar bitarray. Una de las implementaciones:

https://pypi.python.org/pypi/bitarray/0.8.1

Answer 2

Aquí hay un código de Python 2 que crea un archivo de primos empaquetados en bytes, con cada byte que codifica la primalidad de un bloque de 30 números, utilizando el hecho de que todos los primos> 5 son coprimos a 30 y por lo tanto son congruentes con uno de (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 http://.com/q/35222244/4014959
''''''

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 http://.com/a/3035188/4014959
    ''''''
    #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()

Y aquí hay un programa que lee el archivo de primebits creado por sieve_bin.py . El archivo se lee en una matriz de bytes sin firmar, por lo que es eficiente en el uso de la RAM: un byte por byte de datos leídos del archivo más una pequeña sobrecarga para el objeto de la array (28 bytes en una máquina de 32 bits).

La función main de este programa crea una lista de primos utilizando la función isprime . Esto es aproximadamente 4 veces más lento que con un tamiz, pero tiene mucha menos memoria por encima. Probablemente se pueda acelerar un poco, pero tales optimizaciones se dejarán como un ejercicio para el lector. :)

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 http://.com/q/35222244/4014959
''''''

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()

En mi vieja máquina de un solo núcleo de 2GHz con 2GB de RAM, toma sieve_bin.py unos 26 segundos para crear un archivo de primebits para los números <64000020 (tamaño del archivo = 2133334 bytes); aproximadamente la mitad de ese tiempo se usa para tamizar los primos. isprime_bin.py tarda unos 124 segundos en producir la lista de primos de ese archivo (enviando la salida a / dev / null).

La salida se verificó comparándola con la producción generada por un programa de tamizado Eratosthenes convencional.

El código en isprime_bin.py está diseñado para probar enteros positivos arbitrarios para primalidad. Para generar simplemente una lista de primos se puede acelerar considerablemente, ya que las dos primeras pruebas if solo son aplicables a números <= 5. Aquí hay una versión modificada que demora alrededor de 47 segundos para producir la lista de todos los números primos de los primobits de 2133334 bytes archivo.

#! /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()