búsqueda booleana en una matriz

tengo varias matrices con cerca de 100 valores posibles, es decir:búsqueda booleana en una matriz

a[0] = (a, b, c, d) 
a[1] = (a, e) 
a[2] = (d, f, g)

quiero volver rápidamente que arrays contiene (A || B) & & (d || e)

en este ejemplo, 0 y 1

Estaba pensando en operaciones bit a bit ... como representar "abcd" por "1111"; "anuncio" por "1001", y así sucesivamente. Entonces podría resolver el "O" con solo un O bit a bit, y luego comprobar si ambos son distintos de cero

¿alguien puede pensar en una solución mejor? este no es muy práctico ya que no parece ser muy escalable

¿Hay algún DBMS que pueda hacer eso rápidamente? Intenté con mongodb, pero parece que todavía no agregaron la función "$ and" (el doc dice que está en la versión 1.9.1, pero solo puedo descargar 1.9.0, y no es estable de todos modos)

I supongamos que es una "búsqueda booleana", similar a lo que Google hace todo el tiempo ... así que supongo que hay una mejor manera (quizás no tan rápido, pero más escalable) que eso

Fuente

2011-07-26 Lem0n

Si sus matrices solo habrán topado con 100 valores posibles, la solución bit a bit en realidad parece bastante buena. –

Como siempre, en la carrera de velocidad de memoria, si puede permitirse duplicar su base de datos, se vuelve trivial (al menos conceptualmente). Y afirmó que "solo" tenía 1 millón de matriz con 80 valores como máximo. Entonces, simplemente construye 80 matrices donde la primera contiene el índice de las matrices que contienen a, etc ... Para ser honesto, supongo que trabajar con la lista de enteros será más rápido que iterar varias veces sobre "representaciones bit a bit" – Fezvez

Sí, funciona una solución bit a bit bastante bien para esto. Sí, algunas bases de datos incluyen dicha capacidad, generalmente denominada columna de mapa de bits (o índice de mapa de bits, según sea el caso). El consejo habitual es aplicarlo a una columna que tenga una cardinalidad relativamente baja (es decir, un número bastante pequeño de valores posibles, como el sexo).

Fuente

2011-07-26 05:04:48

¿En qué sentido no es escalable? 16 bytes de datos por (bit) matriz no está mal! No estoy seguro de por qué quieres un DBMS para esto; puedes poner datos binarios allí si lo necesitas (con suerte bloques de matrices), y sacarlo todo para consultar. A menos que esté planeando tener miles de millones de matrices.

Para pequeños números de elementos, la lógica de bits es la más rápida. Pero si comienzas a superar los 100 valores, entonces mantener las matrices ordenadas y hacer búsquedas binarias (¡o incluso lineales!) Será más rápido. Necesitará comparar en su sistema para encontrar el punto de corte exacto, pero si sus matrices tienen ~ 4 elementos cada uno, generalmente encuentro la búsqueda lineal más rápida (contando las ocurrencias de los elementos que está buscando en la lógica booleana como ir), y que supera las matemáticas binarias aproximadamente en el mismo punto en que las representaciones binarias también se vuelven más grandes.

Fuente

2011-07-26 05:22:10

Mi problema de escalabilidad es que si tengo, digamos, 80 valores posibles y 1 millón de matrices, tendré que pasar por todas las matrices que realizan la operación bit a bit. Entonces es O (N) en la cantidad de datos. Quizás haya una solución que sea O (N) (o tal vez incluso O (N^3)) en lugar de la cantidad de valores posibles. – Lem0n

Lo que puedo pensar es de alguna manera la creación de un árbol de "valores posibles" que permiten la búsqueda booleana. Y las hojas serían todas las claves que coinciden con esta búsqueda. – Lem0n

@ Lem0n: puede crear un mapa a partir de cada valor posible para cada matriz que lo contenga. Entonces solo debes fusionar e intersecar los mapas. Pero esto es probable que sea solo decir 1/20 de la cantidad de operaciones de hacer lo bit a bit, y manipular un bit podría ser más de 20 veces más rápido. –

tienda sus matrices como un trie, por ejemplo,

a 
b 
    c 
    d 
e 
d 
f 
    g

Crear un trie de la expresión, así, por ejemplo,

a 
b 
    d 
    e 
d 
e 
b 
d 
e

Se puede sincronizar el último trie contra el primero (ignorando cualquier valores que no están en la expresión, es decir, 'c', 'f' y 'g') para obtener las soluciones. Dejo los detalles de la representación trie y el algoritmo de coincidencia a su criterio.

Fuente

2011-07-26 07:29:07

Como dijiste, los valores posibles son aproximadamente 100, pero tienes muchas matrices, creo que una tabla hash es mejor que la operación (s) de nivel de bits.
Por ejemplo.
tienen una tabla hash de conjunto con los valores de la expresión, es decir A, B pone a 1 y D, E establece en 2.

for each array a in arrays  
    for each value v in array 
    sum+= ht[v] 
    if sum == 3 
     print found 
     break

(Lo anterior no con duplicados, aunque!)
el primer ciclo for se puede paralelizar, probablemente con un framework map-reduce o incluso openMP.
(por cierto, el segundo también se puede paralelizar!)
Esto debería ser más rápido que construir una representación de bits de elementos completos en la matriz y hacer AND u OR. Básicamente se beneficiará con el mejor caso (por ejemplo, a y d son los primeros 2 elementos!) El peor de los casos es el mismo para ambos métodos (puede ser el hecho si cada elemento está sobrecargado)

Fuente

2011-08-16 16:38:38 Davinc

Respuesta

Cuestiones relacionadas