Encontrar el tamaño de los conjuntos de sumas en un espacio limitado

Question

Sea $S=\{a+b:\ a\in A,\ b\in B\}$ . Tengo una representación explícita de $A$ y $B$ pero $S$ es demasiado grande para almacenarlo en memoria. (Por ejemplo $A$ y $B$ son 100 MB y $S$ es de 1000 TB). ¿Existe algún método razonablemente eficaz para encontrar $|S|$ ?

El caso especial $B=\{0,n\}$ para $n\ne0$ es útil: con $A$ ordenado, bucle a través de sus elementos $a$ y compruebe si $na$ está en $A,$ incrementando un contador en caso contrario. A continuación, basta con sumar el número de elementos en $A$ . (Esto requiere $|A|\log|A|$ tiempo y sin espacio adicional más allá del necesario para la entrada y la salida). Pero esto no es fácilmente escalable.

(De hecho, en mi aplicación cuento $S'=\{ab:\ a\in A,\ b\in B\}$ pero estos se corresponden mediante logaritmos).

Answer 1

Si $A$ y $B$ caben en la memoria y $A$ está ordenada, es bastante fácil enumerar $A+\{b\}$ en orden creciente utilizando un espacio constante para cada $b\in B$ . Así tendrás espacio para construir $|B|$ tales generadores y fusionan perezosamente los flujos que salen de ellos. Esto enumerará $A+B$ en orden creciente, con repeticiones, y es fácil contar el número de elementos distintos a medida que se producen.

Esto tiene buena $O(|A|+|B|)$ complejidad espacial, pero el tiempo de ejecución de $O(|A||B| \log |B|)$ no es nada del otro mundo.