PRÁCTICA 5A: REPORTE ESCRITO. EXPERIMENTOS Y ANÁLISIS DE ALGORITMOS DE INTERSECCIÓN DE CONJUNTOS.

PROFESOR: DR. ERIC SADIT TÉLLEZ AVILA

ESTUDIANTE: EDGAR SANTIAGO GONZALEZ MARTINEZ

Introducción

La intersección de listas ordenadas es una operación central en el modelo de comparación y en tareas de recuperación de información, donde cada lista representa un conjunto de documentos o registros que cumplen cierta condición (Baeza-Yates & Ribeiro-Neto, 2011). En este contexto, interesa no solo obtener correctamente la intersección, sino también minimizar el tiempo de ejecución y el número de comparaciones entre claves.

En este reporte se estudian tres esquemas de intersección de conjuntos: Melding (ME), que intersecta primero las listas más pequeñas para reducir el tamaño de los resultados intermedios; Baeza–Yates (BY), un algoritmo divide-y-vencerás que utiliza una lista guía y realiza búsquedas sobre las demás; y Barbay & Kenyon (BK), que mantiene punteros en todas las listas y actualiza de forma adaptativa un candidato común. El algoritmo de Baeza–Yates se implementa parametrizado con tres estrategias de búsqueda sobre listas ordenadas: búsqueda binaria clásica y dos variantes de búsqueda no acotada (B1 y B2).

Para la evaluación empírica se utilizan tres familias de datos (A, B y C), correspondientes a pares, tripletas y tetrapletas de listas ordenadas. En cada familia se mide, para cada algoritmo, el tiempo de ejecución, el número de comparaciones y la longitud de la intersección resultante, repitiendo los experimentos varias veces y resumiendo los resultados mediante tablas y gráficos tipo boxplot.

Conexión de Google Drive con Google Colab

Como primer procedimiento, se conecta Google Drive con Google Colab para poder acceder a los archivos almacenados en la nube.

La instrucción from google.colab import drive permite importar el módulo drive, el cual posibilita que Colab interactúe con Google Drive. El comando drive.mount('/content/drive') monta Google Drive en la carpeta /content/drive.

from google.colab import drive
drive.mount('/content/drive')

Mounted at /content/drive

Importación de librerías y carga de datos

En esta sección se importan las librerías necesarias para el experimento. Los módulos os y json permiten manejar rutas de archivos y leer datos en formato JSON. Numpy y pandas se utilizan para trabajar con arreglos y tablas de datos, matplotlib.pyplot para generar las gráficas de resultados y time para medir tiempos de ejecución.

import os, json, time
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

Después se define la ruta BASE, que apunta a la carpeta de trabajo en Google Drive donde se encuentran los archivos de la unidad 5. A partir de esta ruta se construye, de forma compacta, la ubicación completa de cada archivo JSON.

BASE = "/content/drive/MyDrive/MCDI/5A_AdA"

def cargar_json(nombre):
    with open(os.path.join(BASE, nombre), encoding="utf-8") as f:
        return json.load(f)

Posteriormente se declara la función cargar_json, que combina BASE con el nombre del archivo, lo abre con codificación adecuada y utiliza json.load para obtener los datos como estructuras de Python. Con esta función se cargan tres colecciones crudas: A_raw, B_raw y C_raw, que corresponden a las familias A, B y C del enunciado. Finalmente se imprimen los tamaños de estas estructuras para comprobar que cada familia tiene el número esperado de grupos y que en cada grupo hay 2, 3 o 4 listas, según corresponda.

A_raw = cargar_json("postinglists-for-intersection-A-k=2.json")
B_raw = cargar_json("postinglists-for-intersection-B-k=3.json")
C_raw = cargar_json("postinglists-for-intersection-C-k=4.json")
print(len(A_raw), len(B_raw), len(C_raw))
print(len(A_raw[0]), len(B_raw[0]), len(C_raw[0]))

200 200 200
2 3 4

Limpieza de datos

Antes de aplicar los algoritmos de intersección, se realiza una limpieza de los datos para que cada lista se comporte realmente como un conjunto ordenado. Para ello, se define una función que recorre cada grupo de la familia (A, B o C) y, dentro de cada grupo, procesa cada lista de identificadores.

En cada lista se aplica primero set(L) para eliminar elementos duplicados y después sorted(...) para ordenar los valores de menor a mayor. El resultado es una nueva estructura en la que todas las listas están libres de repeticiones y en orden creciente, lo que coincide con el supuesto teórico de conjuntos ordenados en el modelo de comparación.

