9/10/24, 11:52 p.m.

Mario_Rodriguez_tarea_6

Reporte de unidad 6
Alumno: Mario Rodríguez Félix

Introducción
El problema de encontrar intersecciones de conjuntos es muy importante en múltiples
áreas de la informática, como por ejemplo, en problemas relacionados con la eficiencia
de los motores de búsqueda y bases de datos. El ser capaz de identificar de manera
eficiente elementos comunes entre distintas estructuras de datos es un requisito
fundamental para procesar de manera óptima consultas de sistemas que manejan
grandes volúmenes de datos. Dada la importancia de este tema, se han realizado
diversos estudios en los que se proponen nuevos algoritmos que buscan mejorar el
rendimiento de las operaciones de intersección, tanto en términos de CPU como el
número de comparaciones realizadas.
En este trabajo se analizan algunos de los algoritmos de intersección más utilizados y se
hace una comparación de su rendimeinto en términos de cantidad de comparaciones y
de tiempo necesario para encontrar las intersecciones. Para este fin se usan conjuntos
de duplas, tripletas y tetrapletas de listas que contienen índices invertidos.

Código y
realizadosanálisis de los experimentos
In [1]: import json
import numpy as np
import random
import time
import copy
import matplotlib.pyplot as plt
import seaborn as sns
import pandas as pd

# Se establece una semilla para los numeros aleatorios

random.seed(123)

In [2]: archivo_json = "./listas-posteo-100.json"

with open(archivo_json, "r") as f:

listas_posteo = json.load(f)

len(listas_posteo)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 1/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

Out[2]: 100

Se genera el conjunto A (duplas)

In [3]: # Se toman las llaves con las que se identifican las listas de posteo
llaves_listas_posteo = []
for key in listas_posteo.keys():
llaves_listas_posteo.append(key)

# Se generan una lista con todos los posibles pares de llaves

# sin que haya dos llaves iguales en un par
P2 = []
for i in llaves_listas_posteo:
for j in llaves_listas_posteo:
if i != j:
P2.append((i, j))

# Se genera una lista que contiene 1000 índices elegidos al azar

# de la lista de los pares de llaves.
P2_rand_elements = []
while len(P2_rand_elements) < 1000:
rand_num = random.randint(1, len(P2)-1)
if rand_num not in P2_rand_elements:
P2_rand_elements.append(rand_num)

# Se usan los mil índices generados al azar, para crear una lista
# que contiene los pares de listas asociadas a cada par de llaves
A = []
for rand_element in P2_rand_elements:
A.append(
[
listas_posteo.get((P2[rand_element][0])),
listas_posteo.get((P2[rand_element][1])),
]
)

Se genera el conjunto B (tripletas)

In [4]: # Se Toma P3 que contiene todos los posibles pares de llaves y se usa
# para generar P3, que contien todas las posibles combinaciones de tres list
P3 = []
for i in P2:
for j in llaves_listas_posteo:
if i[0] != j and i[1] != j:
P3.append((i[0], i[1], j))

# Se genera una lista que contiene 1000 índices elegidos al azar

# de la lista de los pares de llaves.
P3_rand_elements = []
while len(P3_rand_elements) < 1000:
rand_num = random.randint(1, len(P3))
if rand_num not in P3_rand_elements:
P3_rand_elements.append(rand_num)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 2/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

# Se usan los mil índices generados al azar, para crear una lista
# que contiene los pares de listas asociadas a cada par de llaves
B = []
for rand_element in P3_rand_elements:
B.append(
[
listas_posteo.get((P3[rand_element][0])),
listas_posteo.get((P3[rand_element][1])),
listas_posteo.get((P3[rand_element][2]))
]
)

Se genera el conjunto C (tetrapletas)

In [5]: # Se Toma P3 que contiene todos los posibles pares de llaves y se usa
# para generar P3, que contien todas las posibles combinaciones de tres list
P4 = []
for i in P3:
for j in llaves_listas_posteo:
if i[0] != j and i[1] != j and i[2] != j:
P4.append((i[0], i[1], i[2], j))

