Lista booleana extremadamente grande en Python

Quiero crear un objeto en python que sea una colección de alrededor de 200,000,000 de valores verdadero/falso. Para que pueda cambiar o recuperar de forma más efectiva cualquier valor verdadero/falso, para poder determinar rápidamente si un número dado, como 123,456,000 es verdadero o falso o cambiar su valor.Lista booleana extremadamente grande en Python

¿Es la mejor manera de hacer esto una lista? o una matriz? o una clase? o solo un int largo usando operaciones de bits? ¿o algo mas?

Soy un poco novato, así que puede que me deletree más cosas que si estuviera haciendo la pregunta en uno de los otros idiomas que conozco mejor. Por favor, dame ejemplos de cómo se vería el funcionamiento de este objeto.

Gracias

Fuente

2009-10-16 Dan

¿Los valores verdadero/falso son densos o escasos? ¿Están distribuidos uniformemente, o es probable que sean rangos más densos y más escasos? La elección ideal de la estructura de datos difiere según estos. Por supuesto, puede que no necesites "ideal". – Steve314

Puede probar el módulo bitarray, o escribir una cosa similar utilizando un array de enteros usted mismo.

Fuente

2009-10-16 19:25:29

Gracias! Nunca antes había instalado un Módulo y estoy teniendo problemas: http://superuser.com/questions/56316/python-module-trouble-installing-bitarray – Dan

Ha considerado el uso de una base de datos ligera como SQLite?

Fuente

2009-10-16 19:23:14 jldupont

+1.200 millones de bits son aproximadamente 24 megabytes de datos, mientras que esto podría caber fácilmente en la memoria en una máquina moderna, cada vez que llegue a ese tamaño de estructura en la memoria, probablemente deba al menos considerar si una base de datos sería una mejor solución. –

"determine rápidamente si un número dado, como 123,456,000 es" en el conjunto "verdadero" o conjunto "falso".

Esto es para lo que es set.

El conjunto "verdadero" es un conjunto de todos los números.

Para hacer que la bandera booleana de un número sea "verdadera", agréguela al conjunto verdadero.

Para hacer que la bandera booleana de un número sea "falsa", elimínela del conjunto verdadero.

La vida será mucho más simple.

Fuente

2009-10-16 20:12:44

+1: es fácil de usar y podría ser lo suficientemente eficiente para una lista dispersa – jfs

Digamos que la mitad de los valores son verdaderos. El tamaño del objeto int es 12 bytes, eso es 1.2GB solo para almacenar las claves + memoria adicional para la tabla hash real. Usando una matriz de bits, el uso de la memoria será de 25 MB. Creo que esa es una diferencia significativa. –

@ Lukáš Lalinský: Su análisis es bueno. Sin embargo, no creo que sea relevante a menos que su procesador no tenga memoria disponible. En la mayoría de los procesadores modernos, hay mucha memoria y el 25M vs. 1.2G realmente no importa mucho. –

A primera vista, el módulo BitVector de Python parece que hace exactamente lo que usted desea. Está disponible en http://cobweb.ecn.purdue.edu/~kak/dist/BitVector-1.5.1.html y dado que es un código de Python puro, se ejecutará en cualquier plataforma sin necesidad de compilación.

Mencionó que necesita cierta velocidad para obtener y establecer cualquier valor arbitrario de verdadero a falso. Para eso necesitas usar una matriz de Python, en lugar de una lista, y si vas a la URL de arriba y buscas el código fuente de BitVector puedes ver que de hecho depende de las matrices de Python.

Lo ideal sería encapsular lo que está haciendo en una clase que subclases de BitVector, es decir

class TFValues(BitVector): 
    pass

De esa manera usted puede hacer cosas como añadir una lista que contiene información asociada, como el nombre de un particular, Valor de TF

Fuente

2009-10-16 20:16:35

También puede probar el módulo bitstring, que es puro Python. Internamente todo se almacena como una matriz de bytes y el enmascaramiento de bits y desplazamiento está hecho para usted:

from bitstring import BitArray 
# Initialise with two hundred million zero bits 
s = BitArray(200000000) 
# Set a few bits to 1 
s.set(1, [76, 33, 123456000]) 
# And test them 
if s.all([33, 76, 123456000]): 
    pass

Los otros carteles son correctas sin embargo, que un simple conjunto podría ser una mejor solución a su problema en particular.

Fuente

2009-10-16 22:53:28

Lista booleana extremadamente grande en Python

Respuesta

Cuestiones relacionadas