Se decidió hacer esta limpieza porque, en los archivos originales, pueden aparecer valores repetidos o desordenados que no forman parte del modelo ideal. Al normalizar, garantizamos que los datos cumplen las condiciones teóricas, evitamos comparaciones “extra” debidas a ruido en los datos y obtenemos resultados más claros y consistentes en los experimentos. A partir de esta normalización se construyen las versiones A, B y C que se utilizan en las pruebas.

def normalizar_familia(F):
    F_norm = []
    for grupo in F:
        nuevo_grupo = []
        for L in grupo:
            L_norm = sorted(set(L))
            nuevo_grupo.append(L_norm)
        F_norm.append(nuevo_grupo)
    return F_norm
A = normalizar_familia(A_raw)
B = normalizar_familia(B_raw)
C = normalizar_familia(C_raw)

Contador de comparaciones y medición de tiempo

Para evaluar el desempeño de los algoritmos no solo se considera el tiempo de ejecución, sino también el número de comparaciones realizadas entre claves. La clase CmpCounter se encarga de llevar ese conteo: inicializa un contador en cero y define tres métodos (lt, le y eq) que encapsulan las comparaciones <, <= y ==. Cada vez que uno de estos métodos se llama dentro de un algoritmo, se incrementa el contador y se devuelve el resultado lógico de la comparación. De esta forma, al final de cada experimento se puede saber cuántas comparaciones realizó el algoritmo sobre las listas.

Además, se define la función medir_tiempo, que recibe una función y sus argumentos, ejecuta el código y mide el intervalo de tiempo usando time.perf_counter(). Esta función devuelve tanto el resultado de la operación como el tiempo transcurrido en segundos. Combinando CmpCounter y medir_tiempo es posible registrar, para cada algoritmo y conjunto de listas, dos métricas clave: el número de comparaciones y el tiempo de ejecución.

class CmpCounter:
    def __init__(self):
        self.count = 0
    def lt(self, a, b):
        self.count += 1
        return a < b
    def le(self, a, b):
        self.count += 1
        return a <= b
    def eq(self, a, b):
        self.count += 1
        return a == b
def medir_tiempo(fn, *args, **kwargs):
    t0 = time.perf_counter()
    res = fn(*args, **kwargs)
    t1 = time.perf_counter()
    return res, (t1 - t0)

Algoritmos de búsqueda: binaria, B1 y B2

En esta sección se definen tres rutinas de búsqueda sobre listas ordenadas que se utilizan como subrutinas dentro de los algoritmos de intersección. Todas reciben una lista A, un valor objetivo x, una posición inicial lo y el contador de comparaciones cmp, siguiendo el enfoque del modelo de comparación presentado en los materiales del curso (Sadit, s. f.-a; Baeza-Yates & Ribeiro-Neto, 2011).

La función findpos_binaria implementa una búsqueda binaria clásica. A partir del rango [lo, len(A)) va partiendo el segmento a la mitad hasta localizar la primera posición p donde A[p] es mayor o igual que x (lower_bound). Cada comparación se realiza a través de cmp.lt, de modo que el número de comparaciones queda registrado.

La función findpos_B1 implementa una búsqueda no acotada de tipo “doubling search”. Primero avanza con saltos crecientes (1, 2, 4, 8, …) desde la posición lo hasta encontrar un rango donde puede estar x. Una vez acotado ese intervalo, aplica búsqueda binaria dentro de ese subrango. Esta estrategia puede ser más eficiente cuando la posición de x está relativamente cerca del punto de partida.

La función findpos_B2 también realiza una búsqueda no acotada, pero con saltos que crecen más rápido (2, 4, 16, 256, …), siguiendo una idea de “double-doubling”. Igual que en B1, al encontrar un intervalo que contiene a x se realiza una búsqueda binaria final. En ambos casos, B1 y B2 usan cmp.lt para contabilizar las comparaciones y permiten estudiar cómo cambia el rendimiento de los algoritmos de intersección al variar la estrategia de búsqueda.

def findpos_binaria(A, x, lo, cmp: CmpCounter):
    hi = len(A)
    while lo < hi:
        mid = (lo + hi) // 2
        if cmp.lt(A[mid], x):
            lo = mid + 1
        else:
            hi = mid
    return lo