# Se genera una lista que contiene 1000 índices elegidos al azar

# de la lista de los pares de llaves.
P4_rand_elements = []
while len(P4_rand_elements) < 1000:
rand_num = random.randint(1, len(P4))
if rand_num not in P4_rand_elements:
P4_rand_elements.append(rand_num)

# Se usan los mil índices generados al azar, para crear una lista
# que contiene los pares de listas asociadas a cada par de llaves
C = []
for rand_element in P4_rand_elements:
C.append(
[
listas_posteo.get((P4[rand_element][0])),
listas_posteo.get((P4[rand_element][1])),
listas_posteo.get((P4[rand_element][2])),
listas_posteo.get((P4[rand_element][3]))
]
)

In [6]: print(
f"El conjunto A contiene {len(A)} listas con {len(A[0])} listas dentro d
)
print(
f"El conjunto A contiene {len(B)} listas con {len(B[0])} listas dentro d
)
print(
f"El conjunto A contiene {len(C)} listas con {len(C[0])} listas dentro d
)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 3/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

El conjunto A contiene 1000 listas con 2 listas dentro de cada una

El conjunto A contiene 1000 listas con 3 listas dentro de cada una
El conjunto A contiene 1000 listas con 4 listas dentro de cada una

Algoritmos de búsqueda
Se usarán dos tipos de algoritmos de búsqueda para realizar las comparaciones de los
rendimientos de los algoritmos de intersección. Para este trabajo se usarán una serie de
algoritmos de intersección, y cada uno será implementado con dos versiones distintas,
es decir, con dos algoritmos de búsqueda distintos esperando variar así su rendimiento.
Los algoritmos de búsqueda que se utilizarán será el de búsqueda binaria total y
búsqueda galopante, el primero es el clásico algoritmo de búsqueda que va
segmentando a la mitad el rango de búsqueda hasta que encuentra su valor objetivo,
mientras el segundo se trata de la búsqueda binaria no acotada, la cual empieza dando
saltos exponenciales hasta que encuentra un intervalo en dentro del cual se encuentra el
valor objetivo, y a partir de la definición de este rango, se realiza una búsqueda binaria
convencional.
In [7]: def total_binary_search(arr, target, low, high):
comparisons = 0
left = low
right = high
while left <= right:
mid = (left + right) // 2
comparisons += 1
if arr[mid] == target:
return True, mid, comparisons
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False, left, comparisons

def galloping_search(arr, target, low, high):

comparisons = 0
if low > high:
return False, low, comparisons
# Primera comparación
comparisons += 1
if arr[low] == target:
return True, low, comparisons
elif arr[low] > target:
return False, low, comparisons

# Exponencialmente buscamos un rango donde pueda estar el target

index = 1
while low + index <= high and arr[low + index] <= target:
comparisons += 1
if arr[low + index] == target:
return True, low + index, comparisons

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 4/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

