Algoritmos de intersección y unión de conjuntos

Capítulo 6 — Análisis de Algoritmos con Julia

Autor/a

Eric S. Téllez

1 Algoritmos de intersección y unión de conjuntos en el modelo de comparación

Objetivos de aprendizaje

Al terminar este capítulo, el lector deberá ser capaz de:

Formular los problemas de intersección y unión de conjuntos representados como arreglos ordenados y derivar su cota inferior $\log_2 {m+n \choose m}$ en el modelo de comparación.
Implementar el algoritmo de mezcla (merge) y explicar por qué es óptimo cuando los conjuntos tienen tamaños similares.
Diseñar algoritmos para conjuntos de tamaños muy distintos combinando búsqueda binaria y búsqueda no acotada del Capítulo 5, incluyendo el algoritmo de Baeza-Yates.
Extender la intersección a tres o más conjuntos con los algoritmos SvS y de Barbay y Kenyon, y explicar en qué sentido son adaptables a la instancia.
Relacionar estos algoritmos con la resolución de consultas sobre un índice invertido en Recuperación de Información.
Evaluar experimentalmente tiempo y número de comparaciones de los algoritmos y presentar los resultados con gráficas de caja (boxplot).

1.1 Problema

Como se vio en capítulos anteriores, un conjunto es una colección de elementos donde no hay repetición. El uso de conjuntos es fundamental para un gran número de problemas. En particular, en este capítulo representaremos conjuntos como arreglos ordenados de números enteros; esto para posicionarlo dentro de un dominio de aplicación objetivo, que es la Recuperación de Información, como parte de la representación de una matriz dispersa muy grande, llamada índice invertido.

El índice invertido

Un índice invertido asocia a cada término del vocabulario la lista ordenada de identificadores de los documentos donde aparece, llamada lista de posteo. Por ejemplo, para una colección de 16 documentos:

término	lista de posteo
`algoritmo`	1, 5, 7, 10, 12, 15
`búsqueda`	2, 5, 7, 15
`julia`	3, 5, 9, 15, 16

La consulta algoritmo AND búsqueda se resuelve con la intersección de las dos primeras listas, $\{5, 7, 15\}$; la consulta algoritmo OR búsqueda con su unión; y algoritmo AND búsqueda AND julia con la intersección de las tres, $\{5, 15\}$. En una colección real las listas tienen desde unos cuantos hasta millones de documentos, y una consulta típica combina términos con listas de tamaños muy distintos; por eso nos interesan algoritmos cuyo costo dependa de la lista pequeña y no de la grande.

Resolveremos los problemas de intersección y unión de conjuntos. Demaine et al. (2000) demuestra que el costo y procedimiento de las intersecciones y uniones de conjuntos representados como arreglos ordenados es básicamente el mismo, ya que requieren determinar la misma información: para cada elemento de un conjunto, su posición de inserción en el otro. Claramente, recolectar los datos para la unión y la intersección requiere diferentes esfuerzos, ya que la salida de la unión puede ser mucho más grande que la de la intersección.

A lo largo del capítulo, $A[1..m] = \{a_1 < a_2 < \cdots < a_m \}$ y $B[1..n] = \{b_1 < b_2 < \cdots < b_n \}$ serán los dos conjuntos a operar, y supondremos sin pérdida de generalidad que $m \leq n$. La razón $n/m$ será el parámetro clave para decidir qué algoritmo usar.

1.1.1 Costo del problema

El costo de la unión, y por lo tanto de la intersección, es \[\log_2{m+n \choose m}\] comparaciones en el peor caso (Hwang y Lin 1971).

Para derivarlo, supongamos que $A \cap B = \emptyset$; esto es, el conjunto de salida será de tamaño $m+n$. De manera similar al razonamiento que se utilizó para el problema de ordenamiento, el resultado de la unión es un orden total de $m+n$ elementos; pero como $A$ y $B$ ya están ordenados, no son posibles las $(m+n)!$ permutaciones, sino solo aquellas que respetan el orden interno de cada conjunto. Estas quedan determinadas por cuáles de las $m+n$ posiciones de la salida ocupan los elementos de $A$, es decir, hay ${n+m \choose m}$ instancias distinguibles. Dado que estamos en un modelo basado en comparaciones y que una comparación divide el espacio de instancias a lo más entre $2$, cualquier algoritmo necesita $\log_2 {n+m \choose m}$ comparaciones para distinguirlas; es el mismo argumento del árbol de decisión del Capítulo 5, ahora con ${n+m \choose m}$ hojas.

Usando la aproximación de Stirling para coeficientes binomiales de MacKay (2003), el costo se convierte en: \[\log_2{m+n \choose m} \approx n\log_2{\frac{m+n}{n}} + m \log_2\frac{n+m}{m}.\]

Recuerde que $\log_2 x = \frac{\log_e x}{\log_e 2}$, y que $\log_2(1 + x) \approx x \log_2 e \approx 1.44\,x$ cuando $x$ es pequeño.

Esta expresión tiene dos regímenes que guiarán el diseño de los algoritmos:

Si $m \approx n$, entonces ambos términos valen aproximadamente $n \log_2 2 = n$, y el costo es $\Theta(m + n)$: hay que tocar todos los elementos, y un algoritmo lineal es óptimo.
Si $m \ll n$, el primer término tiende a $n \log_2(1 + m/n) \approx 1.44\,m$ y el segundo a $m \log_2 (n/m)$; el costo es $\Theta(m \log (n/m))$. Note que es menor que $m \log_2 n$, el costo de hacer $m$ búsquedas binarias independientes, y que la diferencia es importante cuando $m$ es grande.

La Figura 1 compara la cota con estas aproximaciones y con los costos de los dos algoritmos ingenuos, la mezcla lineal y las búsquedas binarias independientes, para $n = 2^{16}$ y todos los valores de $m$.

using Plots, LaTeXStrings

logbinom(n, m) = sum(log2((n + i) / i) for i in 1:m)   # log2 C(n+m, m), sin desbordamientos
n = 2^16
M = unique(round.(Int, 2 .^ (0:0.25:16)))
plot(M, [logbinom(n, m) for m in M], xscale=:log2, yscale=:log2, lw=3,
     label="cota inferior", xlabel=L"m", ylabel="comparaciones", legend=:topleft)
plot!(M, [m + n for m in M], label=L"m + n", lw=2)
plot!(M, [m * log2(n) for m in M], label=L"m \log_2 n", lw=2)
M2 = filter(m -> m <= n ÷ 2, M)
plot!(M2, [m * log2(n / m) for m in M2], label=L"m \log_2 (n/m)", lw=2, ls=:dash)

Figura 1: Cota inferior $\log_2 {m+n \choose m}$ para la intersección de dos conjuntos con $n = 2^{16}$, en función de $m$, comparada con el costo de la mezcla ($m+n$), de $m$ búsquedas binarias independientes ($m \log_2 n$) y con la aproximación $m \log_2(n/m)$. Ambos ejes están en escala logarítmica.

Observe que la mezcla es casi óptima cuando $m$ se acerca a $n$, que las búsquedas binarias son casi óptimas cuando $m$ es muy pequeña, y que hay un amplio rango intermedio donde ninguna de las dos lo es: ese es el territorio de los algoritmos de este capítulo.

1.2 Algoritmos para conjuntos de tamaño similar: mezcla

Si $m \approx n$ el costo óptimo es $\Theta(m + n)$, y lo alcanza el algoritmo de mezcla (merge), el mismo que usa merge sort en el Capítulo 4: se recorren ambos arreglos simultáneamente con un índice en cada uno, y en cada paso se compara el elemento actual de $A$ con el de $B$ y se avanza el índice del menor (o ambos si son iguales).

Listado 1: Unión de dos conjuntos ordenados por mezcla

function merge_union!(C, A, B)
    i = j = 1
    m, n = length(A), length(B)

1    while i <= m && j <= n
        a, b = A[i], B[j]
2        if a == b
            push!(C, a)
            i += 1
            j += 1
3        elseif a < b
            push!(C, a)
            i += 1
        else
            push!(C, b)
            j += 1
        end
    end

4    while i <= m
        push!(C, A[i])
        i += 1
    end
    while j <= n
        push!(C, B[j])
        j += 1
    end

    C
end

merge_union!(Int[], [1, 5, 7, 10, 12, 15], [2, 5, 7, 15])

1: Mientras ninguno de los dos arreglos se haya agotado.
2: El elemento está en ambos conjuntos: se escribe una sola vez y se avanza en ambos.
3: El menor de los dos elementos actuales no puede estar en el otro conjunto (todos los elementos que faltan por ver son mayores), así que se escribe y se avanza solo en su arreglo.
4: Cuando uno de los arreglos se agota, el resto del otro va directo a la salida; estos elementos no requieren comparaciones.

7-element Vector{Int64}:
  1
  2
  5
  7
 10
 12
 15

Cada iteración del primer ciclo hace una o dos comparaciones y avanza al menos un índice, así que el número de iteraciones es a lo más $m + n - 1$; el costo total es $O(m + n)$ comparaciones y es independiente de qué tan entrelazados estén los conjuntos. Para la intersección, el algoritmo es idéntico salvo que solo se escriben los elementos comunes, y el ciclo puede terminar en cuanto se agota cualquiera de los dos arreglos.

Listado 2: Intersección de dos conjuntos ordenados por mezcla

function merge_intersect!(C, A, B)
    i = j = 1
    m, n = length(A), length(B)

    while i <= m && j <= n
        a, b = A[i], B[j]
        if a == b
            push!(C, a)
            i += 1
            j += 1
        elseif a < b
            i += 1
        else
            j += 1
        end
    end

    C
end

merge_intersect!(Int[], [1, 5, 7, 10, 12, 15], [2, 5, 7, 15])

3-element Vector{Int64}:
  5
  7
 15

La mezcla es el algoritmo más simple y, por sus accesos secuenciales y predecibles a memoria, el más rápido en la práctica cuando los tamaños son parecidos. Su debilidad es evidente cuando $m \ll n$: recorre los $n$ elementos de $B$ aunque la cota inferior sea de solo $O(m \log (n/m))$ comparaciones. Por ejemplo, intersectar una lista de $10$ elementos con una de un millón cuesta un millón de pasos con la mezcla, pero bastarían unas $200$ comparaciones.

1.2.0.1 Ejercicios

