4
\$\begingroup\$
categories = [{id: "761601bc-4daf-4db2-a0cf-fe7f443fcb94", name: "Shoes"},{id: "601ebcfe-fcbd-4075-a4b4-a42e356c5747", name: "Hats"},{id: "238933cf-77a5-4443-b290-7d7c836f80ff", name: "Eyewear"}];

voucher = {id:1,categories:["761601bc-4daf-4db2-a0cf-fe7f443fcb94","601ebcfe-fcbd-4075-a4b4-a42e356c5747"]};

filterCategories(voucher) {
  const result = voucher.categories
    ? categories
        .filter(cat => {
          return voucher.categories.includes(cat.id);
        })
        .map(v => v.name)
        .sort()
        .join()
    : "";

  return result;
}

Expecting: "Hats,Shoes"

The result needs to be filtered and sorted and returned as a string. Is there a faster, more efficient way of doing this. Maybe using Lodash?

\$\endgroup\$
1
  • \$\begingroup\$ I think that this would widely be considered to be the most concise and easily accepted approach. As for time complexity, I don't think that there would be a more efficient way without a trade-off in readability. \$\endgroup\$ Jan 29, 2020 at 14:59

2 Answers 2

3
\$\begingroup\$

Normally there are a lot of categories, so I'd go through the voucher.categories array:

const filterCategories = (voucher, categories) => (
  Array.isArray(voucher.categories) ?
    voucher.categories
      .map(categoryId => {
        const categoryFound = categories.find(c => c.id === categoryId);
        return categoryFound ? categoryFound.name : null;
      })
      .filter(categoryName => categoryName !== null)
      .sort()
      .join() :
    ""
);

This way you don't have to go through the entire list of 'master' categories (which in practice may be very long) doing a search on the voucher categories in each iteration.

Note: it would be much faster if you could have the categories as an object with the id as index:

categories = {
  ["761601bc-4daf-4db2-a0cf-fe7f443fcb94"]: {name: "Shoes"},
  ["601ebcfe-fcbd-4075-a4b4-a42e356c5747"]: {name: "Hats"},
  ["238933cf-77a5-4443-b290-7d7c836f80ff"]: {name: "Eyewear"}
};

const filterCategories = (voucher, categories) => (
      Array.isArray(voucher.categories) ?
        voucher.categories
          .map(categoryId => {
            const categoryFound = categories[categoryId];
            return categoryFound ? categoryFound.name : null;
          })
          .filter(categoryName => categoryName !== null)
          .sort()
          .join() :
        ""
    );
\$\endgroup\$
5
  • \$\begingroup\$ You are wrong. Assuming the ids Are unique and c = categories.length And v=voucher.categories.length, ignoring sort And join, time complexity Is c*v+v in OP's implementation And v*c+v in yours. And that's the same thing. \$\endgroup\$
    – slepic
    Jan 30, 2020 at 8:58
  • \$\begingroup\$ But hey thinking about it, for randomly chosen voucher categories you probably save some searches in most cases. Just the asymptotic upper limit is the same. \$\endgroup\$
    – slepic
    Jan 30, 2020 at 9:10
  • \$\begingroup\$ @slepic thanks for your comments. I'm assuming 'categories' is a master table of categories, with id as PK (unique). I'm also assuming 'categories' is in practice much longer than 'voucher.categories' (c >> v). So under these conditions, even with the same asymptotic limit, I think my function would be faster, but I haven't measured it. \$\endgroup\$
    – lgonzalo
    Jan 31, 2020 at 12:19
  • \$\begingroup\$ To be more specific. If all the voucher categories are on the end of the master categories list, the performance will be same. If all voucher categories are on the beginning of the master categories list, then your implementation goes to v*v + v. Somewhere between for the rest (and likely most) of cases. The performance gain will also be proportional to c - v (assuming v<=c, although, in practise, likely just v<c or even v<<c). \$\endgroup\$
    – slepic
    Jan 31, 2020 at 19:29
  • \$\begingroup\$ So yeah yours is gonna be (somewhat) faster in most real world scenarios. I already voted your answer up yesterday :) Anyway, now I'm getting curious if a simple for loop combining the map and filter can make it even faster... \$\endgroup\$
    – slepic
    Jan 31, 2020 at 19:38
2
\$\begingroup\$

It may make sense to turn voucher.categories into a Set (or store them in a Set instead of an array in the first place) to speed up the contains call, however that is only sensible, if you expect it to contain a lot of items.

Other than that I'd move the check for the existence of voucher.categories (and add a check if it's empty) outside the expression, in order to reduce the indentations and make the code more readable:

filterCategories(voucher) {
  if (!voucher.categories || voucher.categories.length == 0) {
     return "";
  }
  return categories
    .filter(cat => voucher.categories.includes(cat.id))
    .map(v => v.name)
    .sort()
    .join();
}
\$\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.