代码之家 › 专栏 › 技术社区 › Parn

快速查找二维频率值关键字数组的方法

performance arrays javascript

Parn · 技术社区 · 6 年前

我有更快的方法来计算二维数组中所有元素的所有频率吗?像这个例子:

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

有人有更快的方法来解决这个问题吗? 注:二维关键字数组(约50000条记录)。

5 回复 | 直到 6 年前

Mark 6 年前

如果这真的是一个瓶颈,从计数中挤出速度是值得的,那么代码就没有功能解决方案那么漂亮了,那么您将面临困难。 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)
    }
}

杰斯普夫 Benchmark here

Mohammad Usman 6 年前

你可以使用 .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);

adiga 6 年前

您可以使用 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))

如果 平的 不是 supported 使用 [].concat(...input).reduce()

Sudhir Ojha 6 年前

您可以通过将单词存储在映射中,然后在末尾迭代映射来降低复杂性。这节省了对每个单词的结果进行迭代

陈旧的复杂性 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));

holydragon 6 年前

在这里,我将原始数组转换为字符串,然后将字符计数为另一个数组。

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)