4
votes

Un moyen plus rapide de trouver une occurrence de tableau bidimensionnel de mots-clés avec une valeur de fréquence

Ai-je un moyen plus rapide de compter toutes les fréquences de tous les éléments d'un tableau à 2 dimensions? Comme cet exemple:

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

Mon résultat attendu serait un tableau d'objets contenant un mot-clé et une valeur de fréquence.
Comme ça,

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

Voici ma solution:

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

Quelqu'un a-t-il un moyen plus rapide de résoudre ce problème? Remarque: avec un tableau bidimensionnel de mots-clés (environ 50 000 enregistrements).

javascript performance arrays

0 commentaires

5 Réponses :

5
votes

Vous pouvez utiliser .reduce () pour obtenir la fréquence souhaitée sous la forme d'un objet:

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

3 commentaires

Bien qu'il s'agisse d'une approche intéressante, elle serait améliorée si vous donniez une comparaison des performances avec la solution OP, car ils ont dit «plus rapide», ce qui pourrait signifier moins de code ou moins de temps de cycle pour le calcul.

Cela devrait être beaucoup plus rapide, merci pour les idées! Je vais essayer de tester avec mes ensembles de données et de trouver le temps d'exécution pour cela.

Celui-ci est en fait plus rapide, j'ai testé avec l'extrait de ma question initiale.

2
votes

Vous pouvez réduire la complexité en stockant des mots dans une carte, puis en effectuant une itération sur la carte à la fin. Cela évite d'itérer le résultat pour chaque mot

Ancienne complexité O (N * M * R) tableau * mot dans chaque groupe * résultat Nouvelle complexité O (N * M + R)

Remarque: Array.prototype.concat , je crois, a une grande exécution. Pour chaque concat, un nouvel objet est créé et les valeurs existantes et nouvelles sont copiées dans ce nouvel objet et renvoyées. C'est pourquoi les anciens tableaux ne sont pas modifiés. Les valeurs sont donc lues encore et encore.

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 commentaires

édité pour qu'il fonctionne réellement. astuce de pro pour la journée: vérifiez le code pour les erreurs avant de soumettre!

a changé l'itération en Object.values après avoir lu la réponse d'adiga

3
votes

Vous pouvez le simplifier en quelque chose comme ceci en utilisant flat et réduire :

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

Si flat n'est pas pris en charge , utilisez [ .concat(...input).reduce()

0 commentaires

1
votes

Ici, je convertis le tableau d'origine en chaîne, puis je compte le caractère dans un autre tableau en conséquence.

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)

2 commentaires

C'est plus rapide?

Que signifie remplacer ici? J'obtiens le même résultat en utilisant uniquement array.join (). Split (",") . Bien que j'aime votre solution car elle est un peu différente des autres, elle reste la plus lente si on la compare à la réduction et à la boucle for. .

3
votes

S'il s'agit vraiment d'un goulot d'étranglement et que réduire la vitesse du comptage vaut du code qui n'est pas aussi joli que les solutions fonctionnelles, vous aurez du mal à battre les boucles for dans les moteurs javascript d'aujourd'hui. Dans mes tests, c'est environ deux fois plus rapide que d'utiliser 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 ici

1 commentaires

Des performances très intéressantes, un code clair et plus facile à lire. Merci beaucoup !