JavaScript - Найти количество повторений массивов

Question

У меня есть следующие массивы:

let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]

Как проверить, сколько раз слова из b содержатся в a?

В приведенном выше случае ответ будет 2 раза, так как все слова из b содержатся дважды. Однако, если a следующее:

let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer"]

Ответом будет 1, поскольку egg содержится только один раз.

Ключевым моментом здесь является эффективность времени, так как я буду работать со списками, содержащими более 100 000 элементов.

Answer 1

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

Производительность должна быть почти линейной в сумме длин a и b. (Вероятно, существует некоторая трудноизмеримая нелинейность в a in o, но я не знаю алгоритмы, используемые внутренне для двигателей, поэтому я не уверен.)

Обратите внимание, что bs.reduce((o, b) => Object.assign(o, {[b]: 0}), {}) вызывается только один раз, чтобы сформировать начальный аккумулятор для первого reduce; это не вложенное сокращение.

const counts = (as, bs) => as.reduce(
  (o, a) => Object.assign(o, a in o ? {[a]: o[a] + 1} : {}),
  bs.reduce((o, b) => Object.assign(o, {[b]: 0}), {})
)

const a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
const b = ["egg", "salt", "beer", "tofu"]

console.log(counts(a, b))

Но фактическая производительность, скорее всего, будет меньше, чем при использовании некоторых ручных циклов for или while. reduce просто не так производительно, как они.

Обновление

Это на самом деле не отвечает на вопрос, который задают. Я неправильно понял вопрос. Обновленная версия

const minMatch = (as, bs) => Math.min(...Object.values(as.reduce(
  (o, a) => Object.assign(o, a in o ? {[a]: o[a] + 1} : {}),
  bs.reduce((o, b) => Object.assign(o, {[b]: 0}), {})
)))

const a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
const b = ["egg", "salt", "beer"]

console.log(minMatch(a, b))

Answer 2

Итеративный массив a с Array.reduce(). Преобразуйте массив b в Map и используйте его в качестве начального значения приведения.

Если элемент из массива a существует на карте, увеличьте значение. Если нет, игнорируйте это. Когда закончите, распространите значения карты через Math.min():

const a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
const b = ["egg", "salt", "beer"]

const result = Math.min(
  ...a.reduce((m, s) =>
      m.has(s) ? m.set(s, (m.get(s) || 0) + 1) : m
    , new Map(b.map(s => [s, 0]))
  ).values()
);

console.log(result);

Answer 3

Используйте числовой цикл for, чтобы уменьшить a в простой объект:

let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]

const keys = b.reduce((o, k) => Object.assign(o, { [k]: true }), {})
const { length } = a
const values = {}

for (let i = 0; i < length; i++) {
  const key = a[i]
  
  if (key in keys) {
    if (key in values) {
      values[key]++
    } else {
      values[key] = 1
    }
  }
}

console.log(values)

Числовой цикл for работает быстрее, чем Array методы, такие как reduce и forEach, и, как правило, быстрее, чем for...of и for...in, поскольку он не использует итераторов или отражения для перечисления ключей массива.

Объект keys предназначен для уменьшения поиска с O (n) до ~ O (1) в зависимости от размера b, что дает вам общую сложность около O (n) . Если b также велико, используйте числовой цикл for для создания keys и обратите внимание, что поиск может ухудшиться с ~ O (1) до O (log (n)), что даст вам общее время сложность O (n log (n)) .

Answer 4

let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]
let counts ={}

b.forEach(word=>{      
    counts[word] = a.filter(item => item ===word).length
});    

console.log(counts)

Answer 5

Вы можете использовать метод reduce:

let words = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]

var initialValue = {};

var reducer = function(word, index){
	if(!word[index]){
		word[index] = 1;
	} else{
		word[index] = word[index] + 1;
	}
	return word;
}

var results = words.reduce(reducer, initialValue);

console.log(results);

Answer 6

Это должно работать

let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "salt"];
let b = ["egg", "salt"];

const products = a.reduce((result, current) => {
  b.forEach(word => {
    if (word === current) {
      result[word] = result[word] ? result[word] + 1 : 1;
    }
  })
  return result;
}, {});

console.log(products); // { egg: 1, salt: 3 }

Answer 7

Подход может заключаться в построении хеш-карты при итерации по массиву A и доступе к этой хеш-карте при итерации по массиву B (см. Код ниже)

let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]
let hashMap = {};

for(let element in a){
  if(!hashMap[a[element]])
     hashMap[a[element]] = 0;
  hashMap[a[element]]++;
}

var minVal = a.length;
for(let element in b){
  if(hashMap[b[element]])
     minVal = Math.min(minVal, hashMap[b[element]]);
}
console.log(minVal);