6 Algoritmos de intersección y unión de conjuntos en el modelo de comparación – Curso Introductorio al Análisis de Algoritmos con Julia

Objetivo

Analizar el rendimiento de algoritmos de unión e intersección de conjuntos representados como listas ordenadas parametrizando los algoritmos con los algoritmos internos de búsqueda, tamaño de los conjuntos y la distribución de los elementos, bajo un enfoque experimental midiendo los costos en términos del tiempo de ejecución y el uso de memoria.

6.1 Problema

Cómo se vió 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 la matriz dispersa muy grande, llamada índice invertido.

Estaremos resolviendo los problemas de intersección y unión de conjuntos. Demaine, López-Ortiz, y Munro (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. Claramente, colectar los datos para la unión y la intersección, requieren diferentes esfuerzos.

6.1.1 Costo del problema

En general, dados dos conjuntos $A[1..m] = \{a_1 < a_2 < \cdots < a_m \}$ y $B[1..n] = \{b_1 < b_2 < \cdots < b_n \}$, el costo de unión es \[\log{m+n \choose m},\] ver Hwang y Lin (1971).

De manera más detallada, 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 problema puede verse como todas las posibles instancias de ordenes o permutaciones de tamaño $n+m$; removiendo la necesidad de los ordenes parciales, esto es ${n+m \choose m}$ posibles instancias de tamaño $n+m$, generadas por dos conjuntos de tamaño $n$ y $m$. Dado que estamos en un modelo basado en comparaciones, y dado el mejor algoritmo $s$ puede dividir el espacio de posibles ordenes en 2, por tanto, dicho algoritmo necesitará \[\log_2 {n+m \choose m}\] comparaciones para resolver la unión de cualquier par de conjuntos de tamaño $m$ y $n$.

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

Recuerde que $\log_2 x = \frac{\log_e x}{\log e}$.

6.2 Algoritmos

Se puede observar que si $m \approx n$, entonces el costo se convierte en $O(m + n)$, esto es, lo más eficiente sería tomar el siguiente algoritmo:


function merge2!(C, A, B)
    i = j = 1
    m, n = length(A), length(B)
    
    @inbounds while i <= m ||  j <= n
        a, b = A[i], B[j]
        if a == b
            push!(C, a)
            i += 1
            j += 1
        elseif a < b
            push!(C, a)
            i += 1
        else
            push!(C, b)
            j += 1
        end
    end

    C
end

merge2! (generic function with 1 method)

6.2.1 Ejercicio

Escriba y pruebe el algoritmo de intersección de merge para $n \approx m$.

6.3 Algoritmos para arreglos de tamaño muy diferente

Si $m \ll n$, el costo tenderá a $O(m \log n)$, por lo que se pueden realizar $m$ búsquedas binarias directas para localizar la posición de inserción en $B$.

Figura 6.1: Dos listas alineadas donde los nodos sombreados son elementos de los conjuntos.

Se hace notar que $A$ y $B$ estan ordenados, y por lo tanto, localizar $A[i]$ en $B[j]$ significa que $B[j-1] < A[i]$, por lo que intentar localizar $A[i+1]$ puede comenzar en $B[j+1]$. A continuación se muestra el código de un algoritmo de intersección usando algoritmos de búsqueda con memoria de la posición anterior.

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

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

    C
end

Hwang y Lin (1971) propone otro algoritmo que funciona para casos similares:

Divide $B$ en bloques de tamaño $m$, define un arreglo virtual $B'[1..n/m]$ donde $B'[i] = B[i \cdot m]$
Se búsca la posición de inserción $p$ de cada $a \in A$ en $B'$, costando $\log n/m$ para cada búsqueda.
Después se localiza dentro del $B$ en el $p$-ésimo bloque, i.e., $B[(p-1)m + 1 .. p\cdot m]$, por la posición de inserción del bloque, con un costo de $\log m$.

Entonces, se obtiene un costo de $O(m \log{n/m} + m \log m)$; esto es equivalente en el peor caso a búsquedas directas, i.e., las posiciones de inserción de $a \in A$ se encuentran distribuidas de manera uniforme en $B$. Sin embargo, es posible mejorar si se descartan bloques en el paso 1. Esto es, si se hay concentración de elementos de $A$ en bloques de $B$. Para esto, es necesario un análisis de costo promedio, el cual se muestra en el artículo.

Incluso cuando hay concentración, podemos recordar la $(i-1)$ posición de inserción para iniciar la $i$-ésima búsqueda, y sacar provecho de posiciones esperadas cercanas de la posición inicial de búsqueda, i.e., podemos utilizar algoritmos de búsqueda adaptables para mejorar el desempeño.

6.3.1 Algoritmo de Baeza Yates

Baeza-Yates (2004) propone un algoritmo eficiente para intersecciones de dos conjuntos. El algoritmo tiene una estrategía dividir para vencer:

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 implementan recurriendo, ajustando los rangos de trabajo.

A continuación se muestra el código en Julia, usando los algoritmos de búsqueda del Cap. 5.

# 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]
    ## our findpos returns n + 1 when median is larger than 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

1: Punto de entrada.
2: Búsqueda de la posición de inserción de la mediana de $A$ en $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 este entre las recurrencias para que output sea un arreglo ordenado.
5: Recurencia para el problema $C_>$.

El algoritmo de Baeza Yates es óptimo en el peor caso y es capaz de aprovechar casos donde $C_<$ o $C_>$ se convierten en triviales, lo cual da muy buenos casos en algunas distribuciones.

6.3.2 Ejercicios

Implemente la unión con el algoritmo de Baeza Yates.

6.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 estan limitadas a dos conjuntos, y por tanto, es importante algoritmos y estrategías para resolver $\bigcup_i A_i$ así como $\bigcap_i A_i$.

6.4.1 Algoritmo SvS

Dado $C = A \cap B$ es un hecho que $|C| \leq min \{|A|, |B|\}$. Recordando, que hay maneras relativamente simples y eficientes de resolver la intersección cuando $m \ll n$; por tanto, cuando tenemos más de dos conjuntos podemos aplicar la estrategía Small vs Small (SvS), que consisten en intersectar los $k$ conjuntos por pares intersectando el par de arreglos más pequeños cada vez.

# 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)
    curr = pop!(L)

    while length(L) > 0
        empty!(prev)
        isize = in2(prev, curr, pop!(L))
        isize == 0 && return prev
        prev, curr = curr, prev
    end

    curr
end

6.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, López-Ortiz, y Ian Munro (2001), Barbay, López-Ortiz, y Lu (2006), y Barbay et al. (2010) muestran algoritmos de intersección basados en búsqueda adaptables para aprovechar instancias simples. Estos estudios se basan en contribuciones teóricas de los mismos autores: Demaine, López-Ortiz, y Munro (2000), Demaine, López-Ortiz, y Ian Munro (2001), Barbay y Kenyon (2002) y Baeza-Yates (2004).

El algoritmo de Barbay, López-Ortiz, y Lu (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 adaptivas 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:

# 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
                c = 0
                el = pval
            end
        end
    end

    output
end

1: El algoritmo de Barbay & 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 elemento siendo búscado en todos los arreglos.
4: c número de listas que contienen el.
5: Búscando la posición de inserción de el en L[i], comenzando en P[i].
6: Esta igualdad implica que hay interección.
7: Reiniciando el y c y actualizando P[i].

De manera particular, Barbay et al. (2010) presentan un estudio experimental sobre los algoritmos presentados en el área durante la decada 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.

6.5 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

6.6 Actividades

Implementación y comparación de diferentes algoritmos de intersección de conjuntos.

Lea cuidadosamente las instrucciones y desarrolle las actividades. Entregue el reporte correspondiente en tiempo.

--- lang: es-MX engine: julia --- # Algoritmos de intersección y unión de conjuntos en el modelo de comparación {#sec-intersecciones} ## Objetivo {.unnumbered} Analizar el rendimiento de algoritmos de unión e intersección de conjuntos representados como listas ordenadas parametrizando los algoritmos con los algoritmos internos de búsqueda, tamaño de los conjuntos y la distribución de los elementos, bajo un enfoque experimental midiendo los costos en términos del tiempo de ejecución y el uso de memoria. ## Problema Cómo se vió 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 la matriz dispersa muy grande, llamada _índice invertido_. Estaremos resolviendo 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. Claramente, colectar los datos para la unión y la intersección, requieren diferentes esfuerzos. ### Costo del problema En general, dados dos conjuntos $A[1..m] = \{a_1 < a_2 < \cdots < a_m \}$ y $B[1..n] = \{b_1 < b_2 < \cdots < b_n \}$, el costo de unión es $$\log{m+n \choose m},$$ ver @hwang1971optimal. De manera más detallada, 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 problema puede verse como todas las posibles instancias de ordenes o permutaciones de tamaño $n+m$; removiendo la necesidad de los ordenes parciales, esto es ${n+m \choose m}$ posibles instancias de tamaño $n+m$, generadas por dos conjuntos de tamaño $n$ y $m$. Dado que estamos en un modelo basado en comparaciones, y dado el mejor algoritmo $s$ puede dividir el espacio de posibles ordenes en 2, por tanto, dicho algoritmo necesitará $$\log_2 {n+m \choose m}$$ comparaciones para resolver la unión de cualquier par de conjuntos de tamaño $m$ y $n$. Usando la aproximación de Stirling para coefficientes binomiales de @mackay2003information, el costo se convierte en: $$\log{m+n \choose m} = n\log{\frac{m+n}{n}} + m \log\frac{n+m}{m} $$ ::: {.column-margin} Recuerde que $\log_2 x = \frac{\log_e x}{\log e}$. ::: ```{julia} #| echo: false #| output: false # tomados de cap5 function binarysearch(A, x, sp=1, ep=length(A)) while sp < ep # <3> mid = div(sp + ep, 2) # <1> if x <= A[mid] # <1> ep = mid # <2> else sp = mid + 1 # <2> end end x <= A[sp] ? sp : sp + 1 # <4> end function doublingsearch(A, x, sp=1) n = length(A) p = 0 i = 1 while sp+i <= n && A[sp+i] < x # <1> p = i i += i end binarysearch(A, x, sp + p, min(n, sp+i)) # <2> end ``` ## Algoritmos Se puede observar que si $m \approx n$, entonces el costo se convierte en $O(m + n)$, esto es, lo más eficiente sería tomar el siguiente algoritmo: ```{julia} function merge2!(C, A, B) # <1> i = j = 1 m, n = length(A), length(B) @inbounds while i <= m || j <= n # <2> a, b = A[i], B[j] if a == b push!(C, a) i += 1 j += 1 elseif a < b push!(C, a) i += 1 else push!(C, b) j += 1 end end C end ``` ### Ejercicio - Escriba y pruebe el algoritmo de intersección de merge para $n \approx m$. ```{julia} #| echo: false #| output: false @assert 1:8 == merge2!(Int[], [1, 3, 4, 6, 8], [2, 5, 7]) @assert 0:9 == merge2!(Int[], [1, 3, 4, 6, 8], [0, 2, 5, 7, 9]) @assert 1:10 == merge2!(Int[], 1:5, 6:10) ``` ## Algoritmos para arreglos de tamaño muy diferente Si $m \ll n$, el costo tenderá a $O(m \log n)$, por lo que se pueden realizar $m$ búsquedas binarias _directas_ para localizar la posición de inserción en $B$. ```{dot} //| label: fig-interseccion //| echo: false //| fig-width: 100% //| fig-cap: | //| Dos listas alineadas donde los nodos sombreados son elementos de los conjuntos. 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]; } ``` Se hace notar que $A$ y $B$ estan ordenados, y por lo tanto, localizar $A[i]$ en $B[j]$ significa que $B[j-1] < A[i]$, por lo que intentar localizar $A[i+1]$ puede comenzar en $B[j+1]$. A continuación se muestra el código de un algoritmo de intersección usando algoritmos de búsqueda con memoria de la posición anterior. ```{julia} #| output: false function intsearch!(C, A, B, algosearch=doublingsearch) if length(B) < length(A) A, B = B, A end p = 1 for (i, a) in enumerate(A) p = algosearch(B, a, p) p > length(B) && break if a == B[p] p += 1 push!(C, a) end end C end ``` ```{julia} #| output: false #| echo: false @assert [4, 6] == intsearch!(Int[], [1, 3, 4, 6, 8], [2, 4, 5, 6, 7]) @assert 1:5 == intsearch!(Int[], 1:10, 1:5) @assert 1:9 == intsearch!(Int[], 0:10, 1:9) @assert 1:2:9 == intsearch!(Int[], 0:10, 1:2:9) ``` @hwang1971optimal propone otro algoritmo que funciona para casos similares: 1. Divide $B$ en bloques de tamaño $m$, define un arreglo _virtual_ $B'[1..n/m]$ donde $B'[i] = B[i \cdot m]$ 2. Se búsca la posición de inserción $p$ de cada $a \in A$ en $B'$, costando $\log n/m$ para cada búsqueda. 3. Después se localiza dentro del $B$ en el $p$-ésimo bloque, i.e., $B[(p-1)m + 1 .. p\cdot m]$, por la posición de inserción del bloque, con un costo de $\log m$. Entonces, se obtiene un costo de $O(m \log{n/m} + m \log m)$; esto es equivalente en el peor caso a búsquedas directas, i.e., las posiciones de inserción de $a \in A$ se encuentran distribuidas de manera uniforme en $B$. Sin embargo, es posible mejorar si se descartan bloques en el paso 1. Esto es, si se hay concentración de elementos de $A$ en bloques de $B$. Para esto, es necesario un análisis de costo promedio, el cual se muestra en el artículo. Incluso cuando hay concentración, podemos recordar la $(i-1)$ posición de inserción para iniciar la $i$-ésima búsqueda, y sacar provecho de posiciones esperadas cercanas de la posición inicial de búsqueda, i.e., podemos utilizar algoritmos de búsqueda adaptables para mejorar el desempeño. ### Algoritmo de Baeza Yates @BY2004 propone un algoritmo eficiente para intersecciones de dos conjuntos. El algoritmo tiene una estrategía _dividir para vencer_: 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 implementan recurriendo, ajustando los rangos de trabajo. A continuación se muestra el código en Julia, usando los algoritmos de búsqueda del Cap. 5. ```{julia} #| output: false # 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] ## our findpos returns n + 1 when median is larger than 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 ``` 1. Punto de entrada. 2. Búsqueda de la posición de inserción de la mediana de $A$ en $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 este entre las recurrencias para que _output_ sea un arreglo ordenado. 5. Recurencia para el problema $C_>$. ```{julia} #| output: false #| echo: false @assert [4, 6] == baezayates!(Int[], [1, 3, 4, 6, 8], [2, 4, 5, 6, 7]) @assert 1:5 == baezayates!(Int[], 1:10, 1:5) @assert 1:9 == baezayates!(Int[], 0:10, 1:9) @assert 1:2:9 == baezayates!(Int[], 0:10, 1:2:9) ``` El algoritmo de Baeza Yates es óptimo en el peor caso y es capaz de aprovechar casos donde $C_<$ o $C_>$ se convierten en triviales, lo cual da muy buenos casos en algunas distribuciones. ### Ejercicios 1. Implemente la unión con el algoritmo de Baeza Yates. ## 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 estan limitadas a dos conjuntos, y por tanto, es importante algoritmos y estrategías para resolver $\bigcup_i A_i$ así como $\bigcap_i A_i$. ### Algoritmo SvS Dado $C = A \cap B$ es un hecho que $|C| \leq min \{|A|, |B|\}$. Recordando, que hay maneras relativamente simples y eficientes de resolver la intersección cuando $m \ll n$; por tanto, cuando tenemos más de dos conjuntos podemos aplicar la estrategía _Small vs Small (SvS)_, que consisten en intersectar los $k$ conjuntos por pares intersectando el par de arreglos más pequeños cada vez. ```{julia} #| output: false # 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) curr = pop!(L) while length(L) > 0 empty!(prev) isize = in2(prev, curr, pop!(L)) isize == 0 && return prev prev, curr = curr, prev end curr end ``` ```{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!) ``` ### 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úsqueda adaptables para aprovechar instancias simples. Estos estudios se basan en contribuciones teóricas de los mismos autores: @DLOM2000, @DLOPM2001, @BK2002 y @BY2004. 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 adaptivas 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} #| output: false # 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 # <7> el = pval # <7> end end end output end ``` 1. El algoritmo de Barbay & 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 elemento siendo búscado en todos los arreglos. 4. `c` número de listas que contienen `el`. 5. Búscando la posición de inserción de `el` en `L[i]`, comenzando en `P[i]`. 6. Esta igualdad implica que hay interección. 7. Reiniciando `el` y `c` y actualizando `P[i]`. ```{julia} #| output: false #| echo: false @assert [4, 6] == bk!([], [[1, 3, 4, 6, 8], [2, 4, 5, 6, 7]]) @assert 1:5 == bk!([], [1:10, 1:5]) @assert 1:9 == bk!([], [0:10, 1:9]) @assert 1:2:9 == bk!([], [0:10, 1:2:9]) ``` De manera particular, @BLOLS2010 presentan un estudio experimental sobre los algoritmos presentados en el área durante la decada 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. ## 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 Implementación y comparación de diferentes algoritmos de intersección de conjuntos. Lea cuidadosamente las instrucciones y desarrolle las actividades. Entregue el reporte correspondiente en tiempo.