JavaScript Funktion schneller machen, ohne die Semantik zu ändern

[CyborgBeta]

Moin,

bitte spart euch Hasskommentare jeder Art...

Ich habe eine JS-Funktion, die zu langsam ist (die Ausführung dauert bei ca. 5000 Wörtern ca. 3-4 Sekunden). Wie könnte man die hinsichtlich der Laufzeit optimieren, ohne die Semantik (all zu sehr) zu ändern?

      function getPredictions(words, removals) {
        let scores = [];
        for (let i = 0; i < words.length; i++) {
          let w = words[i];
          let set1 = new Set(w.split(""));
          let set2 = new Set([...w].filter((x) => !removals.includes(x)));
          scores.push([w, set1, set2, 0, i + 1]);
        }
        for (let i = 0; i < scores.length; i++) {
          for (let j = 0; j < scores.length; j++) {
            if (i != j) {
              let c = 0;
              scores[i][1].forEach((e) => {
                if (scores[j][2].has(e)) {
                  c++;
                }
              });
              if (c > 0) {
                scores[i][3]++;
              }
            }
          }
        }
        scores.sort((a, b) => {
          return b[3] - a[3];
        });
        return scores;
      }

Wird set1 überhaupt gebraucht?

Besten Dank im Voraus

 

[BeBur]

Ohne tiefer drauf geschaut zu haben: Ich habe letztens eine JS Funktion optimiert und eine der Sachen, die eine großer Verbesserung gebracht hat war, den GC nicht in jeder Iteration anzutriggern, sondern möglichst viele Variablen außerhalb der kritischen Schleife zu deklarieren. Da sehe ich hier spontan ebenso Potential.

Man optimiert aber nicht in die eigene Fantasie hinein, sondern startet mit einem Profiling, das ist bei JS ja nun auch einfach genug.

 

[duAffentier]

bitte spart euch Hasskommentare jeder Art...

Falls du noch nicht die KI gefragt hast, wo man sehr gut Codes erstellen kann:

function getOptimizedPredictions(words, removals) {
let removalsSet = new Set(removals);
let scores = words.map((w, i) => {
let originalSet = new Set(w);
let filteredSet = new Set([...w].filter(x => !removalsSet.has(x)));
return [w, originalSet, filteredSet, 0, i + 1];
});

// Vermeide doppelte Überprüfungen und reduziere die inneren Schleifen
for (let i = 0; i < scores.length; i++) {
for (let j = i + 1; j < scores.length; j++) {
// Zähle nur einmal pro Wortpaar, um die Komplexität zu reduzieren
let common = new Set([...scores[1]].filter(e => scores[j][2].has(e)));
if (common.size > 0) {
scores[3]++;
scores[j][3]++;
}
}
}

// Sortierung bleibt unverändert
scores.sort((a, b) => b[3] - a[3]);

return scores;
}

Ein JavaForum wird wohl eher helfen, da dort die ganzen Fachleute sitzen.

 

[Drexel]

Evtl solltest Du auch sagen was die Semantik ist, also was die Funktion machen soll...

 

[BeBur]

@sh. Noch schneller geht's, wenn man gar nichts programmiert! Davon mal abgesehen ist JS heutzutage üblicherweise (z.B. V8) recht performant für eine nicht AoT kompilierte Sprache.

 

[abcddcba]

Ein JavaForum wird wohl eher helfen

Java wäre eher die falsche Sprache ...

Ergänzung (21. Februar 2024)

ohne die Semantik (all zu sehr) zu ändern?

könntest natürlich auch einfach mal sagen was dein Programm machen soll, dann muss man sich nicht erstmal durch die Schleifen arbeiten, ist ja nicht so als wenn es nicht möglicherweise Algorithmen für bestimmte Probleme gibt.

die Ausführung dauert bei ca. 5000 Wörtern ca. 3-4 Sekunden

was ist denn das Ziel bei der Laufzeit dann? <1s?

bitte spart euch Hasskommentare jeder Art...

Verstehe nicht ganz wie man so einen Thread beginnen kann wenn man nach Hilfe fragt - woran liegt das? Welche "Hasskomentare" bekommst du denn hier auf CB?

Ansonsten kannst du für sowas evtl. auch auf Code Review hier mal posten: https://codereview.stackexchange.com/
Aber auch dort wird man dich nach der Problemstellung fragen, einfach nur ein Code-Snippet hinwerfen wird nicht reichen

 

[KingLz]

Brech die c-Schleife vorzeitig ab wenn die Bedingung erfüllt ist.

Ich glaube das Problem kann deutlich performanter gelöst werden, aber dazu müsste man den Ansatz ändern.

 

[H4110]

Wenn ich den Code richtig interpretiere, berechnest Du für jedes der Wörter in words die Anzahl der anderen Wörter, mit denen es mindestens einen nicht in removals enthaltenen Buchstaben gemeinsam hat?

 

[CyborgBeta]

Danke für die ganzen Beiträge, das mit den "Hasskommentaren" war nicht so gemeint... ich meinte damit eher js bashing und rants.

Also, es geht darum, dass man ein Wort suchen muss, ähnlich wie bei dem Spiel Hangman. Von den normalen Regeln abweichend, gibt man aber ein ganzes Wort ein und bekommt dann gesagt, welcher Buchstabe vorkommt oder nicht vorkommt (removals).

Die Funktion soll nun ein Wort vorschlagen, wodurch möglichst viele andere Wörter im nächsten Rateversuch ausgeschlossen werden können.