index *= 2
# Realizamos búsqueda binaria en el rango encontrado
new_low = low + index // 2 + 1
new_high = min(low + index - 1, high)
found, indexB, comps = total_binary_search(arr, target, new_low, new_hig
comparisons += comps
return found, indexB, comparisons

Algoritmos Melding
SvS
El algoritmo SvS (Set versus Set) es un enfoque común para la intersección de conjuntos
ordenados, donde se intersectan los conjuntos de dos en dos, comenzando por los más
pequeños. Primero, se ordenan los conjuntos por tamaño. Luego, se toma el conjunto
más pequeño como el conjunto candidato para la intersección. Para cada elemento de
este conjunto candidato, se busca su presencia en los otros conjuntos utilizando
búsquedas binarias o variantes de búsqueda. Si el elemento se encuentra en todos los
conjuntos, permanece en el conjunto candidato; de lo contrario, se elimina. Este proceso
se repite hasta que se han examinado todos los elementos, obteniendo el conjunto de
intersección
In [8]: def svs(lists, search_algorithm):
total_comparisons = {"count": 0}
lists = [sorted(lst) for lst in lists]
lists.sort(key=len)
result = lists[0]
for i in range(1, len(lists)):
current_list = lists[i]
new_result = []
if len(result) > len(current_list):
result, current_list = current_list, result
for element in result:
found, indexB, comparisons = search_algorithm(
current_list, element, 0, len(current_list) - 1
)
total_comparisons["count"] += comparisons
if found:
new_result.append(element)
result = new_result
if not result:
break
return result, total_comparisons["count"]

Small adaptive
El algoritmo Small Adaptive es un híbrido que combina las características del algoritmo
SvS y el algoritmo Adaptive. Su enfoque es seleccionar el elemento del conjunto más
pequeño (eliminador) y luego buscar ese elemento en los otros conjuntos utilizando una
file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 5/29
9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

búsqueda galopante (galloping search). Si el eliminador se encuentra en todos los

conjuntos, se agrega al conjunto de intersección. El algoritmo sigue avanzando de
izquierda a derecha en los conjuntos, ordenándolos de nuevo en cada paso por el
tamaño de los elementos que quedan sin examinar, repitiendo el proceso hasta que uno
de los conjuntos queda vacío.
In [ ]: def small_adaptive(lists, search_algorithm):
total_comparisons = {"count": 0}
lists = [sorted(lst) for lst in lists]
lists.sort(key=len)
result = lists[0]
for i in range(1, len(lists)):
current_list = lists[i]
new_result = []
for element in result:
found, indexB, comparisons = search_algorithm(
current_list, element, 0, len(current_list) - 1
)
total_comparisons["count"] += comparisons
if found:
new_result.append(element)
result = new_result
if not result:
break
return result, total_comparisons["count"]

Sequential
El algoritmo Sequential es un enfoque para la intersección de conjuntos que se basa en
la selección de un "eliminador", es decir, un elemento del primer conjunto, y luego
realiza búsquedas secuenciales en los otros conjuntos para determinar si dicho
elemento está presente en todos ellos. Si el elemento se encuentra en todos los
conjuntos, se añade al conjunto de intersección. En cada paso, el algoritmo avanza en
los conjuntos de forma cíclica, repitiendo el proceso hasta que todos los conjuntos han
sido explorados. Aunque es eficiente en ciertos contextos, su rendimiento puede ser
inferior en casos donde los elementos buscados están distribuidos uniformemente en
los conjuntos.
In [ ]: def sequential(lists, search_algorithm):
total_comparisons = {"count": 0}
lists = [sorted(lst) for lst in lists]

# Ordenamos las listas por tamaño para optimizar el proceso

lists.sort(key=len)

# Inicializamos el resultado con la primera lista

result = lists[0]

# Iteramos sobre las demás listas

for i in range(1, len(lists)):

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 6/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

current_list = lists[i]
new_result = []

# Recorremos result y buscamos cada elemento en current_list usando

for element in result:
found, indexB, comparisons = search_algorithm(
current_list, element, 0, len(current_list) - 1
)
total_comparisons["count"] += comparisons
if found:
new_result.append(element)

result = new_result

# Salida temprana si el resultado está vacío

if not result:
break

return result, total_comparisons["count"]

Baeza-Yates
El algoritmo de Baeza-Yates es un enfoque para la intersección de dos listas ordenadas.
Su estrategia principal es seleccionar el elemento medio de la lista más pequeña y
buscarlo en la lista más grande utilizando una búsqueda binaria. Si el elemento se
encuentra en ambas listas, se añade al conjunto de intersección. Luego, el problema se
divide recursivamente en dos subproblemas, dividiendo las listas en partes menores
basadas en la posición del elemento medio. Para manejar más de dos listas, el algoritmo
intersecta las listas de dos en dos, comenzando por las más pequeñas.
In [ ]: def baeza_yates(lists, search_algorithm):
# Inicializamos el contador de comparaciones
total_comparisons = {"count": 0}

# Convertimos las listas a listas ordenadas y las ordenamos por tamaño

lists = [sorted(lst) for lst in lists]
lists.sort(key=lambda s: len(s))

# El conjunto candidato es el más pequeño

candidate = lists[0]

# Iteramos sobre las demás listas

for i in range(1, len(lists)):
current_list = lists[i]
candidate = by_intersect(
candidate,
current_list,
0,
len(candidate) - 1,
0,
len(current_list) - 1,
search_algorithm,
total_comparisons

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 7/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

# Si el candidato se vuelve vacío, no hay intersección

if not candidate:
return [], total_comparisons["count"]

return candidate, total_comparisons["count"]

def by_intersect(
listA,
listB,
minA,
maxA,
minB,
maxB,
search_algorithm,
total_comparisons,
):
# Caso base: si los índices son inválidos
if minA > maxA or minB > maxB:
return []

# Calculamos el punto medio y obtenemos el elemento mediano de listA

m = (minA + maxA) // 2
medianA = listA[m]

found, indexB, comparisons = search_algorithm(listB, medianA, minB, maxB

total_comparisons["count"] += comparisons
result = []

if found:
# Si medianA se encuentra en listB, lo agregamos al resultado
result.append(medianA)
# Realizamos llamadas recursivas en ambos lados
result.extend(
by_intersect(
listA,
listB,
minA,
m - 1,
minB,
indexB - 1,
search_algorithm,
total_comparisons
)
)
result.extend(
by_intersect(
listA,
listB,
m + 1,
maxA,
indexB + 1,
maxB,

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 8/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

search_algorithm,
total_comparisons
)
)
else:
# Si no se encuentra, indexB es el punto de inserción
result.extend(
by_intersect(
listA,
listB,
minA,
m - 1,
minB,
indexB - 1,
search_algorithm,
total_comparisons
)
)
result.extend(
by_intersect(
listA,
listB,
m + 1,
maxA,
indexB,
maxB,
search_algorithm,
total_comparisons,
)
)

return result

Se generan las métricas de comparación entre algoritmos

In [ ]: # Se crea una función que toma como argumentos un algoritmo melding,
# uno de búsqueda y uno de los conjuntos de listas A, B o C.
# y regresa los tiempos en los que se encuentran las intersecciones
# la cantidad de comparaciones que se realizan y el largo de las
# interseciones encontradas.
def experiment_metrics(algorithm, search_algorithm, sets):
total_times = []
total_comparisons = []
total_lenghts = []
for i in sets:
start = time.time()
intersection, comparisons = algorithm(i, search_algorithm)
final = time.time()
total_time = final - start

total_times.append(total_time)
total_comparisons.append(comparisons)
total_lenghts.append(len(intersection))

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 9/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

return total_times, total_comparisons, total_lenghts

Se calculan las métricas para el algoritmo SvS-binarySearch

In [10]: svs_binary_A_total_times, svs_binary_A_total_comparisons, svs_binary_A_total
experiment_metrics(svs, total_binary_search, A)
)

svs_binary_B_total_times, svs_binary_B_total_comparisons, svs_binary_B_total

experiment_metrics(svs, total_binary_search, B)
)

svs_binary_C_total_times, svs_binary_C_total_comparisons, svs_binary_C_total

experiment_metrics(svs, total_binary_search, C)
)