def findpos_B1(A, x, lo, cmp: CmpCounter):
    n = len(A)
    if lo >= n:
        return n
    if not cmp.lt(A[lo], x):
        return lo
    bound = 1
    while lo + bound < n:
        if cmp.lt(A[lo + bound], x):
            bound *= 2
        else:
            break
    left = lo + bound // 2
    right = min(lo + bound, n)
    if left < lo:
        left = lo

    while left < right:
        mid = (left + right) // 2
        if cmp.lt(A[mid], x):
            left = mid + 1
        else:
            right = mid
    return left

def findpos_B2(A, x, lo, cmp: CmpCounter):
    n = len(A)
    if lo >= n:
        return n
    if not cmp.lt(A[lo], x):
        return lo
    step = 2
    prev = 0
    while True:
        idx = lo + step
        if idx >= n:
            left = lo + prev
            right = n
            break
        if cmp.lt(A[idx], x):
            prev = step
            step = step * step
        else:
            left = lo + prev
            right = idx
            break

    if left >= n:
        return n

    while left < right:
        mid = (left + right) // 2
        if cmp.lt(A[mid], x):
            left = mid + 1
        else:
            right = mid
    return left

Intersección de dos listas con el algoritmo de Baeza–Yates

La función by_intersection_2 implementa el algoritmo de Baeza–Yates para calcular la intersección de dos listas ordenadas A y B. La función recibe también un procedimiento de búsqueda findpos (puede ser binaria, B1 o B2) y el contador de comparaciones cmp. Los parámetros a_lo, a_hi, b_lo y b_hi delimitan los rangos activos de A y B, y permiten que el algoritmo se llame de forma recursiva sobre subsegmentos, siguiendo la idea presentada por Baeza-Yates en el contexto de recuperación de información (Baeza-Yates & Ribeiro-Neto, 2011; Sadit, s. f.-b).

La idea principal es de tipo divide y vencerás. En cada llamada se toma un elemento pivote median en la mitad del segmento de A. Luego se busca esa mediana en B mediante findpos. Si la posición encontrada queda fuera del rango activo de B, se continúa recursivamente solo en la parte izquierda de A, porque la intersección solo puede estar allí. Si se encuentra una coincidencia exacta (cmp.eq), primero se exploran recursivamente los subrangos de la izquierda, después se agrega la mediana a la salida y finalmente se procesan los subrangos de la derecha. Si no hay coincidencia, se dividen los rangos en izquierda y derecha sin agregar nada a la salida. De esta forma, by_intersection_2 construye recursivamente la intersección A ∩ B utilizando la rutina de búsqueda que se le pasa como parámetro.

def by_intersection_2(A, B, findpos, cmp: CmpCounter,
                      a_lo=0, a_hi=None, b_lo=0, b_hi=None, out=None):
    if a_hi is None:
        a_hi = len(A)
    if b_hi is None:
        b_hi = len(B)
    if out is None:
        out = []
    if a_lo >= a_hi or b_lo >= b_hi:
        return out
    mid = (a_lo + a_hi) // 2
    median = A[mid]
    pos = findpos(B, median, b_lo, cmp)
    if pos >= b_hi:
        return by_intersection_2(A, B, findpos, cmp,
                                 a_lo, mid, b_lo, b_hi, out)
    if cmp.eq(B[pos], median):
        by_intersection_2(A, B, findpos, cmp,
                          a_lo, mid, b_lo, pos, out)
        out.append(median)
        by_intersection_2(A, B, findpos, cmp,
                          mid + 1, a_hi, pos + 1, b_hi, out)
    else:
        by_intersection_2(A, B, findpos, cmp,
                          a_lo, mid, b_lo, pos, out)
        by_intersection_2(A, B, findpos, cmp,
                          mid + 1, a_hi, pos, b_hi, out)
    return out

Variantes de Baeza–Yates según la búsqueda utilizada

Estas funciones definen tres variantes del algoritmo de Baeza–Yates para la intersección de dos listas, según el tipo de búsqueda que se utilice internamente. La función BY_binaria llama a by_intersection_2 usando findpos_binaria, es decir, emplea búsqueda binaria clásica para localizar cada pivote en la segunda lista. La función BY_B1 hace lo mismo pero usando findpos_B1, que implementa una búsqueda no acotada con saltos crecientes antes de aplicar una búsqueda binaria final. Finalmente, BY_B2 utiliza findpos_B2, que realiza una búsqueda no acotada con saltos que crecen más rápidamente. Estas tres variantes permiten comparar el efecto de la estrategia de búsqueda sobre el comportamiento del algoritmo de Baeza–Yates.

