4A. Reporte escrito. Experimentos y análisis de algoritmos de búsqueda por comparación.

Author

José Alberto Villegas Díaz Disciplina.

Lista de cambios:

Se corrigió el algoritmo de búsqueda secuencial, lo que mejoró considerablemente su desempeño. Se detalló de manera correcta la complejidad de \(B1\) y \(B2\) que es \(O(log p)\) donde \(p\) es la posición de inserción.

Introducción

Knuth (1998) señala que el problema de búsqueda consiste en encontrar datos almacenados a partir de una identificación única, conocida como clave. Dado un conjunto de \(N\) registros, el objetivo es localizar aquel que contiene la clave proporcionada.

En este reporte, se implementan y comparan cinco algoritmos de búsqueda por comparación:

  1. Búsqueda binaria acotada: Un método eficiente para buscar en arreglos ordenados, con complejidad \(O(\log n)\).
  2. Búsqueda secuencial B0 (búsqueda unaria): Una búsqueda lineal simple que examina cada elemento secuencialmente hasta encontrar el objetivo, con complejidad en el peor caso \(O(n)\).
  3. Búsqueda no acotada B1 (doubling search/galloping): Una técnica que combina búsqueda lineal con saltos exponenciales para localizar un intervalo antes de aplicar búsqueda binaria, útil cuando el tamaño del conjunto de datos es desconocido.
  4. Búsqueda no acotada B2 (doubling-doubling search): Una variante más agresiva de la búsqueda B1, que incrementa el tamaño de los saltos de manera más rápida para reducir el número de comparaciones.
  5. Búsqueda mediante SkipList: Una estructura de datos probabilística que permite búsquedas eficientes con complejidad esperada \(O(\log n)\).

El objetivo de este estudio es analizar el rendimiento de estos algoritmos bajo diferentes condiciones, evaluando su eficiencia en términos de tiempo de ejecución y número de comparaciones realizadas. A través de experimentos controlados, se busca determinar en qué escenarios cada algoritmo ofrece el mejor desempeño, considerando tanto entornos acotados (donde el tamaño del conjunto de datos es conocido) como no acotados (donde el tamaño es dinámico o desconocido).

Los resultados obtenidos proporcionarán insights valiosos sobre las ventajas y desventajas de cada método, permitiendo una selección informada del algoritmo más adecuado según los requisitos específicos de una aplicación dada.

Ordenamiento previo

Para el correcto funcionamiento de los algoritmos de búsqueda, es necesario que las listas de posteo dónde realizaremos dichas búsquedas estén ordenadas. Por lo que se utilizará el algoritmo de ordenamiento “heapsort” mismo que demostró una mayor eficiencia para el ordenamiento de estas listas de posteo en el “Reporte 3.A Experimentos y análisis de algoritmos de ordenamiento”.

using JSON
using Dates

# Función para ajustar el montículo (heapify) - Índices basados en 1
function heapify!(arr, n, i)
    largest = i
    left = 2 * i      # Hijo izquierdo (ajustado para base 1)
    right = 2 * i + 1 # Hijo derecho (ajustado para base 1)

    # Comparar con el hijo izquierdo
    if left <= n && arr[left] > arr[largest]
        largest = left
    end

    # Comparar con el hijo derecho
    if right <= n && arr[right] > arr[largest]
        largest = right
    end

    # Si el mayor no es la raíz, intercambiar y seguir ajustando
    if largest != i
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify!(arr, n, largest)
    end
end

# Implementación de HeapSort - Índices basados en 1
function heapsort!(arr)
    n = length(arr)

    # Construir el max-heap
    for i in n ÷ 2:-1:1
        heapify!(arr, n, i)
    end

    # Extraer elementos del heap uno por uno
    for i in n:-1:2
        arr[1], arr[i] = arr[i], arr[1]  # Mover la raíz al final
        heapify!(arr, i - 1, 1)
    end

    return arr
end

# Función para cargar y ordenar el archivo JSON
function ordenar_json(p::String)
    # Construir la ruta del archivo
    ruta_archivo = joinpath(homedir(), raw"C:\Users\josea\Downloads\listas-posteo-con-perturbaciones", 
                           "listas-posteo-con-perturbaciones-p=" * p * ".json")

    # Cargar el archivo JSON
    datos = JSON.parsefile(ruta_archivo)
    
    # Ordenar cada lista en el archivo JSON
    for (clave, arr) in datos
        heapsort!(arr)
    end
    
    # Devolver los datos ordenados
    return datos
