Unidad 5. Algoritmos de intersección y unión de conjuntos en el modelo de comparación

Introducción

Conforme a Demaine, López-Ortiz, y Munro (2000) dado un conjunto de \(𝑘\) listas ordenadas \(𝐴_{1}\), \(𝐴_{2}\), … ,\(𝐴_{k}\) la intersección consiste en un conjunto que contenga los elementos comunes a todas ellas. Para validar esto cada elemento de la intersección debe estar presente en todas las listas (esto se prueba con comparaciones de igualdad).

En este reporte se evaluará el desempeño de algoritmos de intersección de conjuntos representados mediante listas ordenadas de diferente tamaño, considerando como parámetros los métodos internos de búsqueda, el tamaño de los conjuntos y la distribución de sus elementos. El análisis se realizará desde una perspectiva experimental, midiendo los costos en términos de tiempo de ejecución y consumo de memoria. Se usarán gráficos y tablas para cada conjunto de listas con el que se trabajará, para facilitar la comparación de los algoritmos.

Carga de Conjuntos

Se trabajará con los siguientes datos:

Conjunto \(A\) que contiene pares de listas.

Conjunto \(B\) que contiene tripletas de listas.

Conjunto \(C\) que contiene tuplas de 4 listas (tetrapleta).

using JSON

A = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\postinglists-for-intersection-A-k=2.json\postinglists-for-intersection-A-k=2.json"))
B = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\postinglists-for-intersection-B-k=3.json\postinglists-for-intersection-B-k=3.json"))
C = JSON.parsefile(joinpath(homedir(), raw"C:\Users\josea\Downloads\postinglists-for-intersection-C-k=4.json\postinglists-for-intersection-C-k=4.json"))

