JS - zliczanie znaków w stringu

Kontekst

Poniżej zadanie, do którego rozwiązania wcielam się w rolę programisty aspirującego na stanowisko seniora w międzynarodowej firmie. Znajdziesz tu kilka propozycji rozwiązań zadania z krótkim uzasadnieniem oraz bardzo często występującymi błędnymi założeniami.

Zaczynamy!

Treść zadania

Policz ilość znaków występujących w podanym tekście

INPUT: Ala ma kota i psa

OUTPUT: { A: 1, l: 1, a: 4, ' ': 4, m: 1, k: 1, o: 1, t: 1, i: 1, p: 1, s: 1 };

 const exampleText = 'Ala ma kota i psa';
 const exampleOutput = { A: 1, l: 1, a: 4, ' ': 4, m: 1,
 k: 1, o: 1, t: 1, i: 1, p: 1, s: 1 };
1
2
3

Kilka definicji na potrzeby zadania:

  • poprzez pojęcie klucz należy rozumieć właściwość obiektu (ang. "object property"),
  • zadanie dotyczy wykonania operacji na powyższym tekście, a co za tym idzie nie będziemy analizować zużycia pamięci oraz przetwarzania tekstów z dużych plików.

#1 for + str.split

Zaczniemy od najprostszej oraz najbardziej opisowej wersji rozwiązania zadania. Bazuje ona na jednej z najczęściej spotykanych wersji, korzystającej z funkcji str.split oraz natywnym obiekcie do przechowywania danych w postaci klucz -> wartość (w naszym przypadku znak -> ilość wystąpień)


 

 






const occurrences = {};                             
const chars = exampleText.split('');                 
for(let i = 0; i < chars.length; i++) {
  const char = chars[i];
  if (occurrences.hasOwnProperty(char) === false) {
    occurrences[char] = 0;
  }
  occurrences[char] = occurrences[char] + 1;
}  
1
2
3
4
5
6
7
8
9

Widok funkcji wraz z komentarzem