Se calculan las métricas para el algoritmo SvS-galloping

In [11]: svs_galloping_A_total_times, svs_galloping_A_total_comparisons, svs_gallopin
experiment_metrics(svs, galloping_search, A)
)

svs_galloping_B_total_times, svs_galloping_B_total_comparisons, svs_gallopin

experiment_metrics(svs, galloping_search, B)
)

svs_galloping_C_total_times, svs_galloping_C_total_comparisons, svs_gallopin

experiment_metrics(svs, galloping_search, C)
)

Se calculan las métricas para el algoritmo SmallAdaptive-

BinarySearching
In [12]: small_adaptive_binary_A_total_times, small_adaptive_binary_A_total_compariso
experiment_metrics(small_adaptive, total_binary_search, A)
)

small_adaptive_binary_B_total_times, small_adaptive_binary_B_total_compariso
experiment_metrics(small_adaptive, total_binary_search, B)
)

small_adaptive_binary_C_total_times, small_adaptive_binary_C_total_compariso
experiment_metrics(small_adaptive, total_binary_search, C)
)

Se calculan
Galloping las métricas para el algoritmo SmallAdaptive-
In [13]: small_adaptive_galloping_A_total_times, small_adaptive_galloping_A_total_com
experiment_metrics(small_adaptive, galloping_search, A)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 10/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