def BY_binaria(A, B, cmp):
    return by_intersection_2(A, B, findpos_binaria, cmp)

def BY_B1(A, B, cmp):
    return by_intersection_2(A, B, findpos_B1, cmp)

def BY_B2(A, B, cmp):
    return by_intersection_2(A, B, findpos_B2, cmp)

Intersección de varias listas con Baeza–Yates

La función BY_multi extiende el algoritmo de Baeza–Yates al caso de k listas. Recibe una lista de listas lists, una función base_BY que calcula la intersección de dos listas (por ejemplo, BY_binaria, BY_B1 o BY_B2) y el contador de comparaciones cmp. El procedimiento toma la primera lista como resultado inicial y luego, de manera secuencial, la va intersectando con cada una de las listas restantes. Si en algún punto la intersección parcial queda vacía, el ciclo se detiene porque ya no puede aparecer ningún elemento en común.

A partir de esta función general se definen tres variantes específicas: BY_multi_binaria, que utiliza BY_binaria como base; BY_multi_B1, que utiliza BY_B1; y BY_multi_B2, que utiliza BY_B2. De este modo se obtiene la intersección de k listas usando Baeza–Yates parametrizado con búsqueda binaria, con B1 o con B2, lo que permite comparar estas tres opciones en los experimentos.

def BY_multi(lists, base_BY, cmp: CmpCounter):
    if not lists:
        return []
    res = lists[0]
    for nxt in lists[1:]:
        res = base_BY(res, nxt, cmp)
        if not res:
            break
    return res
def BY_multi_binaria(lists, cmp):
    return BY_multi(lists, BY_binaria, cmp)
def BY_multi_B1(lists, cmp):
    return BY_multi(lists, BY_B1, cmp)
def BY_multi_B2(lists, cmp):
    return BY_multi(lists, BY_B2, cmp)

Intersección Melding (ME) con estrategia small-vs-small

La función ME_melding implementa la estrategia Melding (small-vs-small) para la intersección de varias listas. Primero ordena las listas de entrada según su longitud, de menor a mayor. Luego toma la lista más pequeña como resultado inicial y la va intersectando, una por una, con las listas restantes mediante la función base_intersection, que calcula la intersección de dos listas. Si en algún punto la intersección parcial queda vacía, el ciclo se detiene porque ya no puede aparecer ningún elemento en común, siguiendo la idea de privilegiar las listas más cortas discutida en el contexto de intersección adaptativa (Barbay & Kenyon, 2002; Barbay, López-Ortiz, & Lu, 2006; Sadit, s. f.-b).

La función ME_BY_binaria es una instancia concreta de este esquema, donde la intersección de dos listas se realiza con BY_binaria. De esta forma, ME utiliza Baeza–Yates con búsqueda binaria como rutina base, pero mantiene la idea central de intersectar primero las listas más pequeñas para reducir el tamaño de los resultados intermedios.

def ME_melding(lists, base_intersection, cmp: CmpCounter):
    if not lists:
        return []
    work = sorted(lists, key=len)
    curr = work[0]
    for nxt in work[1:]:
        curr = base_intersection(curr, nxt, cmp)
        if not curr:
            break
    return curr
def ME_BY_binaria(lists, cmp):
    return ME_melding(lists, BY_binaria, cmp)

Intersección de varias listas con el algoritmo de Barbay y Kenyon (BK)

La función BK_intersection implementa el algoritmo de Barbay y Kenyon para calcular la intersección de k listas ordenadas. En primer lugar se revisa si alguna lista está vacía; en ese caso, la intersección es vacía. También se consideran los casos triviales de cero listas (devuelve una lista vacía) y de una sola lista (devuelve una copia de esa lista). Para el caso general, se inicializa un arreglo de punteros P, uno por cada lista, y se toma como candidato inicial el el primer elemento de la primera lista.

Dentro del ciclo principal, el algoritmo intenta “alinear” el candidato el en todas las listas. Para cada lista i, se busca la posición adecuada mediante findpos, empezando desde el puntero actual P[i]. Si la posición queda fuera de la lista, se termina y se devuelve la intersección acumulada. En caso contrario, se actualiza P[i] y se compara el valor encontrado con el candidato. Si todas las listas coinciden en el mismo valor, se agrega ese elemento a la salida y se avanza el puntero de la primera lista para buscar el siguiente candidato. Si alguna lista tiene un valor mayor, se actualiza el a ese nuevo valor y se reinicia el conteo de coincidencias. De esta forma, BK recorre las listas de manera coordinada, usando findpos para avanzar, y construye la intersección paso a paso. La función BK_binaria fija que las búsquedas internas se hagan con findpos_binaria, es decir, con búsqueda binaria sobre cada lista.

