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

admin管理员组

文章数量:1355031

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

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

• javascript
• arrays
• performance

Share Improve this question Follow edited Jan 18, 2019 at 6:45 Parn asked Jan 18, 2019 at 6:00 ParnParn 91877 silver badges1919 bronze badges

Add a ment  | 

5 Answers 5

Sorted by: Reset to default 5

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

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

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

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

Old plexity O(N * M * R) array * word in each group * result New plexity 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));

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)

本文标签：