200-element Vector{Any}:
 Any[Any[3, 4, 10, 17, 30, 38, 43, 49, 63, 66  …  49863, 49869, 49882, 49883, 49905, 49943, 49963, 49965, 49986, 49987], Any[243, 1553, 1848, 1887, 1949, 2177, 2402, 2466, 2564, 3005  …  48266, 48333, 48347, 48696, 48838, 49129, 49379, 49714, 49863, 49986], Any[1848, 3482, 3482, 3626, 4490, 4999, 7169, 7641, 7903, 8256  …  46176, 46404, 46948, 47395, 47465, 47465, 47714, 48089, 48838, 49764], Any[4, 49, 91, 210, 237, 242, 318, 327, 353, 358  …  48377, 48507, 48844, 48846, 49278, 49331, 49390, 49444, 49667, 49764]]
 Any[Any[43, 334, 367, 412, 493, 935, 1203, 1329, 1367, 1726  …  48369, 48724, 48790, 48932, 49032, 49504, 49519, 49780, 49784, 49880], Any[13, 26, 42, 45, 132, 134, 150, 165, 172, 210  …  49624, 49661, 49758, 49882, 49905, 49915, 49917, 49971, 49975, 49979], Any[43, 521, 1203, 1657, 2345, 2445, 2681, 3518, 3798, 4648  …  45407, 45603, 46274, 46655, 47767, 48790, 49262, 49504, 49519, 49519], Any[2, 3, 7, 9, 11, 12, 15, 16, 18, 19  …  49963, 49967, 49968, 49975, 49978, 49982, 49983, 49984, 49985, 49990]]
 Any[Any[196, 1192, 2220, 2220, 2530, 4735, 5655, 5766, 5828, 5828  …  46896, 46931, 47424, 47613, 47640, 47713, 47846, 47942, 48825, 49232], Any[3, 12, 46, 224, 260, 262, 269, 272, 273, 281  …  49862, 49863, 49864, 49876, 49897, 49937, 49949, 49974, 49981, 49992], Any[1, 2, 3, 4, 6, 8, 9, 10, 11, 12  …  49989, 49990, 49991, 49993, 49994, 49996, 49997, 49998, 49999, 50000], Any[390, 446, 1104, 1192, 1474, 1747, 2530, 3441, 3716, 4518  …  48565, 48715, 48825, 48830, 49232, 49232, 49348, 49801, 49850, 49897]]
 Any[Any[12, 26, 66, 102, 265, 270, 275, 285, 294, 297  …  49888, 49891, 49904, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[649, 756, 835, 835, 1249, 1649, 2160, 2309, 2309, 2309  …  44886, 45442, 46059, 46059, 47119, 47319, 47563, 48460, 48619, 49617], Any[2, 7, 11, 12, 18, 19, 20, 22, 28, 35  …  48959, 49335, 49481, 49730, 49865, 49869, 49911, 49934, 49952, 49963], Any[556, 716, 759, 835, 1117, 1157, 1459, 1459, 1459, 1679  …  48619, 48722, 49153, 49163, 49192, 49197, 49321, 49617, 49653, 49852]]
 Any[Any[461, 594, 677, 1158, 1159, 1363, 1556, 1766, 1812, 2117  …  45377, 45788, 45895, 46976, 47314, 47569, 47627, 48627, 49852, 49917], Any[1158, 1302, 1812, 2129, 2873, 3082, 3082, 3173, 3173, 3283  …  30587, 30587, 36082, 39276, 39698, 42287, 44488, 44694, 45225, 49852], Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[68, 260, 262, 267, 269, 272, 273, 281, 282, 289  …  37225, 39568, 39750, 42287, 42650, 43202, 44029, 45597, 46007, 46054]]
 Any[Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[510, 834, 1130, 1139, 1170, 1532, 2316, 2559, 2719, 3077  …  47430, 47484, 47840, 48261, 48285, 48495, 48585, 48594, 48599, 49631], Any[461, 1139, 1168, 1863, 2056, 2316, 2662, 2662, 2785, 2785  …  46021, 46528, 47430, 47484, 48261, 48460, 48585, 48585, 48599, 48703], Any[12, 26, 66, 102, 265, 270, 275, 285, 294, 297  …  49888, 49891, 49904, 49912, 49915, 49917, 49940, 49962, 49966, 49989]]
 Any[Any[1, 3, 6, 7, 12, 16, 18, 19, 27, 28  …  49316, 49416, 49470, 49595, 49708, 49759, 49785, 49907, 49945, 49954], Any[19, 201, 443, 563, 580, 580, 1400, 1415, 1419, 1430  …  41716, 41822, 42370, 42370, 42640, 43936, 44377, 44377, 44593, 48564], Any[25, 31, 32, 37, 52, 62, 66, 74, 91, 92  …  49972, 49974, 49976, 49978, 49989, 49990, 49993, 49994, 49996, 49998], Any[19, 53, 107, 160, 201, 231, 443, 443, 509, 547  …  40841, 42370, 42640, 43125, 43212, 43268, 44593, 47521, 48305, 49139]]
 Any[Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[269, 1054, 2045, 2045, 2328, 3841, 4209, 4444, 4471, 5939  …  48064, 48162, 48269, 48416, 48855, 48991, 49056, 49320, 49463, 49614], Any[777, 797, 797, 1158, 1272, 1411, 1411, 1444, 1494, 1644  …  44173, 44753, 45589, 46343, 46343, 46465, 47034, 48874, 48991, 49614], Any[67, 125, 129, 153, 207, 233, 267, 268, 269, 299  …  49901, 49910, 49936, 49937, 49939, 49951, 49953, 49958, 49963, 49976]]
 Any[Any[3, 12, 46, 224, 260, 262, 269, 272, 273, 281  …  49862, 49863, 49864, 49876, 49897, 49937, 49949, 49974, 49981, 49992], Any[477, 573, 3673, 5311, 5883, 6152, 6327, 6411, 6411, 6703  …  44302, 44937, 44937, 45286, 46019, 46306, 46540, 48213, 49149, 49951], Any[461, 474, 515, 1251, 1280, 2777, 3203, 3271, 3449, 3673  …  48928, 48967, 48984, 49214, 49368, 49707, 49770, 49855, 49937, 49951], Any[67, 125, 129, 153, 207, 233, 267, 268, 269, 299  …  49901, 49910, 49936, 49937, 49939, 49951, 49953, 49958, 49963, 49976]]
 Any[Any[13, 26, 42, 45, 132, 134, 150, 165, 172, 210  …  49579, 49585, 49613, 49624, 49661, 49758, 49882, 49905, 49915, 49917], Any[1251, 1866, 3126, 3476, 3972, 4213, 5263, 5494, 5829, 5911  …  48298, 48537, 48847, 48928, 48966, 48966, 48984, 49585, 49690, 49710], Any[1100, 1328, 2290, 2584, 2756, 2756, 2862, 3126, 3126, 3485  …  46821, 47568, 48467, 48537, 49494, 49494, 49501, 49501, 49690, 49710], Any[67, 125, 129, 153, 207, 233, 267, 268, 269, 299  …  49901, 49910, 49936, 49937, 49939, 49951, 49953, 49958, 49963, 49976]]
 Any[Any[12, 26, 66, 102, 265, 270, 275, 285, 294, 297  …  49888, 49891, 49904, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[587, 971, 1128, 1625, 1625, 1854, 2632, 3456, 4297, 4815  …  46305, 46575, 46575, 46642, 46938, 47121, 47575, 47575, 47575, 47622], Any[529, 654, 1128, 1166, 1196, 1776, 2099, 2632, 2826, 3117  …  47121, 47162, 47288, 47575, 47694, 47794, 48357, 48422, 48887, 49114], Any[3, 4, 10, 17, 30, 38, 43, 49, 63, 66  …  49863, 49869, 49882, 49883, 49905, 49943, 49963, 49965, 49986, 49987]]
 Any[Any[788, 869, 1112, 1188, 3002, 4000, 4000, 4141, 4141, 4247  …  45827, 45904, 46030, 47101, 47101, 48328, 49007, 49007, 49048, 49598], Any[316, 355, 359, 380, 388, 389, 396, 429, 555, 558  …  49301, 49312, 49359, 49463, 49466, 49565, 49634, 49727, 49744, 49969], Any[184, 325, 538, 667, 788, 790, 869, 1112, 1178, 1188  …  48915, 49007, 49105, 49244, 49305, 49334, 49598, 49629, 49765, 49796], Any[5, 8, 12, 14, 20, 22, 24, 28, 29, 32  …  49988, 49990, 49993, 49994, 49995, 49996, 49997, 49998, 49999, 50000]]
 Any[Any[260, 275, 294, 296, 314, 317, 341, 384, 457, 529  …  49550, 49567, 49570, 49596, 49716, 49860, 49918, 49971, 49975, 49987], Any[262, 262, 681, 928, 1835, 3791, 3806, 3806, 3888, 4576  …  42729, 43024, 43419, 43582, 44296, 44361, 44975, 45908, 46570, 46861], Any[681, 3443, 3806, 3888, 4970, 5038, 5120, 5132, 5210, 5330  …  45134, 45177, 45471, 45497, 45908, 46016, 46611, 46861, 46922, 49716], Any[260, 262, 267, 269, 272, 273, 281, 282, 289, 294  …  49173, 49301, 49415, 49423, 49461, 49478, 49619, 49715, 49813, 49840]]
 ⋮
 Any[Any[12, 26, 66, 102, 265, 270, 275, 285, 294, 297  …  49888, 49891, 49904, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[270, 302, 322, 782, 2427, 3947, 3975, 4014, 4613, 4895  …  47100, 47413, 47430, 47505, 47538, 47539, 47786, 48437, 49197, 49966], Any[701, 782, 1400, 2571, 2796, 2796, 3214, 3869, 3869, 3975  …  45902, 45902, 46594, 46861, 46885, 46904, 46904, 47425, 47505, 47538], Any[12, 26, 66, 98, 102, 265, 270, 275, 285, 294  …  49904, 49912, 49915, 49917, 49929, 49940, 49962, 49966, 49980, 49989]]
 Any[Any[45, 134, 165, 231, 234, 324, 353, 378, 378, 392  …  45456, 45672, 45741, 46343, 46861, 46886, 47249, 48997, 49882, 49912], Any[25, 31, 32, 37, 52, 62, 66, 74, 91, 92  …  49972, 49974, 49976, 49978, 49989, 49990, 49993, 49994, 49996, 49998], Any[134, 165, 353, 353, 515, 515, 612, 612, 627, 627  …  44008, 44194, 45394, 46419, 46687, 46687, 46861, 46886, 47923, 48981], Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989]]
 Any[Any[660, 788, 1170, 1606, 2646, 2813, 2843, 3162, 3724, 3935  …  46938, 47026, 47222, 47336, 47365, 47934, 49037, 49356, 49530, 49899], Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[583, 1101, 1264, 1298, 1606, 2167, 2242, 2813, 3071, 3281  …  42533, 42533, 44295, 44832, 45377, 45399, 46305, 46305, 46938, 49037], Any[12, 26, 66, 98, 102, 265, 270, 275, 285, 294  …  49904, 49912, 49915, 49917, 49929, 49940, 49962, 49966, 49980, 49989]]
 Any[Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[13, 26, 32, 42, 45, 89, 94, 134, 150, 157  …  49877, 49882, 49905, 49912, 49915, 49917, 49940, 49962, 49966, 49989], Any[42, 345, 510, 616, 865, 1053, 1214, 1286, 1808, 1844  …  46040, 46097, 46168, 46793, 46804, 46887, 47119, 47990, 49905, 49912], Any[42, 42, 89, 345, 353, 616, 1808, 2090, 2383, 2393  …  35853, 35996, 36747, 38005, 39380, 41488, 45077, 46097, 46821, 49694]]
 Any[Any[2028, 2463, 3175, 3175, 3526, 3767, 4234, 4234, 4688, 5119  …  45833, 45970, 47415, 47650, 48211, 48211, 48211, 48344, 48443, 49469], Any[12, 26, 66, 98, 102, 265, 270, 275, 285, 294  …  49904, 49912, 49915, 49917, 49929, 49940, 49962, 49966, 49980, 49989], Any[2, 3, 7, 9, 11, 12, 15, 16, 18, 19  …  49963, 49967, 49968, 49975, 49978, 49982, 49983, 49984, 49985, 49990], Any[130, 300, 1310, 1364, 1894, 1955, 1984, 2028, 2030, 2463  …  48335, 48339, 48442, 48849, 49331, 49469, 49486, 49630, 49724, 49824]]
 Any[Any[273, 446, 785, 2468, 4235, 4499, 4518, 4923, 5112, 5135  …  46921, 47618, 47775, 48090, 48201, 48218, 48382, 49226, 49861, 49981], Any[446, 653, 1097, 1097, 1237, 1237, 2145, 2145, 2468, 3758  …  46788, 47766, 48218, 48581, 49209, 49226, 49226, 49797, 49861, 49861], Any[25, 31, 32, 37, 52, 62, 66, 74, 91, 92  …  49972, 49974, 49976, 49978, 49989, 49990, 49993, 49994, 49996, 49998], Any[3, 12, 46, 224, 260, 262, 269, 272, 273, 281  …  49862, 49863, 49864, 49876, 49897, 49937, 49949, 49974, 49981, 49992]]
 Any[Any[122, 521, 734, 743, 938, 1043, 1053, 1100, 1133, 1159  …  48942, 48962, 49033, 49056, 49082, 49280, 49282, 49602, 49696, 49813], Any[293, 613, 659, 702, 1043, 1694, 1928, 2406, 2608, 2856  …  45432, 45660, 47011, 47426, 47577, 47577, 48119, 48237, 49637, 49648], Any[293, 613, 659, 702, 722, 906, 939, 1234, 1249, 1270  …  48119, 48133, 48453, 48974, 49392, 49414, 49489, 49637, 49648, 49931], Any[5, 8, 12, 14, 20, 22, 24, 28, 29, 32  …  49988, 49990, 49993, 49994, 49995, 49996, 49997, 49998, 49999, 50000]]
 Any[Any[49, 162, 274, 308, 486, 503, 1556, 1779, 1807, 2155  …  45631, 46025, 46069, 46099, 46537, 46848, 46928, 47702, 48696, 49179], Any[3, 4, 10, 17, 30, 38, 43, 49, 63, 66  …  49863, 49869, 49882, 49883, 49905, 49943, 49963, 49965, 49986, 49987], Any[49, 308, 1617, 1617, 1630, 1630, 1630, 1700, 1830, 1850  …  43148, 43342, 43656, 43747, 43747, 44123, 44680, 44844, 46025, 46099], Any[2, 7, 11, 12, 18, 19, 20, 22, 28, 35  …  48959, 49335, 49481, 49730, 49865, 49869, 49911, 49934, 49952, 49963]]
 Any[Any[64, 137, 287, 831, 1090, 1509, 1784, 2158, 2275, 2484  …  48067, 48328, 48450, 48596, 49018, 49106, 49230, 49583, 49701, 49977], Any[25, 31, 32, 37, 52, 62, 66, 74, 91, 92  …  49972, 49974, 49976, 49978, 49989, 49990, 49993, 49994, 49996, 49998], Any[5, 8, 12, 14, 20, 22, 24, 28, 29, 32  …  49988, 49990, 49993, 49994, 49995, 49996, 49997, 49998, 49999, 50000], Any[25, 32, 137, 1784, 2329, 2329, 2602, 3332, 3553, 3553  …  47511, 47666, 47679, 47921, 47966, 48057, 48156, 49018, 49783, 49791]]
 Any[Any[10, 13, 14, 15, 21, 25, 27, 30, 36, 40  …  49806, 49835, 49839, 49857, 49877, 49884, 49889, 49926, 49930, 49943], Any[101, 157, 161, 220, 351, 514, 523, 544, 601, 631  …  46117, 46390, 46480, 46559, 46615, 46908, 47297, 47419, 48801, 49276], Any[13, 26, 42, 45, 132, 134, 150, 165, 172, 210  …  49624, 49661, 49758, 49882, 49905, 49915, 49917, 49971, 49975, 49979], Any[544, 884, 1152, 1516, 1601, 1772, 2036, 2117, 2143, 2143  …  41580, 41719, 42068, 42461, 43031, 43179, 46117, 46887, 47505, 48289]]
 Any[Any[10, 133, 306, 347, 475, 525, 796, 971, 1148, 1148  …  45198, 45198, 45859, 45859, 46242, 46901, 48079, 48176, 48509, 48677], Any[306, 475, 576, 651, 796, 822, 857, 971, 1267, 1344  …  46916, 47320, 47555, 48176, 48509, 48677, 49066, 49145, 49179, 49965], Any[10, 13, 14, 15, 21, 25, 27, 30, 36, 40  …  49806, 49835, 49839, 49857, 49877, 49884, 49889, 49926, 49930, 49943], Any[3, 4, 10, 17, 30, 38, 43, 49, 63, 66  …  49863, 49869, 49882, 49883, 49905, 49943, 49963, 49965, 49986, 49987]]
 Any[Any[4, 49, 91, 210, 237, 242, 318, 327, 353, 358  …  48377, 48507, 48844, 48846, 49278, 49331, 49390, 49444, 49667, 49764], Any[654, 654, 1302, 2319, 2319, 3767, 3961, 4203, 4547, 4912  …  46828, 47012, 47179, 47441, 47614, 48594, 49652, 49817, 49817, 49817], Any[12, 26, 66, 98, 102, 265, 270, 275, 285, 294  …  49904, 49912, 49915, 49917, 49929, 49940, 49962, 49966, 49980, 49989], Any[285, 324, 654, 654, 834, 1103, 1128, 1302, 1654, 1654  …  48422, 48460, 48516, 48594, 49114, 49159, 49652, 49678, 49817, 49877]]

Algortimo Melding \((ME)\)

Baeza-Yates (2004, 2005) señala al \(\textit{merging}\) como uno de los métodos clásicos para calcular la intersección de conjuntos ordenados, con una complejidad como se muestra:

Complejidad:

Baeza-Yates (2004, 2005) destaca que la fusión tradicional (como la que se usa en el algoritmo MergeSort) requiere \(O(n+m)\) comparaciones en el peor caso, donde \(n\) y \(m\) son los tamaños de los dos conjuntos ordenados \(D\) y \(Q\). Esto es óptimo cuando \(n≈m\), pero ineficiente cuando \(n≫m\) (es decir; intersectar una lista grande con una pequeña).

Se tiene que tener en consideración que una de las limitantes de este algoritmo es siempre inspecciona todos los elementos de ambas listas, incluso si no hay superposición.

Plan de implementación

1. Se definirá una función base para realizar la intersección de dos conjuntos por \(ME\)
2. Se definirán funciones de soporte que nos permitirán procesar los datos en función del tipo de conjunto ( Para pares, tripletas y cuadruples de listas)
3. Se definirá una función para computar todas las intersecciones. Esta, a su vez, generará un reporte con métricas para medir el desempeño del algoritmo, como; tiempo de ejecución, número de comparaciones y las longitudes de las intersecciones para cada conjunto de datos.

# Función base para intersección de dos listas
function intersect_two!(result, A, B)
    i = j = 1
    m, n = length(A), length(B)
    
    @inbounds while i <= m && j <= n
        a, b = A[i], B[j]
        if a == b
            push!(result, a)
            i += 1
            j += 1
        elseif a < b
            i += 1
        else
            j += 1
        end
    end
    
    result
end  

intersect_two! (generic function with 1 method)

# Función para pares de listas (Conjunto A) 
function intersect_pairs(pairs_list)
    results = []
    total_comparisons = 0
    total_time = 0.0
    total_result_length = 0  
    
    for (A, B) in pairs_list
        result = Int[]
        time_taken = @elapsed begin
            comparisons = intersect_two_count!(result, A, B)
        end
        
        push!(results, IntersectionResult(result, comparisons, time_taken))
        total_comparisons += comparisons
        total_time += time_taken
        total_result_length += length(result)  # Sumamos la longitud de este resultado
    end
    
    (results=results, total_comparisons=total_comparisons, 
     total_time=total_time, total_result_length=total_result_length)
end

# Función para tripletas de listas (Conjunto B) 
function intersect_triplets(triplets_list)
    results = []
    total_comparisons = 0
    total_time = 0.0
    total_result_length = 0  
    
    for (A, B, C) in triplets_list
        temp = Int[]
        time_taken1 = @elapsed comp1 = intersect_two_count!(temp, A, B)
        
        result = Int[]
        time_taken2 = @elapsed comp2 = intersect_two_count!(result, temp, C)
        
        total_comp = comp1 + comp2
        total_time_taken = time_taken1 + time_taken2
        
        push!(results, IntersectionResult(result, total_comp, total_time_taken))
        total_comparisons += total_comp
        total_time += total_time_taken
        total_result_length += length(result)  # Sumamos la longitud de este resultado
    end
    
    (results=results, total_comparisons=total_comparisons,
     total_time=total_time, total_result_length=total_result_length)
end

# Función para cuádruples de listas (Conjunto C) 
function intersect_quadruples(quadruples_list)
    results = []
    total_comparisons = 0
    total_time = 0.0
    total_result_length = 0  
    
    for (A, B, C, D) in quadruples_list
        temp1 = Int[]
        time_taken1 = @elapsed comp1 = intersect_two_count!(temp1, A, B)
        
        temp2 = Int[]
        time_taken2 = @elapsed comp2 = intersect_two_count!(temp2, temp1, C)
        
        result = Int[]
        time_taken3 = @elapsed comp3 = intersect_two_count!(result, temp2, D)
        
        total_comp = comp1 + comp2 + comp3
        total_time_taken = time_taken1 + time_taken2 + time_taken3
        
        push!(results, IntersectionResult(result, total_comp, total_time_taken))
        total_comparisons += total_comp
        total_time += total_time_taken
        total_result_length += length(result)  # Sumamos la longitud de este resultado
    end
    
    (results=results, total_comparisons=total_comparisons,
     total_time=total_time, total_result_length=total_result_length)
end

intersect_quadruples (generic function with 1 method)

# Función general 
function compute_all_intersections(pairs_A, triplets_B, quadruples_C)
    println("Procesando Conjunto A (pares)...")
    result_A = intersect_pairs(pairs_A)
    
    println("\nProcesando Conjunto B (tripletas)...")
    result_B = intersect_triplets(triplets_B)
    
    println("\nProcesando Conjunto C (cuádruples)...")
    result_C = intersect_quadruples(quadruples_C)
    
    # Crear reporte resumido actualizado
    report = """
    RESUMEN DE RESULTADOS:
    
    CONJUNTO A (PARES):
    - Total de pares procesados: $(length(pairs_A))
    - Comparaciones totales: $(result_A.total_comparisons)
    - Tiempo total (s): $(round(result_A.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_A.total_result_length)
    - Longitud promedio por resultado: $(round(result_A.total_result_length/length(pairs_A), digits=2))
    
    CONJUNTO B (TRIPLETAS):
    - Total de tripletas procesadas: $(length(triplets_B))
    - Comparaciones totales: $(result_B.total_comparisons)
    - Tiempo total (s): $(round(result_B.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_B.total_result_length)
    - Longitud promedio por resultado: $(round(result_B.total_result_length/length(triplets_B), digits=2))
    
    CONJUNTO C (CUÁDRUPLES):
    - Total de cuádruples procesadas: $(length(quadruples_C))
    - Comparaciones totales: $(result_C.total_comparisons)
    - Tiempo total (s): $(round(result_C.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_C.total_result_length)
    - Longitud promedio por resultado: $(round(result_C.total_result_length/length(quadruples_C), digits=2))
    """
    
    println(report)
    
    (result_A, result_B, result_C, report)
end

compute_all_intersections (generic function with 1 method)

compute_all_intersections(A, B, C)

Procesando Conjunto A (pares)...

Procesando Conjunto B (tripletas)...

Procesando Conjunto C (cuádruples)...
RESUMEN DE RESULTADOS:

CONJUNTO A (PARES):
- Total de pares procesados: 200
- Comparaciones totales: 3238899
- Tiempo total (s): 0.072497
- Suma de longitudes de resultados: 3627
- Longitud promedio por resultado: 18.14

CONJUNTO B (TRIPLETAS):
- Total de tripletas procesadas: 200
- Comparaciones totales: 5276587
- Tiempo total (s): 0.131184
- Suma de longitudes de resultados: 4723
- Longitud promedio por resultado: 23.62

CONJUNTO C (CUÁDRUPLES):
- Total de cuádruples procesadas: 200
- Comparaciones totales: 4261034
- Tiempo total (s): 0.221043
- Suma de longitudes de resultados: 1550
- Longitud promedio por resultado: 7.75

((results = Any[IntersectionResult([6323, 12498], 42938, 0.0009946), IntersectionResult([21109, 37491, 38824, 40060, 43252, 48615], 6402, 0.0001619), IntersectionResult([10441], 4725, 0.000119), IntersectionResult([227, 2802, 3122, 3220, 35566, 38126, 38679, 39587, 39971, 40488, 40976, 41053, 41367, 46954, 46955, 49582], 8930, 0.0002035), IntersectionResult([4850, 11205, 20287, 23256, 29729], 6621, 0.0001474), IntersectionResult([4399, 5450, 10487, 25589], 6156, 0.0001411), IntersectionResult([5194, 6030, 7380, 7932, 12040, 12583, 14811], 4615, 0.0001061), IntersectionResult([2729, 10222, 13543, 23966, 29304, 36381, 42776], 8127, 0.0001835), IntersectionResult([337, 573, 676, 782, 1175, 1196, 1279, 3126, 3767, 4358  …  42994, 43453, 43723, 44271, 44433, 44447, 44492, 44639, 45051, 47320], 78056, 0.0017294), IntersectionResult([9008, 15039, 20863, 20870, 24643, 31997, 32817], 5891, 0.0001338)  …  IntersectionResult([533, 2342, 4110, 6373, 6845, 11165, 14145, 14159, 14192, 14217  …  36901, 37631, 39409, 42585, 42596, 45398, 45528, 47346, 47669, 47924], 29106, 0.0005912), IntersectionResult([12189, 39789, 40618], 4777, 0.0001004), IntersectionResult([1851, 2533, 2756, 2814, 8897, 17536], 4674, 9.67e-5), IntersectionResult([2673, 3189, 3275, 3565, 3729, 3897, 4486, 5944, 9708, 9731  …  40963, 41278, 41469, 41530, 43418, 43965, 47263, 48515, 49005, 49175], 81246, 0.001686), IntersectionResult([5917, 5953, 6004, 6416, 7946, 9841, 12491, 22944, 46097], 4757, 0.0001015), IntersectionResult([613, 1244, 1871, 2271, 2893, 2908, 3296, 3559, 7308, 8196  …  33616, 35432, 36646, 37509, 39507, 41946, 43243, 44808, 44973, 49738], 42755, 0.0008775), IntersectionResult([15521, 21090, 22638], 7413, 0.0001538), IntersectionResult([1097, 2487, 2503, 2770, 8216, 17669, 42376], 7863, 0.0001666), IntersectionResult([5363, 8739, 12242, 14529, 24924], 8025, 0.0001737), IntersectionResult([1686, 6265, 9541, 14340, 43083, 43183, 44310, 44481, 46206], 8181, 0.0001718)], total_comparisons = 3238899, total_time = 0.0724968, total_result_length = 3627), (results = Any[IntersectionResult([5239, 6162, 6806, 7411, 8951, 11279], 9652, 0.0002813), IntersectionResult([5204, 5250, 6571, 8505, 21631, 30697, 36071], 46257, 0.0010402), IntersectionResult([585, 1097, 2368, 8929, 11134, 11776, 14196, 14258, 17611, 24256, 26851, 27931, 37075, 37350, 37463, 49091], 49451, 0.0011871), IntersectionResult([4961, 20059, 40091, 40106], 14690, 0.00041190000000000004), IntersectionResult([46886], 8509, 0.0002148), IntersectionResult([314, 384, 675, 759, 2559, 3509, 4149, 4812, 5190, 5210  …  45352, 45363, 45413, 45425, 45841, 46153, 47235, 48086, 49596, 49716], 47791, 0.0011094), IntersectionResult([4273, 4702, 5081, 5122, 5145, 5311, 5330, 5366, 6409, 6532  …  45007, 45284, 45330, 45734, 46040, 46048, 46127, 46751, 47542, 49570], 35306, 0.0008248000000000001), IntersectionResult([297, 731, 743, 777, 936, 977, 1214, 1461, 1468, 1617  …  44421, 45059, 45357, 45480, 46861, 47523, 49114, 49404, 49915, 49917], 6700, 0.000281), IntersectionResult([656, 745, 1256, 1783, 1948, 2080, 2156, 2202, 2624, 2749  …  46040, 47368, 48106, 48710, 48928, 48967, 49076, 49214, 49229, 49593], 110930, 0.0026601999999999997), IntersectionResult([4997, 5223, 5439, 5564, 5655, 5797, 6010, 6028, 6056, 6186  …  6591, 6616, 6675, 6811, 7033, 10701, 12741, 17305, 30237, 34502], 9868, 0.0002559)  …  IntersectionResult([291, 738, 1196, 1234, 2041, 2050, 6757, 11740, 14447, 15428, 38763, 49954], 50757, 0.0014661000000000001), IntersectionResult([15287, 42767], 14094, 0.00036950000000000004), IntersectionResult([2316, 12774, 12838, 18103, 23914, 27715, 40838, 44982], 12304, 0.0003034), IntersectionResult([275, 1494, 1979, 2508, 19085, 21630, 28195, 36747], 12335, 0.0003372), IntersectionResult([2703, 6305, 7111, 15456, 46674], 12994, 0.0003548), IntersectionResult([36813, 45326], 32195, 0.0007241000000000001), IntersectionResult([7418, 18463, 23704, 26896, 30677, 30977, 35574, 35602, 36832, 39841, 40630], 70694, 0.0020865000000000002), IntersectionResult([2909, 13712, 22475, 23606, 31618, 35409, 38102, 38625, 42221, 48249], 34057, 0.0007616), IntersectionResult([15517, 33999], 30980, 0.0009181), IntersectionResult([1196, 2728, 2991, 3126, 3518, 5661, 5911, 6009, 6205, 6470  …  9513, 10155, 10441, 11787, 12583, 14361, 16645, 17346, 21983, 29133], 8393, 0.0002117)], total_comparisons = 5276587, total_time = 0.13118379999999996, total_result_length = 4723), (results = Any[IntersectionResult(Int64[], 9854, 0.0002651), IntersectionResult([41697, 41975], 27522, 0.0008225999999999999), IntersectionResult([1192, 2530, 5655, 5766, 5828, 6462, 6515, 6811, 7041, 7253  …  44370, 44477, 44663, 45924, 46455, 46561, 46931, 47846, 47942, 48825], 88125, 0.002637), IntersectionResult([2309, 2334, 2826], 9895, 0.0002759), IntersectionResult([4977, 5111, 9073, 9952], 7130, 0.0002248), IntersectionResult([2316, 5316, 5711, 6001, 7323, 8792, 9122, 9960, 10143, 10804, 11383, 11783, 16430, 17256, 17517, 20413, 20787, 32079, 46528], 10093, 0.0002787), IntersectionResult([201, 443, 1903, 2568, 3571, 8904, 12928, 18489, 21396, 21644, 27378], 20364, 0.0006012), IntersectionResult([9117, 14353, 41555], 9788, 0.0002634), IntersectionResult([8289, 12366, 16834, 31510, 33936], 10551, 0.00027289999999999997), IntersectionResult(Int64[], 2827, 6.7e-5)  …  IntersectionResult([5743, 6042, 6720, 9994, 10879, 10898, 11978, 17668, 18037, 18504, 28427, 45377], 11336, 0.00028379999999999996), IntersectionResult([42, 345, 616, 1808, 2090, 2795, 3133, 3912, 5039, 5240  …  23904, 26098, 26870, 28427, 29213, 33474, 35853, 35996, 36747, 46097], 7105, 0.00024270000000000002), IntersectionResult(Int64[], 35896, 0.0009747), IntersectionResult([11327, 32778, 46318, 48218, 49861], 20305, 0.0005597), IntersectionResult([2406, 4010, 23082, 25325, 37211, 41584, 42416, 44598, 44599], 42430, 0.0011412), IntersectionResult([2466, 23191, 24711, 27172, 38942], 10897, 0.0002561), IntersectionResult([15601, 22028, 27245, 30117, 30251, 47966, 49018], 56039, 0.001433), IntersectionResult([28029], 10867, 0.0002491), IntersectionResult([1530, 2956, 22833, 39553], 13776, 0.00037810000000000003), IntersectionResult(Int64[], 8461, 0.0002175)], total_comparisons = 4261034, total_time = 0.2210433000000001, total_result_length = 1550), "RESUMEN DE RESULTADOS:\n\nCONJUNTO A (PARES):\n- Total de pares procesados: 200\n- Comparaciones totales: 3238899\n- Tiempo total (s): 0.072497\n- Suma de longitudes de resultados: 3627\n- Longitud promedio por resultado: 18.14\n\nCONJUNTO B (TRIPLETAS):\n- Total de tripletas procesadas: 200\n- Comparaciones totales: 5276587\n- Tiempo total (s): 0.131184\n- Suma de longitudes de resultados: 4723\n- Longitud promedio por resultado: 23.62\n\nCONJUNTO C (CUÁDRUPLES):\n- Total de cuádruples procesadas: 200\n- Comparaciones totales: 4261034\n- Tiempo total (s): 0.221043\n- Suma de longitudes de resultados: 1550\n- Longitud promedio por resultado: 7.75\n")

Algortimo Baeza-Yates \((BY)\)

Baeza-Yates (2004) propone un algoritmo innovador que optimiza la intersección de conjuntos, superando en eficiencia a métodos tradicionales como la fusión lineal (merging) o la búsqueda binaria múltiple, es especialmente útil en escenarios donde los tamaños de los conjuntos difieren significativamente. Un algoritmo clásico como la fusión lineal tiene complejidad \(O(n+m)\) , lo que resulta ineficiente cuando \(n≫m\).

El algoritmo combina estrategias de divide y vencerás y búsqueda binaria para:

1. Adaptarse dinámicamente al tamaño de los conjuntos, priorizando la lista más pequeña (Q) para minimizar comparaciones.

2. Recursivamente dividir el problema alrededor de la mediana de Q, buscando su posición en D mediante búsqueda binaria.

3. Descartar rápidamente subconjuntos sin superposición, reduciendo el espacio de búsqueda

Complejidad:

• Peor caso: \(O(mlogn)\) (similar a \(m\) búsquedas binarias)

• Caso promedio: Mejor que \(m+n\) (merge) cuando \(n≫m\).

• Mejor caso: \(O(log^2n)\) (si no hay intersección)

Plan de implementación

1. Para este reporte se además de la búsqueda binaria propuesta en el algoritmo Baeza-Yates (2004), se buscará parametrizar \(BY\) para los siguientes algoritmos de búsqueda: Búsqueda no acotada \(B_{1}\) (Exponencial) y Búsqueda no acotada \(B_{2}\) (Doblemente doblada). En ese sentido, en primer lugar, se definirán las funciones de búsqueda con las que se parametrizará el algoritmo.
2. Se definirá una función base para realizar la intersección de dos conjuntos por \(BY\)
3. Se definirán funciones de soporte que nos permitirán procesar los datos en función del tipo de conjunto ( Para pares, tripletas y cuadruples de listas)
4. Se definirá una función para computar todas las intersecciones. Esta, a su vez, generará un reporte con métricas para medir el desempeño del algoritmo, como; tiempo de ejecución, número de comparaciones y las longitudes de las intersecciones para cada conjunto de datos. También permitirá indicar el nombre del algoritmo de búsqueda con el que se realizará el ordenamiento.

#Definición de los algoritmos de búsqueda para la parametrización de BY

# Búsqueda binaria
function binary_search(arr::Vector{Int}, x::Int, start::Int, counter::Base.RefValue{Int}=Ref(0))
    low, high = start, length(arr)
    while low <= high
        mid = (low + high) ÷ 2
        counter[] += 1
        if arr[mid] == x
            return mid
        elseif arr[mid] < x
            low = mid + 1
        else
            high = mid - 1
        end
    end
    return low
end

# Búsqueda exponencial(B1)
function exponential_search(arr::Vector{Int}, x::Int, start::Int, counter::Base.RefValue{Int}=Ref(0))
    n = length(arr)
    if start > n
        return n + 1
    end
    if arr[start] == x
        counter[] += 1
        return start
    end
    i = 1
    while (start + i <= n) && (arr[start + i] < x)
        counter[] += 1
        i *= 2
    end
    low = start + (i ÷ 2)
    high = min(start + i, n)
    while low <= high
        mid = (low + high) ÷ 2
        counter[] += 1
        if arr[mid] == x
            return mid
        elseif arr[mid] < x
            low = mid + 1
        else
            high = mid - 1
        end
    end
    return low
end

# Búsqueda doblemente doblada (B2)
function doubling_search(arr::Vector{Int}, x::Int, start::Int, counter::Base.RefValue{Int}=Ref(0))
    n = length(arr)
    idx = start

    if idx <= n && arr[idx] == x
        counter[] += 1
        return idx
    end

    i = 1
    while (idx + i <= n) && (arr[idx + i] < x)
        counter[] += 1
        i *= 2
    end

    low = idx + (i ÷ 2)
    high = min(idx + i, n)

    while low <= high
        mid = (low + high) ÷ 2
        counter[] += 1
        if arr[mid] == x
            return mid
        elseif arr[mid] < x
            low = mid + 1
        else
            high = mid - 1
        end
    end

    return low
end

doubling_search (generic function with 2 methods)

function baezayates!(
    output::Vector{Int},
    A::Vector{Int}, a_sp::Int, a_ep::Int,
    B::Vector{Int}, b_sp::Int, b_ep::Int,
    findpos::Function,
    comps::Base.RefValue{Int}
)
    (a_ep < a_sp || b_ep < b_sp) && return output
    imedian = (a_sp + a_ep) ÷ 2
    median = A[imedian]
    medpos = min(findpos(B, median, b_sp, comps), b_ep)

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

function baezayates!(output::Vector{Int}, A::Vector{Int}, B::Vector{Int}, findpos::Function)
    comps = Ref(0)
    baezayates!(output, A, 1, length(A), B, 1, length(B), findpos, comps)
    return comps[]
end

baezayates! (generic function with 7 methods)

struct IntersectionResultby
    result::Vector{Int}
    comparisons::Int
    time_taken::Float64
end

function intersect_baeza_yates_recursive!(result::Vector{Int}, lists::Vector{Vector{Int}}, findpos::Function)
    comparisons = 0
    sorted_lists = sort(lists, by=length)
    base_list = sorted_lists[1]
    for i in 2:length(sorted_lists)
        new_result = Int[]
        comps = baezayates!(new_result, base_list, sorted_lists[i], findpos)
        comparisons += comps
        base_list = new_result
        if isempty(base_list)
            break
        end
    end
    append!(result, base_list)
    return comparisons
end

function intersect_baeza_groups_general(groups, findpos::Function)
    results = []
    total_comparisons = 0
    total_time = 0.0
    total_result_length = 0

    for group in groups
        result = Int[]
        time_taken = @elapsed begin
            comparisons = intersect_baeza_yates_recursive!(result, [Vector{Int}(x) for x in group], findpos)
            total_comparisons += comparisons
            total_result_length += length(result)
        end
        push!(results, IntersectionResultby(result, comparisons, time_taken))
        total_time += time_taken
    end

    return (
        results=results,
        total_comparisons=total_comparisons,
        total_time=total_time,
        total_result_length=total_result_length
    )
end

intersect_baeza_groups_general (generic function with 1 method)

# Función general para procesar todos los conjuntos y generar reporte
function compute_all_intersections_baeza_custom(pairs_A, triplets_B, quadruples_C, findpos::Function, metodo::String)
    println("Procesando Conjunto A (pares) con Baeza-Yates y búsqueda $metodo...")
    result_A = intersect_baeza_groups_general(pairs_A, findpos)

    println("\nProcesando Conjunto B (tripletas) con Baeza-Yates y búsqueda $metodo...")
    result_B = intersect_baeza_groups_general(triplets_B, findpos)

    println("\nProcesando Conjunto C (cuádruples) con Baeza-Yates y búsqueda $metodo...")
    result_C = intersect_baeza_groups_general(quadruples_C, findpos)

    report = """
    RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA $metodo):

    CONJUNTO A (PARES):
    - Total de pares procesados: $(length(pairs_A))
    - Comparaciones totales: $(result_A.total_comparisons)
    - Tiempo total (s): $(round(result_A.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_A.total_result_length)
    - Longitud promedio por resultado: $(round(result_A.total_result_length / max(length(pairs_A),1), digits=2))

    CONJUNTO B (TRIPLETAS):
    - Total de tripletas procesadas: $(length(triplets_B))
    - Comparaciones totales: $(result_B.total_comparisons)
    - Tiempo total (s): $(round(result_B.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_B.total_result_length)
    - Longitud promedio por resultado: $(round(result_B.total_result_length / max(length(triplets_B),1), digits=2))

    CONJUNTO C (CUÁDRUPLES):
    - Total de cuádruples procesadas: $(length(quadruples_C))
    - Comparaciones totales: $(result_C.total_comparisons)
    - Tiempo total (s): $(round(result_C.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_C.total_result_length)
    - Longitud promedio por resultado: $(round(result_C.total_result_length / max(length(quadruples_C),1), digits=2))
    """

    println(report)
    return (result_A, result_B, result_C, report)
end

compute_all_intersections_baeza_custom (generic function with 1 method)

compute_all_intersections_baeza_custom(A, B, C, binary_search, "Binaria")

Procesando Conjunto A (pares) con Baeza-Yates y búsqueda Binaria...

Procesando Conjunto B (tripletas) con Baeza-Yates y búsqueda Binaria...

Procesando Conjunto C (cuádruples) con Baeza-Yates y búsqueda Binaria...
RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA Binaria):

CONJUNTO A (PARES):
- Total de pares procesados: 200
- Comparaciones totales: 236662
- Tiempo total (s): 0.687597
- Suma de longitudes de resultados: 3627
- Longitud promedio por resultado: 18.14

CONJUNTO B (TRIPLETAS):
- Total de tripletas procesadas: 200
- Comparaciones totales: 478929
- Tiempo total (s): 0.305697
- Suma de longitudes de resultados: 4723
- Longitud promedio por resultado: 23.62

CONJUNTO C (CUÁDRUPLES):
- Total de cuádruples procesadas: 200
- Comparaciones totales: 270415
- Tiempo total (s): 0.244972
- Suma de longitudes de resultados: 1550
- Longitud promedio por resultado: 7.75

((results = Any[IntersectionResultby([6323, 12498], 1584, 0.1633762), IntersectionResultby([21109, 37491, 38824, 40060, 43252, 48615], 1179, 0.000518), IntersectionResultby([10441], 935, 0.0003726), IntersectionResultby([227, 2802, 3122, 3220, 35566, 38126, 38679, 39587, 39971, 40488, 40976, 41053, 41367, 46954, 46955, 49582], 1091, 0.0008286), IntersectionResultby([4850, 11205, 20287, 23256, 29729], 1148, 0.0006772), IntersectionResultby([4399, 5450, 10487, 25589], 1324, 0.0005932), IntersectionResultby([5194, 6030, 7380, 7932, 12040, 12583, 14811], 1122, 0.0002404), IntersectionResultby([2729, 10222, 13543, 23966, 29304, 36381, 42776], 1071, 0.0007421), IntersectionResultby([337, 573, 676, 782, 1175, 1196, 1279, 3126, 3767, 4358  …  42994, 43453, 43723, 44271, 44433, 44447, 44492, 44639, 45051, 47320], 1710, 0.0055981), IntersectionResultby([9008, 15039, 20863, 20870, 24643, 31997, 32817], 1131, 0.0003867)  …  IntersectionResultby([533, 2342, 4110, 6373, 6845, 11165, 14145, 14159, 14192, 14217  …  36901, 37631, 39409, 42585, 42596, 45398, 45528, 47346, 47669, 47924], 1499, 0.0014745), IntersectionResultby([12189, 39789, 40618], 1061, 0.0002145), IntersectionResultby([1851, 2533, 2756, 2814, 8897, 17536], 953, 0.0002063), IntersectionResultby([2673, 3189, 3275, 3565, 3729, 3897, 4486, 5944, 9708, 9731  …  40963, 41278, 41469, 41530, 43418, 43965, 47263, 48515, 49005, 49175], 1553, 0.0039977), IntersectionResultby([5917, 5953, 6004, 6416, 7946, 9841, 12491, 22944, 46097], 1106, 0.0002573), IntersectionResultby([613, 1244, 1871, 2271, 2893, 2908, 3296, 3559, 7308, 8196  …  33616, 35432, 36646, 37509, 39507, 41946, 43243, 44808, 44973, 49738], 1446, 0.0025071), IntersectionResultby([15521, 21090, 22638], 1229, 0.000356), IntersectionResultby([1097, 2487, 2503, 2770, 8216, 17669, 42376], 1367, 0.0005921), IntersectionResultby([5363, 8739, 12242, 14529, 24924], 1067, 0.0007018), IntersectionResultby([1686, 6265, 9541, 14340, 43083, 43183, 44310, 44481, 46206], 1280, 0.0003812)], total_comparisons = 236662, total_time = 0.6875974000000001, total_result_length = 3627), (results = Any[IntersectionResultby([5239, 6162, 6806, 7411, 8951, 11279], 1383, 0.0027635), IntersectionResultby([5204, 5250, 6571, 8505, 21631, 30697, 36071], 2077, 0.0026191), IntersectionResultby([585, 1097, 2368, 8929, 11134, 11776, 14196, 14258, 17611, 24256, 26851, 27931, 37075, 37350, 37463, 49091], 2772, 0.0029741), IntersectionResultby([4961, 20059, 40091, 40106], 1104, 0.001035), IntersectionResultby([46886], 1259, 0.0010802), IntersectionResultby([314, 384, 675, 759, 2559, 3509, 4149, 4812, 5190, 5210  …  45352, 45363, 45413, 45425, 45841, 46153, 47235, 48086, 49596, 49716], 5293, 0.0033613), IntersectionResultby([4273, 4702, 5081, 5122, 5145, 5311, 5330, 5366, 6409, 6532  …  45007, 45284, 45330, 45734, 46040, 46048, 46127, 46751, 47542, 49570], 3863, 0.0018482), IntersectionResultby([297, 731, 743, 777, 936, 977, 1214, 1461, 1468, 1617  …  44421, 45059, 45357, 45480, 46861, 47523, 49114, 49404, 49915, 49917], 2996, 0.0009311), IntersectionResultby([656, 745, 1256, 1783, 1948, 2080, 2156, 2202, 2624, 2749  …  46040, 47368, 48106, 48710, 48928, 48967, 49076, 49214, 49229, 49593], 5215, 0.0061996), IntersectionResultby([4997, 5223, 5439, 5564, 5655, 5797, 6010, 6028, 6056, 6186  …  6591, 6616, 6675, 6811, 7033, 10701, 12741, 17305, 30237, 34502], 1890, 0.0008448)  …  IntersectionResultby([291, 738, 1196, 1234, 2041, 2050, 6757, 11740, 14447, 15428, 38763, 49954], 3146, 0.0046778), IntersectionResultby([15287, 42767], 1993, 0.0007), IntersectionResultby([2316, 12774, 12838, 18103, 23914, 27715, 40838, 44982], 2980, 0.0006408), IntersectionResultby([275, 1494, 1979, 2508, 19085, 21630, 28195, 36747], 2474, 0.0007673), IntersectionResultby([2703, 6305, 7111, 15456, 46674], 1421, 0.0009011), IntersectionResultby([36813, 45326], 1928, 0.0021574), IntersectionResultby([7418, 18463, 23704, 26896, 30677, 30977, 35574, 35602, 36832, 39841, 40630], 2216, 0.003412), IntersectionResultby([2909, 13712, 22475, 23606, 31618, 35409, 38102, 38625, 42221, 48249], 3324, 0.0013682), IntersectionResultby([15517, 33999], 2026, 0.0018652), IntersectionResultby([1196, 2728, 2991, 3126, 3518, 5661, 5911, 6009, 6205, 6470  …  9513, 10155, 10441, 11787, 12583, 14361, 16645, 17346, 21983, 29133], 2412, 0.0007339)], total_comparisons = 478929, total_time = 0.30569720000000006, total_result_length = 4723), (results = Any[IntersectionResultby(Int64[], 1016, 0.0009319), IntersectionResultby([41697, 41975], 1162, 0.0015046), IntersectionResultby([1192, 2530, 5655, 5766, 5828, 6462, 6515, 6811, 7041, 7253  …  44370, 44477, 44663, 45924, 46455, 46561, 46931, 47846, 47942, 48825], 1953, 0.0066795), IntersectionResultby([2309, 2334, 2826], 1190, 0.0007235), IntersectionResultby([4977, 5111, 9073, 9952], 988, 0.0006293), IntersectionResultby([2316, 5316, 5711, 6001, 7323, 8792, 9122, 9960, 10143, 10804, 11383, 11783, 16430, 17256, 17517, 20413, 20787, 32079, 46528], 1330, 0.0006352), IntersectionResultby([201, 443, 1903, 2568, 3571, 8904, 12928, 18489, 21396, 21644, 27378], 1900, 0.0010753), IntersectionResultby([9117, 14353, 41555], 1214, 0.0007497), IntersectionResultby([8289, 12366, 16834, 31510, 33936], 1626, 0.0005161), IntersectionResultby(Int64[], 922, 0.000567)  …  IntersectionResultby([5743, 6042, 6720, 9994, 10879, 10898, 11978, 17668, 18037, 18504, 28427, 45377], 1176, 0.0006644), IntersectionResultby([42, 345, 616, 1808, 2090, 2795, 3133, 3912, 5039, 5240  …  23904, 26098, 26870, 28427, 29213, 33474, 35853, 35996, 36747, 46097], 1431, 0.0005418), IntersectionResultby(Int64[], 1088, 0.0018264), IntersectionResultby([11327, 32778, 46318, 48218, 49861], 1763, 0.0011444), IntersectionResultby([2406, 4010, 23082, 25325, 37211, 41584, 42416, 44598, 44599], 1432, 0.0026898), IntersectionResultby([2466, 23191, 24711, 27172, 38942], 1207, 0.0004806), IntersectionResultby([15601, 22028, 27245, 30117, 30251, 47966, 49018], 1281, 0.0025573), IntersectionResultby([28029], 1123, 0.0009668), IntersectionResultby([1530, 2956, 22833, 39553], 1924, 0.0007055), IntersectionResultby(Int64[], 1331, 0.0003632)], total_comparisons = 270415, total_time = 0.24497200000000013, total_result_length = 1550), "RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA Binaria):\n\nCONJUNTO A (PARES):\n- Total de pares procesados: 200\n- Comparaciones totales: 236662\n- Tiempo total (s): 0.687597\n- Suma de longitudes de resultados: 3627\n- Longitud promedio por resultado: 18.14\n\nCONJUNTO B (TRIPLETAS):\n- Total de tripletas procesadas: 200\n- Comparaciones totales: 478929\n- Tiempo total (s): 0.305697\n- Suma de longitudes de resultados: 4723\n- Longitud promedio por resultado: 23.62\n\nCONJUNTO C (CUÁDRUPLES):\n- Total de cuádruples procesadas: 200\n- Comparaciones totales: 270415\n- Tiempo total (s): 0.244972\n- Suma de longitudes de resultados: 1550\n- Longitud promedio por resultado: 7.75\n")

compute_all_intersections_baeza_custom(A, B, C, exponential_search, "Exponencial")

Procesando Conjunto A (pares) con Baeza-Yates y búsqueda Exponencial...

Procesando Conjunto B (tripletas) con Baeza-Yates y búsqueda Exponencial...

Procesando Conjunto C (cuádruples) con Baeza-Yates y búsqueda Exponencial...
RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA Exponencial):