def BK_intersection(lists, findpos, cmp: CmpCounter):
    if any(len(lst) == 0 for lst in lists):
        return []
    L = lists
    k = len(L)
    if k == 0:
        return []
    if k == 1:
        return L[0][:]
    P = [0] * k
    out = []
    el = L[0][0]
    while True:
        c = 0
        for i in range(k):
            pos = findpos(L[i], el, P[i], cmp)
            if pos >= len(L[i]):
                return out
            P[i] = pos
            val = L[i][pos]
            if cmp.eq(val, el):
                c += 1
            else:
                el = val
                c = 1
        if c == k:
            out.append(el)
            P[0] += 1
            if P[0] >= len(L[0]):
                return out
            el = L[0][P[0]]
def BK_binaria(lists, cmp):
    return BK_intersection(lists, findpos_binaria, cmp)

Ejecución de un experimento

La función correr_experimento ejecuta varias veces el mismo algoritmo de intersección sobre un grupo de listas y registra las métricas obtenidas. En cada repetición se crea un nuevo contador CmpCounter, se llama a algofn usando medir_tiempo para obtener la intersección y el tiempo de ejecución, y se guarda una fila con la familia, el identificador de grupo, el número de listas k, el nombre del algoritmo, el índice de repetición, el tiempo en segundos, el número de comparaciones y la longitud de la intersección. Al final, todas las repeticiones se devuelven como un DataFrame de pandas.

En este caso se utiliza reps = 100 para cada combinación de familia, grupo y algoritmo. Hacer muchas repeticiones ayuda a reducir el efecto del ruido en la medición del tiempo (variaciones del sistema, carga de la máquina, etc.) y permite estimar de manera más estable los tiempos promedio y la variabilidad de cada algoritmo. Así, los resultados que se analizan en las tablas y gráficas son más confiables y menos sensibles a una sola ejecución “atípica”.

def correr_experimento(familia, grupo_id, listas, algoname, algofn, reps=100):
    filas = []
    for r in range(reps):
        cmp = CmpCounter()
        inter, dt = medir_tiempo(algofn, listas, cmp)
        filas.append({
            "familia": familia,
            "grupo": grupo_id,
            "k": len(listas),
            "algoritmo": algoname,
            "rep": r,
            "tiempo_s": dt,
            "comparaciones": cmp.count,
            "len_inter": len(inter),
        })
    return pd.DataFrame(filas)

Definición de los algoritmos a comparar

El diccionario ALGORITMOS_5 reúne los cinco algoritmos de intersección que se van a comparar en los experimentos. Cada clave es una etiqueta de texto que identifica al algoritmo en las tablas y gráficos, y cada valor es una función anónima (lambda) que recibe la lista de listas L y el contador de comparaciones cmp, y devuelve la intersección correspondiente.

En particular, la entrada "ME" llama a ME_BY_binaria, que implementa la estrategia Melding usando Baeza–Yates con búsqueda binaria como rutina base. La entrada "BK" utiliza BK_binaria, que corresponde al algoritmo de Barbay y Kenyon con búsqueda binaria interna. Las otras tres entradas ("BY_binaria", "BY_B1" y "BY_B2") invocan a BY_multi_binaria, BY_multi_B1 y BY_multi_B2, es decir, Baeza–Yates para k listas parametrizado con búsqueda binaria, con B1 y con B2. De esta forma, el diccionario concentra exactamente los algoritmos solicitados en la unidad: ME, BK y las tres variantes de BY según la estrategia de búsqueda.

ALGORITMOS_5 = {
    "ME":          lambda L, cmp: ME_BY_binaria(L, cmp),
    "BK":          lambda L, cmp: BK_binaria(L, cmp),
    "BY_binaria":  lambda L, cmp: BY_multi_binaria(L, cmp),
    "BY_B1":       lambda L, cmp: BY_multi_B1(L, cmp),
    "BY_B2":       lambda L, cmp: BY_multi_B2(L, cmp),}

Bucle principal de experimentos y construcción del DataFrame global

