Contar el número de intersecciones binarias (Y) para cada elemento con otros elementos del arreglo.
Mientras resolvía otro problema complicado, me encontré con este: Tengo un array de longs, por ejemplo, en una representación binaria se vería así:
0000100
0000100
0000101
0000001
0001100
0001101
para cada uno de estos longs, tengo que calcular el número de otros longs con los que se intersecta:
0000100 -> 4
0000100 -> 4
0000101 -> 5
0000001 -> 2
0001100 -> 4
0001101 -> 5
La solución simple de fuerza bruta obviamente requiere N^2 operaciones y se vuelve inaceptablemente lenta para mí cuando N = 20K-100K. Lo mejor que he inventado (que creo que sigue siendo subóptimo) es lo siguiente: calcular un array de índices de longs, que contengan cierto bit para cada bit:
bit0: [2 3 5]
bit1: []
bit2: [0 1 2 4 5]
bit3: [4 5]
Luego creo un array temporal de la misma longitud que el array original y luego para cada bit puedo realizar mi propio bucle n^2 (esperemos que más pequeño). El array temporal se utiliza para almacenar las máscaras que permiten evitar el incremento doble en el array objetivo (que estamos buscando). Para mí, los ceros predominan sobre los unos, por lo que generalmente estos pequeños n^2 siguen siendo mejores que el gran N^2.
También intenté ordenar estos longs y luego construir un árbol binario con el número de bits no nulos adjuntos en cada nivel de profundidad. Funciona, pero la mejora de rendimiento es pequeña, porque el árbol en sí se vuelve bastante grande para 64 bits.
Una cosa más que intenté fue ordenar filas y columnas de esta matriz, por así decirlo, dio algunos beneficios de rendimiento a algunos de mis enfoques, pero fue insignificante.
La tarea parece tan elegante, pero no pude encontrar nada ni siquiera parecido en Google. ¿Cómo puedo resolver esto eficientemente?
davy.ai
Cálculo eficiente de intersecciones de arrays largos
La solución por fuerza bruta para calcular el número de intersecciones entre arrays largos requiere
N^2operaciones, lo que se vuelve muy lento para valores deNgrandes como 20K-100K.Una solución óptima para este problema implica calcular los índices de los enteros con ciertos bits, lo cual permite soluciones n^2 pequeñas en comparación con
N^2. El array temporal que contiene las máscaras se utiliza para evitar incrementos dobles en el array objetivo.Ordenar las filas y columnas de la matriz también proporciona algunos beneficios de rendimiento, pero es insignificante.
La tarea aún es ardua y todavía no se ha encontrado una solución óptima, pero dadas los pasos anteriores, es posible resolver el problema de manera eficiente.