PROBLEMA
El propósito de este post es el de documentar y analizar la eficiencia en TIEMPO de las diferentes implementaciones para eliminar los elementos duplicados de un arreglo (array).
CLARIFICACIÓN
Optimizar una parte específica del código debe considerarse cuando hay una dependencia estrecha entre la ejecución del programa y el tiempo que tarda en ejecutarse esa fracción de código en específico (Ley de Amdahl).
Al fin y al cabo, esto es una cuestión de coste-beneficio combinado con un ejercicio de análisis de rendimiento. El rendimiento de una sección de código es una combinación entre la frecuencia y la eficiencia de la ejecución:
¿Cuántas veces se ejecutará el código y cuán frecuentemente? ¿Con qué datos se ejecutará?¡Las optimizaciones pueden ser un arma de doble filo! Las optimizaciones pueden proveer algunas mejoras en tiempo o espacio pero al mismo tiempo puede ser que estes sacrificando legibilidad, fiabiliad y tiempo del programador que usualmente suelen ser más importantes en muchos casos. Por ello, deberíamos preocuparnos sólo de optimizar aquello que marque una diferencia.
Este experimento no tiene sentido con una pequeña muestra de datos dado que el impacto del algoritmo en estos casos suele ser ridídulo. Hay factores que serán mucho más determinantes que el algoritmo en si mismo. El sobrecoste ( overhead) más común en este tipo de experimentos suele ser la carga de trabajo de la CPU, la capacidad de transferencia y memoria del sistema,... durante la ejecución del experimento. Estos pueden afectar drásticamente y añadir cierta aletoriedad al experimento. No voy a tomar ningún tipo de enfoque teórico. ¡Esto solo es un experimento!
SOLUCIÓN
Para medir el impacto del algoritmo, se van a introducir 2 variables: el tamaño del arreglo (NUM_ELEMENTS) y el coeficiente de repetición (REPETITION_RATE).
const NUM_ELEMENTS = 10_000; // 10.000
const REPETITION_RATE = {
UNUSUAL: NUM_ELEMENTS * 1000,
CASUAL: NUM_ELEMENTS * 100,
LIKELY: NUM_ELEMENTS
};
El coeficiente de repetición es un pseudosolución para introducir algunos elementos duplicados con mayor o menor probabilidad. Para hacerlo, definí 3 niveles de repetición: LIKELY, CASUAL, y UNUSUAL, cada nivel de repetición tiene un rango diferente de posibles valores que cada arreglo puede tener.
Para calcular un arreglo de NUM_ELEMENTS elementos y rellenarlo con números aleatorios entre los rangos definidos, vamos a usar la siguiente función:
const data = (rate) => Array(NUM_ELEMENTS).fill().map(
() => Math.floor(Math.random() * REPETITION_RATE[rate])
);
Teniendo en cuenta lo previamente mencionado, voy a presentar posiblemente la más común y simple solución para eliminar elementos duplicados de un arreglo. En aras de simplificar el problema, los experimentos se harán sobre un arreglo de números (numbers):
const withSet = (array) => {
return [...new Set(array)]
};
const withForLoop = (array) => {
var seen = {};
var out = [];
var len = array.length;
var j = 0;
for (var i = 0; i < len; i++) {
var item = array[i];
if (seen[item] !== 1) {
seen[item] = 1;
out[j++] = item;
}
}
return out;
}
const withSort = (array) => {
return array.sort().filter((item, i, self) => {
return !i || item != self[i - 1];
})
}
const withFilter = (array) => {
return array.filter((item, i, self) => {
return self.indexOf(item) == i
})
}
Para dar más fiabilidad al resultado empírico, cada algoritmo se ejecutará 10 veces sobre el mismo conjunto de datos. Para ello, creé una función muy simple para medir el tiempo de ejecución de cada ejecución del algoritmo:
const calculate = (execute) => {
let init = performance.now();
execute();
let end = performance.now();
return end - init;
}
Con el fin de poder medir el impacto del algoritmo, se usará un arreglo lo suficientemente grande (NUN_ELEMENTS = 10.000).
Vamos a analizar cuántos milisegundos tarda en ejecutarse cada algoritmo y lo representaremos en un diagrama de cajas ('boxplot'). Podéis consultar todos los datos en crudo en el sección del Anexo.
El peor algoritmo de lejos es el withFilter. Además, como se puede observar, está altamente afectado por el coeficiente de repetición: a mayor coeficiente de repetición, mejores resultados arroja.
Si omitimos los resultados del algoritmo withFilter, podemos observar con más detalle los resultados del resto:
Independientemente del coeficinte de repetición, el withSet funciona mucho mejor que los otros algoritmos.
Además, podemos observar que hay una correlación entre el coeficiente de repetición y el rendimiento del algoritmo withForLoop y el withSet (al igual que en el de withFilter).
Mayor coeficiente de repetición ⇒ Mejor rendimiento. Procesar un elemento con valor único tiene un coste mayor que procesar un valor de un elemento repetido.
Por ejemplo, en el algoritmo withForLoop, podemos adivinar fácilmente el trabajo extra que tiene que hacer por cada valor único:
// Duplicado?
if (seen[item] !== 1) {
// Añadir un nuevo elemento
seen[item] = 1;
out[j++] = item;
}
Sin embargo, el withSort no está prácticamente afectado lo cuál tiene sentido.
¿Qué pasará si aplicamos los algoritmos a un millón de elementos (NUM_ELEMENTS = 1.000.000)?
Podemos observar que la correlación es más que evidente cuando aplicamos los algoritmos en conjuntos de datos mayores. En arreglos suficientemente grandes, el algoritmo withSort es el peor respecto a los dos restantes (withForLoop y withSet)
Aún así, hay un escenario donde el método withSort funciona mejor que los otros; cuando el arreglo ya está previamente ordenado.
Además, en este escenario, el withForLoop funciona un poco mejor que el withSet cuando tenemos un coeficiente de repetición alto. Parece estar relacionado con la predicción de salto.
Si omitimos los resultados del withSort, podemos entra en más detalle en los resultados. Incuso, si ignoramos el escenario del arreglo ordenado y mantenemos la arbitrariedad, ¿qué sucederá si aplicamos los algorimos a 10 millones de elementos (NUM_ELEMENTS = 10.000.000)?
CONCLUSIÓN
El mejor algorimo sin discusión es el withSet. ¡Afortunadamente es el más simple y el más legible!
Como dije, en la gran mayoria de los casos, no deberiamos preocuparnos por estas micro-optimizaciones a menos que el algoritmo sea el núcleo de la aplicación. Al fin y al cabo, es un ejercicio de análisis de rendimiento.
ANEXO
NUM_ELEMENTS = 10_000 - REPETITION_RATE = LIKELY
{
withForLoop: {
min: 0.6161800026893616,
max: 4.2332499995827675,
average: 1.553389500454068,
median: 1.015947999432683,
results: [
4.2332499995827675,
1.1240199990570545,
2.6671050004661083,
2.2087169997394085,
0.7861710004508495,
0.9078759998083115,
1.594580002129078,
0.6161800026893616,
0.642960000783205,
0.7530359998345375
]
},
withSet: {
min: 0.4024589993059635,
max: 0.6405039988458157,
average: 0.4619603998959064,
median: 0.4326910004019737,
results: [
0.48315799981355667,
0.43505600094795227,
0.4303259998559952,
0.4024589993059635,
0.6405039988458157,
0.453405000269413,
0.43005000054836273,
0.4045730009675026,
0.5168850012123585,
0.4231879971921444
]
},
withSort: {
min: 2.767271999269724,
max: 3.8152489997446537,
average: 3.165797100588679,
median: 3.0043945014476776,
results: [
3.8009399995207787,
3.5159769989550114,
2.9593700021505356,
2.9771270006895065,
3.199684999883175,
3.0316620022058487,
2.794938001781702,
2.767271999269724,
2.7957510016858578,
3.8152489997446537
]
},
withFilter: {
min: 33.65182099863887,
max: 35.35537299886346,
average: 34.15013259984553,
median: 34.02158449962735,
results: [
34.800221998244524,
35.35537299886346,
33.73582600057125,
33.99973299726844,
34.043436001986265,
34.06344199925661,
33.9438509978354,
33.76401100307703,
34.14361100271344,
33.65182099863887
]
}
}
NUM_ELEMENTS = 10_000 - REPETITION_RATE = CASUAL
{
withForLoop: {
min: 2.145897999405861,
max: 5.599513001739979,
average: 3.1290818996727467,
median: 2.733591500669718,
results: [
5.599513001739979,
2.9871659986674786,
4.6746309995651245,
2.351264998316765,
2.435266997665167,
2.145897999405861,
2.3316360004246235,
3.298259999603033,
2.9040569998323917,
2.563126001507044
]
},
withSet: {
min: 0.5837909989058971,
max: 0.9629179984331131,
average: 0.6997227989137172,
median: 0.6336345002055168,
results: [
0.6274590007960796,
0.8656079992651939,
0.7128149978816509,
0.5837909989058971,
0.5877099968492985,
0.9629179984331131,
0.6015109978616238,
0.639809999614954,
0.5845829993486404,
0.8310230001807213
]
},
withSort: {
min: 2.7234829999506474,
max: 3.549414001405239,
average: 2.9976361002773046,
median: 2.9778910018503666,
results: [
3.0144580006599426,
3.0532069988548756,
2.7598399966955185,
3.1632930003106594,
2.9413240030407906,
2.752921000123024,
2.7234829999506474,
2.8584109991788864,
3.549414001405239,
3.160010002553463
]
},
withFilter: {
min: 45.12157400324941,
max: 48.27394500002265,
average: 46.47778210006654,
median: 46.11468300037086,
results: [
48.27394500002265,
46.07310400158167,
45.861281000077724,
45.44522299990058,
45.12157400324941,
47.66389499977231,
45.37212799862027,
47.487910997122526,
47.32249800115824,
46.15626199916005
]
}
}
NUM_ELEMENTS = 10_000 - REPETITION_RATE = UNUSUAL
{
withForLoop: {
min: 2.3064499981701374,
max: 6.645658999681473,
average: 3.8001832999289036,
median: 3.140233000740409,
results: [
6.1662480011582375,
2.7944019995629787,
4.219734001904726,
2.8926009982824326,
4.283261999487877,
2.3064499981701374,
2.9883799999952316,
3.292086001485586,
2.413010999560356,
6.645658999681473
]
},
withSet: {
min: 0.5926219969987869,
max: 4.515944998711348,
average: 1.2056124992668629,
median: 0.6688965000212193,
results: [
0.6639479994773865,
1.4014370031654835,
4.515944998711348,
0.673845000565052,
0.6214400008320808,
0.8942089974880219,
0.6134370006620884,
0.617748998105526,
0.5926219969987869,
1.4614929966628551
]
},
withSort: {
min: 2.7875970005989075,
max: 3.5085639990866184,
average: 3.068043800070882,
median: 3.0669784992933273,
results: [
3.1199680007994175,
3.5085639990866184,
2.927454002201557,
3.3949429988861084,
2.795676000416279,
2.815430000424385,
2.7875970005989075,
3.134131997823715,
3.013988997787237,
3.182685002684593
]
},
withFilter: {
min: 45.30747600272298,
max: 60.73564099892974,
average: 48.38645560033619,
median: 46.84241000004113,
results: [
60.73564099892974,
47.12230399996042,
46.28296400234103,
45.34110099822283,
45.996991001069546,
45.30747600272298,
46.56251600012183,
48.059397000819445,
48.20021599903703,
50.25595000013709
]
}
}
NUM_ELEMENTS = 1_000_000 - REPETITION_RATE = LIKELY
{
withForLoop: {
min: 155.05746100097895,
max: 245.10848499834538,
average: 181.6651143990457,
median: 169.08007649704814,
results: [
203.5708300024271,
161.23485799878836,
155.05746100097895,
170.27531999349594,
157.80864299833775,
225.59701199829578,
245.10848499834538,
171.7655059993267,
167.88483300060034,
158.34819599986076
]
},
withSet: {
min: 121.78685899823904,
max: 145.75340899825096,
average: 128.705806799978,
median: 127.01133299991488,
results: [
127.67670299857855,
126.34596300125122,
122.60724800080061,
125.9666019976139,
121.78685899823904,
130.07025100290775,
145.75340899825096,
133.6826130002737,
125.13346000015736,
128.03496000170708
]
},
withSort: {
min: 448.8328679949045,
max: 493.5059050023556,
average: 465.22751189991834,
median: 461.2731125019491,
results: [
448.8328679949045,
466.63669400662184,
464.6501320004463,
449.6672699972987,
493.5059050023556,
457.8960930034518,
451.7257089987397,
489.2764909937978,
451.85943400114775,
478.22452300041914
]
}
}
NUM_ELEMENTS = 1_000_000 - REPETITION_RATE = CASUAL
{
withForLoop: {
min: 384.021381996572,
max: 488.5499190017581,
average: 427.4536935999989,
median: 425.1403129994869,
results: [
394.7962369993329,
408.4729050025344,
413.82565400004387,
450.74423100054264,
455.4311800003052,
436.45497199893,
488.5499190017581,
384.021381996572,
387.7007130011916,
454.5397429987788
]
},
withSet: {
min: 135.95582000166178,
max: 167.32689300179482,
average: 142.8933510005474,
median: 139.64554500207305,
results: [
137.69809199869633,
141.28855700045824,
138.00253300368786,
137.7896299958229,
142.44284000247717,
141.87754200398922,
167.32689300179482,
149.52464500069618,
135.95582000166178,
137.0269579961896
]
},
withSort: {
min: 459.81696800142527,
max: 524.4922409951687,
average: 478.2014821983874,
median: 472.2513504959643,
results: [
459.81696800142527,
524.4922409951687,
470.29814099520445,
474.20455999672413,
486.25255700200796,
461.06839399784803,
467.16533199697733,
470.1375120058656,
484.4119429960847,
484.1671739965677
]
}
}
NUM_ELEMENTS = 1_000_000 - REPETITION_RATE = UNUSUAL
{
withForLoop: {
min: 386.68828999996185,
max: 512.5664549991488,
average: 424.4509158007801,
median: 412.9922320023179,
results: [
387.05061000585556,
386.68828999996185,
451.6580500006676,
512.5664549991488,
423.45554799586535,
407.7165110036731,
457.4781470000744,
399.9279880002141,
399.6996060013771,
418.26795300096273
]
},
withSet: {
min: 136.28456499427557,
max: 174.66381999850273,
average: 150.22565199807286,
median: 148.61589350178838,
results: [
153.5806260034442,
161.41218699514866,
143.65116100013256,
136.28456499427557,
143.53657999634743,
139.3451649993658,
174.66381999850273,
156.44387900084257,
155.3550329953432,
137.9835039973259
]
},
withSort: {
min: 456.1394260004163,
max: 537.935175999999,
average: 488.6582931995392,
median: 480.69253949820995,
results: [
473.29733599722385,
517.2986389994621,
456.1394260004163,
537.935175999999,
517.5273750051856,
468.0702169984579,
461.11141999810934,
493.8182640001178,
479.4086980000138,
481.9763809964061
]
}
}
NUM_ELEMENTS = 1_000_000 - REPETITION_RATE = LIKELY - PRESORTED
{
withForLoop: {
min: 67.32201500236988,
max: 88.55460099875927,
average: 80.63559990078211,
median: 82.08199950307608,
results: [
88.55460099875927,
81.92778299748898,
87.59654499590397,
84.62078499794006,
88.41655300557613,
82.23621600866318,
69.48410500586033,
67.32201500236988,
75.0740189999342,
81.12337699532509
]
},
withSet: {
min: 90.35226999223232,
max: 121.71554899215698,
average: 101.35781189799309,
median: 97.61934300512075,
results: [
121.71554899215698,
100.78924599289894,
93.27231799066067,
94.89483200013638,
94.51389099657536,
112.895673006773,
109.90565399825573,
97.37541399896145,
90.35226999223232,
97.86327201128006
]
},
withSort: {
min: 55.708606988191605,
max: 63.539028003811836,
average: 58.58115369826555,
median: 57.44712050259113,
results: [
57.8816349953413,
57.012606009840965,
62.98825399577618,
55.708606988191605,
56.07959200441837,
56.68088099360466,
58.779587000608444,
61.02952899038792,
56.11181800067425,
63.539028003811836
]
}
}
NUM_ELEMENTS = 1_000_000 - REPETITION_RATE = CASUAL - PRESORTED
{
withForLoop: {
min: 367.14336800575256,
max: 408.04874999821186,
average: 379.1356734991074,
median: 374.08505799621344,
results: [
408.04874999821186,
385.46425899863243,
386.83866499364376,
389.89311300218105,
368.5118200033903,
375.32072000205517,
369.17063499987125,
372.8493959903717,
368.1160089969635,
367.14336800575256
]
},
withSet: {
min: 117.38054099678993,
max: 141.73810701072216,
average: 125.5299181997776,
median: 122.77016250044107,
results: [
141.73810701072216,
121.27236399054527,
122.01307900249958,
121.94323199987411,
122.74919401109219,
131.10868400335312,
117.38054099678993,
126.6241319924593,
127.6787180006504,
122.79113098978996
]
},
withSort: {
min: 55.56011998653412,
max: 65.89031200110912,
average: 58.22068350017071,
median: 57.26997400075197,
results: [
60.35952399671078,
57.611115008592606,
56.768538013100624,
57.54646299779415,
58.87953099608421,
65.89031200110912,
55.56011998653412,
56.99348500370979,
56.1416649967432,
56.45608200132847
]
}
}
NUM_ELEMENTS = 1_000_000 - REPETITION_RATE = UNUSUAL - PRESORTED
{
withForLoop: {
min: 327.7845759987831,
max: 362.2078289985657,
average: 342.5873847991228,
median: 342.51240300387144,
results: [
336.3179539889097,
355.4238319993019,
346.7273070067167,
327.7845759987831,
362.2078289985657,
344.6583460122347,
327.86210499703884,
331.5532739907503,
340.3664599955082,
352.9721650034189
]
},
withSet: {
min: 106.5443020015955,
max: 138.63980700075626,
average: 117.35592220425606,
median: 114.33523450791836,
results: [
110.89038001000881,
108.69839200377464,
129.5499380081892,
138.63980700075626,
106.5443020015955,
114.91061700880527,
118.87106600403786,
120.74676299095154,
110.94810500741005,
113.75985200703144
]
},
withSort: {
min: 33.01224599778652,
max: 44.01350799202919,
average: 37.149842695891856,
median: 36.649998001754284,
results: [
36.47280099987984,
36.19507499039173,
36.40855699777603,
44.01350799202919,
36.82719500362873,
37.01220999658108,
38.938134998083115,
33.01224599778652,
34.333357989788055,
38.28534199297428
]
}
}
NUM_ELEMENTS = 10_000_000 - REPETITION_RATE = LIKELY
{
withForLoop: {
min: 1917.3692060038447,
max: 2010.0801389962435,
average: 1962.0589136004448,
median: 1954.4033880010247,
results: [
2010.0801389962435,
1917.3692060038447,
1959.8589759990573,
1949.5907730013132,
1956.6235629990697,
1952.1832130029798,
1981.0251489952207,
1951.4385790005326,
1994.0854310020804,
1948.334107004106
]
},
withSet: {
min: 1790.3471409976482,
max: 1853.03464499861,
average: 1805.2915181994438,
median: 1799.2067870013416,
results: [
1819.8134460002184,
1805.9403330013156,
1806.3639229983091,
1795.3301180005074,
1790.3471409976482,
1795.9115020036697,
1791.045364998281,
1792.6266369968653,
1853.03464499861,
1802.5020719990134
]
}
}
NUM_ELEMENTS = 10_000_000 - REPETITION_RATE = CASUAL
{
withForLoop: {
min: 3789.1354789957404,
max: 4630.735077001154,
average: 4178.7110580004755,
median: 4081.3821364976466,
results: [
3789.1354789957404,
4028.857537999749,
4010.4580660015345,
4574.977958001196,
4630.735077001154,
4160.151626005769,
3983.446921005845,
4065.9210390001535,
4096.84323399514,
4446.58364199847
]
},
withSet: {
min: 2518.947176001966,
max: 2839.48312599957,
average: 2616.3203426986934,
median: 2596.4002064988017,
results: [
2668.5661209970713,
2687.6818829998374,
2589.4644069969654,
2519.6772719994187,
2603.336006000638,
2839.48312599957,
2607.236534997821,
2554.2970929965377,
2574.5138079971075,
2518.947176001966
]
}
}
NUM_ELEMENTS = 10_000_000 - REPETITION_RATE = UNUSUAL
{
withForLoop: {
min: 10235.086987003684,
max: 13434.179785996675,
average: 11923.496706897766,
median: 11667.779426496476,
results: [
10235.086987003684,
12663.538829997182,
11813.862790994346,
11065.280889995396,
11427.339896000922,
11521.696061998606,
11503.277909994125,
13021.919983997941,
13434.179785996675,
12548.783932998776
]
},
withSet: {
min: 4166.4050879999995,
max: 4891.42372700572,
average: 4458.152116901428,
median: 4385.465481501073,
results: [
4308.565682001412,
4891.42372700572,
4195.092826999724,
4806.711855001748,
4205.6086410060525,
4744.175035998225,
4258.800287000835,
4462.365281000733,
4166.4050879999995,
4542.372744999826
]
}
}