small_adaptive_galloping_B_total_times, small_adaptive_galloping_B_total_com
experiment_metrics(small_adaptive, galloping_search, B)
)

small_adaptive_galloping_C_total_times, small_adaptive_galloping_C_total_com
experiment_metrics(small_adaptive, galloping_search, C)
)

Se calculan las métricas para el algoritmo Sequential-

BinarySearching
In [14]: sequential_binary_A_total_times, sequential_binary_A_total_comparisons, sequ
experiment_metrics(sequential, total_binary_search, A)
)

sequential_binary_B_total_times, sequential_binary_B_total_comparisons, sequ

experiment_metrics(sequential, total_binary_search, B)
)

sequential_binary_C_total_times, sequential_binary_C_total_comparisons, sequ

experiment_metrics(sequential, total_binary_search, C)
)

Se calculan las métricas para el algoritmo Sequential-Galloping

In [15]: sequential_galloping_A_total_times, sequential_galloping_A_total_comparisons
experiment_metrics(sequential, galloping_search, A)
)

sequential_galloping_B_total_times, sequential_galloping_B_total_comparisons
experiment_metrics(sequential, galloping_search, B)
)

sequential_galloping_C_total_times, sequential_galloping_C_total_comparisons
experiment_metrics(sequential, galloping_search, C)
)

Se calculan las métricas para el algoritmo BaezaYates-

BinarySearching
In [16]: baeza_yates_binary_A_total_times, baeza_yates_binary_A_total_comparisons, ba
experiment_metrics(baeza_yates, total_binary_search, A)
)

baeza_yates_binary_B_total_times, baeza_yates_binary_B_total_comparisons, ba
experiment_metrics(baeza_yates, total_binary_search, B)
)

baeza_yates_binary_C_total_times, baeza_yates_binary_C_total_comparisons, ba

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 11/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

experiment_metrics(baeza_yates, total_binary_search, C)
)

Se calculan
Galloping las métricas para el algoritmo BaezaYates-
In [17]: baeza_yates_galloping_A_total_times, baeza_yates_galloping_A_total_compariso
experiment_metrics(baeza_yates, galloping_search, A)
)

baeza_yates_galloping_B_total_times, baeza_yates_galloping_B_total_compariso
experiment_metrics(baeza_yates, galloping_search, B)
)

baeza_yates_galloping_C_total_times, baeza_yates_galloping_C_total_compariso
experiment_metrics(baeza_yates, galloping_search, C)
)

Se grafican los resultados

In [91]: # ------------------------------ SvS Binary --------------------------------
df1 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": svs_binary_A_total_times,
}
)
df2 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": svs_binary_B_total_times,
}
)

df3 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": svs_binary_C_total_times,
}
)

# ------------------------------ SvS Galloping -----------------------------

df4 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": svs_galloping_A_total_times,
}
)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 12/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

df5 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": svs_galloping_B_total_times,
}
)

df6 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": svs_galloping_C_total_times,
}
)

# ------------------------------ Small adaptive Binary ---------------------

df7 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": small_adaptive_binary_A_total_times,
}
)

df8 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": small_adaptive_binary_B_total_times,
}
)

df9 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": small_adaptive_binary_C_total_times,
}
)

# ------------------------------ Small adaptive Galloping ------------------

df10 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": small_adaptive_galloping_A_total_times,
}
)