La función correr_todos ejecuta el experimento completo sobre las tres familias de datos. Recorre en orden las familias A, B y C, y para cada una itera sobre todos sus grupos mediante enumerate, obteniendo el identificador de grupo (gid) y las listas asociadas. Para cada grupo, aplica todos los algoritmos definidos en ALGORITMOS_5, llamando a correr_experimento con la familia, el grupo, las listas, el nombre del algoritmo y el número de repeticiones reps (en este caso, 100). Cada llamada devuelve un DataFrame con las repeticiones de esa combinación, que se acumula en la lista dfs. Al final, todos estos resultados se concatenan con pd.concat para formar un solo DataFrame global (df_res), que contiene la información de todas las familias, grupos, algoritmos y repeticiones y sirve como base para los resúmenes y los gráficos de comparación.

def correr_todos(A, B, C, reps=100):
    dfs = []
    for familia, F in [("A", A), ("B", B), ("C", C)]:
        for gid, listas in enumerate(F):
            for algoname, algofn in ALGORITMOS_5.items():
                dfs.append(
                    correr_experimento(familia, gid, listas,
                                       algoname, algofn, reps))
    return pd.concat(dfs, ignore_index=True)
df_res = correr_todos(A, B, C, reps=100)

La instrucción df_res.head(5) muestra las primeras 5 filas del DataFrame df_res. Esta vista preliminar se utiliza como una verificación rápida de que los resultados se están registrando correctamente.

df_res.head(5)

	familia	grupo	k	algoritmo	rep	tiempo_s	comparaciones	len_inter
0	A	0	2	ME	0	0.000715	1564	2
1	A	0	2	ME	1	0.002145	1564	2
2	A	0	2	ME	2	0.000540	1564	2
3	A	0	2	ME	3	0.001504	1564	2
4	A	0	2	ME	4	0.000523	1564	2

Tabla resumen por familia y algoritmo

Para sintetizar los resultados se agrupa el DataFrame df_res por familia y algoritmo, y se calculan estadísticas agregadas con groupby(["familia", "algoritmo"]).agg(...). Para cada combinación se obtiene el número de observaciones (n_obs), el tiempo medio y su desviación estándar (tiempo_medio, tiempo_std), el número medio de comparaciones (comps_medias) y la longitud media de la intersección (inter_medias). Tras aplicar reset_index(), se obtiene una tabla compacta que resume el comportamiento de cada algoritmo en cada familia.

En la tabla se observa que n_obs es 20 000 en todos los casos, lo que corresponde a 200 grupos por familia y 100 repeticiones por combinación. La columna inter_medias es constante para todos los algoritmos dentro de cada familia, lo que indica que todos producen intersecciones del mismo tamaño; por lo tanto, las diferencias entre algoritmos se centran en el tiempo de ejecución y en el número de comparaciones.

En las tres familias (A, B y C) se repite el mismo patrón: ME es sistemáticamente el algoritmo más eficiente, con los menores tiempos medios y el menor número de comparaciones. BK aparece como una opción intermedia, más costosa que ME pero claramente mejor que las variantes de Baeza–Yates. Las tres versiones de BY (con búsqueda binaria, B1 y B2) son las más lentas y las que más comparan; B1 y B2 mejoran a BY_binaria, pero aun así quedan por debajo de ME y BK. En conjunto, la tabla respalda que ME domina a las demás alternativas, mientras que BK ofrece un compromiso razonable y BY resulta menos eficiente aunque produzca las mismas intersecciones.

resumen = (df_res
    .groupby(["familia", "algoritmo"])
    .agg(
        n_obs=("tiempo_s", "count"),
        tiempo_medio=("tiempo_s", "mean"),
        tiempo_std=("tiempo_s", "std"),
        comps_medias=("comparaciones", "mean"),
        inter_medias=("len_inter", "mean"),)
    .reset_index())
resumen["tiempo_medio"] = resumen["tiempo_medio"].round(6)
resumen["tiempo_std"]   = resumen["tiempo_std"].round(6)
resumen["comps_medias"] = resumen["comps_medias"].round(1)
resumen["inter_medias"] = resumen["inter_medias"].round(2)
resumen

	familia	algoritmo	n_obs	tiempo_medio	tiempo_std	comps_medias	inter_medias