end
ordenar_json (generic function with 1 method)
# Como son las mismas listas con diferentes niveles de desorden basta con que tomemos un archivo (el de menor perturbación)
lista = ordenar_json("016")
Dict{String, Any} with 100 entries:
  "reunion"      => Any[260, 275, 294, 296, 314, 317, 341, 384, 457, 529  …  49…
  "virtual"      => Any[45, 47, 63, 97, 255, 291, 295, 310, 327, 370  …  49582,…
  "julio"        => Any[25, 31, 74, 260, 297, 341, 361, 404, 434, 443  …  47540…
  "votos"        => Any[66, 86, 102, 311, 330, 334, 462, 560, 637, 655  …  4483…
  "propuesta"    => Any[37, 3109, 3637, 3676, 4013, 4015, 4021, 4027, 4046, 404…
  "nacional"     => Any[260, 262, 267, 269, 272, 273, 281, 282, 289, 294  …  49…
  "electoral"    => Any[65, 132, 170, 190, 208, 310, 578, 591, 701, 745  …  472…
  "@m_ebrard"    => Any[351, 359, 366, 623, 1745, 1983, 2838, 2923, 3360, 3538 …
  "jovenes"      => Any[22, 191, 192, 195, 196, 213, 220, 245, 350, 365  …  486…
  "_num"         => Any[25, 31, 32, 37, 52, 62, 66, 74, 91, 92  …  49972, 49974…
  "aqui"         => Any[19, 52, 92, 299, 315, 504, 598, 659, 678, 776  …  49079…
  "mayor"        => Any[54, 290, 423, 701, 887, 1107, 1148, 1379, 1617, 1719  ……
  "#envivo"      => Any[11, 15, 19, 24, 39, 58, 59, 63, 73, 81  …  49613, 49618…
  "👉"           => Any[30, 31, 87, 295, 365, 504, 557, 600, 838, 964  …  49442…
  "mexico"       => Any[10, 13, 14, 15, 21, 25, 27, 30, 36, 40  …  49806, 49835…
  "@epn"         => Any[3, 12, 46, 224, 260, 262, 269, 272, 273, 281  …  49862,…
  "poder"        => Any[37, 314, 374, 671, 767, 817, 888, 908, 943, 984  …  488…
  "pri"          => Any[52, 92, 168, 233, 564, 627, 657, 671, 692, 698  …  4887…
  "encuentro"    => Any[716, 1036, 1060, 1209, 1256, 3285, 3573, 3632, 3716, 37…
  "pena"         => Any[12, 26, 66, 98, 102, 265, 270, 275, 285, 294  …  49904,…
  "gano"         => Any[49, 153, 183, 304, 369, 490, 527, 584, 597, 602  …  470…
  "reune"        => Any[3173, 3208, 3628, 3913, 4478, 4502, 4662, 4673, 4699, 4…
  "plan"         => Any[202, 1209, 1351, 3109, 3730, 3863, 4218, 4259, 4261, 43…
  "presidencial" => Any[12, 16, 47, 63, 132, 145, 242, 259, 317, 450  …  48944,…
  "resultados"   => Any[1, 31, 49, 50, 153, 162, 237, 241, 242, 251  …  45776, …
  ⋮              => ⋮
# Cargar listas de consultas
consultas1 = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\consultas-1-listas-posteo.json"))
consultas2 = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\consultas-2-listas-posteo.json"))
consultas3 = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\consultas-3-listas-posteo.json"))
consultas4 = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\consultas-4-listas-posteo.json"))
10000-element Vector{Any}:
 39835
 37103
 20584
 11036
  3086
 26699
  9561
 36445
  2853
 27873
  2216
  1500
 48987
     ⋮
  4218
 23841
 38354
 40129
 20626
 32118
 42722
 20874
 47462
 37764
 29520
 10134
#Inspeccionamos de manera general las características de las listas de consulta. 
println(length(consultas1))
println(length(consultas2))
println(length(consultas3))
println(length(consultas4))
10000
10000
10000
10000
println(consultas1[1:20])
println(consultas2[1:10])
println(consultas3[1:10])
println(consultas4[1:10])
Any[5, 12, 3, 2, 4, 3, 15, 1, 4, 14, 5, 3, 14, 9, 3, 4, 1, 12, 13, 5]
Any[200, 229, 46, 186, 58, 183, 208, 212, 162, 72]
Any[694, 555, 2078, 3674, 667, 1144, 2329, 1163, 3398, 3291]
Any[39835, 37103, 20584, 11036, 3086, 26699, 9561, 36445, 2853, 27873]

De lo anterior podemos darnos cuenta que las listas de consulta constan del mismo número de elementos, con la particularidad que los elementos de las listas aumentan en uno o dos órdenes de magnitud consecutivamente. De tal manera que la primera lista contiene elementos de orden de \(10^0\) a \(10^1\) y la última elementos de \(10^3\) y \(10^4\)

Búsqueda binaria acotada

De acuerdo con Knuth (1998), la búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada. Funciona comparando el valor buscado \(K\) con el elemento central de la lista:

  1. Si \(K\) es igual al valor medio, la búsqueda finaliza con éxito.
  2. Si \(K\) es menor, se repite la búsqueda en la mitad inferior de la lista.
  3. Si \(K\) es mayor, se repite en la mitad superior.

Este proceso se repite hasta encontrar el elemento o determinar que no está en la lista.

Algoritmo

Dada una lista ordenada con claves \(K_1, K_2, \dots, K_N\), el algoritmo se describe así:

  • Inicialización: Definir los límites \(l = 1\) y \(u = N\).
  • Bucle: Mientras \(l \leq u\):
    • Calcular el punto medio: \(i = \lfloor (l + u)/2 \rfloor\).
    • Si \(K = K_i\), retornar éxito.
    • Si \(K < K_i\), actualizar \(u = i - 1\).
    • Si \(K > K_i\), actualizar \(l = i + 1\).
  • Si el bucle termina sin éxito, el elemento no está en la lista.

Complejidad $ O(n) $

using JSON

function busqueda_binaria_acotada(arr, valor, bajo, alto, contador)
    while bajo <= alto
        medio = (bajo + alto) ÷ 2
        contador[] += 1  # Incrementar contador de comparaciones
        
        if arr[medio] == valor
            return medio  # Valor encontrado
        elseif arr[medio] < valor
            bajo = medio + 1
        else
            alto = medio - 1
        end
    end
    return -1  # Valor no encontrado
end

function buscar_en_listas_ordenadas(datos_ordenados, elementos_a_buscar)
    # Contador de comparaciones (usamos un Ref para poder modificarlo en las funciones)
    total_comparaciones = Ref(0)
    
    # Diccionario para guardar resultados por clave
    resultados = Dict{String, Dict}()
    
    for (clave, arr) in datos_ordenados
        resultados_clave = Dict{Any, Any}()
        comparaciones_clave = 0
        
        for elemento in elementos_a_buscar
            # Realizar búsqueda binaria acotada
            posicion = busqueda_binaria_acotada(arr, elemento, 1, length(arr), total_comparaciones)
            resultados_clave[elemento] = posicion != -1 ? "Encontrado en posición $posicion" : "No encontrado"
        end
        
        resultados[clave] = resultados_clave
    end
    
    # Devolver resultados y total de comparaciones
    return resultados, total_comparaciones[]
end

# Función completa para cargar, ordenar y buscar
function procesar_archivo_y_buscar(datos_ordenados, elementos_a_buscar)
    
    # Realizar búsquedas en las listas ordenadas del diccionario
    
    resultados, total_comparaciones = buscar_en_listas_ordenadas(datos_ordenados, elementos_a_buscar)
    
    println("Total de comparaciones realizadas: $total_comparaciones")
    return resultados
end
procesar_archivo_y_buscar (generic function with 1 method)
using JSON

function busqueda_binaria_acotada(arr, valor, bajo, alto, contador)
    while bajo <= alto
        medio = (bajo + alto) ÷ 2
        contador[] += 1  # Incrementar contador de comparaciones
        
        if arr[medio] == valor
            return medio  # Valor encontrado
        elseif arr[medio] < valor
            bajo = medio + 1
        else
            alto = medio - 1
        end
    end
    return -1  # Valor no encontrado
end

function buscar_en_listas_ordenadas(datos_ordenados, elementos_a_buscar)
    # Contador de comparaciones (usamos un Ref para poder modificarlo en las funciones)
    total_comparaciones = Ref(0)
    
    # Diccionario para guardar resultados por clave
    resultados = Dict{String, Dict}()
    
    for (clave, arr) in datos_ordenados
        resultados_clave = Dict{Any, Any}()
        comparaciones_clave = 0
        
        for elemento in elementos_a_buscar
            # Realizar búsqueda binaria acotada
            posicion = busqueda_binaria_acotada(arr, elemento, 1, length(arr), total_comparaciones)
            resultados_clave[elemento] = posicion != -1 ? "Encontrado en posición $posicion" : "No encontrado"
        end
        
        resultados[clave] = resultados_clave
    end
    
    # Devolver resultados y total de comparaciones
    return resultados, total_comparaciones[]
end

# Función completa para cargar, ordenar y buscar
function procesar_archivo_y_buscar(datos_ordenados, elementos_a_buscar)
    
    # Realizar búsquedas en las listas ordenadas del diccionario
    
    resultados, total_comparaciones = buscar_en_listas_ordenadas(datos_ordenados, elementos_a_buscar)
    
    println("Total de comparaciones realizadas: $total_comparaciones")
    return resultados
end
procesar_archivo_y_buscar (generic function with 1 method)
@time begin
    procesar_archivo_y_buscar(lista,(consultas1))
end
@time begin
    procesar_archivo_y_buscar(lista,(consultas2))
end
@time begin
    procesar_archivo_y_buscar(lista,(consultas3))
end
@time begin
    procesar_archivo_y_buscar(lista,(consultas4))
end
Total de comparaciones realizadas: 9658445
  0.857163 seconds (1.27 M allocations: 26.252 MiB, 19.35% gc time, 9.43% compilation time)
Total de comparaciones realizadas: 9810026
  0.635125 seconds (1.25 M allocations: 26.321 MiB, 1.37% gc time, 0.50% compilation time)
Total de comparaciones realizadas: 9999849
  1.125757 seconds (20.15 M allocations: 352.905 MiB, 20.68% gc time)
Total de comparaciones realizadas: 10052264
  1.054306 seconds (22.81 M allocations: 393.393 MiB, 13.41% gc time)
Dict{String, Dict} with 100 entries:
  "reunion"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "virtual"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "julio"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "votos"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "propuesta"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "nacional"     => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "electoral"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "@m_ebrard"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "jovenes"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "_num"         => Dict{Any, Any}(31905=>"Encontrado en posición 4212", 4700=>…
  "aqui"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "mayor"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "#envivo"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "👉"           => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "mexico"       => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "@epn"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "poder"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "pri"          => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "encuentro"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "pena"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "gano"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "reune"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "plan"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "presidencial" => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "resultados"   => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  ⋮              => ⋮

De lo anterior podemos observar el número de comparaciones y los tiempos de ejecución permanecieron relativamente constantes, con una variación mínima. Esto es de esperarse ya que el algortimo de búsqueda binaria tine una complejidad de \(O(\log n)\). Sin embargo, sí se observa un incremento considerable número de asignaciones, esto se puede atribuir al tamaño de los números que integran las listas de consulta.

Búsqueda secuencial o lineal \(B_0\)

De acuerdo con Knuth (1998) Dada una tabla de registros \(R_1, R_2, \dots, R_N\), cuyas claves respectivas son \(K_1, K_2, \dots, K_N\), este algoritmo busca un argumento dado \(K\). Suponemos que \(N \geq 1\).

  1. [Inicialización.] Establecer \(i \gets 1\).
  2. [Comparación.] Si \(K = K_i\), el algoritmo termina con éxito.
  3. [Avance.] Aumentar \(i\) en 1.
  4. [¿Fin de archivo?] Si \(i \leq N\), regresar al paso 2. De lo contrario, el algoritmo termina sin éxito.

La complejidad de este algoritmo en el peor caso es \(O(n)\)

function busqueda_lineal(arr, valor, contador)
    for (i, elemento) in enumerate(arr)
        contador[] += 1  # Incrementar contador de comparaciones
        if elemento >= valor
            return i  # Devuelve la posición de inserción
        end
    end
    return length(arr) + 1  # Insertar al final si todos los elementos son menores
end


function buscar_lineal_en_listas(datos_ordenados, elementos_a_buscar)
    # Contador de comparaciones (usamos un Ref para poder modificarlo en las funciones)
    total_comparaciones = Ref(0)
    
    # Diccionario para guardar resultados por clave
    resultados = Dict{String, Dict}()
    
    for (clave, arr) in datos_ordenados
        resultados_clave = Dict{Any, Any}()
        comparaciones_clave = 0
        
        for elemento in elementos_a_buscar
            # Realizar búsqueda lineal
            posicion = busqueda_lineal(arr, elemento, total_comparaciones)
            resultados_clave[elemento] = posicion != -1 ? "Encontrado en posición $posicion" : "No encontrado"
        end
        
        resultados[clave] = resultados_clave
    end
    
    # Devolver resultados y total de comparaciones
    return resultados, total_comparaciones[]
end

# Función completa para cargar y buscar 
function procesar_archivo_y_buscar_lineal(datos_ordenados, elementos_a_buscar)

    #Realizar búsquedas lineales en las listas
    resultados, total_comparaciones = buscar_lineal_en_listas(datos_ordenados, elementos_a_buscar)
    
    println("Total de comparaciones realizadas (lineal): $total_comparaciones")
    return resultados
end
procesar_archivo_y_buscar_lineal (generic function with 1 method)
@time begin 
    procesar_archivo_y_buscar_lineal(lista,consultas1)
end
@time begin 
    procesar_archivo_y_buscar_lineal(lista,consultas2)
end
@time begin 
    procesar_archivo_y_buscar_lineal(lista,consultas3)
end
@time begin 
    procesar_archivo_y_buscar_lineal(lista,consultas4)
end
Total de comparaciones realizadas (lineal): 1285284
  1.085884 seconds (5.08 M allocations: 194.840 MiB, 49.78% gc time, 60.72% compilation time)
Total de comparaciones realizadas (lineal): 6025401
  0.574643 seconds (5.04 M allocations: 193.952 MiB, 6.19% gc time, 0.51% compilation time)
Total de comparaciones realizadas (lineal): 76747269
  3.351496 seconds (81.82 M allocations: 1.371 GiB, 14.31% gc time)
Total de comparaciones realizadas (lineal): 989149917
 45.471095 seconds (996.18 M allocations: 14.996 GiB, 6.26% gc time)
Dict{String, Dict} with 100 entries:
  "reunion"      => Dict{Any, Any}(31905=>"Encontrado en posición 1712", 4700=>…
  "virtual"      => Dict{Any, Any}(31905=>"Encontrado en posición 712", 4700=>"…
  "julio"        => Dict{Any, Any}(31905=>"Encontrado en posición 439", 4700=>"…
  "votos"        => Dict{Any, Any}(31905=>"Encontrado en posición 752", 4700=>"…
  "propuesta"    => Dict{Any, Any}(31905=>"Encontrado en posición 286", 4700=>"…
  "nacional"     => Dict{Any, Any}(31905=>"Encontrado en posición 1530", 4700=>…
  "electoral"    => Dict{Any, Any}(31905=>"Encontrado en posición 670", 4700=>"…
  "@m_ebrard"    => Dict{Any, Any}(31905=>"Encontrado en posición 309", 4700=>"…
  "jovenes"      => Dict{Any, Any}(31905=>"Encontrado en posición 424", 4700=>"…
  "_num"         => Dict{Any, Any}(31905=>"Encontrado en posición 4212", 4700=>…
  "aqui"         => Dict{Any, Any}(31905=>"Encontrado en posición 440", 4700=>"…
  "mayor"        => Dict{Any, Any}(31905=>"Encontrado en posición 323", 4700=>"…
  "#envivo"      => Dict{Any, Any}(31905=>"Encontrado en posición 606", 4700=>"…
  "👉"           => Dict{Any, Any}(31905=>"Encontrado en posición 345", 4700=>"…
  "mexico"       => Dict{Any, Any}(31905=>"Encontrado en posición 2852", 4700=>…
  "@epn"         => Dict{Any, Any}(31905=>"Encontrado en posición 2158", 4700=>…
  "poder"        => Dict{Any, Any}(31905=>"Encontrado en posición 434", 4700=>"…
  "pri"          => Dict{Any, Any}(31905=>"Encontrado en posición 532", 4700=>"…
  "encuentro"    => Dict{Any, Any}(31905=>"Encontrado en posición 647", 4700=>"…
  "pena"         => Dict{Any, Any}(31905=>"Encontrado en posición 2500", 4700=>…
  "gano"         => Dict{Any, Any}(31905=>"Encontrado en posición 495", 4700=>"…
  "reune"        => Dict{Any, Any}(31905=>"Encontrado en posición 388", 4700=>"…
  "plan"         => Dict{Any, Any}(31905=>"Encontrado en posición 358", 4700=>"…
  "presidencial" => Dict{Any, Any}(31905=>"Encontrado en posición 680", 4700=>"…
  "resultados"   => Dict{Any, Any}(31905=>"Encontrado en posición 469", 4700=>"…
  ⋮              => ⋮

Podemos observar que los tiempos de ejecuciones y número de comparaciones de este algoritmo aumentaron de manera significativa respecto al de búsqueda binaria, esto es porque la complejidad depende de la posición del valor buscado y de si se encuentra o no, siendo el peor caso \(O(n)\). Podemos observar que muchos de los valores que buscó no fueron encontrados para lo que el algoritmo comparó el valor buscado con todos los elementos de la lista antes de concluir que no está presente, es decir se comportó múltiples veces como el peor caso. Esto explica el aumento en varios órdenes en tiempos de ejecución y comparaciones.

Búsqueda no acotada \(B_1\)

Baeza-Yates y Salinger (2010) mencionan que el algoritmo de búsqueda exponencial, que se utiliza para localizar un elemento en un conjunto ordenado de manera eficiente consiste en dos fases:

Fase 1: El proceso comienza seleccionando un elemento y buscándolo en otro conjunto mediante saltos exponenciales (1, 2, 4, …). hasta que el salto supera la posición del elemento buscado.

Fase 2: Se realiza búsqueda binaria en el rango detectado. Esta estrategia, conocida como búsqueda galopante, imita la búsqueda binaria en secuencias no acotadas y mantiene una complejidad de \(O(\log p)\) donde \(p\) es la posición de inserción.

using JSON

function busqueda_doubling(arr, valor, contador)
    n = length(arr)
    

    # Fase 1: Búsqueda exponencial para encontrar el rango
    if arr[1] == valor
        contador[] += 1
        return 1
    end
    
    indice = 2  # Comenzamos desde el segundo elemento (índice 1 ya verificado)
    while indice <= n && arr[indice] < valor
        contador[] += 1  # Comparación arr[indice] < valor
        indice *= 2
    end
    
    # Ajustar los límites para la búsqueda binaria
    bajo = indice ÷ 2
    alto = min(indice, n)
    
    # Fase 2: Búsqueda binaria dentro del rango encontrado
    while bajo <= alto
        medio = (bajo + alto) ÷ 2
        contador[] += 1  # Comparación arr[medio] == valor
        
        if arr[medio] == valor
            return medio
        elseif arr[medio] < valor
            bajo = medio + 1
        else
            alto = medio - 1
        end
    end
    
    return -1  # Elemento no encontrado
end

function buscar_con_doubling(datos_ordenados, elementos_a_buscar)
    # Contador de comparaciones
    total_comparaciones = Ref(0)
    
    # Diccionario para resultados
    resultados = Dict{String, Dict}()
    
    for (clave, arr) in datos_ordenados
        resultados_clave = Dict{Any, Any}()
        
        for elemento in elementos_a_buscar
            posicion = busqueda_doubling(arr, elemento, total_comparaciones)
            resultados_clave[elemento] = posicion != -1 ? "Encontrado en posición $posicion" : "No encontrado"
        end
        
        resultados[clave] = resultados_clave
    end
    
    return resultados, total_comparaciones[]
end

function procesar_archivo_y_buscar_doubling(datos_ordenados, elementos_a_buscar)
    
    #Realizar búsquedas con doubling search
    resultados, total_comparaciones = buscar_con_doubling(datos_ordenados, elementos_a_buscar)
    
    println("Total de comparaciones realizadas (doubling search): $total_comparaciones")
    return resultados
end
procesar_archivo_y_buscar_doubling (generic function with 1 method)
@time begin 
    procesar_archivo_y_buscar_doubling(lista,consultas1)
end
@time begin 
    procesar_archivo_y_buscar_doubling(lista,consultas2)
end
@time begin 
    procesar_archivo_y_buscar_doubling(lista,consultas3)
end
@time begin 
    procesar_archivo_y_buscar_doubling(lista,consultas4)
end
Total de comparaciones realizadas (doubling search): 1228088
  0.480016 seconds (257.94 k allocations: 10.365 MiB, 34.07% compilation time)
Total de comparaciones realizadas (doubling search): 2917009
  0.363662 seconds (247.15 k allocations: 11.062 MiB)
Total de comparaciones realizadas (doubling search): 8181939
  1.246572 seconds (15.08 M allocations: 275.526 MiB)
Total de comparaciones realizadas (doubling search): 15754351
  2.742887 seconds (27.03 M allocations: 457.676 MiB)
Dict{String, Dict} with 100 entries:
  "reunion"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "virtual"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "julio"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "votos"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "propuesta"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "nacional"     => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "electoral"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "@m_ebrard"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "jovenes"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "_num"         => Dict{Any, Any}(31905=>"Encontrado en posición 4212", 4700=>…
  "aqui"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "mayor"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "#envivo"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "👉"           => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "mexico"       => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "@epn"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "poder"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "pri"          => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "encuentro"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "pena"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "gano"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "reune"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "plan"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "presidencial" => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "resultados"   => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  ⋮              => ⋮

Aquí podemos observar tiempos de ejecución y número de comparaciones similares a aquellos observados en búsqueda binaria lo cual es esperable ya que tiene un peor caso de $ O(n) $, sin embargo \(B_1\) ofrece la ventaja que mientras más cercano esté el valor buscado al inicio de la lista puede ser más rápido que búsqueda binaria. Esto se aprecia claramente con las dos primeras listas de consultas, se ejecutan en menor tiempo y con menos número de comparaciones que Busqueda binaria, esto es porque los valores son menores y están más cerca del inicio de la lista si es que existen.

Búsqueda no acotada \(B_2\)

Similar a \(B_1\) pero en lugar de aumentar el rango de búsqueda en potencias de 2 (como en \(B_1\): \(1, 2, 4, 8, 16, \dots\)),

\(B_2\) podría usa potencias de potencias, como \(2^{2^k}\):

Ejemplo: \(2, 4, 16, 256, 65536, \dots\)

Tiene complejidad de \(O(\log p)\) donde \(p\) es la posición de inserción.

using JSON

function busqueda_doblemente_doblada(arr, valor, contador)
    n = length(arr)
    
    # Verificar el primer elemento
    contador[] += 1
    arr[1] == valor && return 1
    
    # Fase 1: Búsqueda doblemente doblada 
    indice = 2
    while indice <= n
        # Comparar el elemento actual
        contador[] += 1
        if arr[indice] == valor
            return indice
        elseif arr[indice] > valor
            break
        end
        
        # Aumentamos el índice de manera más agresiva 
        indice_previo = indice
        indice *= indice
        
        # Verificar si nos pasamos del array
        if indice > n
            # Retroceder y hacer búsqueda binaria entre indice_previo y n
            indice = n
            break
        end
    end
    
    # Ajustar los límites para la búsqueda binaria
    bajo = max(indice ÷ 4, 1)  # Retrocedemos un paso
    alto = min(indice, n)
    
    # Fase 2: Búsqueda binaria precisa
    while bajo <= alto
        medio = (bajo + alto) ÷ 2
        contador[] += 1
        
        if arr[medio] == valor
            return medio
        elseif arr[medio] < valor
            bajo = medio + 1
        else
            alto = medio - 1
        end
    end
    
    return -1
end

function buscar_con_doblemente_doblada(datos_ordenados, elementos_a_buscar)
    total_comparaciones = Ref(0)
    resultados = Dict{String, Dict}()
    
    for (clave, arr) in datos_ordenados
        resultados_clave = Dict{Any, Any}()
        
        for elemento in elementos_a_buscar
            posicion = busqueda_doblemente_doblada(arr, elemento, total_comparaciones)
            resultados_clave[elemento] = posicion != -1 ? "Encontrado en posición $posicion" : "No encontrado"
        end
        
        resultados[clave] = resultados_clave
    end
    
    return resultados, total_comparaciones[]
end

function procesar_archivo_y_buscar_dd(datos_ordenados, elementos_a_buscar)

    resultados, total_comparaciones = buscar_con_doblemente_doblada(datos_ordenados, elementos_a_buscar)
    
    println("Total de comparaciones realizadas (doubling-doubling search): $total_comparaciones")
    return resultados
end
procesar_archivo_y_buscar_dd (generic function with 1 method)
@time begin 
    procesar_archivo_y_buscar_dd(lista,consultas1)
end
@time begin 
    procesar_archivo_y_buscar_dd(lista,consultas2)
end
@time begin 
    procesar_archivo_y_buscar_dd(lista,consultas3)
end
@time begin 
    procesar_archivo_y_buscar_dd(lista,consultas4)
end
Total de comparaciones realizadas (doubling-doubling search): 3197982
  0.417825 seconds (261.24 k allocations: 10.552 MiB, 24.58% compilation time)
Total de comparaciones realizadas (doubling-doubling search): 5158847
  0.420363 seconds (183.97 k allocations: 8.652 MiB)
Total de comparaciones realizadas (doubling-doubling search): 10121250
  3.014676 seconds (19.33 M allocations: 337.420 MiB, 67.26% gc time)
Total de comparaciones realizadas (doubling-doubling search): 13909594
  1.143733 seconds (28.57 M allocations: 480.533 MiB)
Dict{String, Dict} with 100 entries:
  "reunion"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "virtual"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "julio"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "votos"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "propuesta"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "nacional"     => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "electoral"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "@m_ebrard"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "jovenes"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "_num"         => Dict{Any, Any}(31905=>"Encontrado en posición 4212", 4700=>…
  "aqui"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "mayor"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "#envivo"      => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "👉"           => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "mexico"       => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "@epn"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "poder"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "pri"          => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "encuentro"    => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "pena"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "gano"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "reune"        => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "plan"         => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "presidencial" => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  "resultados"   => Dict{Any, Any}(31905=>"No encontrado", 4700=>"No encontrado…
  ⋮              => ⋮

Como podemos ver \(B_2\) no muestra diferencias significativas respecto a \(B_1\), en términos de tiempo de ejecución se muestra similar y en número de comparaciones también está dentro del mismo orden de magnitud. Este algoritmo podría ser más últil en busquedas dentro de listas de un tamaño mucho mayor a las usadas en este experimento, ya que su fase de expansión crece de manera más acelerada.

Búsqueda mediante la estructura de datos SkipList

Pugh (1990) propuso como una alternativa simple y eficiente a estructuras de datos balanceadas como los árboles de búsqueda. Una SkipList es una lista enlazada jerárquica con múltiples niveles. Cada nivel es una sublista de los niveles inferiores, lo que permite realizar búsquedas en \(O(logn)\) en promedio.

Se empieza en el nivel más alto y se desciende progresivamente hasta encontrar el elemento deseado.Se asigna un nivel aleatorio al nuevo nodo y se insertan enlaces en los niveles correspondientes. Se eliminan los enlaces del nodo en cada nivel en el que aparece.

Dependen de la asignación aleatoria de niveles a los nodos, lo que en promedio garantiza una estructura balanceada sin necesidad de reestructuración explícita.

Aunque el peor caso es \(O(n)\), este es muy poco probable, y en la práctica, el tiempo esperado para búsqueda, inserción y eliminación es \(O(logn)\). (Pugh, 1990)

# Se cambia el tipo de datos en las listas del diccionario a enteros, para que el algortimo pueda funcionar correctamente
for clave in keys(lista)
    lista[clave] = [Int(x) for x in lista[clave]]
end
using Random

# Estructura de nodo para la Skip List
mutable struct SkipNode
    value::Int
    forward::Vector{Union{SkipNode, Nothing}}  # Array de punteros forward
end

# Estructura de la Skip List
mutable struct SkipList
    header::SkipNode
    level::Int
    max_level::Int
    p::Float64  # Probabilidad para los niveles
end

# Función para crear un nuevo nodo
function create_node(value::Int, level::Int)
    SkipNode(value, [nothing for _ in 1:level])
end

# Función para inicializar una Skip List
function create_skip_list(max_level::Int, p::Float64=0.5)
    header = create_node(-1, max_level)  # Valor -1 como cabeza
    SkipList(header, 1, max_level, p)
end

# Función para determinar el nivel aleatorio de un nuevo nodo
function random_level(skip_list::SkipList)
    level = 1
    while rand() < skip_list.p && level < skip_list.max_level
        level += 1
    end
    return level
end

# Función para insertar un valor en la Skip List
function insert!(skip_list::SkipList, value::Int)
    update = [nothing for _ in 1:skip_list.max_level]
    current = skip_list.header
    
    # Buscar la posición de inserción
    for i in skip_list.level:-1:1
        while current.forward[i] !== nothing && current.forward[i].value < value
            current = current.forward[i]
        end
        update[i] = current
    end
    
    current = current.forward[1]
    
    # Si el valor no existe, insertarlo
    if current === nothing || current.value != value
        new_level = random_level(skip_list)
        
        # Ajustar el nivel de la Skip List si es necesario
        if new_level > skip_list.level
            for i in skip_list.level+1:new_level
                update[i] = skip_list.header
            end
            skip_list.level = new_level
        end
        
        # Crear el nuevo nodo
        new_node = create_node(value, new_level)
        
        # Insertar el nodo
        for i in 1:new_level
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
        end
    end
end

# Función de búsqueda en la Skip List (con contador de comparaciones)
function search(skip_list::SkipList, value::Int, counter::Ref{Int}=Ref(0))
    current = skip_list.header
    
    # Buscar desde el nivel más alto hacia abajo
    for i in skip_list.level:-1:1
        while current.forward[i] !== nothing
            counter[] += 1  # Contar la comparación
            if current.forward[i].value == value
                return true  # Valor encontrado
            elseif current.forward[i].value < value
                current = current.forward[i]
            else
                break
            end
        end
    end
    
    # Verificar en el nivel más bajo
    current = current.forward[1]
    if current !== nothing && current.value == value
        counter[] += 1
        return true
    end
    
    return false  # Valor no encontrado
end

# Función para construir Skip List desde un array ordenado
function build_skip_list(sorted_array::Vector{Int}, max_level::Int=16, p::Float64=0.5)
    skip_list = create_skip_list(max_level, p)
    for value in sorted_array
        insert!(skip_list, value)
    end
    return skip_list
end

# Función principal para buscar en múltiples listas
function buscar_con_skip_lists(datos_ordenados, elementos_a_buscar)
    total_comparaciones = Ref(0)
    resultados = Dict{String, Dict}()
    
    for (clave, arr) in datos_ordenados
        resultados_clave = Dict{Any, Any}()
        
        # Construir la Skip List para esta lista ordenada
        skip_list = build_skip_list(arr)
        
        for elemento in elementos_a_buscar
            counter = Ref(0)
            encontrado = search(skip_list, elemento, counter)
            total_comparaciones[] += counter[]
            resultados_clave[elemento] = encontrado ? "Encontrado" : "No encontrado"
        end
        
        resultados[clave] = resultados_clave
    end
    
    return resultados, total_comparaciones[]
end

# Función completa para procesar archivos
function procesar_archivo_con_skip_lists(datos_ordenados, elementos_a_buscar)
    #datos_ordenados = ordenar_json(p)
    resultados, total_comparaciones = buscar_con_skip_lists(datos_ordenados, elementos_a_buscar)
    
    println("Total de comparaciones realizadas (Skip List): $total_comparaciones")
    return resultados
end
procesar_archivo_con_skip_lists (generic function with 2 methods)
procesar_archivo_con_skip_lists(lista, consultas1)
LoadError: cannot convert a value to nothing for assignment
cannot convert a value to nothing for assignment

Stacktrace:
  [1] error(s::String)
    @ Base .\error.jl:35
  [2] nonnothingtype_checked(T::Type)
    @ Base .\some.jl:32
  [3] convert(::Type{Nothing}, x::SkipNode)
    @ Base .\some.jl:37
  [4] setindex!(A::Vector{Nothing}, x::SkipNode, i::Int64)
    @ Base .\array.jl:987
  [5] insert!(skip_list::SkipList, value::Int64)
    @ Main .\In[19]:47
  [6] build_skip_list
    @ .\In[19]:107 [inlined]
  [7] build_skip_list
    @ .\In[19]:105 [inlined]
  [8] buscar_con_skip_lists(datos_ordenados::Dict{String, Any}, elementos_a_buscar::Vector{Any})
    @ Main .\In[19]:121
  [9] procesar_archivo_con_skip_lists(datos_ordenados::Dict{String, Any}, elementos_a_buscar::Vector{Any})
    @ Main .\In[19]:139
 [10] top-level scope
    @ In[20]:1

Discusión y resultados

A continuación se muestran dos tablas en las que se resumen los resultados de los experimentos. Una de tiempos de ejecución y la otra de Número de comparaciones.

Tabla. 1 Tiempo de ejecución en segundos de cada lista de consultas con su respectivo orden de magnitud para cada algoritmo.

\[\begin{array}{|l|c|c|c|c|} \hline & \textbf{B. binaria} & \textbf{$B_0$} & \textbf{$B_1$} & \textbf{$B_2$} \\ \hline Consultas orden 10^0 & 0.857163 & 1.085884 & 0.480016 & 0.417825 \\ Consultas orden 10^1 & 0.635125 & 0.574643 & 0.363662 & 0.420363 \\ Consultas orden 10^2 & 1.125757 & 3.351496 & 1.246572 & 3.014676 \\ Consultas orden 10^3 & 1.054306 & 45.471095 & 2.742887 & 1.143733 \\ \hline \end{array}\]

Tabla. 2 Número de comparaciones realizadas de cada lista de consultas con su respectivo orden de magnitud para cada algoritmo.

\[\begin{array}{|l|c|c|c|c|} \hline & \textbf{B. binaria} & \textbf{$B_0$} & \textbf{$B_1$} & \textbf{$B_2$} \\ \hline \text{Consultas orden }10^0 & 9.66 \times 10^6 & 1.28 \times 10^6 & 1.23 \times 10^6 & 3.20 \times 10^6 \\ \text{Consultas orden }10^1 & 9.81 \times 10^6 & 6.02 \times 10^6 & 2.92 \times 10^6 & 5.16 \times 10^6 \\ \text{Consultas orden }10^2 & 1.00 \times 10^7 & 7.67 \times 10^7 & 8.18 \times 10^6 & 1.01 \times 10^7 \\ \text{Consultas orden }10^3 & 1.01 \times 10^7 & 9.89 \times 10^8 & 1.58 \times 10^7 & 1.39 \times 10^7 \\ \hline \end{array}\]

Los resultados experimentales permiten observar diferencias fundamentales en el comportamiento de los algoritmos de búsqueda analizados:

1. Búsqueda Binaria

Como era de esperarse por su complejidad teórica \(O(\log n)\), este algoritmo mantuvo tiempos de ejecución y número de comparaciones relativamente constantes, independientemente del orden de magnitud de los elementos en las listas de consulta (que variaban desde \(10^0\) hasta \(10^3\)). Sin embargo, se registró un incremento notable en el número de asignaciones, lo cual puede atribuirse al manejo de números más grandes en las operaciones de comparación.

2. Búsqueda no acotada Secuencial (\(B_0\))

Para las consultas de menor orden presento rendimientos comparables al resto de los algoritmos, incluso mejores que en búqueda binaria, pero para las de mayor orden presentó un deterioro significativo en el rendimiento, con tiempos de ejecución y comparaciones que aumentaron hasta un órden de magnitud respecto a los otros algoritmos. Esto se explica por su naturaleza \(O(n)\) y porque, en muchos casos, el algoritmo operó en el peor escenario posible.

3. Búsqueda no acotada (\(B_1\))

Mostró un rendimiento comparable al de la búsqueda binaria (\(O(\log n)\) en el peor caso), pero con una ventaja notable para valores cercanos al inicio de la lista. Esto fue particularmente evidente en las consultas con elementos de menor magnitud (\(10^0\) y \(10^1\)).

4. Búsqueda no acotada (\(B_2\))

No mostró diferencias significativas respecto a \(B_1\) en este experimento, manteniéndose en el mismo orden de magnitud tanto en tiempo como en comparaciones.

Conclusión

De lo anterior se puede concluir que probablemente búsqueda binaria sea la opción más confiable para conjuntos ordenados de tamaño arbitrario, sin embargo, \(B_1\) y \(B_2\) mostraron ser alternativas fiables en todos los casos y con potencial para ser usados en contextos específicos, como tamaños de listas muy grandes o busqueda de valores cercanos al inicio de la lista. Finalmente la busqueda secuencial si bien es el algoritmo más simple, también demostró ser el más lento e ineficiente.

Bibliografía

Baeza-Yates, R., & Salinger, A. (2010). Fast intersection algorithms for sorted sequences. In T. Elomaa, H. Mannila, & P. Orponen (Eds.), Algorithms and applications: Essays dedicated to Esko Ukkonen on the occasion of his 60th birthday (pp. 45–61). Springer. https://doi.org/10.1007/978-3-642-12476-1_3

Knuth, D. E. (1998). The art of computer programming (2ª ed.). Addison Wesley Longman, Inc.

Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668-676. https://doi.org/10.1145/78973.78977