df11 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 13/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

"Grupo": ["B" for i in range(1000)],

"Tiempo": small_adaptive_galloping_B_total_times,
}
)

df12 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": small_adaptive_galloping_C_total_times,
}
)

# ------------------------------ Sequential Binary -------------------------

df13 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": sequential_binary_A_total_times,
}
)

df14 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": sequential_binary_B_total_times,
}
)

df15 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": sequential_binary_C_total_times,
}
)

# ------------------------------ Sequential Galloping ----------------------

df16 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": sequential_galloping_A_total_times,
}
)

df17 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": sequential_galloping_B_total_times,
}
)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 14/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

df18 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": sequential_galloping_C_total_times,
}
)

# ------------------------------ BaezaYates binary -------------------------

df19 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": baeza_yates_binary_A_total_times
}
)

df20 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": baeza_yates_binary_B_total_times,
}
)

df21 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": baeza_yates_binary_C_total_times,
}
)

# ------------------------------ BaezaYates Galloping ----------------------

df22 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": baeza_yates_galloping_A_total_times
}
)

df23 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": baeza_yates_galloping_B_total_times,
}
)

df24 = pd.DataFrame(

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 15/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": baeza_yates_galloping_C_total_times,
}
)

df = pd.concat(
[
df1,
df2,
df3,
df4,
df5,
df6,
df7,
df8,
df9,
df10,
df11,
df12,
df13,
df14,
df15,
df16,
df17,
df18,
df19,
df20,
df21,
df22,
df23,
df24
],
ignore_index=True,
)

plt.figure(figsize=(13, 10))
sns.boxplot(data=df, y="Grupo", x="Tiempo", hue="Algoritmo", orient="h")
plt.title("Comparación de tiempos por algotimo\ny por grupo",
fontsize=25,
fontweight="bold",
y=1.02)
plt.xlabel("Tiempo (Segundos)",
fontsize=10,
fontweight="bold")
plt.ylabel("Grupo",
fontsize=10,
fontweight="bold")
plt.show()

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 16/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

Respecto a los tiempos de para encontrar cada intersección, se puede ver que los
algoritmos melding que implementan busqueda binaria total como algotimo de
búsqueda, son más rapidos que aquellos que emplean búsqueda galopante, esto para
todos los algoritmos y para todos los grupos. En teoría la búsqueda galopante debería
ser más rápido, pero quizá esto solo se cumpla para el caso en el que las listas en las
que se busca son mucho más grandes, en cuyo caso, los saltos exponenciales del
algoritmo galopante darían una ventaja.
Otra cosa importante que se puede observar en la gráfica es que los algoritmos SvS,
Small adaptive y sequential se tienen tiempos muy similares entre sí en los distinos
grupos, mientras que Baeza-Yates tiene tiempos más cortos en todos los grupos y con
ambos algoritmos de búsqueda.
Para el caso de los conjuntos de datos usados en este trabajo, Baeza-Yates es el
algoritmo más veloz de en sus dos variantes, siendo el que usa binary search el más
veloz de todos, aunque en el grupo 3, tiene algunos outliers que se separan mucho de el
conjunto del resto de los tiempos de este algoritmo.

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 17/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

In [93]: # ------------------------------ SvS Binary --------------------------------

df1 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": svs_binary_A_total_comparisons,
}
)
df2 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": svs_binary_B_total_comparisons,
}
)

df3 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": svs_binary_C_total_comparisons,
}
)

# ------------------------------ SvS Galloping -----------------------------

df4 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": svs_galloping_A_total_comparisons,
}
)

df5 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": svs_galloping_B_total_comparisons,
}
)

df6 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": svs_galloping_C_total_comparisons,
}
)

# ------------------------------ Small adaptive Binary ---------------------

df7 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 18/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

"Grupo": ["A" for i in range(1000)],

"Tiempo": small_adaptive_binary_A_total_comparisons,
}
)

df8 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": small_adaptive_binary_B_total_comparisons,
}
)

