Более быстрый способ найти вхождение двумерного массива ключевых слов со значением частоты

Question

Есть ли у меня более быстрый способ подсчета всей частоты всех элементов в 2-мерном массиве? Как этот образец:

var array = [["a", "b"]["c", "d"]["b", "d"]["c", "a", "b"], ["a", "b", "c", "d"];

Мой ожидаемый результат будет массив объектов, содержащих ключевое слово и значение частоты.
Вот так

result = [{ keyword: "a",
            frequency: 3
          }, {
            keyword: "b",
            frequency: 4
          }, ... ];

Вот мое решение:

function generateData (records) {
  var data = [];
  for (var i = 0; i < records; ++i) {
      data.push(["a", "b", "c", "d", "e"]);
  }
  // some gap to insert data
  setTimeout(function () {
  }, Math.random() * 1000);
  return data;
}

function mine (data) {
  var result = [];
  data.forEach( function (keywords) {
      for (var i = 0, len = keywords.length; i < len; ++i) {
          var pos = result.map( function (x) {
              return x.keyword;
          }).indexOf(keywords[i]);

          if (pos == -1) {
              var newKeyword = {
                  keyword: keywords[i],
                  frequency: 1
              }
              result.push(newKeyword);
          } else { 
              result[pos].frequency += 1;
          }
      }
  });
  return result;
}

var dataset = generateData(50000);

var start = performance.now();
var result = mine(dataset);
var end = performance.now();

console.log(result);
console.log("Total time: " + (end - start) + " milliseconds.");

У кого-нибудь есть более быстрый способ решить эту проблему? Примечание. С двумерным массивом ключевых слов (около 50 000 записей).

Answer 1

Если это действительно узкое место и выжимание скорости из подсчета стоит кода, который не так хорош, как функциональные решения, вам будет непросто обойти циклы for в современных движках javascript. В моих тестах это примерно в два раза быстрее, чем при использовании reduce():

var array = [["a", "b"],["c", "d"],["b", "d"],["c", "a", "b"], ["a", "b", "c", "d"]];

let counts = new Map()
for (let i = 0; i < array.length; i++){
    for (let j = 0; j < array[i].length; j++){
        let n = counts.get(array[i][j]) || 0
        counts.set(array[i][j], n + 1)
    }
}

JSperf Тест здесь

Answer 2

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

const array = [
  ["a", "b"],
  ["c", "d"],
  ["b", "d"],
  ["c", "a", "b"],
  ["a", "b", "c", "d"]
]
let result = array.join().replace(/[ ]/g, '').split(',')
let count = {}
result.forEach(c => count[c] = (count[c] || 0) + 1)
console.log(count)

Answer 3

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

Старая сложность O(N * M * R) массив * слово в каждой группе * результат Новая сложность O(N*M + R)

Примечание: Array.prototype.concat, я считаю, имеет большое время выполнения. Для каждого concat создается новый объект, а существующие и новые значения копируются в этот новый объект и возвращаются. Вот почему старые массивы не модифицируются. Значения читаются снова и снова.

var array = [["a", "b"],["c", "d"],["b", "d"],["c", "a", "b"], ["a", "b", "c", "d"]];
var resultMap = {};
array.forEach(function (keywords) {
    keywords.forEach(function(word, i){
    if(resultMap[word]) {
        resultMap[word].frequency = resultMap[word].frequency + 1;
    }
    else{
        resultMap[word] = {
        keyword: word,
        frequency: 1
      };
    }
  });
});

console.log(Object.values(resultMap));

Answer 4

Вы можете упростить это до чего-то подобного, используя flat и reduce:

const input = [["a", "b"],["c", "d"],["b", "d"],["c", "a", "b"],["a", "b", "c", "d"]]

,output = input.flat().reduce((acc, a) =>
  ((acc[a] = acc[a] || {keyword: a, frequency: 0})["frequency"]++, acc)
,{})

console.log(Object.values(output))

Если flat не поддерживается , используйте [].concat(...input).reduce()

Answer 5

Вы можете использовать .reduce(), чтобы получить желаемую частоту в виде объекта:

let data = [
  ["a", "b"],
  ["c", "d"],
  ["b", "d"],
  ["c", "a", "b"],
  ["a", "b", "c", "d"]
];

let result = [].concat(...data).reduce((r, c) => (r[c] = (r[c] || 0) + 1, r), {});

console.log(result);