Modifique Listado 2 para calcular la diferencia $A \setminus B$ y la diferencia simétrica $(A \setminus B) \cup (B \setminus A)$.
Muestre con un ejemplo que la mezcla hace exactamente $m + n - 1$ comparaciones en el peor caso cuando usa una comparación de tres resultados ($<$, $=$, $>$), e indique una instancia donde la intersección termina mucho antes.
La intersección por mezcla es, en el sentido del Capítulo 5, $m$ búsquedas sucesivas con el algoritmo $B_0$ a partir de la posición anterior. Explique por qué, y qué sucede si se reemplaza $B_0$ por $B_1$. Esta observación motiva la siguiente sección.

1.3 Algoritmos para conjuntos de tamaño muy diferente

Si $m \ll n$, el costo óptimo tiende a $O(m \log (n/m))$. Una primera idea es realizar $m$ búsquedas binarias directas para localizar la posición de inserción de cada $a \in A$ en $B$, con un costo de $O(m \log n)$. La Figura 2 ilustra el problema: los elementos de $A$ (arriba) deben localizarse en $B$ (abajo); los nodos sombreados son los elementos de cada conjunto.

Figura 2: Dos listas alineadas sobre el universo $1..16$ donde los nodos sombreados son elementos de los conjuntos: $A = \{2, 5, 7, 15\}$ arriba y $B = \{1, 5, 7, 10, 12, 15\}$ abajo. La intersección es $\{5, 7, 15\}$.

1.3.1 Búsquedas sucesivas con memoria

Se hace notar que $A$ y $B$ están ordenados; por lo tanto, si la posición de inserción de $A[i]$ en $B$ es $j$, entonces $B[j-1] < A[i] < A[i+1]$ y la búsqueda de $A[i+1]$ puede comenzar en $B[j]$. Esto es exactamente el escenario de búsquedas sucesivas con dedo del Capítulo 5: las $m$ búsquedas se realizan en orden, cada una comienza donde terminó la anterior, y su costo depende de la distancia $p_i$ entre posiciones consecutivas y no de $n$. A continuación se muestra el código de un algoritmo de intersección que sigue esta estrategia, parametrizado por el algoritmo de búsqueda.

Listado 3: Intersección por búsquedas sucesivas con memoria de la posición anterior

function intsearch!(C, A, B, algosearch=doublingsearch)
1    if length(B) < length(A)
        A, B = B, A
    end

    p = 1
    for a in A
2        p = algosearch(B, a, p)
3        p > length(B) && break
4        if a == B[p]
            push!(C, a)
            p += 1
        end
    end

    C
end

intsearch!(Int[], [2, 5, 7, 15], [1, 5, 7, 10, 12, 15])

1: Siempre se recorre el conjunto pequeño y se busca en el grande.
2: La búsqueda de a comienza en la posición p donde terminó la anterior; todo elemento antes de p es menor que a.
3: Si a es mayor que todo B, también lo son los elementos restantes de A: terminamos.
4: Si a está en B, va a la salida y la siguiente búsqueda comienza después de él.

3-element Vector{Int64}:
  5
  7
 15

El análisis de Listado 3 depende del algoritmo de búsqueda:

Con búsqueda binaria acotada, cada búsqueda cuesta $O(\log n)$ aunque la pista acorte el rango, y el total es $O(m \log n)$.
Con $B_0$ (búsqueda secuencial), el algoritmo se convierte en la mezcla, con costo $O(m + n)$.
Con $B_1$ (búsqueda doblada), la $i$-ésima búsqueda cuesta $2 \log_2 p_i + O(1)$, donde $p_i$ es la distancia desde la posición anterior. Como las distancias suman a lo más $n$, i.e., $\sum_i p_i \leq n$, y el logaritmo es cóncavo, la suma $\sum_i \log_2 p_i$ se maximiza cuando todas las distancias son iguales a $n/m$, de donde el costo total es a lo más \[2 m \log_2 \frac{n}{m} + O(m).\]

Este último resultado es notable: con un cambio de una línea respecto a las búsquedas binarias independientes, obtenemos un algoritmo cuyo peor caso está a un factor de $2$ de la cota inferior $\Theta(m \log(n/m))$, y que además es adaptable: si los elementos de $A$ están concentrados en una zona de $B$, las distancias $p_i$ son pequeñas y el costo baja proporcionalmente, sin que el algoritmo tenga que saber nada de la instancia. Con $B_2$ el factor $2$ se reduce a $1 + o(1)$ a cambio de constantes mayores.

Al algoritmo Listado 3 con $B_1$ también se le conoce como intersección por galloping o exponential search, y es la base de los algoritmos de intersección usados en motores de búsqueda como Lucene. La misma idea se usa en TimSort para mezclar corridas de tamaños muy distintos.

1.3.2 El algoritmo de Hwang y Lin

Hwang y Lin (1971) proponen otro algoritmo que alcanza el costo $O(m \log(n/m))$ en el peor caso:

Divide $B$ en bloques de tamaño $n/m$ y define un arreglo virtual $B'[1..m]$ con el último elemento de cada bloque, $B'[i] = B[i \cdot n/m]$.
Se busca la posición de inserción $p$ de cada $a \in A$ en $B'$, costando $\log_2 m$ comparaciones cada una; esto identifica el bloque donde debe estar $a$.
Después se localiza dentro del $p$-ésimo bloque, i.e., $B[(p-1)n/m + 1 .. p \cdot n/m]$, la posición de inserción de $a$, con un costo de $\log_2 (n/m)$.

El paso 3 cuesta en total $m \log_2(n/m)$, el término dominante; el paso 2 cuesta $m \log_2 m$, pero se puede evitar: como los elementos de $A$ también están ordenados, el bloque de $a_{i+1}$ no puede estar antes que el de $a_i$, así que basta con avanzar en $B'$ secuencialmente, con un costo total de $O(m)$ para todos los bloques. La versión completa es equivalente a una mezcla sobre los bloques seguida de búsquedas binarias dentro de ellos. Hwang y Lin muestran además que si hay concentración de elementos de $A$ en pocos bloques de $B$, los bloques vacíos se descartan con una sola comparación, y hacen un análisis de caso promedio que puede consultarse en el artículo.

1.3.3 Algoritmo de Baeza-Yates

Baeza-Yates (2004) propone un algoritmo eficiente para intersecciones de dos conjuntos con una estrategia dividir para vencer, que en lugar de recorrer $A$ de izquierda a derecha comienza por su mediana:

Se toma la mediana $M$ de $A$ y se busca en $B$ obteniendo su posición de inserción $p$.
El problema entonces se divide en 3 subproblemas: \[\begin{align} C_< &= A[1..M-1] \cap B[1..p-e] \\ C_= &= \{A[M]\} \cap \{B[p]\} \\ C_> &= A[M+1..m] \cap B[p+e..n] \\ \end{align}\] donde $e=1$ si $A[M] = B[p]$ y $e=0$ cuando $A[M] \not= B[p]$.
La unión de estos tres conjuntos es la solución $C_< \cup C_= \cup C_>$.
El problema $C_=$ es trivial, y $C_<$ y $C_>$ se resuelven de forma recursiva, ajustando los rangos de trabajo. Si alguno de los dos rangos queda vacío, su subproblema es trivial y no cuesta nada.

La clave es el punto 2: una sola búsqueda de la mediana parte ambos conjuntos, y los elementos a la izquierda de $M$ solo pueden emparejarse con los elementos a la izquierda de $p$, y los de la derecha con los de la derecha. A continuación se muestra el código en Julia, usando los algoritmos de búsqueda del Capítulo 5.

Listado 4: Algoritmo de Baeza-Yates

# Adaptado de https://github.com/sadit/Intersections.jl

1function baezayates!(output, A, B, findpos::Function=binarysearch)
    baezayates!(output, A, 1, length(A), B, 1, length(B), findpos)
end

function baezayates!(output, A, a_sp::Int, a_ep::Int, B, b_sp::Int, b_ep::Int,
                     findpos::Function)
    (a_ep < a_sp || b_ep < b_sp) && return output
    imedian = ceil(Int, (a_ep + a_sp) / 2)
    median = A[imedian]
    ## findpos regresa n + 1 cuando median es mayor que B[end]
2    medpos = min(findpos(B, median, b_sp), b_ep)

    matches = median == B[medpos]
3    baezayates!(output, A, a_sp, imedian - 1, B, b_sp, medpos - matches, findpos)
4    matches && push!(output, median)
5    baezayates!(output, A, imedian + 1, a_ep, B, medpos + matches, b_ep, findpos)
    output
end

baezayates!(Int[], [2, 5, 7, 15], [1, 5, 7, 10, 12, 15])

1: Punto de entrada; findpos es cualquiera de los algoritmos de búsqueda con pista del Capítulo 5.
2: Búsqueda de la posición de inserción de la mediana de $A$ en el rango activo de $B$.
3: Recurrencia para el problema $C_<$.
4: Añadir al resultado el valor de la mediana si es que se encontró en $B$; es importante que este paso esté entre las recurrencias para que output sea un arreglo ordenado.
5: Recurrencia para el problema $C_>$.

3-element Vector{Int64}:
  5
  7
 15

Para analizar el peor caso, piense en el árbol de recursión: en el nivel $j$ hay a lo más $2^j$ subproblemas, cada uno con unos $m/2^j$ elementos de $A$ y rangos de $B$ disjuntos cuyos tamaños suman a lo más $n$. Cada subproblema hace una búsqueda binaria en su rango; por la concavidad del logaritmo, las $2^j$ búsquedas del nivel cuestan a lo más $2^j \log_2(n/2^j)$. Sumando sobre los $\log_2 m$ niveles se obtiene $O(m \log_2 (n/m))$, así que el algoritmo de Baeza-Yates es óptimo en el peor caso. Además, es capaz de aprovechar los casos donde $C_<$ o $C_>$ se vuelven triviales, ya sea porque un rango de $B$ queda vacío o porque la mediana cae fuera de él, lo cual da muy buenos resultados en algunas distribuciones; la elección de findpos permite además explotar la cercanía entre la pista b_sp y la respuesta.

1.3.3.1 Ejercicios

Implemente la unión con el algoritmo de Baeza-Yates. ¿Qué información adicional debe producir cada subproblema para que la salida quede ordenada?
Trace a mano la ejecución de Listado 4 con $A = \{2, 5, 7, 15\}$ y $B = \{1, 5, 7, 10, 12, 15\}$, anotando las llamadas recursivas y las comparaciones de cada búsqueda. Compare con la traza de Listado 3 sobre la misma instancia.
Implemente el algoritmo de Hwang y Lin, con la mejora de avanzar secuencialmente sobre los bloques, y compare su número de comparaciones con Listado 3 usando $B_1$ sobre instancias con $n/m \in \{1, 16, 256\}$.
Construya una instancia donde Listado 3 con $B_1$ haga muchas menos comparaciones que con búsqueda binaria, y otra donde haga más. Explique ambas con el análisis de la sección.