df9 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": small_adaptive_binary_C_total_comparisons,
}
)

# ------------------------------ Small adaptive Galloping ------------------

df10 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": small_adaptive_galloping_A_total_comparisons,
}
)

df11 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": small_adaptive_galloping_B_total_comparisons,
}
)

df12 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": small_adaptive_galloping_C_total_comparisons,
}
)

# ------------------------------ Sequential Binary -------------------------

df13 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": sequential_binary_A_total_comparisons,
}
)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 19/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

df14 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": sequential_binary_B_total_comparisons,
}
)

df15 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": sequential_binary_C_total_comparisons,
}
)

# ------------------------------ Sequential Galloping ----------------------

df16 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": sequential_galloping_A_total_comparisons,
}
)

df17 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": sequential_galloping_B_total_comparisons,
}
)

df18 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": sequential_galloping_C_total_comparisons,
}
)

# ------------------------------ BaezaYates binary -------------------------

df19 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": baeza_yates_binary_A_total_comparisons
}
)

df20 = pd.DataFrame(
{

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 20/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],

"Grupo": ["B" for i in range(1000)],
"Tiempo": baeza_yates_binary_B_total_comparisons,
}
)

df21 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": baeza_yates_binary_C_total_comparisons,
}
)

# ------------------------------ BaezaYates Galloping ----------------------

df22 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": baeza_yates_galloping_A_total_comparisons
}
)

df23 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": baeza_yates_galloping_B_total_comparisons,
}
)

df24 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": baeza_yates_galloping_C_total_comparisons,
}
)

df = pd.concat(
[
df1,
df2,
df3,
df4,
df5,
df6,
df7,
df8,
df9,
df10,
df11,
df12,

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 21/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

df13,
df14,
df15,
df16,
df17,
df18,
df19,
df20,
df21,
df22,
df23,
df24
],
ignore_index=True,
)

plt.figure(figsize=(13, 10))
sns.boxplot(data=df, y="Grupo", x="Tiempo", hue="Algoritmo", orient="h")
plt.title("Número de comparaciones por algotimo\ny por grupo",
fontsize=25,
fontweight="bold",
y=1.02)
plt.xlabel("Número Comparaciones",
fontsize=10,
fontweight="bold")
plt.ylabel("Grupo",
fontsize=10,
fontweight="bold")
plt.show()

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 22/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

Las distribuciones del número de comparaciones es muy similar a la de los tiempos. De

nuevo vemos que SvS, Small adaptive y sequential generan una cantidad similar de
comparaciones entre ellos en sus distintas variaciones de algoritmo de búsqueda y
Baeza-Yates nuevamente es el que genera menor número de comparaciones, sin
embargo, la difernecia entre el número de comparaciones es parece ser más grande que
las diferencias de los tiempos. Esto signiica que Baeza-Yates genera significativamente
menos comparaciones que los demás algoritmos siendo la variante que usa búsqueda
binaria la que genera el menor número de comparaciones.
In [105… # ------------------------------ SvS Binary --------------------------------
df1 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": svs_binary_A_total_lenghts,
}
)
df2 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 23/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

"Tiempo": svs_binary_B_total_lenghts,
}
)

df3 = pd.DataFrame(
{
"Algoritmo": ["SvS_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": svs_binary_C_total_lenghts,
}
)

# ------------------------------ SvS Galloping -----------------------------

df4 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": svs_galloping_A_total_lenghts,
}
)

df5 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": svs_galloping_B_total_lenghts,
}
)

df6 = pd.DataFrame(
{
"Algoritmo": ["SvS_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": svs_galloping_C_total_lenghts,
}
)

# ------------------------------ Small adaptive Binary ---------------------

df7 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": small_adaptive_binary_A_total_lenghts,
}
)

df8 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": small_adaptive_binary_B_total_lenghts,
}
)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 24/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

df9 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": small_adaptive_binary_C_total_lenghts,
}
)

# ------------------------------ Small adaptive Galloping ------------------