/* Definiujemy obiekt, w którym będziemy przechowywali wynik.
Za pomocą obiektu stworzymy mapowanie, gdzie kluczem będzie znak,
a wartością ilość wystąpień. */
const occurrences = {};                             
/* Wykonamy konwersję tekstu na tablicę znaków używając funkcji 
split z pustym stringiem jako argument
np. 'aabc'.split('') === ['a', 'a', 'b', 'c'] */
const chars = exampleText.split('');                 
/* Wykonamy iterowanie po wcześniej utworzonej tablicy "chars" */
for(let i = 0; i < chars.length; i++) {
  const char = chars[i];
  /* Sprawdzamy, czy dla obiektu "occurrences" przypisany został już klucz 
(kolejny znak stringa, jeżeli nie - inicjalizujemy wartością 0) */
  if (occurrences.hasOwnProperty(char) === false) {
    occurrences[char] = 0;
  }
  /* Zwiększamy ilość wystąpień o 1 (celowo nie korzystamy z wyrażenia i++) */
  occurrences[char] = occurrences[char] + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Czas wykonania 1334.160ms. Jest dobrze. 😃

Wniosek:

  • kod wykonuje się poprawnie oraz jest czytelny.

#2 for + str.charAt

Pozostają jednak możliwości jego ulepszenia. W kolejnej wersji zastąpimy str.split funkcją str.charAt.




 






const occurrences = {};                             
for(let i = 0; i < exampleText.length; i++) {
  /* str.charAt zwraca znak na podstawie miejsca w stringu (indeks) */
  const char = exampleText.charAt(i);
  if (occurrences.hasOwnProperty(char) === false) {
    occurrences[char] = 0;
  }
  occurrences[char] = occurrences[char] + 1;
}  
1
2
3
4
5
6
7
8
9

Czas wykonania 1141.780ms.

Wniosek:

  • kod wykonuje się niemal 10% szybciej względem poprzedniej wersji,
  • w przypadku 10 serwerów, które wykonują tylko tą funkcję jeden z nich możemy wyłaczyć,
  • pod względem optymalizacji zużycia zasobów sprzętowych jest to duża optymalizacja.

Użycie funkcji str.split niesie za sobą następujące konsekwencje:

  1. Pamięciożerność, gdyż funkcja przechodzi po całym stringu, a następnie tworzy nową tablicę. W pamięci utworzona zostaje kopia wczytanego stringa, co skutkuje dwukrotnie większym zużyciem pamięci.
  2. Większa ilość wymaganych cykli procesora.

Dzięki wykorzystaniu str.charAt oszczędzamy znaczną ilość pamięci oraz cykli procesora.

#3 for - Object.hasOwnProperty

Zajmijmy się teraz małym, aż bardzo ważnym aspektem - inicjalizacją klucza w obiekcie. Często powielana jest informacja, że do tego typu zadania należy użyć opisowej wersji z użyciem Object.hasOwnProperty Wykorzystajmy starsze i prostsze wyrażenie, lecz mniej opisowe i jednoznaczne.




 


const occurrences = {};                             
for(let i = 0; i < exampleText.length; i++) {
  const char = exampleText.charAt(i);
  occurrences[char] = (occurrences[char] || 0) + 1;
} 
1
2
3
4
5

Nowy wynik 714.695ms.

Wniosek:

  • kod jest o 50% szybszy niż pierwsza wersja,
  • kod stał się bardziej czytelny oraz wykonuje się szybciej,
  • możemy wyłączyć połowę serwerów 👍.

#4 for v2 + str.charAt

Może jeszcze lepiej, przecież for nie musi być uzależnione od długości stringa. Możemy także bezpośrednio sprawdzić czy on się już nie skończył.


 



const occurrences = {};                             
for(let i = 0, char = null;  char = exampleText.charAt(i); i++) {
  occurrences[char] = (occurrences[char] || 0) + 1;
}
1
2
3
4

Kod teraz jest bardziej zaawansowany, gdyż nie każdy programista zna możliwość wykorzystania pętli for w taki sposób. Innymi słowy, mogę zabłysnąć. Wykonajmy test szybkości.

Czas wykonania 748.815ms.

Wniosek:

  • funkcja działa wolniej,
  • czytelność kodu także zmalała,
  • wykorzystana konstrukcja jest mało znana, więc utrudniam pracę innym.

#5 Array.forEach

For zostało wprowadzone do języka JavaScript już dawno, dawno temu. Teraz mamy ES6 i programujemy funkcyjnie. Wykorzystajmy te nowe możliwości.

Na początek możemy rozpakować naszego stringa do tablicy i użyć Array.forEach.



 


const occurrences = {};                             
/* [ ...'abc' ] === ['a', 'b', 'c'] */
[ ...exampleText ].forEach(char =>
  (occurrences[char] = (occurrences[char] || 0) + 1)); 
1
2
3
4

Wygląda dobrze! Czas przetestować rozwiązanie:

Czas wykonania 1884.268ms.

Wniosek:

  • to najwolniejsze rozwiązanie do tej pory,
  • to z pewnością rozpakowanie argumentów do tablicy.

#6 str.split + Array.forEach

Pozostańmy przy Array.forEach, jednak wykorzystajmy ponownie funkcję str.split - pamięć nie zawsze jest najważniejsza.


 


const occurrences = {};                             
exampleText.split('').forEach(char => 
  (occurrences[char] = (occurrences[char] || 0) + 1)); 
1
2
3

Czas wykonania 1074.878ms.

Wniosek:

  • w dalszym ciągu kod działa wolniej niż jego poprzednie wersje,
  • problemem musi być funkcja str.split.

#7 Array.from + Array.forEach

Czas najwyższy posilić się dokumentacją. Po chwili czytania mam to. Nowsza funkcja Array.from - wykorzystajmy ją w nastepnej wersji naszego kodu.


 


const occurrences = {};                             
Array.from(exampleText).forEach(char => 
  (occurrences[char] = (occurrences[char] || 0) + 1));
1
2
3

Czas wykonania 3409.910ms.

Wniosek:

  • jest to najwolniejsze rozwiązanie do tej pory,
  • kierunek rozwoju kodu okazał się zły.

#8 str.split + Array.map

Zostawmy jednak str.split, problemem zatem musi być w Array.forEach. Wykorzystajmy w nowszej wersji Array.map, które wykonuje funkcję dla każdego elementu i zwraca nową tablicę. Jednak skoro nasz kod nie zwraca nic to ten problem nie powinien nas dotyczyć.


 


const occurrences = {};                             
exampleText.split('').map(char => 
  (occurrences[char] = (occurrences[char] || 0) + 1));
1
2
3

Czas wykonania 1063.132ms

Wniosek:

  • Lepiej niż z użyciem Array.from, ale Array.forEach jednak był szybszy.

#9 for..of

Czas odwołać się ponownie do prostszych rozwiązań. Zostańmy przy for..of. Zgodnie z dokumentacją otrzymamy wynik znak po znaku, a użyjemy nowoczesnych rozwiązań.


 



const occurrences = {};                             
for(const char of exampleText) {
  occurrences[char] = (occurrences[char] || 0) + 1;
}
1
2
3
4

Czas wykonania 777.837ms

Wniosek:

  • rozwiązanie jest zdecydowanie szybsze.

#10 for..in + str.charAt

Możliwe, że rozwiązanie działające na indeksach wykonuje się w przypadku naszego zadania szybciej. Użyjmy rozwiązania for..in działającego na indeksach, a jednocześnie będącego 10 lat młodszą technologią.


 




const occurrences = {};                             
for(const i in exampleText) {
  const char = exampleText.charAt(i);
  occurrences[char] = (occurrences[char] || 0) + 1;
}
1
2
3
4
5

Czas wykonania 4598.743ms.

Wniosek:

  • najwolniejszy wynik. 👎

#11 while + str.charAt

Pozbądźmy się for..in i wykorzystajmy pętlę while.



 




const occurrences = {};                             
let i = exampleText.length;
while (i--) {
  const char = exampleText.charAt(exampleText.length - i - 1);
  occurrences[char] = (occurrences[char] || 0) + 1;
}
1
2
3
4
5
6

Czas wykonania 749.833ms.

Wniosek:

  • najnowsza wersja kodu zrobiła się skomplikowana,
  • w dalszym ciągu nie jest to najszybsze rozwiązanie.

#12 str.split + Array.reduce

Być może należy podejść do problemu funkcyjnie, użyję Array.reduce. To będzie idealne zastosowanie. Dostaję poprzedni wynik oraz kolejny znak.

 




exampleText.split('').reduce((prev, c) => { 
  prev[c] = (prev[c] || 0) + 1; 
  return prev; 
}, {});
1
2
3
4

Czas wykonania 1046.132ms.

Wniosek:

  • Array.reduce jest przecież szybki, to musi być wina tego str.split.

#13 Object.values + Array.reduce

Skoro string w javascript to obiekt, którego wartościami są znaki to wykorzystajmy Object.values

 




Object.values(exampleText).reduce((prev, c) => { 
  prev[c] = (prev[c] || 0) + 1; 
  return prev; 
}, {});
1
2
3
4

Czas wykonania 4627.519ms.

Wniosek:

  • wykorzystaliśmy dwie nowoczesne funkcje, a otrzymaliśmy najwolniejsze rozwiązanie. 👎

#14 while + iterator

Możliwe, że nieoptymalne jest wykorzystanie pamięci, skorzystajmy z iteratora. Można przyjąć, że w przypadku JavaScript jest to nowość i jak powszechnie wiadomo przy wykorzystaniu iteratorów mamy lepszą kontrolę nad wykorzystaniem pamięci.


 
 





const occurrences = {};       
let iterator = exampleText[Symbol.iterator]();
let i = iterator.next();
while (!i.done) {
  occurrences[i.value] = (occurrences[i.value] || 0) + 1;
  i = iterator.next();
}
1
2
3
4
5
6
7

Czas wykonania 801.962ms.

Wniosek:

  • kod w dalszym ciągu jest wolniejszy niż najszybciej działające rozwiązanie,
  • kod jest skomplikowany.

Podsumowanie

  1. Szybkość ma znaczenie, oczywiście nie ma co przesadzać.
  2. Używanie fikuśnych rozwiązań często przynosi odwrotny efekt.
  3. Warto poświecić czas na douczenie się żeby potem od raz pisać czytelniejszy i szybszy kod.
Rozwiązanie Czas
#3 for - Object.hasOwnProperty 714.695
#4for v2 + str.charAt 748.815
#11while + str.charAt 749.833
#9for..of 777.837
#14while + iterator 801.962
#12str.split + Array.reduce 1046.132
#8str.split + Array.map 1063.132
#6str.split + Array.forEach 1074.878
#2for + str.charAt 1141.780
#1for + str.split 1334.160
#5Array.forEach 1884.268
#7Array.from + Array.forEach 3409.910
#10for..in + str.charAt 4598.743
#13Object.values + Array.reduce 4627.519

Warunki, w jakich przeprowadzone zostały testy:

  • wersja Node v8.9.4
  • system/Sprzęt: Linux, Intel(R) Xeon(R) CPU E3-1245 V2 @ 3.40GHz, 32Gb
  • ilość powtórzeń wykonania funkcji, dla której liczony jest czas wynosi 1 000 000




Pozostałe artykuły