1.4 Operaciones con tres o más conjuntos

Los algoritmos y costos hasta ahora revisados se cumplen para dos conjuntos; se mencionaron diferentes algoritmos, algunos de ellos especializados por características como las proporciones de los conjuntos de entrada.

En particular, es importante hacer notar que ni el problema ni las aplicaciones están limitadas a dos conjuntos y, por lo tanto, son importantes los algoritmos y estrategias para resolver $\bigcup_i A_i$ así como $\bigcap_i A_i$ para $k$ conjuntos $A_1, \ldots, A_k$. Una consulta con tres términos, como en el ejemplo del índice invertido, es una intersección de tres listas.

1.4.1 Algoritmo SvS

Dado que $C = A \cap B$, es un hecho que $|C| \leq \min \{|A|, |B|\}$: la intersección nunca crece. Recordando que hay maneras relativamente simples y eficientes de resolver la intersección cuando $m \ll n$, cuando tenemos más de dos conjuntos podemos aplicar la estrategia Small vs Small (SvS), que consiste en ordenar los $k$ conjuntos por tamaño e intersectar el resultado parcial, que comienza siendo el conjunto más pequeño, con el siguiente conjunto más pequeño. Como el resultado parcial solo puede decrecer, cada intersección binaria se hace entre un conjunto cada vez más chico y uno grande, que es justo el caso que los algoritmos anteriores resuelven mejor; y si el resultado parcial se vacía, podemos terminar de inmediato.

Listado 5: Estrategia Small vs Small para $k$ conjuntos, parametrizada por el algoritmo de intersección binaria

# Adaptado de https://github.com/sadit/Intersections.jl

function svs(L::Vector{T}, in2::Function=baezayates!) where T
    prev, curr = eltype(T)[], eltype(T)[]
1    sort!(L, by=length, rev=true)
2    curr = pop!(L)

    while length(L) > 0
        empty!(prev)
3        in2(prev, curr, pop!(L))
4        isempty(prev) && return prev
5        prev, curr = curr, prev
    end

    curr
end

svs([[1, 5, 7, 10, 12, 15], [2, 5, 7, 15], [3, 5, 9, 15, 16]])

1: Se ordenan los conjuntos de mayor a menor para extraerlos del final, del más pequeño al más grande.
2: El resultado parcial inicial es el conjunto más pequeño.
3: Se intersecta el resultado parcial con el siguiente conjunto más pequeño usando cualquier algoritmo binario de intersección que escriba su salida en prev.
4: Si la intersección parcial es vacía, el resultado final también lo es.
5: Se intercambian los arreglos para reutilizar la memoria.

2-element Vector{Int64}:
  5
 15

1.4.2 Algoritmo de Barbay y Kenyon

Existe otra familia de algoritmos, basados en búsquedas adaptativas que pueden llegar a mejorar el desempeño bajo cierto tipo de entradas. Demaine et al. (2001), Barbay et al. (2006) y Barbay et al. (2010) muestran algoritmos de intersección basados en búsquedas adaptativas para aprovechar instancias simples. Estos estudios se basan en contribuciones teóricas de los mismos autores: Demaine et al. (2000), Demaine et al. (2001), Barbay y Kenyon (2002) y Baeza-Yates (2004).

La idea central es la de un eliminador: se toma un candidato el, inicialmente el primer elemento de la primera lista, y se busca su posición de inserción en las demás listas, una por una, de forma cíclica. Si todas las listas contienen a el, pertenece a la intersección. Si alguna lista no lo contiene, el elemento que encontramos en su lugar, L[i][P[i]], es mayor que el y ningún elemento entre ambos puede estar en la intersección; ese elemento se convierte en el nuevo candidato y la ronda comienza de nuevo. Las posiciones P[i] se recuerdan entre rondas, de modo que cada lista se recorre una sola vez de izquierda a derecha, con búsquedas no acotadas que aprovechan la cercanía entre candidatos sucesivos.

El algoritmo de Barbay et al. (2006) trabaja sobre los $k$ conjuntos de entrada, representados como arreglos ordenados de números enteros. Es un algoritmo simple pero poderoso: hace uso de búsquedas adaptativas con memoria para guardar las posiciones donde se avanza, de tal forma que no se recalculen posiciones. Las diferentes estrategias para revisar los conjuntos pueden dar diferentes desempeños, como se valida en Barbay et al. (2010), donde además de hacer una gran variedad de experimentos sobre diferentes algoritmos de búsqueda, se introducen variantes en el orden de acceso de cada conjunto.

A continuación se muestra el código del algoritmo base:

Listado 6: Algoritmo de Barbay y Kenyon para $k$ conjuntos

# Adaptado de https://github.com/sadit/Intersections.jl

function bk!(output, L::AbstractVector, findpos::Function=doublingsearch)
    P = ones(Int, length(L))
    bk!(output, L, P, findpos)
end

1function bk!(output, L, P, findpos::Function=doublingsearch)
2    n = length(L)
3    el = L[1][1]
4    c = 0

    @inbounds while true
        for i in eachindex(P)
5            P[i] = findpos(L[i], el, P[i])
            P[i] > length(L[i]) && return output
            pval = L[i][P[i]]
            if pval == el
                c += 1
6                if c == n
                    push!(output, el)
7                    c = 0
                    P[i] += 1
                    P[i] > length(L[i]) && return output
                    el = L[i][P[i]]
                end
            else
8                c = 0
                el = pval
            end
        end
    end

    output
end

bk!(Int[], [[1, 5, 7, 10, 12, 15], [2, 5, 7, 15], [3, 5, 9, 15, 16]])

1: El algoritmo de Barbay y Kenyon recibe: i) output el conjunto de salida. ii) L la lista de conjuntos (representados como arreglos ordenados). iii) P arreglo de posiciones actuales para cada arreglo. iv) findpos función de búsqueda.
2: Número de conjuntos en L.
3: el es el candidato o eliminador actual, el elemento siendo buscado en todos los arreglos.
4: c número de listas consecutivas que contienen el.
5: Buscando la posición de inserción de el en L[i], comenzando en P[i]. Si el es mayor que todo L[i], no hay más elementos en la intersección.
6: Si las $n$ listas contienen el, hay intersección.
7: Se reporta el, se avanza la posición en la lista actual y el siguiente elemento de esa lista es el nuevo candidato.
8: La lista i no contiene a el; el elemento encontrado en su lugar es mayor y se vuelve el nuevo candidato, reiniciando la cuenta.

2-element Vector{Int64}:
  5
 15

La adaptabilidad del algoritmo se mide con el tamaño del certificado de la instancia: el número mínimo de comparaciones que bastarían para convencer a alguien de que la intersección es la correcta. En instancias donde los conjuntos se alternan en bloques grandes (todos los elementos de una lista están entre dos elementos consecutivos de otra), el certificado es pequeño y el algoritmo de Barbay y Kenyon lo aprovecha saltando bloques enteros con cada búsqueda; en instancias donde los conjuntos están finamente entrelazados, el certificado es grande y ningún algoritmo puede hacerlo mucho mejor que la mezcla.

De manera particular, Barbay et al. (2010) presentan un estudio experimental sobre los algoritmos presentados en el área durante la década de 2000 a 2010, dichos algoritmos se parametrizaron de maneras que nos permiten aprender diferentes características de cada uno de ellos, dependiendo de los algoritmos de búsqueda que usan, la arquitectura computacional donde se evalúa, y el número de conjuntos siendo procesados. Una de las lecciones de ese estudio es que el número de comparaciones no determina el tiempo: los algoritmos con accesos más secuenciales a memoria suelen ganar en tiempo aunque hagan más comparaciones.

1.4.2.1 Ejercicios

Compare el orden en que SvS y Barbay y Kenyon procesan las listas. ¿Qué ventaja tiene cada enfoque cuando una de las listas es mucho más pequeña que las demás? ¿Y cuando todas tienen tamaños parecidos?
Trace Listado 6 sobre las tres listas de posteo del ejemplo del índice invertido, anotando el candidato el y el arreglo P después de cada búsqueda.
Construya una instancia de $k = 3$ listas de tamaño $n$ donde Barbay y Kenyon haga $O(\log n)$ búsquedas y otra donde haga $\Omega(n)$. Relacione ambas con el tamaño del certificado.
Implemente la unión de $k$ conjuntos con una cola de prioridad (heap) que mantenga el frente de cada lista, y analice su costo.

1.5 Lecturas

La cota inferior y el algoritmo para conjuntos de tamaños muy distintos se presentan en Hwang y Lin (1971); la lectura de las primeras secciones es accesible y es un buen ejemplo de análisis en el modelo de comparación. Baeza-Yates (2004) presenta el algoritmo de Baeza-Yates con su análisis y experimentos, y Baeza-Yates y Salinger (2005) lo extiende con una evaluación experimental más amplia. Los fundamentos de los algoritmos adaptables para intersección están en Demaine et al. (2000) y Demaine et al. (2001), y el algoritmo de Barbay y Kenyon, con su análisis en términos del certificado de la instancia, en Barbay y Kenyon (2002). Finalmente, Barbay et al. (2006) y Barbay et al. (2010) son los estudios experimentales de referencia; se recomienda leer con atención la metodología experimental de Barbay et al. (2010), ya que la actividad de este capítulo sigue el mismo espíritu.

1.6 Recursos audio-visuales de la unidad

Parte 1: Algoritmos de intersección (y unión) de listas ordenadas

Parte 2: Algoritmos de intersección y algunas aplicaciones

1.7 Actividades

1.7.1 Actividad 1: Intersección de listas de posteo sintéticas

El objetivo es comparar experimentalmente los algoritmos de intersección del capítulo sobre grupos de $k$ listas con razones de tamaño y traslapes controlados, que imitan a las listas de posteo de un índice invertido. Todos los datos se generan con el código de Listado 7, con semillas fijas, para que todos los reportes trabajen sobre las mismas instancias; no utilice archivos externos ni cambie las semillas ni los parámetros predeterminados.

El generador construye un grupo de $k$ listas de la siguiente manera: la lista más pequeña, de tamaño $n_k$, se toma uniformemente del universo $1:U$; cada lista más grande tiene un tamaño $n_i = n_1 / r^{i-1}$, donde $r$ es la razón entre tamaños consecutivos, e incluye cada elemento de la lista pequeña con probabilidad $t$ (el traslape) más elementos uniformes hasta completar su tamaño. Así, la intersección tiene aproximadamente $t^{k-1} n_k$ elementos, y la razón $r$ controla si estamos en el régimen de la mezcla ($r = 1$) o en el de las búsquedas ($r \gg 1$).