CONJUNTO A (PARES):
- Total de pares procesados: 200
- Comparaciones totales: 229942
- Tiempo total (s): 0.138168
- Suma de longitudes de resultados: 3627
- Longitud promedio por resultado: 18.14

CONJUNTO B (TRIPLETAS):
- Total de tripletas procesadas: 200
- Comparaciones totales: 400028
- Tiempo total (s): 0.115626
- Suma de longitudes de resultados: 4723
- Longitud promedio por resultado: 23.62

CONJUNTO C (CUÁDRUPLES):
- Total de cuádruples procesadas: 200
- Comparaciones totales: 235415
- Tiempo total (s): 0.098732
- Suma de longitudes de resultados: 1550
- Longitud promedio por resultado: 7.75

((results = Any[IntersectionResultby([6323, 12498], 1767, 0.0600775), IntersectionResultby([21109, 37491, 38824, 40060, 43252, 48615], 1102, 0.0001729), IntersectionResultby([10441], 873, 0.0001021), IntersectionResultby([227, 2802, 3122, 3220, 35566, 38126, 38679, 39587, 39971, 40488, 40976, 41053, 41367, 46954, 46955, 49582], 1132, 0.000174), IntersectionResultby([4850, 11205, 20287, 23256, 29729], 1070, 0.0001324), IntersectionResultby([4399, 5450, 10487, 25589], 1084, 0.0001268), IntersectionResultby([5194, 6030, 7380, 7932, 12040, 12583, 14811], 1020, 9.02e-5), IntersectionResultby([2729, 10222, 13543, 23966, 29304, 36381, 42776], 1099, 0.0001514), IntersectionResultby([337, 573, 676, 782, 1175, 1196, 1279, 3126, 3767, 4358  …  42994, 43453, 43723, 44271, 44433, 44447, 44492, 44639, 45051, 47320], 1936, 0.0015794), IntersectionResultby([9008, 15039, 20863, 20870, 24643, 31997, 32817], 944, 0.0001368)  …  IntersectionResultby([533, 2342, 4110, 6373, 6845, 11165, 14145, 14159, 14192, 14217  …  36901, 37631, 39409, 42585, 42596, 45398, 45528, 47346, 47669, 47924], 1573, 0.0005212), IntersectionResultby([12189, 39789, 40618], 944, 8.78e-5), IntersectionResultby([1851, 2533, 2756, 2814, 8897, 17536], 833, 8.78e-5), IntersectionResultby([2673, 3189, 3275, 3565, 3729, 3897, 4486, 5944, 9708, 9731  …  40963, 41278, 41469, 41530, 43418, 43965, 47263, 48515, 49005, 49175], 1747, 0.0016039), IntersectionResultby([5917, 5953, 6004, 6416, 7946, 9841, 12491, 22944, 46097], 1062, 9.8e-5), IntersectionResultby([613, 1244, 1871, 2271, 2893, 2908, 3296, 3559, 7308, 8196  …  33616, 35432, 36646, 37509, 39507, 41946, 43243, 44808, 44973, 49738], 1601, 0.0009207), IntersectionResultby([15521, 21090, 22638], 1057, 0.0001424), IntersectionResultby([1097, 2487, 2503, 2770, 8216, 17669, 42376], 1181, 0.0002906), IntersectionResultby([5363, 8739, 12242, 14529, 24924], 1114, 0.0001524), IntersectionResultby([1686, 6265, 9541, 14340, 43083, 43183, 44310, 44481, 46206], 1228, 0.0001505)], total_comparisons = 229942, total_time = 0.13816779999999987, total_result_length = 3627), (results = Any[IntersectionResultby([5239, 6162, 6806, 7411, 8951, 11279], 1005, 0.0007604), IntersectionResultby([5204, 5250, 6571, 8505, 21631, 30697, 36071], 1577, 0.0008215), IntersectionResultby([585, 1097, 2368, 8929, 11134, 11776, 14196, 14258, 17611, 24256, 26851, 27931, 37075, 37350, 37463, 49091], 2494, 0.0009574), IntersectionResultby([4961, 20059, 40091, 40106], 954, 0.0003187), IntersectionResultby([46886], 929, 0.0001637), IntersectionResultby([314, 384, 675, 759, 2559, 3509, 4149, 4812, 5190, 5210  …  45352, 45363, 45413, 45425, 45841, 46153, 47235, 48086, 49596, 49716], 4703, 0.0008844), IntersectionResultby([4273, 4702, 5081, 5122, 5145, 5311, 5330, 5366, 6409, 6532  …  45007, 45284, 45330, 45734, 46040, 46048, 46127, 46751, 47542, 49570], 3625, 0.0010997), IntersectionResultby([297, 731, 743, 777, 936, 977, 1214, 1461, 1468, 1617  …  44421, 45059, 45357, 45480, 46861, 47523, 49114, 49404, 49915, 49917], 2506, 0.0003634), IntersectionResultby([656, 745, 1256, 1783, 1948, 2080, 2156, 2202, 2624, 2749  …  46040, 47368, 48106, 48710, 48928, 48967, 49076, 49214, 49229, 49593], 5694, 0.0023724), IntersectionResultby([4997, 5223, 5439, 5564, 5655, 5797, 6010, 6028, 6056, 6186  …  6591, 6616, 6675, 6811, 7033, 10701, 12741, 17305, 30237, 34502], 1627, 0.0002117)  …  IntersectionResultby([291, 738, 1196, 1234, 2041, 2050, 6757, 11740, 14447, 15428, 38763, 49954], 3277, 0.0008525), IntersectionResultby([15287, 42767], 1378, 0.000247), IntersectionResultby([2316, 12774, 12838, 18103, 23914, 27715, 40838, 44982], 2695, 0.0002478), IntersectionResultby([275, 1494, 1979, 2508, 19085, 21630, 28195, 36747], 2298, 0.0002161), IntersectionResultby([2703, 6305, 7111, 15456, 46674], 1320, 0.0002216), IntersectionResultby([36813, 45326], 1054, 0.0005284), IntersectionResultby([7418, 18463, 23704, 26896, 30677, 30977, 35574, 35602, 36832, 39841, 40630], 1724, 0.0014321), IntersectionResultby([2909, 13712, 22475, 23606, 31618, 35409, 38102, 38625, 42221, 48249], 3094, 0.0005703), IntersectionResultby([15517, 33999], 1440, 0.0007589), IntersectionResultby([1196, 2728, 2991, 3126, 3518, 5661, 5911, 6009, 6205, 6470  …  9513, 10155, 10441, 11787, 12583, 14361, 16645, 17346, 21983, 29133], 1838, 0.0001548)], total_comparisons = 400028, total_time = 0.1156262, total_result_length = 4723), (results = Any[IntersectionResultby(Int64[], 831, 0.0001784), IntersectionResultby([41697, 41975], 949, 0.0005421), IntersectionResultby([1192, 2530, 5655, 5766, 5828, 6462, 6515, 6811, 7041, 7253  …  44370, 44477, 44663, 45924, 46455, 46561, 46931, 47846, 47942, 48825], 2134, 0.0015116), IntersectionResultby([2309, 2334, 2826], 950, 0.0002284), IntersectionResultby([4977, 5111, 9073, 9952], 806, 0.0001386), IntersectionResultby([2316, 5316, 5711, 6001, 7323, 8792, 9122, 9960, 10143, 10804, 11383, 11783, 16430, 17256, 17517, 20413, 20787, 32079, 46528], 1247, 0.0001858), IntersectionResultby([201, 443, 1903, 2568, 3571, 8904, 12928, 18489, 21396, 21644, 27378], 1843, 0.0003854), IntersectionResultby([9117, 14353, 41555], 919, 0.000192), IntersectionResultby([8289, 12366, 16834, 31510, 33936], 1573, 0.0002312), IntersectionResultby(Int64[], 725, 0.0006072)  …  IntersectionResultby([5743, 6042, 6720, 9994, 10879, 10898, 11978, 17668, 18037, 18504, 28427, 45377], 1091, 0.0003507), IntersectionResultby([42, 345, 616, 1808, 2090, 2795, 3133, 3912, 5039, 5240  …  23904, 26098, 26870, 28427, 29213, 33474, 35853, 35996, 36747, 46097], 1330, 0.0001651), IntersectionResultby(Int64[], 941, 0.0006089), IntersectionResultby([11327, 32778, 46318, 48218, 49861], 1647, 0.0003554), IntersectionResultby([2406, 4010, 23082, 25325, 37211, 41584, 42416, 44598, 44599], 1127, 0.0037482), IntersectionResultby([2466, 23191, 24711, 27172, 38942], 1007, 0.000203), IntersectionResultby([15601, 22028, 27245, 30117, 30251, 47966, 49018], 1205, 0.000968), IntersectionResultby([28029], 909, 0.0001926), IntersectionResultby([1530, 2956, 22833, 39553], 1906, 0.0002667), IntersectionResultby(Int64[], 948, 0.0001939)], total_comparisons = 235415, total_time = 0.09873159999999999, total_result_length = 1550), "RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA Exponencial):\n\nCONJUNTO A (PARES):\n- Total de pares procesados: 200\n- Comparaciones totales: 229942\n- Tiempo total (s): 0.138168\n- Suma de longitudes de resultados: 3627\n- Longitud promedio por resultado: 18.14\n\nCONJUNTO B (TRIPLETAS):\n- Total de tripletas procesadas: 200\n- Comparaciones totales: 400028\n- Tiempo total (s): 0.115626\n- Suma de longitudes de resultados: 4723\n- Longitud promedio por resultado: 23.62\n\nCONJUNTO C (CUÁDRUPLES):\n- Total de cuádruples procesadas: 200\n- Comparaciones totales: 235415\n- Tiempo total (s): 0.098732\n- Suma de longitudes de resultados: 1550\n- Longitud promedio por resultado: 7.75\n")

