Looping through Array or Object to update counts

Question

I have a problem that is similar to the following:

let fruits = { Apples:0, Bananas:0, Oranges:0 }


var basket = ['Apples', 'Oranges', 'Bananas', 'Potatoes', 'Cucumber']

Objective: to update the count in fruits object based on the presence of the fruit in the basket array.

Note: the fruits object may contain more properties (fruits) than items in the basket array.

For this case, please assume that an item in the basket will not appear more than once.

I have come up with 2 solutions:

for (const fruit of Object.keys(fruits)) {
    basket.includes(fruit) && fruits[fruit]++
} 

basket.forEach( (fruit) => { 
    fruits.hasOwnProperty(fruit) && fruits[fruit]++ 
} )

What is the most effective way (in terms of performance) of solving this?

The first one won't even work if there are more than one Bananas right? — TKoL, Jan 07 '20 at 17:46
I'm assuming if 'basket' has Bananas twice, you'd want `fruits` to have `Bananas: 2` — TKoL, Jan 07 '20 at 17:47
Sorry i should have clarified - in this case, it's unlikely that you will have any item appear twice. — Adnan, Jan 07 '20 at 17:48

score 2 · Answer 1 · answered Jan 07 '20 at 18:02

2

If you only ask about performances, the second way is better, and that's why:

In the first case you are iterating over the array of keys, and for each key you iterate over the whole basket. This brings the order to O(n * m) where n is the number of keys and m the number of fruits in the basket.

You could rewrite the second solution as fruit in fruits && fruits[fruit]++, and the result is that for each fruit in basket you would only need to check the existance of a key in an object, which happens in almost constant time, therefore the order will be O(m).

answered Jan 07 '20 at 18:02

grokked

401
2
8

I beg to differ, both the solution have same time complexity. In the first one, every key from **fruits** object is checked against every fruit in **basket** array. Hence, time complexity: **O(mn)**. In the second one, every fruit from **basket** array is checked against every key of **fruits** object. Which is again **O(mn)**. – hrithik gautham TG Jan 07 '20 at 18:26
I think @hrithik is correct. Is there any performance difference in checking if object has a value than if array has value? (Is there any difference in checking if fruits object has the fruit item (from basket array) vs if basket array has the fruit (key from fruits object)? – Adnan Jan 07 '20 at 18:58
@Adnan I think if Javascript **Maps** were used instead of **Object** for **fruits**, the time complexity for searching a key in **fruits** will come down to **O(1)**. Which makes the second solution*(with forEach)* **O(m)**, where, **m** is the size of the **basket** array. – hrithik gautham TG Jan 07 '20 at 19:07
@hrithikgautham Thanks for this, I wasn't even aware of Maps until now. Will look into this further. – Adnan Jan 07 '20 at 19:25
@hrithikgautham according to https://stackoverflow.com/questions/368280/javascript-hashmap-equivalent JS objects are implemented as hashmaps, and key retrieval in hashmaps has constant time complexity, or O(1). So what I said is correct. Also, using for instead of foreach the change is less substantial, while using your second solution would speed up significantly while using a lot of keys. You can check https://jsperf.com/object-faster-loop this to see that my answer is correct. – grokked Jan 08 '20 at 01:03

Mr. Polywhirl · Answer 2 · 2020-01-07T18:35:50.417

You can specify if you want to retain all findings, or just the ones you want by passing your fruits object in the frequency function as the second optional parameter.

The frequency builds a frequency map of all the fruits found.

If you want a real optimization, ask over at the Code Review Stack Exchange site.

let basket = ['Apples', 'Oranges', 'Bananas', 'Potatoes', 'Cucumber']
let fruits = { Apples: 0, Bananas: 0, Oranges: 0 }

console.log(frequency(basket, fruits)) // only the ones request
console.log(frequency(basket))         // all fruits

function frequency(items, initial) {
  return items.reduce((freq, item, index) => {
    return initial == null || (initial != null && initial[item] != null)
      ? Object.assign(freq, { [item] : (freq[item] || 0) + 1 })
      : freq
  }, Object.assign({}, initial))
}

.as-console-wrapper {
  top: 0;
  max-height: 100% !important;
}

Feedback

As for your intended question, you can look at this two ways.

Looping over all the items in the basket and incrementing the fruit count

This will have to traverse all the way through the basket, but it is efficient because it is O(n) + O(1).

basket.forEach(fruit => {
  if (fruits[fruit] !== undefined) {
    fruits[fruit]++
  }
})
console.log(fruits)

Looping over the fruits and checking if they are in the basket.

This is your desired behavior, because you check only for the fruits you want to know about and the fruit count will never increment above 1.

Object.keys(fruits).forEach(fruit => {
  if (basket.includes(fruit)) {
    fruits[fruit]++;
  }
})
console.log(fruits);

hrithik gautham TG · Accepted Answer · 2020-01-07T18:16:59.403

Experts say that the mainstream for loop are the best for iterating. They afford a good performance compared forEach and for of loops.

Under the hood, java script engine is using for loop for forEach and for of loops.

I'll provide an example using for loop to tackle this problem,

let fruits = { Apples:0, Bananas:0, Oranges:0 }


var basket = ['Apples', 'Oranges', 'Bananas', 'Potatoes', 'Cucumber']

// using for loop
for(let i = 0 ; i < basket.length ; i++){
  const fruitFromBasket = basket[i];
  if(fruitFromBasket in fruits)
    fruits[fruitFromBasket]++;
}
console.log("fruits: ", fruits);

To sum up, if you are concerned with performance, then for loop is your best bet.

here are couple of links pertaining to this discussion,
stackoverflow.
hackernoon.
davidtang.

Looping through Array or Object to update counts

3 Answers3

Feedback