Listado 7: Generador de grupos de listas de posteo sintéticas con semillas fijas

using Random

const SEMILLA = 2026

"""
    genera_grupo(k, n1, razon, traslape; U=2^20, semilla=SEMILLA)

Grupo de `k` listas ordenadas de enteros distintos en `1:U`. La lista `i` tiene tamaño
aproximado `n1 ÷ razon^(i-1)`; cada lista contiene cada elemento de la lista más pequeña
con probabilidad `traslape`, por lo que la intersección tiene unos `traslape^(k-1) * nk`
elementos.
"""
function genera_grupo(k, n1, razon, traslape; U=2^20, semilla=SEMILLA)
    rng = Xoshiro(semilla)
    tams = [max(1, n1 ÷ razon^(i - 1)) for i in 1:k]
    S = sort!(randperm(rng, U)[1:tams[k]])            # la lista más pequeña
    L = Vector{Vector{Int}}(undef, k)
    L[k] = S
    for i in 1:k-1
        nucleo = S[rand(rng, length(S)) .< traslape]  # elementos plantados de S
        resto = randperm(rng, U)[1:tams[i] - length(nucleo)]
        L[i] = sort!(unique!(vcat(nucleo, resto)))
    end
    L
end

"""
    genera_coleccion(k; n1=2^16, razones=(1, 4, 16), traslape=0.5, repeticiones=20)

Colección de grupos de `k` listas: `repeticiones` grupos por cada razón de tamaños.
Regresa un vector de pares `(razon, grupo)`.
"""
function genera_coleccion(k; n1=2^16, razones=(1, 4, 16), traslape=0.5, repeticiones=20)
    C = Tuple{Int, Vector{Vector{Int}}}[]
    for (j, r) in enumerate(razones), rep in 1:repeticiones
        semilla = SEMILLA + 10_000k + 100j + rep
        push!(C, (r, genera_grupo(k, n1, r, traslape; semilla)))
    end
    C
end

La siguiente salida sirve como control: reproduzca estos valores con sus propios datos antes de medir nada; si trabaja en Python, replique la lógica del generador y verifique que los tamaños y las longitudes de las intersecciones sean similares.

for k in (2, 3, 4)
    C = genera_coleccion(k)
    for r in (1, 4, 16)
        grupos = [L for (razon, L) in C if razon == r]
        tams = round.(Int, sum(length.(L) for L in grupos) ./ length(grupos))
        inter = sum(length(svs(copy(L), merge_intersect!)) for L in grupos)
        inter /= length(grupos)
        print("k = $k, razón = $(lpad(r, 2)): $(length(grupos)) grupos, ")
        println("tamaños ~ $tams, |interseccion| ~ $(round(inter, digits=1))")
    end
end

k = 2, razón =  1: 20 grupos, tamaños ~ [64522, 65536], |interseccion| ~ 33796.6
k = 2, razón =  4: 20 grupos, tamaños ~ [65090, 16384], |interseccion| ~ 8637.5
k = 2, razón = 16: 20 grupos, tamaños ~ [65412, 4096], |interseccion| ~ 2165.6
k = 3, razón =  1: 20 grupos, tamaños ~ [64505, 64526, 65536], |interseccion| ~ 17438.0
k = 3, razón =  4: 20 grupos, tamaños ~ [65413, 16356, 4096], |interseccion| ~ 1113.8
k = 3, razón = 16: 20 grupos, tamaños ~ [65528, 4095, 256], |interseccion| ~ 67.7
k = 4, razón =  1: 20 grupos, tamaños ~ [64528, 64516, 64527, 65536], |interseccion| ~ 8984.6
k = 4, razón =  4: 20 grupos, tamaños ~ [65504, 16377, 4094, 1024], |interseccion| ~ 140.6
k = 4, razón = 16: 20 grupos, tamaños ~ [65535, 4096, 256, 16], |interseccion| ~ 1.9

Con estos datos, realice lo siguiente:

Implementación. Implemente la intersección por mezcla (ME), por búsquedas sucesivas (Listado 3), el algoritmo de Baeza-Yates (BY) y el de Barbay y Kenyon (BK), reutilizando los algoritmos de búsqueda que desarrolló en la actividad del Capítulo 5. Parametrice las búsquedas sucesivas, BY y BK con búsqueda binaria, $B_1$ y $B_2$. Para $k \geq 3$ use SvS con cada algoritmo binario, y BK directamente sobre las $k$ listas. Verifique todas las combinaciones contra la intersección con Set de Julia sobre instancias pequeñas aleatorias.
Datos. Genere las colecciones para $k \in \{2, 3, 4\}$ con genera_coleccion y sus parámetros predeterminados: $n_1 = 2^{16}$, razones $r \in \{1, 4, 16\}$, traslape $0.5$ y $20$ repeticiones por razón. Si su equipo no lo permite, reduzca $n_1$ y repórtelo; sus valores de control serán entonces distintos.
Experimentación. Para cada grupo, calcule la intersección con cada algoritmo y acumule el tiempo en segundos y el número de comparaciones; puede envolver las listas en CountingArray del Capítulo 5 para contar los accesos. Repita las mediciones de tiempo las veces necesarias para que sean fiables (vea la metodología del Capítulo 2). Presente gráficas de caja (boxplot), una por cada combinación de $k$ y razón $r$, que incluyan todos los algoritmos para que sean fáciles de comparar:
- tiempo en segundos por algoritmo,
- número de comparaciones por algoritmo,
- longitud de la intersección resultante; esta gráfica es de control: todos los algoritmos deben coincidir, y los valores deben ser compatibles con el cuadro anterior.
Análisis. Examine las diferencias en tiempo y número de comparaciones entre los algoritmos para cada $k$ y razón $r$. En particular: ¿para qué razones gana la mezcla y para cuáles los algoritmos basados en búsqueda? ¿Cómo se compara el número de comparaciones con la cota inferior $\log_2 {m+n \choose m}$ y con $2m\log_2(n/m)$? ¿Coinciden los ganadores en comparaciones y en tiempo? ¿Qué algoritmo de búsqueda conviene como parámetro de BY y de BK, y depende de $r$? Discuta cualquier tendencia, anomalía o patrón interesante observado, y concluya con una recomendación para resolver consultas en un índice invertido.

1.7.2 Entregable

Su trabajo se entregará en PDF y con el notebook fuente, se entregará en el sistema en archivos separados. El código se debe documentar, así como mantener una estructura del documento que permita a un lector interesado entender el problema, sus experimentos y metodología, así como sus conclusiones. Tenga en cuenta que los notebooks pueden alternar celdas de texto y código.

No olvide estructurar su reporte, en particular el reporte debe cubrir los siguientes puntos:

Título del reporte, su nombre.
Introducción.
Desarrollo de las actividades.
Conclusiones
Lista de referencias. Nota, una lista de referencias que no fueron utilizadas en el cuerpo del texto será interpretada como una lista vacía.

Nota: no olvides revisar la rúbrica del curso.

Referencias

Baeza-Yates, Ricardo. 2004. “A fast set intersection algorithm for sorted sequences”. Combinatorial Pattern Matching: 15th Annual Symposium, CPM 2004, Istanbul, Turkey, July 5-7, 2004. Proceedings 15, 400–408.

Baeza-Yates, Ricardo, y Alejandro Salinger. 2005. “Experimental analysis of a fast intersection algorithm for sorted sequences”. International Symposium on String Processing and Information Retrieval, 13–24.

Barbay, Jérémy, y Claire Kenyon. 2002. “Adaptive intersection and t-threshold problems”. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (USA), SODA ’02, 390–99.

Barbay, Jérémy, Alejandro López-Ortiz, y Tyler Lu. 2006. “Faster adaptive set intersections for text searching”. Experimental Algorithms: 5th International Workshop, WEA 2006, Cala Galdana, Menorca, Spain, May 24-27, 2006. Proceedings 5, 146–57.

Barbay, Jérémy, Alejandro López-Ortiz, Tyler Lu, y Alejandro Salinger. 2010. “An experimental investigation of set intersection algorithms for text searching”. Journal of Experimental Algorithmics (JEA) 14: 3–7.

Demaine, Erik D, Alejandro López-Ortiz, y J Ian Munro. 2001. “Experiments on adaptive set intersections for text retrieval systems”. Algorithm Engineering and Experimentation: Third International Workshop, ALENEX 2001 Washington, DC, USA, January 5–6, 2001 Revised Papers 3, 91–104.

Demaine, Erik D, Alejandro López-Ortiz, y J Ian Munro. 2000. “Adaptive set intersections, unions, and differences”. Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, 743–52.

Hwang, Frank K., y Shen Lin. 1971. “Optimal merging of 2 elements with n elements”. Acta Informatica 1 (2): 145–58.

MacKay, David JC. 2003. Information theory, inference and learning algorithms. Cambridge university press.