compute_all_intersections_baeza_custom(A, B, C, doubling_search, "B2")

Procesando Conjunto A (pares) con Baeza-Yates y búsqueda B2...

Procesando Conjunto B (tripletas) con Baeza-Yates y búsqueda B2...

Procesando Conjunto C (cuádruples) con Baeza-Yates y búsqueda B2...
RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA B2):

CONJUNTO A (PARES):
- Total de pares procesados: 200
- Comparaciones totales: 229942
- Tiempo total (s): 0.126267
- Suma de longitudes de resultados: 3627
- Longitud promedio por resultado: 18.14

CONJUNTO B (TRIPLETAS):
- Total de tripletas procesadas: 200
- Comparaciones totales: 400028
- Tiempo total (s): 0.106735
- Suma de longitudes de resultados: 4723
- Longitud promedio por resultado: 23.62

CONJUNTO C (CUÁDRUPLES):
- Total de cuádruples procesadas: 200
- Comparaciones totales: 235415
- Tiempo total (s): 0.086077
- Suma de longitudes de resultados: 1550
- Longitud promedio por resultado: 7.75

((results = Any[IntersectionResultby([6323, 12498], 1767, 0.0662942), IntersectionResultby([21109, 37491, 38824, 40060, 43252, 48615], 1102, 0.0004762), IntersectionResultby([10441], 873, 0.0003053), IntersectionResultby([227, 2802, 3122, 3220, 35566, 38126, 38679, 39587, 39971, 40488, 40976, 41053, 41367, 46954, 46955, 49582], 1132, 0.00049), IntersectionResultby([4850, 11205, 20287, 23256, 29729], 1070, 0.0001446), IntersectionResultby([4399, 5450, 10487, 25589], 1084, 0.0001202), IntersectionResultby([5194, 6030, 7380, 7932, 12040, 12583, 14811], 1020, 8.81e-5), IntersectionResultby([2729, 10222, 13543, 23966, 29304, 36381, 42776], 1099, 0.0001489), IntersectionResultby([337, 573, 676, 782, 1175, 1196, 1279, 3126, 3767, 4358  …  42994, 43453, 43723, 44271, 44433, 44447, 44492, 44639, 45051, 47320], 1936, 0.0015054), IntersectionResultby([9008, 15039, 20863, 20870, 24643, 31997, 32817], 944, 0.0001253)  …  IntersectionResultby([533, 2342, 4110, 6373, 6845, 11165, 14145, 14159, 14192, 14217  …  36901, 37631, 39409, 42585, 42596, 45398, 45528, 47346, 47669, 47924], 1573, 0.0004952), IntersectionResultby([12189, 39789, 40618], 944, 8.38e-5), IntersectionResultby([1851, 2533, 2756, 2814, 8897, 17536], 833, 8.35e-5), IntersectionResultby([2673, 3189, 3275, 3565, 3729, 3897, 4486, 5944, 9708, 9731  …  40963, 41278, 41469, 41530, 43418, 43965, 47263, 48515, 49005, 49175], 1747, 0.001359), IntersectionResultby([5917, 5953, 6004, 6416, 7946, 9841, 12491, 22944, 46097], 1062, 8.36e-5), IntersectionResultby([613, 1244, 1871, 2271, 2893, 2908, 3296, 3559, 7308, 8196  …  33616, 35432, 36646, 37509, 39507, 41946, 43243, 44808, 44973, 49738], 1601, 0.0007095), IntersectionResultby([15521, 21090, 22638], 1057, 0.0001246), IntersectionResultby([1097, 2487, 2503, 2770, 8216, 17669, 42376], 1181, 0.0001501), IntersectionResultby([5363, 8739, 12242, 14529, 24924], 1114, 0.0001359), IntersectionResultby([1686, 6265, 9541, 14340, 43083, 43183, 44310, 44481, 46206], 1228, 0.0001369)], total_comparisons = 229942, total_time = 0.12626689999999993, total_result_length = 3627), (results = Any[IntersectionResultby([5239, 6162, 6806, 7411, 8951, 11279], 1005, 0.0005328), IntersectionResultby([5204, 5250, 6571, 8505, 21631, 30697, 36071], 1577, 0.0007714), IntersectionResultby([585, 1097, 2368, 8929, 11134, 11776, 14196, 14258, 17611, 24256, 26851, 27931, 37075, 37350, 37463, 49091], 2494, 0.0008658), IntersectionResultby([4961, 20059, 40091, 40106], 954, 0.0002881), IntersectionResultby([46886], 929, 0.0001453), IntersectionResultby([314, 384, 675, 759, 2559, 3509, 4149, 4812, 5190, 5210  …  45352, 45363, 45413, 45425, 45841, 46153, 47235, 48086, 49596, 49716], 4703, 0.0055194), IntersectionResultby([4273, 4702, 5081, 5122, 5145, 5311, 5330, 5366, 6409, 6532  …  45007, 45284, 45330, 45734, 46040, 46048, 46127, 46751, 47542, 49570], 3625, 0.0006207), IntersectionResultby([297, 731, 743, 777, 936, 977, 1214, 1461, 1468, 1617  …  44421, 45059, 45357, 45480, 46861, 47523, 49114, 49404, 49915, 49917], 2506, 0.0001641), IntersectionResultby([656, 745, 1256, 1783, 1948, 2080, 2156, 2202, 2624, 2749  …  46040, 47368, 48106, 48710, 48928, 48967, 49076, 49214, 49229, 49593], 5694, 0.0019199), IntersectionResultby([4997, 5223, 5439, 5564, 5655, 5797, 6010, 6028, 6056, 6186  …  6591, 6616, 6675, 6811, 7033, 10701, 12741, 17305, 30237, 34502], 1627, 0.0001821)  …  IntersectionResultby([291, 738, 1196, 1234, 2041, 2050, 6757, 11740, 14447, 15428, 38763, 49954], 3277, 0.0007993), IntersectionResultby([15287, 42767], 1378, 0.0002207), IntersectionResultby([2316, 12774, 12838, 18103, 23914, 27715, 40838, 44982], 2695, 0.0002005), IntersectionResultby([275, 1494, 1979, 2508, 19085, 21630, 28195, 36747], 2298, 0.0002118), IntersectionResultby([2703, 6305, 7111, 15456, 46674], 1320, 0.0002049), IntersectionResultby([36813, 45326], 1054, 0.0004898), IntersectionResultby([7418, 18463, 23704, 26896, 30677, 30977, 35574, 35602, 36832, 39841, 40630], 1724, 0.0013194), IntersectionResultby([2909, 13712, 22475, 23606, 31618, 35409, 38102, 38625, 42221, 48249], 3094, 0.0005277), IntersectionResultby([15517, 33999], 1440, 0.0007373), IntersectionResultby([1196, 2728, 2991, 3126, 3518, 5661, 5911, 6009, 6205, 6470  …  9513, 10155, 10441, 11787, 12583, 14361, 16645, 17346, 21983, 29133], 1838, 0.0001482)], total_comparisons = 400028, total_time = 0.10673520000000002, total_result_length = 4723), (results = Any[IntersectionResultby(Int64[], 831, 0.0001719), IntersectionResultby([41697, 41975], 949, 0.0005153), IntersectionResultby([1192, 2530, 5655, 5766, 5828, 6462, 6515, 6811, 7041, 7253  …  44370, 44477, 44663, 45924, 46455, 46561, 46931, 47846, 47942, 48825], 2134, 0.0014266), IntersectionResultby([2309, 2334, 2826], 950, 0.0001723), IntersectionResultby([4977, 5111, 9073, 9952], 806, 0.0001163), IntersectionResultby([2316, 5316, 5711, 6001, 7323, 8792, 9122, 9960, 10143, 10804, 11383, 11783, 16430, 17256, 17517, 20413, 20787, 32079, 46528], 1247, 0.0001744), IntersectionResultby([201, 443, 1903, 2568, 3571, 8904, 12928, 18489, 21396, 21644, 27378], 1843, 0.0003656), IntersectionResultby([9117, 14353, 41555], 919, 0.0001896), IntersectionResultby([8289, 12366, 16834, 31510, 33936], 1573, 0.0002114), IntersectionResultby(Int64[], 725, 0.0001419)  …  IntersectionResultby([5743, 6042, 6720, 9994, 10879, 10898, 11978, 17668, 18037, 18504, 28427, 45377], 1091, 0.0002045), IntersectionResultby([42, 345, 616, 1808, 2090, 2795, 3133, 3912, 5039, 5240  …  23904, 26098, 26870, 28427, 29213, 33474, 35853, 35996, 36747, 46097], 1330, 0.0001596), IntersectionResultby(Int64[], 941, 0.000606), IntersectionResultby([11327, 32778, 46318, 48218, 49861], 1647, 0.0003564), IntersectionResultby([2406, 4010, 23082, 25325, 37211, 41584, 42416, 44598, 44599], 1127, 0.0007915), IntersectionResultby([2466, 23191, 24711, 27172, 38942], 1007, 0.000184), IntersectionResultby([15601, 22028, 27245, 30117, 30251, 47966, 49018], 1205, 0.0009023), IntersectionResultby([28029], 909, 0.0001732), IntersectionResultby([1530, 2956, 22833, 39553], 1906, 0.0003101), IntersectionResultby(Int64[], 948, 0.0002936)], total_comparisons = 235415, total_time = 0.08607699999999996, total_result_length = 1550), "RESUMEN DE RESULTADOS (BAEZA-YATES CON BÚSQUEDA B2):\n\nCONJUNTO A (PARES):\n- Total de pares procesados: 200\n- Comparaciones totales: 229942\n- Tiempo total (s): 0.126267\n- Suma de longitudes de resultados: 3627\n- Longitud promedio por resultado: 18.14\n\nCONJUNTO B (TRIPLETAS):\n- Total de tripletas procesadas: 200\n- Comparaciones totales: 400028\n- Tiempo total (s): 0.106735\n- Suma de longitudes de resultados: 4723\n- Longitud promedio por resultado: 23.62\n\nCONJUNTO C (CUÁDRUPLES):\n- Total de cuádruples procesadas: 200\n- Comparaciones totales: 235415\n- Tiempo total (s): 0.086077\n- Suma de longitudes de resultados: 1550\n- Longitud promedio por resultado: 7.75\n")

