Kann ich die Häufigkeit aller Elemente in einem zweidimensionalen Array schneller zählen? Wie dieses Beispiel:

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

Mein erwartetes Ergebnis wäre ein Array von Objekten, die Schlüsselwörter und Häufigkeitswerte enthalten.
So was,

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

Hier ist meine Lösung:

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

Hat jemand einen schnelleren Weg, um dieses Problem zu lösen? Hinweis: Mit zweidimensionalem Schlüsselwort-Array (ca. 50.000 Datensätze).

4
Parn 18 Jän. 2019 im 09:00

5 Antworten

Beste Antwort

Wenn dies wirklich ein Engpass ist und das Herauspressen der Geschwindigkeit aus dem Zählen Code wert ist, der nicht ganz so hübsch ist wie die funktionalen Lösungen, fällt es Ihnen schwer, for - Schleifen in den heutigen Javascript-Engines zu schlagen. In meinen Tests ist dies ungefähr doppelt so schnell wie bei Verwendung von 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 hier

3
Mark Meyer 18 Jän. 2019 im 06:49

Hier konvertiere ich das ursprüngliche Array in einen String und zähle das Zeichen als Ergebnis in ein anderes Array.

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)
1
holydragon 18 Jän. 2019 im 06:35

Sie können die Komplexität reduzieren, indem Sie Wörter in einer Karte speichern und am Ende auf der Karte iterieren. Dies erspart das Iterieren des Ergebnisses für jedes Wort

Alte Komplexität O(N * M * R) Array * Wort in jeder Gruppe * Ergebnis Neue Komplexität O(N*M + R)

Hinweis: Array.prototype.concat hat meiner Meinung nach eine große Laufzeit. Für jeden Concat wird ein neues Objekt erstellt und die vorhandenen und neuen Werte werden in dieses neue Objekt kopiert und zurückgegeben. Deshalb werden die alten Arrays nicht geändert. So werden Werte immer wieder gelesen.

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));
2
Sudhir Ojha 18 Jän. 2019 im 06:36

Sie können es mit {vereinfachen {X0}} und { {X1}}:

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

Wenn flat nicht unterstützt, benutze [].concat(...input).reduce()

3
adiga 18 Jän. 2019 im 06:20

Mit .reduce() können Sie die gewünschte Frequenz in Form eines Objekts abrufen:

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);
5
Mohammad Usman 18 Jän. 2019 im 06:07