Ergänzung (21. Februar 2024)

Wenn ich den Code richtig interpretiere, berechnest Du für jedes der Wörter in words die Anzahl der anderen Wörter, mit denen es mindestens einen nicht in removals enthaltenen Buchstaben gemeinsam hat?

Ja genau, das ist der "Score".

Ergänzung (21. Februar 2024)

Edit: Quasi eine Intersection mit Score in JS.

 

[H4110]

Dann wäre aber eine andere Herangehensweise sinnvoller:
function findCandidateWords(words, includedLetters, excludedLetters) { ... }

Wobei includedLetters die von den bisherigen Rateversuchen akkumulierten Buchstaben enthält, die enthalten sein müssen, und excludedLetters analog dazu die, die nicht enthalten sein dürfen.

Dürfte auch sehr viel schneller gehen. Ein Ranking der möglichen Wörter halte ich dabei nicht für sinnvoll.

 

[CyborgBeta]

Dürfte auch sehr viel schneller gehen. Ein Ranking der möglichen Wörter halte ich dabei nicht für sinnvoll.

Hm, es geht darum, dem Benutzer... 1-5 Wörter vorzuschlagen, die er als nächstes wählen könnte.

 

[H4110]

Okay, aber jedes Wort, dass die Anforderungen erfüllt (enthält alle bestätigten Buchstaben und keine ausgeschlossenen Buchstaben), ist eigentlich gleich gut. Nimm halt zufällige oder irgendein anderes Kriterium. Edit: ...oder einfach die ersten fünf gefundenen, das beschleunigt die Sache auch. 😉

 

[CyborgBeta]

Ok, ich muss noch erwähnen... removals ist ein Array mit Buchstaben, die sicher nicht vorkommen, und words ist ein Array mit Wörtern, die schon gefiltert wurden, das heißt, das nur Wörter enthält, die möglicherweise gesucht sind, also noch offen sind.

Bisschen kompliziert, ja.

 

[KitKat::new()]

Wie könnte man die hinsichtlich der Laufzeit optimieren, ohne die Semantik (all zu sehr) zu ändern?

WASM nutzen

 

[CyborgBeta]

Hm, das würde ich erst dann machen wollen, nachdem der Algorithmus "optimal" wäre ...

Es wäre schön, wenn das in <= 1 Sekunde ginge.

 

[KingLz]

Wenn du es wirklich schnell haben willst, dann würde ich folgenden Ansatz wählen:

Für jedes Wort und Buchstabe eine Wahrheitstabelle erstellen, z.B.:

Affe: ABCDEFGH 10001100
Habe: ABCDEFGH 11001001

Bitweises AND ergibt dann => 10001000
Das Ergebnis ist >0 und damit gibt es mindestens einen gleichen Buchstaben in beiden Wörtern.

Bei UTF8 Codierung kann man jede Tabelle in 4 Byte unterbringen, das sollte vom Platz her also akzeptabel sein.

Bei diesem Vorgehen müsstest du jeden Buchstaben nur einmal anschauen.

Ist mir gerade eingefallen, du arbeitest doch schon mit Sets. Theoretisch müsste es für Sets eine Methode geben die genau die gleiche Auswertung macht und deutlich performanter sein müsste als die foreach Schleife!
Da kannst du im Prinzip alles beibehalten und einfach nur einen besseren Vergleich implementieren.

 

[CyborgBeta]

Ein JavaForum wird wohl eher helfen, da dort die ganzen Fachleute sitzen.

Also, ich will nicht andere Foren schlechtreden oder generalisieren, aber theoretische Algorithmiker findet man dort eher selten.

Und deine von ChatGpt generierte Antwort ist sogar ganz "gut" ... damit würde man die Hälfte der Iterationen sparen.

Ergänzung (21. Februar 2024)

Verbesserung a:

      function getPredictions(words, removals) {
        let scores = [];
        for (let i = 0; i < words.length; i++) {
          let w = words[i];
          let array1 = [...w];
          let set2 = new Set(array1.filter((x) => !removals.includes(x)));
          scores.push([w, array1, set2, 0, i + 1]);
        }
        for (let i = 0; i < scores.length; i++) {
          for (let j = i + 1; j < scores.length; j++) {
            let c = 0;
            for (let k = 0; k < scores[i][1].length; k++) {
              let e = scores[i][1][k];
              if (scores[j][2].has(e)) {
                c++;
              }
            }
            if (c > 0) {
              scores[i][3]++;
              scores[j][3]++;
            }
          }
        }
        scores.sort((a, b) => {
          return b[3] - a[3];
        });
        return scores;
      }

Verbesserung b:

      function getPredictions(words, removals) {
        let scores = [];
        for (let i = 0; i < words.length; i++) {
          let w = words[i];
          let array1 = [...w];
          let set2 = new Set(array1.filter((x) => !removals.includes(x)));
          scores.push([w, array1, set2, 0, i + 1]);
        }
        for (let i = 0; i < scores.length; i++) {
          for (let j = i + 1; j < scores.length; j++) {
            for (let k = 0; k < scores[i][1].length; k++) {
              let e = scores[i][1][k];
              if (scores[j][2].has(e)) {
                scores[i][3]++;
                scores[j][3]++;
                break;
              }
            }
          }
        }
        scores.sort((a, b) => {
          return b[3] - a[3];
        });
        return scores;
      }

Damit bin ich schon bei unter 1 Sekunde, das reicht ... wasm nicht mehr notwendig.