Barbay & Kenyon \((BK)\)

El algoritmo de Barbay y Kenyon es un algoritmo adaptativo para la intersección de listas ordenadas, propuesto por Jérémy Barbay y Claire Kenyon en su artículo “Adaptive intersection and t-threshold problems”, presentado en el SODA 2002 (Symposium on Discrete Algorithms).

Barbay y Kenyon (2002) proponen algoritmos adaptativos que ajustan su complejidad según la “dificultad” de la instancia, definida en términos de la estructura no determinista del problema. El algoritmo presentado se basa en una búsqueda por duplicación y binaria para calcular la intersección de \(k\) conjuntos ordenados de manera óptima.

Complejidad:

\(O(kδlog(n/δ))\), donde \(δ\) es la dificultad de la instancia.

Plan de implementación

1. Se definirá una función base para realizar la intersección de dos conjuntos por \(BK\)
2. Se definirán funciones de soporte que nos permitirán procesar los datos en función del tipo de conjunto ( Para pares, tripletas y cuadruples de listas)
3. Se definirá una función para computar todas las intersecciones. Esta, a su vez, generará un reporte con métricas para medir el desempeño del algoritmo, como; tiempo de ejecución, número de comparaciones y las longitudes de las intersecciones para cada conjunto de datos.

# Estructura para almacenar resultados
struct IntersectionResultBK
    result::Vector{Int}
    comparisons::Int
    time_taken::Float64
