How to filter and then aggregate results in Javascript-CodePudding

Say you have two arrays and want to find the most visited group (or groups - limit will be given) in from:

const Animal= [
  { id: 1, name: "cat", group: "four legs"},
  { id: 2, name: "dog", group: "four legs"},
  { id: 3, name: "bird", group: "two legs"},
  { id: 4, name: "fish", group: "no legs"},
  { id: 5, name: "ants", group: "six legs"},
  { id: 6, name: "monkey", group: "two legs"},
  { id: 7, name: "horse", group: "four legs"},
  { id: 8, name: "spiders", group: "eight legs"},  
  { id: 9, name: "catepillar", group: "many legs"},  
]
const AnimalVisits= [
  { id: 1, visits: 40 },
  { id: 2, visits: 30 },
  { id: 3, visits: 50 }, 
  { id: 4, visits: 100 },
  { id: 5, visits: 90 },
  { id: 6, visits: 110 },
  { id: 7, visits: 20 },
  { id: 8, visits: 165 },
  { id: 9, visits: 1000 },
]

Expected answer "many legs".

I have written my own solution but I am not convinced it's the most efficient. My Steps:

Create a new array with "group" out of Animal and AnimalVisits.
Aggregate by "group".
Sort and filter based on the given limit.
Reduce to array result that outputs something like:
- limit "1" output: "many legs"
- limit "2" output: "many legs, eight legs"
- limit "3" output: "many legs, eight legs, two legs"

CodePudding user response：

I make a function with an approach of doing sorting by Array.sort() method in descending order (from top to bottom), followed by cutting the array by how many limits do you want, Then map it with animals array and get only the property group you want, Finally join them back with comma ', '.

const animals = [
  { id: 1, name: "cat", group: "four legs" },
  { id: 2, name: "dog", group: "four legs" },
  { id: 3, name: "bird", group: "two legs" },
  { id: 4, name: "fish", group: "no legs" },
  { id: 5, name: "ants", group: "six legs" },
  { id: 6, name: "monkey", group: "two legs" },
  { id: 7, name: "horse", group: "four legs" },
  { id: 8, name: "spiders", group: "eight legs" },
  { id: 9, name: "catepillar", group: "many legs" },
];
const animalsVisits = [
  { id: 1, visits: 40 },
  { id: 2, visits: 30 },
  { id: 3, visits: 50 },
  { id: 4, visits: 100 },
  { id: 5, visits: 90 },
  { id: 6, visits: 110 },
  { id: 7, visits: 20 },
  { id: 8, visits: 165 },
  { id: 9, visits: 1000 },
];
const topVisited = (limit) =>
  animalsVisits
    .slice() //shallow copy
    .sort((a, b) => b.visits - a.visits) //sorting in desending order
    .slice(0, limit) // cut how many top limit
    .map(({ id }) => animals.find((animal) => animal.id === id).group) //mapped with group from animals array
    .join(", ");

Tests:

console.log(topVisited(1) === "many legs"); //true
console.log(topVisited(2) === "many legs, eight legs");//true
console.log(topVisited(3) === "many legs, eight legs, two legs");//true

Note: doing a Array.sort() method would change the original array, that's why I used Array.slice() to just make a copy of it.
Tip: About variable naming, if it is an array, it's preferable to name it in plurals instead of Animal do animals!

CodePudding user response：

I'd say there may be faster solutions to this problem - but it depends on what's involved in the steps you outlined. Specifically, the first step you mention :

"Create a new array with "group" out of Animal and AnimalVisits."

Because the visits and animals arrays in your OP are both ordered by ID already, this could be accomplished in linear time, however if that's not always going to be a given for the problem then implementations may vary wildly. For example, are you looping the whole Animals array every time to find the overlapping ID?

Moving on, the "aggregate by group" step can also be accomplished in linear time by reading each element into a map, but you don't mention a map so again time complexity may vary based on implementation - again like step 1 the most expensive way to add time to this method would be to loop the array as you aggregate.

IMO any efficient approach to this problem will involve a map / hash table etc. Below I've posted a semi-efficient solution to the problem, but note* this problem has a lot in common with the find the Kth largest element in a list problem, and the most efficient solution uses a priority queue to keep the elements in order. Javascript doesn't natively support a priority queue but that's where I'd go to speed this up - looks like there is at least 1 package already on NPM (disclaimer: I haven't used it). As it is, I simply sort the output and then slice off the last N items to fulfill your limit requirement.

function mostVisits(animals, visits, topN) {
    const groups = new Map();
    const animalLookup = new Map();

    for (let i = 0; i < animals.length; i  ) {
        animalLookup.set(animals[i].id, animals[i])
    }

    for (let j = 0; j < visits.length; j  ) {
        console.log(visits[j], animalLookup.get(visits[j].id))
        const group = animalLookup.get(visits[j].id).group;
        if (!groups.has(group)) groups.set(group, visits[j].visits);
        else groups.set(group, groups.get(group)   visits[j].visits);
    }

    return Array.from(groups).sort((a, b) => a[1] - b[1]).slice(-1 * topN);
}

Here's almost the same solution showing how you could exploit the fact that the inputs are already ordered :

function mostVisits(animals, visits, topN) {
    const groups = new Map();

    for (let i = 0; i < animals.length; i  ) {
        const group = animals[i].group;
        if (!groups.has(group)) groups.set(group, visits[i].visits);
        else groups.set(group, groups.get(group)   visits[i].visits);
    }

    return Array.from(groups).sort((a, b) => a[1] - b[1]).slice(-1 * topN);
}

Note* if you were to use a priority queue to speed things up, it'd replace the last line of my function there ie. Array.from().sort().slice()

Hope this helps!

CodePudding user response：

You could make a dictionary with the group as the keys and loop over the visits array and keep adding to the group's value. This handles having more than one entry for the same group.

Then use Object.entries() to turn it into an array of [key, value], and sort based on the value.

Finally use Array.prototype.slice() to get the range of values you need.

const Animal= [
  { id: 1, name: "cat", group: "four legs"},
  { id: 2, name: "dog", group: "four legs"},
  { id: 3, name: "bird", group: "two legs"},
  { id: 4, name: "fish", group: "no legs"},
  { id: 5, name: "ants", group: "six legs"},
  { id: 6, name: "monkey", group: "two legs"},
  { id: 7, name: "horse", group: "four legs"},
  { id: 8, name: "spiders", group: "eight legs"},  
  { id: 9, name: "catepillar", group: "many legs"},  
]
const AnimalVisits= [
  { id: 1, visits: 40 },
  { id: 2, visits: 30 },
  { id: 3, visits: 50 }, 
  { id: 4, visits: 100 },
  { id: 5, visits: 90 },
  { id: 6, visits: 110 },
  { id: 7, visits: 20 },
  { id: 8, visits: 165 },
  { id: 9, visits: 1000 },
]

const visitDict = Animal.reduce((dict, animal) => {
  dict[animal.group] ||= 0;
  dict[animal.group]  = AnimalVisits.find(obj => obj.id === animal.id).visits || 0;
  return dict
}, {})
console.log('Dictionary: ', visitDict)

const sortedArray = Object.entries(visitDict).sort((a, b) => b[1] - a[1])
console.log('Sorted: ', sortedArray)

const sortedGroups = sortedArray.map(arr => arr[0]) // Can be chained after the sort above
console.log('Sorted Groups: ', sortedGroups)

const getTop = (num) => sortedGroups
  .slice(0, num)
  .join(', ')
  
console.log('Top 3: '   getTop(3))