0	A	BK	20000	0.000396	0.000205	1986.3	18.14
1	A	BY_B1	20000	0.000386	0.000208	1547.2	18.14
2	A	BY_B2	20000	0.000343	0.000154	1553.1	18.14
3	A	BY_binaria	20000	0.000448	0.000286	2275.3	18.14
4	A	ME	20000	0.000257	0.000119	1209.6	18.14
5	B	BK	20000	0.001083	0.000572	5545.3	23.62
6	B	BY_B1	20000	0.002498	0.004175	9633.2	23.62
7	B	BY_B2	20000	0.002269	0.004067	9636.0	23.62
8	B	BY_binaria	20000	0.004138	0.010280	20825.4	23.62
9	B	ME	20000	0.000561	0.000326	2636.3	23.62
10	C	BK	20000	0.000559	0.000219	2879.0	7.75
11	C	BY_B1	20000	0.001049	0.001311	4372.3	7.75
12	C	BY_B2	20000	0.000953	0.001201	4298.8	7.75
13	C	BY_binaria	20000	0.001491	0.003193	7349.9	7.75
14	C	ME	20000	0.000299	0.000125	1494.5	7.75

En la familia A se observan dos patrones muy claros.

En el gráfico de la izquierda (tiempo), todas las cajas están en el orden de milisegundos, pero ME es el que concentra sus tiempos más cerca de cero: su caja es la más pegada al eje y bastante compacta. BK, BY_B1, BY_B2 y sobre todo BY_binaria muestran cajas más desplazadas hacia la derecha y con colas más largas, lo que indica ejecuciones más lentas y con mayor variabilidad. Visualmente, ME es el más rápido, BY_binaria el más lento, y los demás quedan en un nivel intermedio.

En el gráfico de la derecha (comparaciones) se ve el mismo orden pero de forma aún más clara. La caja de ME está más a la izquierda, indicando que es el algoritmo que necesita menos comparaciones en promedio. Le siguen BY_B1 y BY_B2, luego BK, y finalmente BY_binaria muy desplazado a la derecha, con una cola larga de casos donde hace muchas comparaciones. Esto confirma que, para pares de listas (familia A), ME es el algoritmo más eficiente tanto en tiempo como en número de comparaciones, mientras que BY_binaria es la alternativa más costosa.

# Filtrar solo la familia A
df_A = df_res[df_res["familia"] == "A"]
metricas = [("tiempo_s",      "segundos",               "Tiempo de intersección"),
    ("comparaciones", "número de comparaciones","Comparaciones de intersección"),]
fig, axes = plt.subplots(1, 2, figsize=(12, 4))
for j, (col, xlabel, titulo_base) in enumerate(metricas):
    ax = axes[j]
    df_A.boxplot(
        column=col,
        by="algoritmo",
        vert=False,
        ax=ax,)
    ax.set_title(f"{titulo_base} - Familia A", fontsize=10)
    ax.set_xlabel(xlabel)
    ax.set_ylabel("algoritmo" if j == 0 else "")
plt.suptitle("")
plt.tight_layout()
plt.show()

En la familia B las listas son tripletas y las diferencias entre algoritmos se amplifican respecto al caso A.

En el gráfico de tiempo (izquierda) se observa que ME y BK tienen las cajas más pegadas al eje, con tiempos muy pequeños y bastante concentrados. BK es algo más lento que ME, pero ambos se mantienen en el mismo orden de magnitud. En cambio, las variantes de BY se desplazan claramente hacia la derecha: BY_B1 y BY_B2 muestran tiempos medios mayores y una dispersión más amplia, y BY_binaria es la peor de todas, con cajas muy extendidas y varios valores atípicos muy alejados (ejecuciones mucho más lentas).

El gráfico de comparaciones (derecha) confirma esta lectura. ME y BK se encuentran cerca del origen, con pocas comparaciones en promedio. Las cajas de BY_B1 y BY_B2 aparecen bastante más a la derecha, indicando que requieren muchas más comparaciones para producir la misma intersección. BY_binaria vuelve a ser la opción más costosa, con una caja muy desplazada y valores atípicos extremos que superan con mucho a los demás algoritmos. En resumen, para tripletas de listas, ME es el algoritmo más eficiente, BK ofrece un rendimiento intermedio aceptable y las variantes de BY, en especial BY_binaria, resultan significativamente más pesadas en tiempo y comparaciones.

df_B = df_res[df_res["familia"] == "B"]
metricas = [("tiempo_s",      "segundos",               "Tiempo de intersección"),
    ("comparaciones", "número de comparaciones","Comparaciones de intersección"),]