end

# Función base: algoritmo de Barbay-Kenyon 
function intersect_bk!(result::Vector{Int}, lists::Vector{Vector{Int}})
    comparisons = 0
    k = length(lists)
    
    # Ordenar listas por longitud ascendente
    #sorted_lists = sort(lists, by=length)
    P = ones(Int, k)  # Posiciones iniciales
    
    # Función de búsqueda binaria 
    function binary_findpos(lst::Vector{Int}, val::Int, start::Int)
        low, high = start, length(lst)
        while low <= high
            comparisons += 1
            mid = div(low + high, 2)
            if lst[mid] == val
                return mid
            elseif lst[mid] < val
                low = mid + 1
            else
                high = mid - 1
            end
        end
        return low > length(lst) ? length(lst)+1 : low
    end

    # Implementación del algoritmo BK 
    _max = lists[1][1]
    c = 0
    i = 1
    
    @inbounds while true
        for i in eachindex(P)
            P[i] = binary_findpos(lists[i], _max, P[i])
            P[i] > length(lists[i]) && return comparisons
            
            pval = lists[i][P[i]]
            if pval == _max
                c += 1
                if c == k
                    push!(result, _max)
                    comparisons += 1  # Contamos la comparación final
                    c = 0
                    P[i] += 1
                    P[i] > length(lists[i]) && return comparisons
                    _max = lists[i][P[i]]
                end
            else
                c = 0
                _max = pval
            end
        end
    end
    
    return comparisons
end

