Faster way to find an occurrence of 2-Dimensional array of keywords with frequency value

user_7888000 0
Viewed 513

Do I have a faster way to count all frequency of all elements in 2-Dimensional array? Like this sample: 

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

My expected result would be an array of objects contain keyword and frequency value.
Like this,

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

Here is my solution:

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

Does anyone have a faster way to solve this problem? Note: With 2-Dimensional of keywords array (around ~50,000 records).

arrays javascript performance
5 Answers

You can use .reduce() to get the desired frequency in the form of an object:

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

user_59336560

You could simplify it to something like this using flat and 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))

If flat isn't supported, use [].concat(...input).reduce()

user_30822960

If this really is a bottleneck and squeezing speed out of the counting is worth code that's not quite as pretty as the functional solutions, you will have a hard time beating for loops in today's javascript engines. In my tests this is about twice as fast as using 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 Benchmark here

user_38746230

You can reduce complexity by storing words in a map, then iterating on the map at the end. This saves iterating on the result for every word

Old complexity O(N * M * R) array * word in each group * result New complexity O(N*M + R)

Note: Array.prototype.concat, I believe, has a big runtime. For each concat, a new object is created and the existing and new values are copied into that new object and returned. That's why the old arrays are not modified. So values are read over and over.

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

user_109314670

Here I convert the original array to string and then count the character into another array as a result.

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)

user_37013930
Related