fig, axes = plt.subplots(1, 2, figsize=(12, 4))
for j, (col, xlabel, titulo_base) in enumerate(metricas):
    ax = axes[j]
    df_B.boxplot(
        column=col,
        by="algoritmo",
        vert=False,
        ax=ax,    )
    ax.set_title(f"{titulo_base} - Familia B", fontsize=10)
    ax.set_xlabel(xlabel)
    ax.set_ylabel("algoritmo" if j == 0 else "")
plt.suptitle("")
plt.tight_layout()
plt.show()

En la familia C se intersectan tetrapletas de listas y el patrón observado es muy parecido al de las familias A y B. En el gráfico de tiempo (izquierda), la caja de ME es la más cercana al eje y la más compacta, lo que indica que sigue siendo el algoritmo más rápido. BK aparece un poco más desplazado a la derecha, con tiempos algo mayores pero aún pequeños. Las variantes de BY (BY_B1, BY_B2 y especialmente BY_binaria) muestran cajas claramente más alejadas y con muchos valores atípicos, reflejando ejecuciones más lentas y variables.

En el gráfico de comparaciones (derecha) se repite el mismo orden. ME requiere el menor número de comparaciones en promedio, seguido por BK. Las versiones BY_B1 y BY_B2 usan muchas más comparaciones y BY_binaria es, de nuevo, la más costosa, con una caja muy desplazada y algunos valores extremadamente altos. En conjunto, estos resultados confirman que, aun cuando se intersectan cuatro listas, ME sigue siendo el algoritmo más eficiente, BK ofrece un rendimiento intermedio razonable y las variantes de Baeza–Yates resultan claramente menos eficientes en términos de tiempo y comparaciones.

df_C = df_res[df_res["familia"] == "C"]
metricas = [("tiempo_s",      "segundos",               "Tiempo de intersección"),
    ("comparaciones", "número de comparaciones","Comparaciones de intersección"),]
fig, axes = plt.subplots(1, 2, figsize=(12, 4))
for j, (col, xlabel, titulo_base) in enumerate(metricas):
    ax = axes[j]
    df_C.boxplot(
        column=col,
        by="algoritmo",
        vert=False,
        ax=ax,    )
    ax.set_title(f"{titulo_base} - Familia C", fontsize=10)
    ax.set_xlabel(xlabel)
    ax.set_ylabel("algoritmo" if j == 0 else "")
plt.suptitle("")
plt.tight_layout()
plt.show()

Conclusiones

En este trabajo se compararon cinco algoritmos de intersección (ME, BK y tres variantes de Baeza–Yates con búsqueda binaria, B1 y B2) sobre tres familias de listas (A, B y C). Para cada combinación se realizaron 100 repeticiones y se midieron tiempo de ejecución y número de comparaciones en el modelo de comparación.

Los resultados son consistentes en todas las familias: ME, basado en la estrategia small-vs-small, es siempre el algoritmo más eficiente, con los menores tiempos medios y el menor número de comparaciones. BK aparece como una alternativa intermedia razonable, mientras que las variantes de Baeza–Yates son claramente más costosas; BY_binaria es la peor, y B1/B2 mejoran su comportamiento pero sin alcanzar a ME ni a BK.

Finalmente, el tamaño de la intersección fue el mismo para todos los algoritmos dentro de cada familia, por lo que las diferencias observadas se deben únicamente a la forma en que cada método organiza las búsquedas y las comparaciones. En este escenario, ME se perfila como la opción preferente para intersectar listas tipo posting lists, con BK como segunda opción y las variantes de BY principalmente como referencia para estudiar el efecto de distintas estrategias de búsqueda.

Referencias

Baeza-Yates, R., & Ribeiro-Neto, B. (2011). Modern Information Retrieval: The Concepts and Technology behind Search (2nd ed.). Addison-Wesley.

Barbay, J., & Kenyon, C. (2002). Adaptive intersection and t-threshold problems. En Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 390–399).

Barbay, J., López-Ortiz, A., & Lu, T. (2006, May). Faster adaptive set intersections for text searching. En R. Fleischer & J. Xu (Eds.), International Workshop on Experimental and Efficient Algorithms (pp. 146–157). Springer.

Sadit. (s. f.-a). 5. Algoritmos de búsqueda en el modelo de comparación. En Curso introductorio al análisis de algoritmos con Julia. Recuperado de https://sadit.github.io/ALGO-IR/cap5-busqueda.html

Sadit. (s. f.-b). 6. Algoritmos de intersección y unión de conjuntos en el modelo de comparación. En Curso introductorio al análisis de algoritmos con Julia. Recuperado de https://sadit.github.io/ALGO-IR/cap6-intersecciones.html