2
\$\begingroup\$

I wrote some function which should take an array of items:Array<Object> and array of excludes:Array<Object> with keys which values can't be present in items. and should return an array of filtered items.

Is there some way to improve it? Is complexity of that function equal O(n + k)?

const items = [
  { type: 'phone', name: 'iPhone', color: 'red' },
  { type: 'laptop', name: 'Chromebook', color: 'gray' },
  // 15,000 items
];

const excludes = [
  { k: 'color', v: 'gold' },
  { k: 'type', v: 'laptop' },
  // 1,000 items
];

const applyFilters = (items, excludes) => {
  const newExcludes = excludes.reduce((acc, curr) => {
    if (!acc[curr.k])
      acc[curr.k] = new Set();
        
    acc[curr.k].add(curr.v);
    
    return acc;
  }, {});
  
  return items.reduce((acc, curr) => {
    for (let key in curr) {
      if (newExcludes[key] && newExcludes[key].has(curr[key]))
        return acc;
    }
          
    return [...acc, curr];
  }, []);
};

console.log(applyFilters(items, excludes));

\$\endgroup\$
2
\$\begingroup\$

I believe you should take a bit more time on documenting what the applyFilters functionality requires from input parameters. You seem to have pretty specific requirements which would be good to have them documented. You could document them using JsDoc syntax in the following way

/**
 * @method applyFilters
 * @param { object[] } items: An array of objects
 * @param { {k: string, v: object}[] } exludes: An array of objects containing key that need to be checked for certain values
 * @returns { object[] } A filtered array of objects
 */
 const applyFilters = (items, excludes) => { /*...*/ };

I think the algorithmn can be improved however with 1 very simple change, nl:

const applyFilters = (items, excludes) => {
  const newExcludes = excludes.reduce((acc, curr) => {
    if (!acc[curr.k])
      acc[curr.k] = new Set();

    acc[curr.k].add(curr.v);

    return acc;
  }, {});

  return items.reduce((acc, curr) => {
    for (let key in curr) {
      if (newExcludes[key] && newExcludes[key].has(curr[key]))
        return acc;
    }
    // using [...acc, curr] is very expensive here
    acc.push(curr);      
    return acc;
  }, []);
};

The operation [...acc, curr] is a very expensive operation to use inside a reduce function. Since you start your operation with an empty arr and you only wish to add 1 item, I don't see why you use the simpler version of pushing an item and returning the existing array. The reason why it is that expensive is because it creates a complete copy of the previous array and just add's one item.

As an addition, I also made a small test that clearly shows the difference in performance, the test generates a set of 1500 items and around a 100 exclude filters, and clearly shows the difference in performance by taking out the expensive copy the spread operator introduces

/**
 * @method applyFilters
 * @param { object[] } items: An array of objects
 * @param { {k: string, v: object}[] } exludes: An array of objects containing key that need to be checked for certain values
 * @returns { object[] } A filtered array of objects
 */
const applyFilters = (items, excludes) => {
  const newExcludes = excludes.reduce((acc, curr) => {
    if (!acc[curr.k])
      acc[curr.k] = new Set();

    acc[curr.k].add(curr.v);

    return acc;
  }, {});

  return items.reduce((acc, curr) => {
    for (let key in curr) {
      if (newExcludes[key] && newExcludes[key].has(curr[key]))
        return acc;
    }
		return [...acc, curr];
  }, []);
};


/**
 * @method applyFiltersNoSpread
 * @param { object[] } items: An array of objects
 * @param { {k: string, v: object}[] } exludes: An array of objects containing key that need to be checked for certain values
 * @returns { object[] } A filtered array of objects
 */
const applyFiltersNoSpread = (items, excludes) => {
  const newExcludes = excludes.reduce((acc, curr) => {
    if (!acc[curr.k])
      acc[curr.k] = new Set();

    acc[curr.k].add(curr.v);

    return acc;
  }, {});

  return items.reduce((acc, curr) => {
    for (let key in curr) {
      if (newExcludes[key] && newExcludes[key].has(curr[key]))
        return acc;
    }
		acc.push(curr);
    return acc;
  }, []);
};

/**
 * @method testScenario
 * @param { number } runTest: how many time should the test be repeated
 */
const testScenario = function(runTest) {

  /**
   * @method generateItems
   * @param { number } totalItems: how many items should be generated
   * @param { object } template: an object describing how the items should look like
   * @param { string[]=* } on or more arrays that provide values for the template to be filled
   * @returns { object[] }
   */
  function generateItems(totalItems, template) {

    let result = [];
    for (let i = 0; i < totalItems; i++) {
      let item = {};
      for (let field in template) {
        let target = arguments[template[field]];
        let index = parseInt(Math.random() * target.length);
        item[field] = target[index];
      }
      result.push(item);
    }
    return result;
  }

  // this will create some larger seeds
  console.time('generate_items');
  const items = generateItems(
    1500, {
      type: 2,
      name: 3,
      color: 4
    }, ['phone', 'laptop', 'computer', 'netbook', 'tablet'], ['iPhone', 'Sony', 'Acer', 'Asus', 'MSI'], ['red', 'gray', 'pink', 'gold', 'silver', 'metalic', 'orange']
  );
  console.timeEnd('generate_items');

  console.time('generate_filters');
  const excludes = generateItems(
    100, {
      k: 2,
      v: 3
    }, ['color', 'type'], ['red', 'black', 'metalic', 'sony', 'iPhone']
  );
  console.timeEnd('generate_filters');

  for (let i = 0; i < runTest; i++) {
    console.log(`running test loop ${i}`);
    console.time('withSpread');
    let setResults = applyFilters(items, excludes);
    console.timeEnd('withSpread');

    console.time('noSpread');
    let noSpread = applyFiltersNoSpread(items, excludes);
    console.timeEnd('noSpread');

    !(noSpread.length === setResults.length && noSpread[0] === setResults[0] && noSpread[noSpread.length] === setResults[setResults.length]) && console.error('results do not match');
  }
};

testScenario(10);

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.