Цикл по массиву или объекту для обновления счетчиков

Question

У меня есть проблема, похожая на следующую:

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


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

Цель : обновить счетчик в объекте фруктов на основе присутствия фруктов в массиве корзины.

Примечание: объект фруктов может содержать больше свойств (фруктов), чем элементов в массиве корзины.

В этом случае, пожалуйста, предположите, что элемент в корзине появится не более одного раза.

Я предложил 2 решения:

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

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

Какой самый эффективный (с точки зрения производительности) способ решения этой проблемы?

Answer 1

Если вы спрашиваете только о производительности, второй способ лучше, и вот почему:

В первом случае вы перебираете массив ключей, и для каждого ключа вы перебираете весь basket. Это приводит к порядку O(n * m), где n - это количество ключей, а m - количество фруктов в корзине.

Второе решение можно переписать как fruit in fruits && fruits[fruit]++, и в результате что для каждого фрукта в basket вам нужно будет только проверить наличие ключа в объекте, что происходит почти постоянно, поэтому порядок будет O(m).

Answer 2

Эксперты говорят, что основной поток for loop лучше всего подходит для итерации. Они обеспечивают хорошую производительность по сравнению с петлями forEach и for of.

Под капотом скрипт-движок java использует for loop для циклов forEach и for of.

Я приведу пример использования for loop для решения этой проблемы,

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);

Подводя итог, если вы заинтересованы в производительности, то for loop - ваш лучший выбор.

вот несколько ссылок, относящихся к этому обсуждению ,
stackoverflow .
hackernoon .
davidtang .

Answer 3

Вы можете указать, хотите ли вы сохранить все результаты или только те, которые вам нужны, передав объект fruits в функцию frequency в качестве второго необязательного параметра.

Сборка frequency карта частот всех найденных фруктов.

Если вы хотите по-настоящему оптимизировать, спросите на сайте Code Review Stack Exchange .

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;
}

---

Обратная связь

Что касается вашего предполагаемого вопроса, вы можете посмотреть на это двумя способами.

1. Перебирая все элементы в корзине и увеличивая количество фруктов

Это должно пройти весь путь через корзину, но это эффективно, потому что это O (n) + O (1 ).

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

Перебирая фрукты и проверяя, есть ли они в корзине.

Это ваше желаемое поведение, потому что вы проверяете только те фрукты, о которых хотите знать, и количество фруктов никогда не увеличивается выше 1.

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