--- title: "Algoritmos de intersección y unión de conjuntos" subtitle: "Capítulo 6 — Análisis de Algoritmos con Julia" author: "Eric S. Téllez" lang: es-MX engine: julia julia: exeflags: ["+1.10"] format: html: other-links: - text: "Descargar PDF" icon: file-pdf href: "cap6-intersecciones.pdf" pdf: default --- ```{julia} #| echo: false #| label: setup #| output: false ENV["GKSwstype"] = "100" # Use "100" on Linux/macOS using Plots gr() # Force GR backend to acknowledge the change ``` # Algoritmos de intersección y unión de conjuntos en el modelo de comparación {#sec-intersecciones} ::: {.callout-note title="Objetivos de aprendizaje"} Al terminar este capítulo, el lector deberá ser capaz de: - Formular los problemas de intersección y unión de conjuntos representados como arreglos ordenados y derivar su cota inferior $\log_2 {m+n \choose m}$ en el modelo de comparación. - Implementar el algoritmo de mezcla (_merge_) y explicar por qué es óptimo cuando los conjuntos tienen tamaños similares. - Diseñar algoritmos para conjuntos de tamaños muy distintos combinando búsqueda binaria y búsqueda no acotada del [Capítulo 5](cap5-busqueda.qmd), incluyendo el algoritmo de Baeza-Yates. - Extender la intersección a tres o más conjuntos con los algoritmos SvS y de Barbay y Kenyon, y explicar en qué sentido son adaptables a la instancia. - Relacionar estos algoritmos con la resolución de consultas sobre un índice invertido en Recuperación de Información. - Evaluar experimentalmente tiempo y número de comparaciones de los algoritmos y presentar los resultados con gráficas de caja (_boxplot_). ::: ## Problema Como se vio en capítulos anteriores, un conjunto es una colección de elementos donde no hay repetición. El uso de conjuntos es fundamental para un gran número de problemas. En particular, en este capítulo representaremos conjuntos como arreglos ordenados de números enteros; esto para posicionarlo dentro de un dominio de aplicación objetivo, que es la Recuperación de Información, como parte de la representación de una matriz dispersa muy grande, llamada _índice invertido_. ::: {.callout-tip title="El índice invertido"} Un índice invertido asocia a cada término del vocabulario la lista ordenada de identificadores de los documentos donde aparece, llamada _lista de posteo_. Por ejemplo, para una colección de 16 documentos: | término | lista de posteo | |:--------|:----------------| | `algoritmo` | 1, 5, 7, 10, 12, 15 | | `búsqueda` | 2, 5, 7, 15 | | `julia` | 3, 5, 9, 15, 16 | La consulta `algoritmo AND búsqueda` se resuelve con la intersección de las dos primeras listas, $\{5, 7, 15\}$; la consulta `algoritmo OR búsqueda` con su unión; y `algoritmo AND búsqueda AND julia` con la intersección de las tres, $\{5, 15\}$. En una colección real las listas tienen desde unos cuantos hasta millones de documentos, y una consulta típica combina términos con listas de tamaños muy distintos; por eso nos interesan algoritmos cuyo costo dependa de la lista pequeña y no de la grande. ::: Resolveremos los problemas de intersección y unión de conjuntos. @DLOM2000 demuestra que el costo y procedimiento de las intersecciones y uniones de conjuntos representados como arreglos ordenados es básicamente el mismo, ya que requieren determinar la misma información: para cada elemento de un conjunto, su posición de inserción en el otro. Claramente, recolectar los datos para la unión y la intersección requiere diferentes esfuerzos, ya que la salida de la unión puede ser mucho más grande que la de la intersección. A lo largo del capítulo, $A[1..m] = \{a_1 < a_2 < \cdots < a_m \}$ y $B[1..n] = \{b_1 < b_2 < \cdots < b_n \}$ serán los dos conjuntos a operar, y supondremos sin pérdida de generalidad que $m \leq n$. La razón $n/m$ será el parámetro clave para decidir qué algoritmo usar. ### Costo del problema El costo de la unión, y por lo tanto de la intersección, es $$\log_2{m+n \choose m}$$ comparaciones en el peor caso [@hwang1971optimal]. Para derivarlo, supongamos que $A \cap B = \emptyset$; esto es, el conjunto de salida será de tamaño $m+n$. De manera similar al razonamiento que se utilizó para el problema de ordenamiento, el resultado de la unión es un orden total de $m+n$ elementos; pero como $A$ y $B$ ya están ordenados, no son posibles las $(m+n)!$ permutaciones, sino solo aquellas que respetan el orden interno de cada conjunto. Estas quedan determinadas por cuáles de las $m+n$ posiciones de la salida ocupan los elementos de $A$, es decir, hay ${n+m \choose m}$ instancias distinguibles. Dado que estamos en un modelo basado en comparaciones y que una comparación divide el espacio de instancias a lo más entre $2$, cualquier algoritmo necesita $\log_2 {n+m \choose m}$ comparaciones para distinguirlas; es el mismo argumento del árbol de decisión del [Capítulo 5](cap5-busqueda.qmd), ahora con ${n+m \choose m}$ hojas. Usando la aproximación de Stirling para coeficientes binomiales de @mackay2003information, el costo se convierte en: $$\log_2{m+n \choose m} \approx n\log_2{\frac{m+n}{n}} + m \log_2\frac{n+m}{m}.$$ ::: {.column-margin} Recuerde que $\log_2 x = \frac{\log_e x}{\log_e 2}$, y que $\log_2(1 + x) \approx x \log_2 e \approx 1.44\,x$ cuando $x$ es pequeño. ::: Esta expresión tiene dos regímenes que guiarán el diseño de los algoritmos: - Si $m \approx n$, entonces ambos términos valen aproximadamente $n \log_2 2 = n$, y el costo es $\Theta(m + n)$: hay que _tocar_ todos los elementos, y un algoritmo lineal es óptimo. - Si $m \ll n$, el primer término tiende a $n \log_2(1 + m/n) \approx 1.44\,m$ y el segundo a $m \log_2 (n/m)$; el costo es $\Theta(m \log (n/m))$. Note que es menor que $m \log_2 n$, el costo de hacer $m$ búsquedas binarias independientes, y que la diferencia es importante cuando $m$ es grande. La @fig-cota-interseccion compara la cota con estas aproximaciones y con los costos de los dos algoritmos ingenuos, la mezcla lineal y las búsquedas binarias independientes, para $n = 2^{16}$ y todos los valores de $m$. ```{julia} #| label: fig-cota-interseccion #| fig-cap: | #| Cota inferior $\log_2 {m+n \choose m}$ para la intersección de dos conjuntos con $n = 2^{16}$, en función de $m$, comparada con el costo de la mezcla ($m+n$), de $m$ búsquedas binarias independientes ($m \log_2 n$) y con la aproximación $m \log_2(n/m)$. Ambos ejes están en escala logarítmica. #| fig-width: 90% using Plots, LaTeXStrings logbinom(n, m) = sum(log2((n + i) / i) for i in 1:m) # log2 C(n+m, m), sin desbordamientos n = 2^16 M = unique(round.(Int, 2 .^ (0:0.25:16))) plot(M, [logbinom(n, m) for m in M], xscale=:log2, yscale=:log2, lw=3, label="cota inferior", xlabel=L"m", ylabel="comparaciones", legend=:topleft) plot!(M, [m + n for m in M], label=L"m + n", lw=2) plot!(M, [m * log2(n) for m in M], label=L"m \log_2 n", lw=2) M2 = filter(m -> m <= n ÷ 2, M) plot!(M2, [m * log2(n / m) for m in M2], label=L"m \log_2 (n/m)", lw=2, ls=:dash) ``` Observe que la mezcla es casi óptima cuando $m$ se acerca a $n$, que las búsquedas binarias son casi óptimas cuando $m$ es muy pequeña, y que hay un amplio rango intermedio donde ninguna de las dos lo es: ese es el territorio de los algoritmos de este capítulo. ```{julia} #| echo: false #| output: false # Algoritmos de búsqueda tomados del Capítulo 5 function binarysearch(A, x, sp=1, ep=length(A)) lo, hi = sp, ep + 1 while lo < hi mid = (lo + hi) ÷ 2 if x <= A[mid] hi = mid else lo = mid + 1 end end lo end function doublingsearch(A, x, sp=1) n = length(A) p = 0 i = 1 while sp+i <= n && A[sp+i] < x p = i i += i end binarysearch(A, x, sp + p, min(n, sp+i)) end function doublingdoublingsearch(A, x, sp=1) n = length(A) pos(e) = e >= 62 ? typemax(Int) : sp + (1 << e) reached(e) = pos(e) > n || x <= A[pos(e)] lo, hi = -1, 1 while !reached(hi) lo = hi hi += hi end lo += 1 while lo < hi mid = (lo + hi) ÷ 2 if reached(mid) hi = mid else lo = mid + 1 end end first = hi == 0 ? sp : pos(hi - 1) binarysearch(A, x, first, min(n, pos(hi))) end ``` ## Algoritmos para conjuntos de tamaño similar: mezcla Si $m \approx n$ el costo óptimo es $\Theta(m + n)$, y lo alcanza el algoritmo de _mezcla_ (_merge_), el mismo que usa _merge sort_ en el [Capítulo 4](cap4-ordenamiento.qmd): se recorren ambos arreglos simultáneamente con un índice en cada uno, y en cada paso se compara el elemento actual de $A$ con el de $B$ y se avanza el índice del menor (o ambos si son iguales). ```{julia} #| lst-label: lst-merge-union #| lst-cap: Unión de dos conjuntos ordenados por mezcla function merge_union!(C, A, B) i = j = 1 m, n = length(A), length(B) while i <= m && j <= n # <1> a, b = A[i], B[j] if a == b # <2> push!(C, a) i += 1 j += 1 elseif a < b # <3> push!(C, a) i += 1 else push!(C, b) j += 1 end end while i <= m # <4> push!(C, A[i]) i += 1 end while j <= n push!(C, B[j]) j += 1 end C end merge_union!(Int[], [1, 5, 7, 10, 12, 15], [2, 5, 7, 15]) ``` 1. Mientras ninguno de los dos arreglos se haya agotado. 2. El elemento está en ambos conjuntos: se escribe una sola vez y se avanza en ambos. 3. El menor de los dos elementos actuales no puede estar en el otro conjunto (todos los elementos que faltan por ver son mayores), así que se escribe y se avanza solo en su arreglo. 4. Cuando uno de los arreglos se agota, el resto del otro va directo a la salida; estos elementos no requieren comparaciones. Cada iteración del primer ciclo hace una o dos comparaciones y avanza al menos un índice, así que el número de iteraciones es a lo más $m + n - 1$; el costo total es $O(m + n)$ comparaciones y es _independiente_ de qué tan entrelazados estén los conjuntos. Para la intersección, el algoritmo es idéntico salvo que solo se escriben los elementos comunes, y el ciclo puede terminar en cuanto se agota cualquiera de los dos arreglos. ```{julia} #| lst-label: lst-merge-intersect #| lst-cap: Intersección de dos conjuntos ordenados por mezcla function merge_intersect!(C, A, B) i = j = 1 m, n = length(A), length(B) while i <= m && j <= n a, b = A[i], B[j] if a == b push!(C, a) i += 1 j += 1 elseif a < b i += 1 else j += 1 end end C end merge_intersect!(Int[], [1, 5, 7, 10, 12, 15], [2, 5, 7, 15]) ``` ```{julia} #| echo: false #| output: false @assert 1:8 == merge_union!(Int[], [1, 3, 4, 6, 8], [2, 5, 7]) @assert 0:9 == merge_union!(Int[], [1, 3, 4, 6, 8], [0, 2, 5, 7, 9]) @assert 1:10 == merge_union!(Int[], 1:5, 6:10) @assert 1:10 == merge_union!(Int[], 6:10, 1:5) @assert [4, 6] == merge_intersect!(Int[], [1, 3, 4, 6, 8], [2, 4, 5, 6, 7]) @assert isempty(merge_intersect!(Int[], 1:5, 6:10)) ``` La mezcla es el algoritmo más simple y, por sus accesos secuenciales y predecibles a memoria, el más rápido en la práctica cuando los tamaños son parecidos. Su debilidad es evidente cuando $m \ll n$: recorre los $n$ elementos de $B$ aunque la cota inferior sea de solo $O(m \log (n/m))$ comparaciones. Por ejemplo, intersectar una lista de $10$ elementos con una de un millón cuesta un millón de pasos con la mezcla, pero bastarían unas $200$ comparaciones. #### Ejercicios 1. Modifique @lst-merge-intersect para calcular la diferencia $A \setminus B$ y la diferencia simétrica $(A \setminus B) \cup (B \setminus A)$. 2. Muestre con un ejemplo que la mezcla hace exactamente $m + n - 1$ comparaciones en el peor caso cuando usa una comparación de tres resultados ($<$, $=$, $>$), e indique una instancia donde la intersección termina mucho antes. 3. La intersección por mezcla es, en el sentido del [Capítulo 5](cap5-busqueda.qmd), $m$ búsquedas sucesivas con el algoritmo $B_0$ a partir de la posición anterior. Explique por qué, y qué sucede si se reemplaza $B_0$ por $B_1$. Esta observación motiva la siguiente sección. ## Algoritmos para conjuntos de tamaño muy diferente Si $m \ll n$, el costo óptimo tiende a $O(m \log (n/m))$. Una primera idea es realizar $m$ búsquedas binarias _directas_ para localizar la posición de inserción de cada $a \in A$ en $B$, con un costo de $O(m \log n)$. La @fig-interseccion ilustra el problema: los elementos de $A$ (arriba) deben localizarse en $B$ (abajo); los nodos sombreados son los elementos de cada conjunto. ```{dot} //| label: fig-interseccion //| echo: false //| fig-width: 100% //| fig-cap: | //| Dos listas alineadas sobre el universo $1..16$ donde los nodos sombreados son elementos de los conjuntos: $A = \{2, 5, 7, 15\}$ arriba y $B = \{1, 5, 7, 10, 12, 15\}$ abajo. La intersección es $\{5, 7, 15\}$. digraph lista { //layout=neato; rankdir=LR; graph [pad="0.5", nodesep="0.5", ranksep="0.5"]; //{rank=same; a; b; c; nothing;} splines="true"; //node [style="invis"]; subgraph A { cluster=true; a1 [label="1"]; a2 [label="2", style="filled"]; a3 [label="3"]; a4 [label="4"]; a5 [label="5", style="filled"]; a6 [label="6"]; a7 [label="7", style="filled"]; a8 [label="8"]; a9 [label="9"]; a10 [label="10"]; a11 [label="11"]; a12 [label="12"]; a13 [label="13"]; a15 [label="15", style="filled"]; a16 [label="16"]; } subgraph B { cluster=true; 1 [label="1", style="filled"]; 2 [label="2"]; 3 [label="3"]; 4 [label="4"]; 5 [label="5", style="filled"]; 6 [label="6"]; 7 [label="7", style="filled"]; 8 [label="8"]; 9 [label="9"]; 10 [label="10", style="filled"]; 11 [label="11"]; 12 [label="12", style="filled"]; 13 [label="13"]; 15 [label="15", style="filled"]; 16 [label="16"]; } edge [style="invis"]; 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 15 -> 16[weight=30]; a1 -> a2 -> a3 -> a4 -> a5 -> a6 -> a7 -> a8 -> a9 -> a10 -> a11 -> a12 -> a13 -> a15 -> a16 [weight=30]; //A -> B //edge [style=""]; //5 -> a5 [weight=0]; //7 -> a7 [weight=0]; //15 -> a15 [weight=0]; } ``` ### Búsquedas sucesivas con memoria Se hace notar que $A$ y $B$ están ordenados; por lo tanto, si la posición de inserción de $A[i]$ en $B$ es $j$, entonces $B[j-1] < A[i] < A[i+1]$ y la búsqueda de $A[i+1]$ puede comenzar en $B[j]$. Esto es exactamente el escenario de _búsquedas sucesivas con dedo_ del [Capítulo 5](cap5-busqueda.qmd): las $m$ búsquedas se realizan en orden, cada una comienza donde terminó la anterior, y su costo depende de la distancia $p_i$ entre posiciones consecutivas y no de $n$. A continuación se muestra el código de un algoritmo de intersección que sigue esta estrategia, parametrizado por el algoritmo de búsqueda. ```{julia} #| lst-label: lst-intsearch #| lst-cap: Intersección por búsquedas sucesivas con memoria de la posición anterior function intsearch!(C, A, B, algosearch=doublingsearch) if length(B) < length(A) # <1> A, B = B, A end p = 1 for a in A p = algosearch(B, a, p) # <2> p > length(B) && break # <3> if a == B[p] # <4> push!(C, a) p += 1 end end C end intsearch!(Int[], [2, 5, 7, 15], [1, 5, 7, 10, 12, 15]) ``` 1. Siempre se recorre el conjunto pequeño y se busca en el grande. 2. La búsqueda de `a` comienza en la posición `p` donde terminó la anterior; todo elemento antes de `p` es menor que `a`. 3. Si `a` es mayor que todo `B`, también lo son los elementos restantes de `A`: terminamos. 4. Si `a` está en `B`, va a la salida y la siguiente búsqueda comienza después de él. ```{julia} #| output: false #| echo: false for f in (binarysearch, doublingsearch, doublingdoublingsearch) @assert [4, 6] == intsearch!(Int[], [1, 3, 4, 6, 8], [2, 4, 5, 6, 7], f) @assert 1:5 == intsearch!(Int[], 1:10, 1:5, f) @assert 1:9 == intsearch!(Int[], 0:10, 1:9, f) @assert 1:2:9 == intsearch!(Int[], 0:10, 1:2:9, f) end ``` El análisis de @lst-intsearch depende del algoritmo de búsqueda: - Con búsqueda binaria acotada, cada búsqueda cuesta $O(\log n)$ aunque la pista acorte el rango, y el total es $O(m \log n)$. - Con $B_0$ (búsqueda secuencial), el algoritmo se convierte en la mezcla, con costo $O(m + n)$. - Con $B_1$ (búsqueda doblada), la $i$-ésima búsqueda cuesta $2 \log_2 p_i + O(1)$, donde $p_i$ es la distancia desde la posición anterior. Como las distancias suman a lo más $n$, i.e., $\sum_i p_i \leq n$, y el logaritmo es cóncavo, la suma $\sum_i \log_2 p_i$ se maximiza cuando todas las distancias son iguales a $n/m$, de donde el costo total es a lo más $$2 m \log_2 \frac{n}{m} + O(m).$$ Este último resultado es notable: con un cambio de una línea respecto a las búsquedas binarias independientes, obtenemos un algoritmo cuyo peor caso está a un factor de $2$ de la cota inferior $\Theta(m \log(n/m))$, y que además es _adaptable_: si los elementos de $A$ están concentrados en una zona de $B$, las distancias $p_i$ son pequeñas y el costo baja proporcionalmente, sin que el algoritmo tenga que saber nada de la instancia. Con $B_2$ el factor $2$ se reduce a $1 + o(1)$ a cambio de constantes mayores. ::: {.column-margin} Al algoritmo @lst-intsearch con $B_1$ también se le conoce como intersección por _galloping_ o _exponential search_, y es la base de los algoritmos de intersección usados en motores de búsqueda como Lucene. La misma idea se usa en _TimSort_ para mezclar corridas de tamaños muy distintos. ::: ### El algoritmo de Hwang y Lin @hwang1971optimal proponen otro algoritmo que alcanza el costo $O(m \log(n/m))$ en el peor caso: 1. Divide $B$ en bloques de tamaño $n/m$ y define un arreglo _virtual_ $B'[1..m]$ con el último elemento de cada bloque, $B'[i] = B[i \cdot n/m]$. 2. Se busca la posición de inserción $p$ de cada $a \in A$ en $B'$, costando $\log_2 m$ comparaciones cada una; esto identifica el bloque donde debe estar $a$. 3. Después se localiza dentro del $p$-ésimo bloque, i.e., $B[(p-1)n/m + 1 .. p \cdot n/m]$, la posición de inserción de $a$, con un costo de $\log_2 (n/m)$. El paso 3 cuesta en total $m \log_2(n/m)$, el término dominante; el paso 2 cuesta $m \log_2 m$, pero se puede evitar: como los elementos de $A$ también están ordenados, el bloque de $a_{i+1}$ no puede estar antes que el de $a_i$, así que basta con _avanzar_ en $B'$ secuencialmente, con un costo total de $O(m)$ para todos los bloques. La versión completa es equivalente a una mezcla sobre los bloques seguida de búsquedas binarias dentro de ellos. Hwang y Lin muestran además que si hay concentración de elementos de $A$ en pocos bloques de $B$, los bloques vacíos se descartan con una sola comparación, y hacen un análisis de caso promedio que puede consultarse en el artículo. ### Algoritmo de Baeza-Yates @BY2004 propone un algoritmo eficiente para intersecciones de dos conjuntos con una estrategia _dividir para vencer_, que en lugar de recorrer $A$ de izquierda a derecha comienza por su mediana: 1. Se toma la mediana $M$ de $A$ y se busca en $B$ obteniendo su posición de inserción $p$. 2. El problema entonces se divide en 3 subproblemas: \begin{align} C_< &= A[1..M-1] \cap B[1..p-e] \\ C_= &= \{A[M]\} \cap \{B[p]\} \\ C_> &= A[M+1..m] \cap B[p+e..n] \\ \end{align} donde $e=1$ si $A[M] = B[p]$ y $e=0$ cuando $A[M] \not= B[p]$. 3. La unión de estos tres conjuntos es la solución $C_< \cup C_= \cup C_>$. 4. El problema $C_=$ es trivial, y $C_<$ y $C_>$ se resuelven de forma recursiva, ajustando los rangos de trabajo. Si alguno de los dos rangos queda vacío, su subproblema es trivial y no cuesta nada. La clave es el punto 2: una sola búsqueda de la mediana _parte_ ambos conjuntos, y los elementos a la izquierda de $M$ solo pueden emparejarse con los elementos a la izquierda de $p$, y los de la derecha con los de la derecha. A continuación se muestra el código en Julia, usando los algoritmos de búsqueda del [Capítulo 5](cap5-busqueda.qmd). ```{julia} #| lst-label: lst-baezayates #| lst-cap: Algoritmo de Baeza-Yates # Adaptado de https://github.com/sadit/Intersections.jl function baezayates!(output, A, B, findpos::Function=binarysearch) # <1> baezayates!(output, A, 1, length(A), B, 1, length(B), findpos) end function baezayates!(output, A, a_sp::Int, a_ep::Int, B, b_sp::Int, b_ep::Int, findpos::Function) (a_ep < a_sp || b_ep < b_sp) && return output imedian = ceil(Int, (a_ep + a_sp) / 2) median = A[imedian] ## findpos regresa n + 1 cuando median es mayor que B[end] medpos = min(findpos(B, median, b_sp), b_ep) # <2> matches = median == B[medpos] baezayates!(output, A, a_sp, imedian - 1, B, b_sp, medpos - matches, findpos) # <3> matches && push!(output, median) # <4> baezayates!(output, A, imedian + 1, a_ep, B, medpos + matches, b_ep, findpos) # <5> output end baezayates!(Int[], [2, 5, 7, 15], [1, 5, 7, 10, 12, 15]) ``` 1. Punto de entrada; `findpos` es cualquiera de los algoritmos de búsqueda con pista del Capítulo 5. 2. Búsqueda de la posición de inserción de la mediana de $A$ en el rango activo de $B$. 3. Recurrencia para el problema $C_<$. 4. Añadir al resultado el valor de la mediana si es que se encontró en $B$; es importante que este paso esté entre las recurrencias para que `output` sea un arreglo ordenado. 5. Recurrencia para el problema $C_>$. ```{julia} #| output: false #| echo: false for f in (binarysearch, doublingsearch, doublingdoublingsearch) @assert [4, 6] == baezayates!(Int[], [1, 3, 4, 6, 8], [2, 4, 5, 6, 7], f) @assert 1:5 == baezayates!(Int[], 1:10, 1:5, f) @assert 1:9 == baezayates!(Int[], 0:10, 1:9, f) @assert 1:2:9 == baezayates!(Int[], 0:10, 1:2:9, f) end ``` Para analizar el peor caso, piense en el árbol de recursión: en el nivel $j$ hay a lo más $2^j$ subproblemas, cada uno con unos $m/2^j$ elementos de $A$ y rangos de $B$ _disjuntos_ cuyos tamaños suman a lo más $n$. Cada subproblema hace una búsqueda binaria en su rango; por la concavidad del logaritmo, las $2^j$ búsquedas del nivel cuestan a lo más $2^j \log_2(n/2^j)$. Sumando sobre los $\log_2 m$ niveles se obtiene $O(m \log_2 (n/m))$, así que el algoritmo de Baeza-Yates es óptimo en el peor caso. Además, es capaz de aprovechar los casos donde $C_<$ o $C_>$ se vuelven triviales, ya sea porque un rango de $B$ queda vacío o porque la mediana cae fuera de él, lo cual da muy buenos resultados en algunas distribuciones; la elección de `findpos` permite además explotar la cercanía entre la pista `b_sp` y la respuesta. #### Ejercicios 1. Implemente la unión con el algoritmo de Baeza-Yates. ¿Qué información adicional debe producir cada subproblema para que la salida quede ordenada? 2. Trace a mano la ejecución de @lst-baezayates con $A = \{2, 5, 7, 15\}$ y $B = \{1, 5, 7, 10, 12, 15\}$, anotando las llamadas recursivas y las comparaciones de cada búsqueda. Compare con la traza de @lst-intsearch sobre la misma instancia. 3. Implemente el algoritmo de Hwang y Lin, con la mejora de avanzar secuencialmente sobre los bloques, y compare su número de comparaciones con @lst-intsearch usando $B_1$ sobre instancias con $n/m \in \{1, 16, 256\}$. 4. Construya una instancia donde @lst-intsearch con $B_1$ haga muchas menos comparaciones que con búsqueda binaria, y otra donde haga más. Explique ambas con el análisis de la sección. ## Operaciones con tres o más conjuntos Los algoritmos y costos hasta ahora revisados se cumplen para dos conjuntos; se mencionaron diferentes algoritmos, algunos de ellos especializados por características como las proporciones de los conjuntos de entrada. En particular, es importante hacer notar que ni el problema ni las aplicaciones están limitadas a dos conjuntos y, por lo tanto, son importantes los algoritmos y estrategias para resolver $\bigcup_i A_i$ así como $\bigcap_i A_i$ para $k$ conjuntos $A_1, \ldots, A_k$. Una consulta con tres términos, como en el ejemplo del índice invertido, es una intersección de tres listas. ### Algoritmo SvS Dado que $C = A \cap B$, es un hecho que $|C| \leq \min \{|A|, |B|\}$: la intersección nunca crece. Recordando que hay maneras relativamente simples y eficientes de resolver la intersección cuando $m \ll n$, cuando tenemos más de dos conjuntos podemos aplicar la estrategia _Small vs Small (SvS)_, que consiste en ordenar los $k$ conjuntos por tamaño e intersectar el resultado parcial, que comienza siendo el conjunto más pequeño, con el siguiente conjunto más pequeño. Como el resultado parcial solo puede decrecer, cada intersección binaria se hace entre un conjunto cada vez más chico y uno grande, que es justo el caso que los algoritmos anteriores resuelven mejor; y si el resultado parcial se vacía, podemos terminar de inmediato. ```{julia} #| lst-label: lst-svs #| lst-cap: Estrategia _Small vs Small_ para $k$ conjuntos, parametrizada por el algoritmo de intersección binaria # Adaptado de https://github.com/sadit/Intersections.jl function svs(L::Vector{T}, in2::Function=baezayates!) where T prev, curr = eltype(T)[], eltype(T)[] sort!(L, by=length, rev=true) # <1> curr = pop!(L) # <2> while length(L) > 0 empty!(prev) in2(prev, curr, pop!(L)) # <3> isempty(prev) && return prev # <4> prev, curr = curr, prev # <5> end curr end svs([[1, 5, 7, 10, 12, 15], [2, 5, 7, 15], [3, 5, 9, 15, 16]]) ``` 1. Se ordenan los conjuntos de mayor a menor para extraerlos del final, del más pequeño al más grande. 2. El resultado parcial inicial es el conjunto más pequeño. 3. Se intersecta el resultado parcial con el siguiente conjunto más pequeño usando cualquier algoritmo binario de intersección que escriba su salida en `prev`. 4. Si la intersección parcial es vacía, el resultado final también lo es. 5. Se intercambian los arreglos para reutilizar la memoria. ```{julia} #| output: false #| echo: false @assert [4, 6] == svs([[1, 3, 4, 6, 8], [2, 4, 5, 6, 7]]) @assert 1:5 == svs([1:10, 1:5]) @assert 1:9 == svs([0:10, 1:9]) @assert 1:2:9 == svs([0:10, 1:2:9]) @assert [4, 6] == svs([[1, 3, 4, 6, 8], [2, 4, 5, 6, 7]], intsearch!) @assert 1:5 == svs([1:10, 1:5], intsearch!) @assert 1:9 == svs([0:10, 1:9], intsearch!) @assert 1:2:9 == svs([0:10, 1:2:9], intsearch!) @assert [5, 15] == svs([[1, 5, 7, 10, 12, 15], [2, 5, 7, 15], [3, 5, 9, 15, 16]], merge_intersect!) ``` ### Algoritmo de Barbay y Kenyon Existe otra familia de algoritmos, basados en búsquedas adaptativas que pueden llegar a mejorar el desempeño bajo cierto tipo de entradas. @DLOPM2001, @BLOL2006 y @BLOLS2010 muestran algoritmos de intersección basados en búsquedas adaptativas para aprovechar instancias simples. Estos estudios se basan en contribuciones teóricas de los mismos autores: @DLOM2000, @DLOPM2001, @BK2002 y @BY2004. La idea central es la de un _eliminador_: se toma un candidato `el`, inicialmente el primer elemento de la primera lista, y se busca su posición de inserción en las demás listas, una por una, de forma cíclica. Si todas las listas contienen a `el`, pertenece a la intersección. Si alguna lista no lo contiene, el elemento que encontramos en su lugar, `L[i][P[i]]`, es mayor que `el` y ningún elemento entre ambos puede estar en la intersección; ese elemento se convierte en el nuevo candidato y la ronda comienza de nuevo. Las posiciones `P[i]` se recuerdan entre rondas, de modo que cada lista se recorre una sola vez de izquierda a derecha, con búsquedas no acotadas que aprovechan la cercanía entre candidatos sucesivos. El algoritmo de @BLOL2006 trabaja sobre los $k$ conjuntos de entrada, representados como arreglos ordenados de números enteros. Es un algoritmo simple pero poderoso: hace uso de búsquedas adaptativas con memoria para guardar las posiciones donde se avanza, de tal forma que no se recalculen posiciones. Las diferentes estrategias para revisar los conjuntos pueden dar diferentes desempeños, como se valida en @BLOLS2010, donde además de hacer una gran variedad de experimentos sobre diferentes algoritmos de búsqueda, se introducen variantes en el orden de acceso de cada conjunto. A continuación se muestra el código del algoritmo base: ```{julia} #| lst-label: lst-bk #| lst-cap: Algoritmo de Barbay y Kenyon para $k$ conjuntos # Adaptado de https://github.com/sadit/Intersections.jl function bk!(output, L::AbstractVector, findpos::Function=doublingsearch) P = ones(Int, length(L)) bk!(output, L, P, findpos) end function bk!(output, L, P, findpos::Function=doublingsearch) # <1> n = length(L) # <2> el = L[1][1] # <3> c = 0 # <4> @inbounds while true for i in eachindex(P) P[i] = findpos(L[i], el, P[i]) # <5> P[i] > length(L[i]) && return output pval = L[i][P[i]] if pval == el c += 1 if c == n # <6> push!(output, el) c = 0 # <7> P[i] += 1 # <7> P[i] > length(L[i]) && return output el = L[i][P[i]] # <7> end else c = 0 # <8> el = pval # <8> end end end output end bk!(Int[], [[1, 5, 7, 10, 12, 15], [2, 5, 7, 15], [3, 5, 9, 15, 16]]) ``` 1. El algoritmo de Barbay y Kenyon recibe: i) `output` el conjunto de salida. ii) `L` la lista de conjuntos (representados como arreglos ordenados). iii) `P` arreglo de posiciones _actuales_ para cada arreglo. iv) `findpos` función de búsqueda. 2. Número de conjuntos en `L`. 3. `el` es el candidato o _eliminador_ actual, el elemento siendo buscado en todos los arreglos. 4. `c` número de listas consecutivas que contienen `el`. 5. Buscando la posición de inserción de `el` en `L[i]`, comenzando en `P[i]`. Si `el` es mayor que todo `L[i]`, no hay más elementos en la intersección. 6. Si las $n$ listas contienen `el`, hay intersección. 7. Se reporta `el`, se avanza la posición en la lista actual y el siguiente elemento de esa lista es el nuevo candidato. 8. La lista `i` no contiene a `el`; el elemento encontrado en su lugar es mayor y se vuelve el nuevo candidato, reiniciando la cuenta. ```{julia} #| output: false #| echo: false for f in (binarysearch, doublingsearch, doublingdoublingsearch) @assert [4, 6] == bk!(Int[], [[1, 3, 4, 6, 8], [2, 4, 5, 6, 7]], f) @assert 1:5 == bk!(Int[], [1:10, 1:5], f) @assert 1:9 == bk!(Int[], [0:10, 1:9], f) @assert 1:2:9 == bk!(Int[], [0:10, 1:2:9], f) @assert [5, 15] == bk!(Int[], [[1, 5, 7, 10, 12, 15], [2, 5, 7, 15], [3, 5, 9, 15, 16]], f) end ``` La adaptabilidad del algoritmo se mide con el tamaño del _certificado_ de la instancia: el número mínimo de comparaciones que bastarían para convencer a alguien de que la intersección es la correcta. En instancias donde los conjuntos se alternan en bloques grandes (todos los elementos de una lista están entre dos elementos consecutivos de otra), el certificado es pequeño y el algoritmo de Barbay y Kenyon lo aprovecha saltando bloques enteros con cada búsqueda; en instancias donde los conjuntos están finamente entrelazados, el certificado es grande y ningún algoritmo puede hacerlo mucho mejor que la mezcla. De manera particular, @BLOLS2010 presentan un estudio experimental sobre los algoritmos presentados en el área durante la década de 2000 a 2010, dichos algoritmos se parametrizaron de maneras que nos permiten aprender diferentes características de cada uno de ellos, dependiendo de los algoritmos de búsqueda que usan, la arquitectura computacional donde se evalúa, y el número de conjuntos siendo procesados. Una de las lecciones de ese estudio es que el número de comparaciones no determina el tiempo: los algoritmos con accesos más secuenciales a memoria suelen ganar en tiempo aunque hagan más comparaciones. #### Ejercicios 1. Compare el orden en que SvS y Barbay y Kenyon procesan las listas. ¿Qué ventaja tiene cada enfoque cuando una de las listas es mucho más pequeña que las demás? ¿Y cuando todas tienen tamaños parecidos? 2. Trace @lst-bk sobre las tres listas de posteo del ejemplo del índice invertido, anotando el candidato `el` y el arreglo `P` después de cada búsqueda. 3. Construya una instancia de $k = 3$ listas de tamaño $n$ donde Barbay y Kenyon haga $O(\log n)$ búsquedas y otra donde haga $\Omega(n)$. Relacione ambas con el tamaño del certificado. 4. Implemente la unión de $k$ conjuntos con una cola de prioridad (_heap_) que mantenga el frente de cada lista, y analice su costo. ## Lecturas La cota inferior y el algoritmo para conjuntos de tamaños muy distintos se presentan en @hwang1971optimal; la lectura de las primeras secciones es accesible y es un buen ejemplo de análisis en el modelo de comparación. @BY2004 presenta el algoritmo de Baeza-Yates con su análisis y experimentos, y @BYS2005 lo extiende con una evaluación experimental más amplia. Los fundamentos de los algoritmos adaptables para intersección están en @DLOM2000 y @DLOPM2001, y el algoritmo de Barbay y Kenyon, con su análisis en términos del certificado de la instancia, en @BK2002. Finalmente, @BLOL2006 y @BLOLS2010 son los estudios experimentales de referencia; se recomienda leer con atención la metodología experimental de @BLOLS2010, ya que la actividad de este capítulo sigue el mismo espíritu. ## Recursos audio-visuales de la unidad Parte 1: Algoritmos de intersección (y unión) de listas ordenadas <iframe width="560" height="315" src="https://www.youtube.com/embed/aDYO39yi-4g" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> Parte 2: Algoritmos de intersección y algunas aplicaciones <iframe width="560" height="315" src="https://www.youtube.com/embed/oOd5LoVJcAs" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> ## Actividades ### Actividad 1: Intersección de listas de posteo sintéticas El objetivo es comparar experimentalmente los algoritmos de intersección del capítulo sobre grupos de $k$ listas con razones de tamaño y traslapes controlados, que imitan a las listas de posteo de un índice invertido. Todos los datos se generan con el código de @lst-generadores-listas, con semillas fijas, para que todos los reportes trabajen sobre las mismas instancias; **no** utilice archivos externos ni cambie las semillas ni los parámetros predeterminados. El generador construye un grupo de $k$ listas de la siguiente manera: la lista más pequeña, de tamaño $n_k$, se toma uniformemente del universo $1:U$; cada lista más grande tiene un tamaño $n_i = n_1 / r^{i-1}$, donde $r$ es la razón entre tamaños consecutivos, e incluye cada elemento de la lista pequeña con probabilidad $t$ (el _traslape_) más elementos uniformes hasta completar su tamaño. Así, la intersección tiene aproximadamente $t^{k-1} n_k$ elementos, y la razón $r$ controla si estamos en el régimen de la mezcla ($r = 1$) o en el de las búsquedas ($r \gg 1$). ```{julia} #| lst-label: lst-generadores-listas #| lst-cap: Generador de grupos de listas de posteo sintéticas con semillas fijas #| output: false using Random const SEMILLA = 2026 """ genera_grupo(k, n1, razon, traslape; U=2^20, semilla=SEMILLA) Grupo de `k` listas ordenadas de enteros distintos en `1:U`. La lista `i` tiene tamaño aproximado `n1 ÷ razon^(i-1)`; cada lista contiene cada elemento de la lista más pequeña con probabilidad `traslape`, por lo que la intersección tiene unos `traslape^(k-1) * nk` elementos. """ function genera_grupo(k, n1, razon, traslape; U=2^20, semilla=SEMILLA) rng = Xoshiro(semilla) tams = [max(1, n1 ÷ razon^(i - 1)) for i in 1:k] S = sort!(randperm(rng, U)[1:tams[k]]) # la lista más pequeña L = Vector{Vector{Int}}(undef, k) L[k] = S for i in 1:k-1 nucleo = S[rand(rng, length(S)) .< traslape] # elementos plantados de S resto = randperm(rng, U)[1:tams[i] - length(nucleo)] L[i] = sort!(unique!(vcat(nucleo, resto))) end L end """ genera_coleccion(k; n1=2^16, razones=(1, 4, 16), traslape=0.5, repeticiones=20) Colección de grupos de `k` listas: `repeticiones` grupos por cada razón de tamaños. Regresa un vector de pares `(razon, grupo)`. """ function genera_coleccion(k; n1=2^16, razones=(1, 4, 16), traslape=0.5, repeticiones=20) C = Tuple{Int, Vector{Vector{Int}}}[] for (j, r) in enumerate(razones), rep in 1:repeticiones semilla = SEMILLA + 10_000k + 100j + rep push!(C, (r, genera_grupo(k, n1, r, traslape; semilla))) end C end ``` La siguiente salida sirve como _control_: reproduzca estos valores con sus propios datos antes de medir nada; si trabaja en Python, replique la lógica del generador y verifique que los tamaños y las longitudes de las intersecciones sean similares. ```{julia} for k in (2, 3, 4) C = genera_coleccion(k) for r in (1, 4, 16) grupos = [L for (razon, L) in C if razon == r] tams = round.(Int, sum(length.(L) for L in grupos) ./ length(grupos)) inter = sum(length(svs(copy(L), merge_intersect!)) for L in grupos) inter /= length(grupos) print("k = $k, razón = $(lpad(r, 2)): $(length(grupos)) grupos, ") println("tamaños ~ $tams, |interseccion| ~ $(round(inter, digits=1))") end end ``` Con estos datos, realice lo siguiente: 1. **Implementación.** Implemente la intersección por mezcla (ME), por búsquedas sucesivas (@lst-intsearch), el algoritmo de Baeza-Yates (BY) y el de Barbay y Kenyon (BK), reutilizando los algoritmos de búsqueda que desarrolló en la actividad del [Capítulo 5](cap5-busqueda.qmd). Parametrice las búsquedas sucesivas, BY y BK con búsqueda binaria, $B_1$ y $B_2$. Para $k \geq 3$ use SvS con cada algoritmo binario, y BK directamente sobre las $k$ listas. Verifique todas las combinaciones contra la intersección con `Set` de Julia sobre instancias pequeñas aleatorias. 2. **Datos.** Genere las colecciones para $k \in \{2, 3, 4\}$ con `genera_coleccion` y sus parámetros predeterminados: $n_1 = 2^{16}$, razones $r \in \{1, 4, 16\}$, traslape $0.5$ y $20$ repeticiones por razón. Si su equipo no lo permite, reduzca $n_1$ y repórtelo; sus valores de control serán entonces distintos. 3. **Experimentación.** Para cada grupo, calcule la intersección con cada algoritmo y acumule el tiempo en segundos y el número de comparaciones; puede envolver las listas en `CountingArray` del Capítulo 5 para contar los accesos. Repita las mediciones de tiempo las veces necesarias para que sean fiables (vea la metodología del [Capítulo 2](cap2-analisis.qmd)). Presente gráficas de caja (_boxplot_), una por cada combinación de $k$ y razón $r$, que incluyan todos los algoritmos para que sean fáciles de comparar: - tiempo en segundos por algoritmo, - número de comparaciones por algoritmo, - longitud de la intersección resultante; esta gráfica es de _control_: todos los algoritmos deben coincidir, y los valores deben ser compatibles con el cuadro anterior. 4. **Análisis.** Examine las diferencias en tiempo y número de comparaciones entre los algoritmos para cada $k$ y razón $r$. En particular: ¿para qué razones gana la mezcla y para cuáles los algoritmos basados en búsqueda? ¿Cómo se compara el número de comparaciones con la cota inferior $\log_2 {m+n \choose m}$ y con $2m\log_2(n/m)$? ¿Coinciden los ganadores en comparaciones y en tiempo? ¿Qué algoritmo de búsqueda conviene como parámetro de BY y de BK, y depende de $r$? Discuta cualquier tendencia, anomalía o patrón interesante observado, y concluya con una recomendación para resolver consultas en un índice invertido. ### Entregable Su trabajo se entregará en PDF y con el notebook fuente, se entregará en el sistema en archivos separados. El código se debe documentar, así como mantener una estructura del documento que permita a un lector interesado entender el problema, sus experimentos y metodología, así como sus conclusiones. Tenga en cuenta que los notebooks pueden alternar celdas de texto y código. No olvide estructurar su reporte, en particular el reporte debe cubrir los siguientes puntos: - Título del reporte, su nombre. - Introducción. - Desarrollo de las actividades. - Conclusiones - Lista de referencias. Nota, una lista de referencias que no fueron utilizadas en el cuerpo del texto será interpretada como una lista vacía. Nota: no olvides revisar la rúbrica del curso.