Que rayos, me pico la curiosidad como resolver esto, y creo que le pegue (NOTA advierto que para algoritmos raros no soy como seoane).
El truco es dejar de pensar en una BD relacional y usar mejor una BD LLave=Valor (NOSQL).
Al usar un BITARRAY, lo que se indica es que el BIT en la posicion X es 1 o 0. Ahora la trampa: Para indicar la posicion hasheo una cadena tipo "IDENTIFICADOR-CATEGORIA" en el caso de que sea True (porque si es falso es redundante setear la posicion!).
Asi que si para buscar el valor, se vuelve a hashear y se mira si en esa posicion esta True. Fin.
Código PHP:
# -*- coding: utf-8 -*-
import random
import string
import os
import mmh3
from bitarray import bitarray
#Las posiciones son hash int32. Crear un bitarray del max de INT32
db = bitarray(2147483647)
# Generar un hash int32. Esta sera la posicion en la BD
def asInt32(key, value):
return mmh3.hash("%s-%s" % (key, value))
# Solo importa si hay problemas.
def saveRecord(key, tieneMulta, tienePago, tieneRobo):
if tieneMulta:
db[asInt32(key, 'M')] = True
if tienePago:
db[asInt32(key, 'P')] = True
if tieneRobo:
db[asInt32(key, 'R')] = True
def rand_string(size=10, chars=string.ascii_uppercase + string.digits):
return ''.join(random.choice(chars) for _ in range(size))
# Boolean aleatorio
def ranB():
return bool(random.getrandbits(1))
# Una fila de la BD aleatoria
def _buildDataRow():
return dict(key=rand_string(), tieneMulta=ranB(), tienePago=ranB(), tieneRobo=ranB())
# Genera filas mediante un generador, sin cargar todo en memoria!...
def getData():
count = 1
for i in xrange(1, 1000 * 1000 * 10):
count += 1
if count >= (100 * 10000):
count = 1
print "%d records.." % i
yield _buildDataRow()
if os.path.exists('somefile.bin'):
print "Cargando archivo de datos.."
with open('somefile.bin', 'wb') as fh:
db.fromfile(fh)
else:
# Llenar la BD de datos...
print "Generando datos.."
for row in getData():
saveRecord(**row)
print "Listo"
#Para encontrar el valor, solo necesito saber si en la posicion del hash
#de la cadena esta en True
def find(key, value):
return db[asInt32(key, value)]
# Una valor fijo pa probar
testRow = getData().next()
saveRecord(**testRow)
def searchForRow(row):
print "Buscar un valor en la BD. Original:", row
key = row['key']
print "Tiene Pago?", find(key, 'P')
print "Tiene Robo?", find(key, 'R')
print "Tiene Multa?", find(key, 'M')
searchForRow(testRow)
#Guardemos el archivo
with open('somefile.bin', 'wb') as fh:
db.tofile(fh)
P.D: El archivo que esto genera es aprox 200 MB, dependiendo de cuantos valor TRUE se generen..
Junto a usar dropbox, esta el tema resuelto:
https://www.dropbox.com/developers