# Función generalizada para pares, tripletas, cuádruples 
function intersect_bk_groups(groups)
    results = []
    total_comparisons = 0
    total_time = 0.0
    total_result_length = 0

    for group in groups
        result = Int[]
        time_taken = @elapsed begin
            comparisons = intersect_bk!(result, [Vector{Int}(x) for x in group])
        end
        push!(results, IntersectionResultBK(result, comparisons, time_taken))
        total_comparisons += comparisons
        total_time += time_taken
        total_result_length += length(result)
    end

    return (
        results=results,
        total_comparisons=total_comparisons,
        total_time=total_time,
        total_result_length=total_result_length
    )
end

# Función general para procesar todos los conjuntos y generar reporte
function compute_all_intersections_bk(pairs_A, triplets_B, quadruples_C)
    println("Procesando Conjunto A (pares) con Barbay-Kenyon...")
    result_A = intersect_bk_groups(pairs_A)

    println("\nProcesando Conjunto B (tripletas) con Barbay-Kenyon...")
    result_B = intersect_bk_groups(triplets_B)

    println("\nProcesando Conjunto C (cuádruples) con Barbay-Kenyon...")
    result_C = intersect_bk_groups(quadruples_C)

    report = """
    RESUMEN DE RESULTADOS (BARBAY-KENYON):
    
    CONJUNTO A (PARES):
    - Total de pares procesados: $(length(pairs_A))
    - Comparaciones totales: $(result_A.total_comparisons)
    - Tiempo total (s): $(round(result_A.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_A.total_result_length)
    - Longitud promedio por resultado: $(round(result_A.total_result_length / max(length(pairs_A),1), digits=2))

    CONJUNTO B (TRIPLETAS):
    - Total de tripletas procesadas: $(length(triplets_B))
    - Comparaciones totales: $(result_B.total_comparisons)
    - Tiempo total (s): $(round(result_B.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_B.total_result_length)
    - Longitud promedio por resultado: $(round(result_B.total_result_length / max(length(triplets_B),1), digits=2))

    CONJUNTO C (CUÁDRUPLES):
    - Total de cuádruples procesadas: $(length(quadruples_C))
    - Comparaciones totales: $(result_C.total_comparisons)
    - Tiempo total (s): $(round(result_C.total_time, digits=6))
    - Suma de longitudes de resultados: $(result_C.total_result_length)
    - Longitud promedio por resultado: $(round(result_C.total_result_length / max(length(quadruples_C),1), digits=2))
    """

    println(report)

    return (result_A, result_B, result_C, report)
end

compute_all_intersections_bk (generic function with 1 method)

compute_all_intersections_bk(A,B, C)

Procesando Conjunto A (pares) con Barbay-Kenyon...

Procesando Conjunto B (tripletas) con Barbay-Kenyon...

Procesando Conjunto C (cuádruples) con Barbay-Kenyon...
RESUMEN DE RESULTADOS (BARBAY-KENYON):

CONJUNTO A (PARES):
- Total de pares procesados: 200
- Comparaciones totales: 316355
- Tiempo total (s): 0.472339
- Suma de longitudes de resultados: 3770
- Longitud promedio por resultado: 18.85

CONJUNTO B (TRIPLETAS):
- Total de tripletas procesadas: 200
- Comparaciones totales: 857660
- Tiempo total (s): 0.2474
- Suma de longitudes de resultados: 4763
- Longitud promedio por resultado: 23.82

CONJUNTO C (CUÁDRUPLES):
- Total de cuádruples procesadas: 200
- Comparaciones totales: 460476
- Tiempo total (s): 0.18608
- Suma de longitudes de resultados: 1637
- Longitud promedio por resultado: 8.18

((results = Any[IntersectionResultBK([6323, 12498], 2034, 0.3122745), IntersectionResultBK([21109, 37491, 37491, 38824, 40060, 40060, 43252, 48615], 1520, 0.0003135), IntersectionResultBK([10441], 1282, 0.0002289), IntersectionResultBK([227, 2802, 3122, 3220, 35566, 38126, 38679, 39587, 39971, 40488, 40976, 41053, 41367, 46954, 46955, 49582], 1582, 0.0004398), IntersectionResultBK([4850, 11205, 20287, 23256, 29729], 1603, 0.0002843), IntersectionResultBK([4399, 5450, 10487, 25589], 1634, 0.0002956), IntersectionResultBK([5194, 6030, 7380, 7932, 12040, 12583, 14811], 1409, 0.0002459), IntersectionResultBK([2729, 10222, 10222, 13543, 23966, 29304, 36381, 42776], 1394, 0.0003665), IntersectionResultBK([337, 573, 676, 782, 1175, 1175, 1196, 1279, 3126, 3767  …  42994, 43453, 43723, 44271, 44433, 44447, 44492, 44639, 45051, 47320], 2382, 0.0040738), IntersectionResultBK([9008, 15039, 20863, 20870, 24643, 31997, 32817], 1459, 0.0004104)  …  IntersectionResultBK([533, 2342, 4110, 6373, 6845, 11165, 14145, 14159, 14192, 14217  …  36901, 37631, 39409, 42585, 42596, 45398, 45528, 47346, 47669, 47924], 1885, 0.0011279), IntersectionResultBK([12189, 39789, 40618], 1365, 0.0003966), IntersectionResultBK([1851, 2533, 2756, 2814, 8897, 17536], 1226, 0.000295), IntersectionResultBK([2673, 3189, 3275, 3565, 3729, 3897, 4486, 4486, 5944, 9708  …  40963, 41278, 41469, 41530, 43418, 43965, 47263, 48515, 49005, 49175], 2147, 0.0032676), IntersectionResultBK([5917, 5953, 6004, 6416, 6416, 7946, 7946, 9841, 12491, 22944, 46097], 1602, 0.0002116), IntersectionResultBK([613, 1244, 1871, 2271, 2893, 2908, 3296, 3559, 7308, 8196  …  33616, 35432, 36646, 37509, 39507, 41946, 43243, 44808, 44973, 49738], 1842, 0.00213), IntersectionResultBK([15521, 21090, 22638, 22638], 1617, 0.0069215), IntersectionResultBK([1097, 2487, 2503, 2770, 8216, 17669, 42376], 1796, 0.0002813), IntersectionResultBK([5363, 8739, 12242, 14529, 24924], 1476, 0.0003568), IntersectionResultBK([1686, 6265, 9541, 14340, 43083, 43183, 44310, 44481, 46206], 1695, 0.0002532)], total_comparisons = 316355, total_time = 0.4723394000000001, total_result_length = 3770), (results = Any[IntersectionResultBK([5239, 6162, 6806, 7411, 8951, 11279], 2586, 0.0014856), IntersectionResultBK([5204, 5250, 6571, 8505, 21631, 30697, 36071], 4903, 0.0017187), IntersectionResultBK([585, 1097, 2368, 8929, 11134, 11776, 14196, 14258, 17611, 24256, 26851, 27931, 37075, 37350, 37463, 49091], 6791, 0.0016961), IntersectionResultBK([4961, 20059, 40091, 40106], 2706, 0.0006107), IntersectionResultBK([46886], 2273, 0.0003048), IntersectionResultBK([314, 384, 675, 759, 2559, 3509, 4149, 4812, 5190, 5210  …  45352, 45363, 45413, 45425, 45841, 46153, 47235, 48086, 49596, 49716], 6914, 0.0018055), IntersectionResultBK([4273, 4702, 5081, 5122, 5145, 5311, 5330, 5366, 6409, 6532  …  45007, 45284, 45330, 45734, 46040, 46048, 46127, 46751, 47542, 49570], 5008, 0.0015027), IntersectionResultBK([297, 731, 743, 777, 936, 977, 1214, 1461, 1468, 1617  …  44421, 45059, 45357, 45480, 46861, 47523, 49114, 49404, 49915, 49917], 4027, 0.0003866), IntersectionResultBK([656, 745, 1256, 1783, 1948, 2080, 2156, 2202, 2624, 2749  …  46040, 47368, 48106, 48710, 48928, 48967, 49076, 49214, 49229, 49593], 6619, 0.0040181), IntersectionResultBK([4997, 5223, 5439, 5564, 5655, 5797, 6010, 6028, 6056, 6186  …  6591, 6616, 6675, 6811, 7033, 10701, 12741, 17305, 30237, 34502], 3989, 0.000464)  …  IntersectionResultBK([291, 738, 1196, 1234, 2041, 2050, 6757, 11740, 14447, 15428, 38763, 49954], 4016, 0.0018549), IntersectionResultBK([15287, 42767], 3790, 0.0006318), IntersectionResultBK([2316, 12774, 12838, 18103, 23914, 27715, 40838, 44982], 3380, 0.0004496), IntersectionResultBK([275, 1494, 1979, 2508, 19085, 21630, 28195, 36747], 2978, 0.0004588), IntersectionResultBK([2703, 6305, 7111, 15456, 46674], 3127, 0.0005092), IntersectionResultBK([36813, 45326], 3336, 0.0010826), IntersectionResultBK([7418, 18463, 23704, 26896, 30677, 30977, 35574, 35602, 36832, 39841, 40630], 5140, 0.0043514), IntersectionResultBK([2909, 13712, 22475, 23606, 31618, 35409, 38102, 38625, 42221, 48249], 4248, 0.0013938), IntersectionResultBK([15517, 33999], 5413, 0.0014987), IntersectionResultBK([1196, 2728, 2991, 3126, 3518, 5661, 5911, 6009, 6205, 6470  …  9513, 10155, 10441, 11787, 12583, 14361, 16645, 17346, 21983, 29133], 5094, 0.0004506)], total_comparisons = 857660, total_time = 0.24740030000000002, total_result_length = 4763), (results = Any[IntersectionResultBK(Int64[], 2069, 0.0004117), IntersectionResultBK([41697, 41975], 2466, 0.0011205), IntersectionResultBK([1192, 2530, 5655, 5766, 5828, 5828, 6462, 6462, 6515, 6515  …  44370, 44477, 44663, 45924, 46455, 46561, 46931, 47846, 47942, 48825], 2959, 0.0029431), IntersectionResultBK([2309, 2334, 2826], 2355, 0.0004417), IntersectionResultBK([4977, 5111, 9073, 9952], 1781, 0.0003001), IntersectionResultBK([2316, 5316, 5711, 6001, 7323, 8792, 9122, 9122, 9960, 10143, 10804, 11383, 11783, 16430, 17256, 17517, 20413, 20787, 32079, 46528], 2209, 0.0003604), IntersectionResultBK([201, 443, 1903, 2568, 3571, 8904, 12928, 18489, 21396, 21644, 27378], 2466, 0.0008686), IntersectionResultBK([9117, 14353, 41555], 1977, 0.000395), IntersectionResultBK([8289, 12366, 16834, 31510, 33936], 2183, 0.0005303), IntersectionResultBK(Int64[], 1780, 0.0003354)  …  IntersectionResultBK([5743, 5743, 6042, 6720, 9994, 10879, 10898, 10898, 11978, 17668, 18037, 18504, 28427, 45377], 2371, 0.0004603), IntersectionResultBK([42, 345, 616, 1808, 2090, 2795, 3133, 3912, 5039, 5240  …  23904, 26098, 26870, 28427, 29213, 33474, 35853, 35996, 36747, 46097], 2330, 0.0003595), IntersectionResultBK(Int64[], 2427, 0.0011854), IntersectionResultBK([11327, 32778, 46318, 48218, 49861], 2401, 0.0007962), IntersectionResultBK([2406, 4010, 23082, 25325, 37211, 41584, 42416, 44598, 44599], 2889, 0.0015695), IntersectionResultBK([2466, 23191, 24711, 27172, 38942], 2138, 0.0003949), IntersectionResultBK([15601, 22028, 27245, 30117, 30251, 47966, 49018], 2623, 0.0019411), IntersectionResultBK([28029], 2316, 0.0004598), IntersectionResultBK([1530, 2956, 2956, 22833, 39553], 2638, 0.0006198), IntersectionResultBK(Int64[], 2296, 0.0003896)], total_comparisons = 460476, total_time = 0.18608049999999987, total_result_length = 1637), "RESUMEN DE RESULTADOS (BARBAY-KENYON):\n\nCONJUNTO A (PARES):\n- Total de pares procesados: 200\n- Comparaciones totales: 316355\n- Tiempo total (s): 0.472339\n- Suma de longitudes de resultados: 3770\n- Longitud promedio por resultado: 18.85\n\nCONJUNTO B (TRIPLETAS):\n- Total de tripletas procesadas: 200\n- Comparaciones totales: 857660\n- Tiempo total (s): 0.2474\n- Suma de longitudes de resultados: 4763\n- Longitud promedio por resultado: 23.82\n\nCONJUNTO C (CUÁDRUPLES):\n- Total de cuádruples procesadas: 200\n- Comparaciones totales: 460476\n- Tiempo total (s): 0.18608\n- Suma de longitudes de resultados: 1637\n- Longitud promedio por resultado: 8.18\n")

Dicusión de Resultados

Tabla 1. Comparación de tiempo de ejecución (segundos) de cada algoritmo para cada conjunto.

