Índice de objeto vs Búsqueda en arreglo

nov17

Written by david

Hace mucho tiempo tenía la corazonada de que la búsqueda por índice en objectos debería ser mucho más rápida que una búsqueda en arreglos, y hace poco me enfrenté con la opción de transformar un arreglo en un objeto con el fin de optimizar la búsqueda, así que realicé una prueba en jsPerf y he descubierto interesantes resultados.

Básicamente la prueba consiste en realizar la búsqueda de una cadena en un arreglo y en un objeto. Lo que intuía era que pedir un indice de un objeto era mucho más eficiente que recorrer un arreglo buscando el mismo.

El código se resume al siguiente:

    var obj ={'test1':{'value':1},
    'test2':{'value':2},
    'test3':{'value':3},
    'test4':{'value':4},
    'test5':{'value':5},
    'test6':{'value':6},
    'test7':{'value':7},
    'test8':{'value':8},
    'test9':{'value':9},
    'test10':{'value':10},
    };

    var arr =[{'name':'test1','value':1},
    {'name':'test2','value':2},
    {'name':'test3','value':3},
    {'name':'test4','value':4},
    {'name':'test5','value':5},
    {'name':'test6','value':6},
    {'name':'test7','value':7},
    {'name':'test8','value':8},
    {'name':'test9','value':9},
    {'name':'test10','value':10}
    ];
    
    function searchInArray(search){
      for(var i=0; i<arr.length; i++){
        var val = arr[i];
        if(val.name==search){
          return val.value;
        }
      }
    }
    
    function searchInObject(search){
      var res = obj[search];
      if(res){
        return res.value;
      }
    }

He incluído un objeto con el valor dentro del gran objeto de prueba, lo cual se podría omitir lógicamente, pero lo hice así para poner en igualdad de condiciones el rendimiento de ambas pruebas. 

El siguiente paso era considerar los posibles escenarios extremos de las búsquedas: 

a)  El valor existe en el primer resultado

b) El valor existe como último resultado

c) El valor no existe

Al correr estas pruebas encontré que en la mayoría de los casos la búsqueda por índice en un objeto es mucho más rápida que en un arreglo, incluso es independiente del orden de los atributos, lo cual me pareció excelente.

Por otra parte, el caso de la búsqueda de un valor inexistente viene siendo mucho más lenta en el objeto que si este existiera, no obstante, le sigue ganando al arreglo (incluso si existiera el índice y estuviera de último). Aquí ya estaba demostrado la eficiencia de realizar las búsquedas por índice.

Sin embargo, y al estilo MythBusters, decidí hacer la prueba con objectos y arreglos mucho más grandes, así que creé otra prueba con 2000 elementos.

    var limit =2000;
    
    var obj2 ={};
    for(var i =0; i < limit; i++){
      obj2['test'+ i]={
        'value': i
      }
    }
    
    var arr2 =[];
    for(var i =0; i < limit; i++){
      arr2.push({
        'name':'test'+ i,
        'value': i
      });
    }
    
    function searchInArray2(search){
      for(var i =0; i < arr2.length; i++){
        var val = arr2[i];
        if(val.name== search){
          return val.value;
        }
      }
    }
    
    function searchInObject2(search){
      var res = obj2[search];
      if(res){
        return res.value;
      }
    }

Los resultados son contundentes! La búsqueda por índice es mucho más eficiente que en arreglos, aquí pueden encontrar los tests:

http://jsperf.com/object-index-vs-array-search

http://jsperf.com/object-index-vs-array-search-bigger

Las conclusiones se resumen a que si se van a manejar objetos y estos contienen identificadores, se optimizaría el rendimiento de las búsquedas almacenando estos en un objeto o transformando el arreglo de búsqueda en un objeto. Lo anterior teniendo en cuenta que al hacer esto se sacrifica un poco de rendimiento en el setup de la aplicación por ganar rendimiento en las futuras búsquedas.

Tags

Categories