df10 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": small_adaptive_galloping_A_total_lenghts,
}
)

df11 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": small_adaptive_galloping_B_total_lenghts,
}
)

df12 = pd.DataFrame(
{
"Algoritmo": ["Small_Adaptive_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": small_adaptive_galloping_C_total_lenghts,
}
)

# ------------------------------ Sequential Binary -------------------------

df13 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": sequential_binary_A_total_lenghts,
}
)

df14 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": sequential_binary_B_total_lenghts,
}
)

df15 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 25/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

"Tiempo": sequential_binary_C_total_lenghts,
}
)

# ------------------------------ Sequential Galloping ----------------------

df16 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": sequential_galloping_A_total_lenghts,
}
)

df17 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": sequential_galloping_B_total_lenghts,
}
)

df18 = pd.DataFrame(
{
"Algoritmo": ["Sequential_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": sequential_galloping_C_total_lenghts,
}
)

# ------------------------------ BaezaYates binary -------------------------

df19 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": baeza_yates_binary_A_total_lenghts
}
)

df20 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": baeza_yates_binary_B_total_lenghts,
}
)

df21 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Binary" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": baeza_yates_binary_C_total_lenghts,
}
)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 26/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

# ------------------------------ BaezaYates Galloping ----------------------

df22 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["A" for i in range(1000)],
"Tiempo": baeza_yates_galloping_A_total_lenghts
}
)

df23 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["B" for i in range(1000)],
"Tiempo": baeza_yates_galloping_B_total_lenghts,
}
)

df24 = pd.DataFrame(
{
"Algoritmo": ["BaezaYates_Galloping" for i in range(1000)],
"Grupo": ["C" for i in range(1000)],
"Tiempo": baeza_yates_galloping_C_total_lenghts,
}
)

df = pd.concat(
[
df1,
df2,
df3,
df4,
df5,
df6,
df7,
df8,
df9,
df10,
df11,
df12,
df13,
df14,
df15,
df16,
df17,
df18,
df19,
df20,
df21,
df22,
df23,
df24
],

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 27/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

ignore_index=True,
)

plt.figure(figsize=(13, 10))
sns.boxplot(data=df, y="Grupo", x="Tiempo", hue="Algoritmo", orient="h", sho
plt.title("Longitudes de las intersecciones por algotimo\ny por grupo",
fontsize=25,
fontweight="bold",
y=1.02)
plt.xlabel("Longitud de intersección",
fontsize=10,
fontweight="bold")
plt.ylabel("Grupo",
fontsize=10,
fontweight="bold")
plt.show()

Para la visualización de las intersecciones se decidió ocultar los outliers ya que no

permitían apreciar adecuadamente las distribuciones de estos valores.
En este caso, se puede ver, como era de esperarse, que todos los algoritmos producen
el mismo número de elementos en cada intersección, lo que significa que todos los

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 28/29

9/10/24, 11:52 p.m. Mario_Rodriguez_tarea_6

algoritmos y sus variantes funcionan adecuadamente y son capaces de encontrar las

intersecciones de los conjuntos de datos.
Además, se ve claramente que conforme hay un mayor número de listas entre los cuales
se intenta establecer una intersección, menor es la longitud de dichas intersecciones.

Conclusiones
De acuerdo con los experiemitos realizados, se puede concluir que, por lo menos para el
caso de los datos utilizados aquí, el algoritmo Baeza-Yates es el más eficiente tanto en
número de comparaciones y de tiempos necesarios para encontrar las intersecciones de
los conjuntos de datos.
Además, se observa que el resto de algoritmos tienen comportamientos muy similares
en cuanto a comparaciones y tiempos tanto al usar busqueda binaria así como al usar
busqueda galopante.

Referencias Bibliográficas
Barbay, et.al, (2010) Baeza-Yates (2004) Hwang & Lin (1971)

file:///Users/mario/Desktop/Mario/Infotec/Primer_semestre/Analisis de algoritmos/Unidad 6/Mario_Rodriguez_tarea_6.html 29/29