\[ \begin{array}{|l|c|c|c|} \hline \textbf{} & \textbf{Conjunto (A)}\ \text{pares} & \textbf{Conjunto (B)}\ \text{tripletas} & \textbf{Conjunto (C)}\ \text{cuádruples} \\ \hline \text{ME} & 0.072497 & 0.131184 & 0.221043 \\ \text{BY Bisección} & 0.687597 & 0.305697 & 0.244972 \\ \text{BY } B_{1} & 0.138168 & 0.115626 & 0.098732 \\ \text{BY } B_{2} & 0.126267 & 0.106735 & 0.086077 \\ \text{BK} & 0.472339 & 0.2474 & 0.18608 \\ \hline \end{array} \]

De la Tabla 1, se puede observar la siguiente:

1. Comportamiento de ME (Melding)

• Es el algoritmo más rápido para pares, lo que podría sugerir que la diferencia en el tamaño de las listas del conjunto A no es tan grande.
• Su rendimiento empeora significativamente con tripletas y cuádruples. Esto sugiere que no escala bien con la aridad de la intersección, esto seguramente se debe a que este algoritmo tiene que inspeccionar todos los elementos de las listas de los conjuntos.

2. BY (Baeza-Yates) con búsqueda binaria clásica (bisección)

• Es el más lento para pares (0.6876s).
• La tendencia de su rendimiento es mejorar al aumentar la aridad, lo cual podría deberse a que las intersecciones son más dispersas, haciendo más eficientes las búsquedas binarias.
• Aun así, es el algoritmo menos eficiente en general, en términos de tiempo de ejecución.

3. BY (Baeza-Yates) con \(B_1\) y \(B_2\)

• Superan claramente a la bisección.
• \(B_2\) es más rápido que \(B_1\), como se espera teóricamente.
• Son los más eficientes para tripletas y cuádruples.
• Escalan muy bien con la aridad.

4. BK (Barbay-Kenyon)

• Tiene un rendimiento intermedio: mejor que \(BY\) Bisección, pero peor que \(BY\) \(B_2\).
• También escala bien, con tiempos decrecientes al aumentar la aridad.

---

Tabla 2. Número de comparaciones realizadas por cada algoritmo para cada conjunto.

\[ \begin{array}{|l|c|c|c|} \hline \textbf{} & \textbf{Conjunto (A)}\ \text{pares} & \textbf{Conjunto (B)}\ \text{tripletas} & \textbf{Conjunto (C)}\ \text{cuádruples} \\ \hline \text{ME} & 3\,238\,899 & 5\,276\,587 & 4\,261\,034 \\ \text{BY Bisección} & 236\,662 & 478\,929 & 270\,415 \\ \text{BY } B_{1} & 229\,942 & 400\,028 & 235\,415 \\ \text{BY } B_{2} & 229\,942 & 400\,028 & 235\,415 \\ \text{BK} & 316\,355 & 857\,660 & 460\,476 \\ \hline \end{array} \]

De la Tabla 2, se puede observar la siguiente:

1. ME (Melding)

• Realiza la mayor cantidad de comparaciones por un amplio margen. Este compartamiento es esperado, pues de antemano se sabe que el algoritmo inspecciona todos los elementos de los conjuntos.
• Especialmente ineficiente en tripletas, con más de 5 millones de comparaciones. Esto explica su bajo rendimiento en tiempo: su carga computacional es muy alta.

2. BY (Baeza-Yates) con búsqueda binaria clásica (bisección)

• Realiza muchas menos comparaciones que \(ME\).
• Sin embargo, es superado cuando se utilizan como función de búsqueda: \(B_1\) y \(B_2\) .

3. BY (Baeza-Yates) con \(B_1\) y \(B_2\)

• Ambos algoritmos realizan exactamente el mismo número de comparaciones en estos conjuntos. Esto se podría explicar debido a que ambos algoritmos de búsqueda siguen un principio similar, con la particularidad de que \(B_2\) aumenta el rango de búsqueda de una manera más agresiva.
• Son los más eficientes computacionalmente en todos los casos. Esto respalda su mejor desempeño en tiempo observado en la Tabla 1.

4. BK (Barbay-Kenyon)

• Realiza menos comparaciones que \(ME\), pero más que las variantes de Baeza-Yates.
• En tripletas, hace incluso más comparaciones que \(BY\) Bisección, lo cual coincide con su tiempo más alto en ese caso.

Tabla 3. Longitudes de las intersecciones resultantes para cada conjunto y algoritmo.

\[ \begin{array}{|l|c|c|c|} \hline \textbf{Longitud} & \textbf{Conjunto (A)}\ \text{pares} & \textbf{Conjunto (B)}\ \text{tripletas} & \textbf{Conjunto (C)}\ \text{cuádruples} \\ \hline \text{ME} & 3627 & 4723 & 1550 \\ \text{BY Bisección} & 3627 & 4723 & 1550 \\ \text{BY } B_{1} & 3627 & 4723 & 1550 \\ \text{BY } B_{2} & 3627 & 4723 & 1550 \\ \text{BK} & 3770 & 4763 & 1637 \\ \hline \end{array} \]

De la Tabla 3, se identifica lo siguiente:

1. ME, BY Bisección, BY \(B_1\) y BY \(B_2\)

• Producen exactamente la misma cantidad de resultados para cada conjunto.
• Debido a la consistencia, probablemente representan el resultado esperado.

2. BK (Barbay-Kenyon)

• Para este algoritmo se identificó una anomalía; entrega más resultados en todos los casos:
  • +143 en pares, +40 en tripletas, +87 en cuádruples.
• Esto podría significar:
  • Que \(BK\) incluye falsos positivos.
  • O que las otras implementaciones están filtrando de más. Esto parece poco probable dado que el resto de algoritmos coinciden.

using Pkg
Pkg.add("StatsPlots")
Pkg.add("DataFrames")

using StatsPlots
using DataFrames

# Nombres de los conjuntos
sets = ["A", "B", "C"]
algoritmos = ["ME", "BY Bisección", "BY B₁", "BY B₂", "BK"]

# Repetimos los nombres de conjunto y algoritmo
set_labels = repeat(sets, inner=5)
alg_labels = repeat(algoritmos, outer=3)

# Tiempos en segundos (Tabla 1)
tiempos = [
    0.072497, 0.687597, 0.138168, 0.126267, 0.472339,  # A
    0.131184, 0.305697, 0.115626, 0.106735, 0.2474,    # B
    0.221043, 0.244972, 0.098732, 0.086077, 0.18608    # C
]

# Comparaciones (Tabla 2)
comparaciones = [
    3238899, 236662, 229942, 229942, 316355,     # A
    5276587, 478929, 400028, 400028, 857660,     # B
    4261034, 270415, 235415, 235415, 460476      # C
]

# Longitudes de las intersecciones (Tabla 3)
longitudes = [
    3627, 3627, 3627, 3627, 3770,     # A
    4723, 4723, 4723, 4723, 4763,     # B
    1550, 1550, 1550, 1550, 1637      # C
]

# DataFrame combinado
df = DataFrame(
    Conjunto = set_labels,
    Algoritmo = alg_labels,
    Tiempo = tiempos,
    Comparaciones = comparaciones,
    Longitud = longitudes
)

15×5 DataFrame

Row	Conjunto	Algoritmo	Tiempo	Comparaciones	Longitud
	String	String	Float64	Int64	Int64
1	A	ME	0.072497	3238899	3627
2	A	BY Bisección	0.687597	236662	3627
3	A	BY B₁	0.138168	229942	3627
4	A	BY B₂	0.126267	229942	3627
5	A	BK	0.472339	316355	3770
6	B	ME	0.131184	5276587	4723
7	B	BY Bisección	0.305697	478929	4723
8	B	BY B₁	0.115626	400028	4723
9	B	BY B₂	0.106735	400028	4723
10	B	BK	0.2474	857660	4763
11	C	ME	0.221043	4261034	1550
12	C	BY Bisección	0.244972	270415	1550
13	C	BY B₁	0.098732	235415	1550
14	C	BY B₂	0.086077	235415	1550
15	C	BK	0.18608	460476	1637

# Gráfico 1: Tiempo
@df df boxplot(
    :Conjunto, :Tiempo,
    title = "Fig 1. Distribución de tiempo por conjunto",
    ylabel = "Tiempo (s)",
    notch = false
)

Figura 1. Corresponde a los tiempos de ejecución. Muestra los “boxplots” de mayor variabilidad. Se puede observar que para el conjunto A, se aprecia un rango más amplio, esto se debe principalmente a que para este conjunto se registraron tanto el tiempo de ejecución más corto (\(ME\)) como el más largo (\(BY\) Bisección). Para los conjuntos B y C se muestran “boxplots” muy compactos que muestran la poca variabilidad en tiempos de ejecución.

Se destaca que, si bien, existe algo de variabilidad principalmente para el conjunto A, en todos los casos los tiempos de ejecución permanecieron en el mismo orden de magnitud.

# Gráfico 2: Comparaciones
@df df boxplot(
    :Conjunto, :Comparaciones,
    title = "Fig 2. Distribución de comparaciones por conjunto",
    ylabel = "Número de comparaciones",
    notch = false
)

Figura 2. Corresponde a las comparaciones realizadas por conjunto. Se muestra para los tres conjuntos una variabilidad muy baja, lo que indica que en la gran mayoría de casos se realizó un número similar de comparaciones. Sin embargo, despliega claros “outliers” de apróximadamente un orden de magnitud mayor, que corresponden al algortimo \(ME\). Como ya se ha comentado este inspecciona todos los elementos de ambas listas.

# Gráfico 3: Longitud total
@df df boxplot(
    :Conjunto, :Longitud,
    title = "Fig 3.Distribución de longitudes de intersección por conjunto",
    ylabel = "Suma de longitudes",
    notch = false
)

Figura 3. Corresponde a la logitud de las intersecciones por conjunto. No hay variabilidad, esto es porque en teoría todos los algoritmos deben llegar al mismo resultado, expresado en la longitud de los conjuntos de intersección, cosa que en la práctica se dio. Con la única excepción del algoritmo \(BK\), que devovió una cantidad mayor de elementos para las intersecciones, esto se muestra como los valores “outliers” en los “boxplots”. Vale la pena destacar que incluso sí \(BK\) mostró valores atípicos, estos están muy cerca de los resultados esperados

Conclusiones

1. Desempeño en tiempo de ejecución

   • Si bien algoritmo Melding (\(ME\)) demostró una buena eficiencia en tiempos de ejecución y en particular en el Conjunto A, tiende a escalar demasiado con la aridad de los problemas. No es recomendable para casos en los que \(n≫m\).
   • Las variantes Baeza-Yates \(B_1\) y \(B_2\) mostraron ser rápidas y escalables, con tiempos significativamente menores que los demás algoritmos.
   • Barbay-Kenyon (\(BK\)) mejora respecto a \(ME\) y \(BY\) con bisección, pero no supera a las variantes parametrizadas de \(BY\).

2. Eficiencia computacional (comparaciones)

   • \(ME\) realiza una cantidad de comparaciones mucho mayor que los demás algoritmos, lo cual explica su mala escalabilidad, y puede tener implicaciones en memoria.
   • \(BY\) \(B_1\) y \(B_2\) realizan la menor cantidad de comparaciones, mostrando una eficiencia óptima.
   • \(BK\) se comporta de forma aceptable, pero no alcanza el nivel de eficiencia de de las variantes de \(BY\).
   • \(BY\) con bisección mejora considerablemente sobre \(ME\), aunque es superado por sus variantes.

3. Correctitud de los resultados (longitud de la intersección)

   • \(ME\) y todas las variantes de \(BY\) producen resultados de igual longitud, lo que indica consistencia y correctitud en sus implementaciones.
   • \(BK\) genera intersecciones ligeramente más largas, lo que puede indicar:
     • Inclusión de falsos positivos,
     • Uso de una definición menos estricta de intersección,
     • O un posible error en la implementación.
   • Esto sugiere que los resultados de \(BK\) deben validarse.

4. Elección recomendada de algoritmo

   En términos generales en los experimentos realizados las variantes \(BY\) \(B_1\) y \(B_2\) son las más recomendables, ya que fueron rápidas, eficientes y precisas, en todos los casos.

Bibliografía

Baeza-Yates, R. (2004). A fast set intersection algorithm for sorted sequences. In S. C. Sahinalp, S. Muthukrishnan, & U. Vishkin (Eds.), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004) (Vol. 3109, pp. 400–408). Springer. https://doi.org/10.1007/978-3-540-27813-7_32

Baeza-Yates, R., & Salinger, A. (2005). Experimental analysis of a fast intersection algorithm for sorted sequences. In Proceedings of the 12th International Conference on String Processing and Information Retrieval (SPIRE 2005) (pp. 13–24). Springer. https://doi.org/10.1007/11575832_3

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

Demaine, E. D., López-Ortiz, A., & Munro, J. I. (2000). Adaptive set intersections, unions, and differences. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 743–752).