Ta strona używa cookies
sprawdź politykę prywatności

Rozumiem

5 algorytmów w JavaScript dla Mid Developera

28/5/2019
Bartek Cis

W tym artykule znajdziesz kilka algorytmów w JSie na poziomie Mid. Każdy ma dodatkowe komentarze pomagające się zorientować w sytuacji.

Czego się dzisiaj dowiesz?

W tym wpisie przeanalizuje 5 różnych zadań programistycznych i napiszę rozwiązania w JavaScript. Każdy z tych algorytmów będzie nieco inny.

Będzie praktyczna wiedza na temat pętli logicznych, schematów myślowych przy rozwiązywaniu algorytmów, pracy z liczbami, stringami, tablicami i obiektami. Jeżeli pokazuje więcej niż jedno rozwiązanie na dany temat sprawdzam też wydajność algorytmu.

Zagadki w sam raz dla Mid Developera 🙂

Dlaczego o tym piszę?

Bo mało na temat artykułów w polskiej społeczności… a szkoda. Rozwiązywanie algorytmów potrafi być nie mniej wciągające jak pisanie samej aplikacji.

Postaram się podejść do tych problemów z różnych perspektyw i użyć różnych metod. Oby było ciekawe… Miej na uwadze, że żaden z tych algorytmów nie musi być optymalny tzn. najlepszy z możliwych. Wszystko się da poprawić 🙂 Jak masz ciekawe sugestie to sekcja komentarzy jest dla Ciebie.

Seria algorytmy w JavaScript

  1. 5 Podstawowych algorytmów w JavaScript.
  2. 5 Średnio-zaawansowanych algorytmów w JavaScript.
  3. 5 Zaawansowanych algorytmów w JavaScript.

Pomiar wydajności – console.time

Jeżeli pokażę więcej niż jedno rozwiązanie spróbuję zbadać wydajność algorytmów. Cel jest prosty, im szybciej tym lepiej.

Użyje do tego właściwości console.time która mierzy czas między poszczególnymi operacjami. Przykładowe użycie znajdziesz w przykładach poniżej.

Kilka słów na temat metody… Jest średnio miarodajna. Dlaczego? Bo przeglądarka ma problemy z jednostajnością tzn. algorytm teoretycznie szybszy nie zawsze taki musi być. Aby pomiary były bardziej reprezentatywne należy wykonać dużą ilość testów (np. 1mln 🙂 ) i potem wyciągnąć średnią.

Moje pomiary to było zazwyczaj kilkanaście prób po których miałem ogólny ogląd. Dobra jedziemy z tym…

Różnica tablic

Masz dwie tablice z danymi. Twoim zadaniem jest wydobyć z każdej z nich unikalne elementy. Unikalne to takie które nie powtarzają się w drugiej (lub innych tablicach). Te unikalne wartości mają stworzyć nową tablicę.

Rozwiązanie 1

Plan jest taki, że stworzę nową tablicę do której będę wrzucał unikalne elementy. Następnie zdefiniuje funkcję która będzie porównywać każdy element z drugą tablicą za pomocą pętli for. Na końcu wywołuje tą funkcję dwukrotnie aby sprawdzić każdą tablicę osobno:

Na pierwszy rzut oka algorytm wygląda OK ale wywołuję tą samą funkcję sprawdzającą uniqueElement dwa razy. Hmm…

Rozwiązanie 2

Dobra to podejdę do tematu inaczej. Najpierw połączę dwie tablice w jedną i posortuje. Użyję do tego metod concat i sort. Jeżeli jakaś wartość będzie się powtarzać to znaczy, że była obecna w obu tablicach. W przeciwnym wypadku wartość jest unikalna. Do porównania używam map i zwykłego if.

Ten algorytm wygląda już nieco lepiej i jest też trochę szybszy. To co ciągle może się nie podobać to to, że sortujemy wszystkie wartości w obu tablicach. Jeżeli jest dużo powtarzalnych elementów to wykonujemy zbędne operacje.

Też logika wewnątrz if wygląda dość skomplikowanie. Po co to?

Pętla for vs map

Jak widzisz wykonuję iterację w inny sposób niż w pierwszym algorytmie. Używam map a nie for.

Obydwie metody mogą sprawdzać tablice z danymi. Ze źródeł z którymi się spotkałem wynika, że for może być trochę szybsze. Jest większa kontrolna nad iteracją i syntax jest bardziej przyjazny dla początkujących developerów.

Z kolei map wygląda bardzo schludnie i łatwiej się to czyta. Ważnym jest też to, że nie modyfikujesz w ten sposób oryginalnej tablicy tylko zwracasz nową. Wartości są nie-mutowalne.

Rozwiązanie 3

Najszybsze rozwiązanie. Najpierw połączę tablicę a potem przefiltruje za pomocą filter.

Filtr zwraca każdą wartość dla której postawiony warunek jest true. Za pomocą includes sprawdzam czy pierwotne tablice posiadają daną wartość. Chodzi o to, że gdy obydwie ją będą miały to będzie true true. Jak to zaneguje nie zwróci nic a jednocześnie zwróci tą wartość która występuje tylko w jednym przypadku czyli wartość unikalną 🙂

No ten algorytm jest znacznie szybszy i krótszy od poprzednich. Sprytnie podchodzi do tematu i minimalizuje zbędne operacje.

Suma nieparzystych liczb w ciągu Fibbonaci’ego

Tym razem zadanie polega na określeniu ciągu Fibonacciego dla wszystkich liczb mniejszych od podanego argumentu. Kolejnym krokiem jest zsumowanie wszystkich wartości nieparzystych.

Rozwiązanie 1

Tutaj nie będę zapisywał samego ciągu. Po prostu kolejne wartości w ciągu będą sprawdzane na parzystość za pomocą modulo %.

Ciąg Fibbonaciego będę generował pętlą while poprzez modyfikację aktualnej wartości w każdej iteracji.

Jak widać logika jest dość prosta. Stworzyłem dwa pierwsze elementy ciągu które są ciągle modyfikowane. Jeżeli warunek jest spełniony to dodaję daną wartość do ostatecznej sumy.

Rozwiązanie 2

Teraz najpierw stworzę ciąg Fibbonaciego za pomocą pętli for a potem zsumuje wszystkie wartości wewnątrz za pomocą reduce.

Ten algorytm wygląda lepiej od poprzedniego i jest też szybszy.

Roman Converter

Algorytm który będzie konwertował dowolną arabską cyfrę na notację rzymską. Koncepcja jest dość prosta, tworzę tablicę znaków rzymskich i osobną tablicę z odpowiadającymi im cyframi arabskimi. Potem tak długo, jak podana liczba jest większa od elementu tablicy dodaję odpowiedni rzymski ekwiwalent do wyniku.

Fajne co nie 🙂 ?

HTML Converter

Pobawię się z podmienianiem znaków w stringu. Dla przykładu niech to będzie poszukiwanie konkretnych symboli HTML i konwersja na ich tekstowy ekwiwalent.

Rozwiązanie 1

Logika będzie dość prosta. Zamieniam string na tablicę przez którą iteruje w poszukiwaniu danego znaku. Do porównania użyję switch.

No jak widać można osiągnąć cel w ten sposób ale nie jest to rozwiązanie najszybsze ani najładniejsze…

Rozwiązanie 2

Tym razem zależy mi na wydajności. Nie będzie konwersji do tablicy. Operuje tylko na stringu dodatkowo do gry wchodzi RegExp:

Algorytm szybki jednak nie do końca ładny… Problemem jest to, że jeśli chcemy zwiększyć ilość znaków do podmianki kompletnie tracimy czytelność kodu…

Rozwiązanie 3

Skoro nie zawsze wydajność jest najważniejsza to postaram się poprawić czytelość kodu. Wszystkie interesujące mnie znaki umieszczę w obiekcie.

Potem klasycznie konwersja do tablicy i porównanie elementów. Warto się też zatrzymać na warunku wewnątrz map. Jest dość zgrabnie skonstruowany 🙂

W ten sposób można łatwo rozbudować funkcję o nowe znaki poprzez np. obiekt z API. A więc nie zawsze wydajność.

Liczby Pierwsze

Przez matematyków traktowane ze szczególną czcią… Ostatnimi laty odkryły wiele ze swych tajemnic (hehe jestem po lekturze rozdziału „Matematycznego myślenia”).

To co ja chcę osiągnąć to policzyć sumę wszystkich liczb pierwszych w danym przedziale!

Rozwiązanie 1

Najpierw muszę znaleźć wszystkie liczby pierwsze w danym zakresie. Użyję funkcji findPrimes. Jest tu zmyślna konstrukcja z podwójną pętlą for. Zaczynam od 2 bo 0 i 1 nie są liczbami pierwszymi.

Te pętle for działają na zasadzie wielokrotności tzn. tablica filter posiada wszystkie wielokrotności przeanalizowanej liczby. Zaczynamy od 2 (które wędruje do liczb pierwszych) i dodajemy 4, 6, 8 … max. W ten sposób wykluczane są potencjalne liczby pierwsze i jak iteracja przesuwa się do przodu nie ma potrzeby sprawdzać wielu liczb.

Rozwiązanie 2

Spróbuje czegoś czego jeszcze dzisiaj nie było – funkcja rekursywna 🙂

Na początku trzeba sprawdzić czy liczba jest pierwsza. Używam pętli for gdzie sprawdzam modulo %. Liczba jest pierwsza jest wtedy jeżeli dzieli się tylko przez siebie i przez 1. Tutaj sprawdzam hipotezę zerową tzn. liczba nie jest pierwsza jeśli dzieli się przez jakąkolwiek liczbę inną niż 1 i ona sama.

Potem w zależności od wyniku analizy zwracam sumę wszystkich pierwszych

Wbrew pozorom ten algorytm jest wolniejszy niż poprzedni jest tak dlatego, że sposób sprawdzania czy liczba jest pierwsza jest bardzo czasochłonny. Za dużo iteracji…

Komentarz ogólny

No w zasadzie to tyle co miałem Ci dzisiaj do przekazania 🙂 Jeśli dotrwałeś/aś do tego momentu to znaczy, że jesteś naprawdę zainteresowany JavaScriptem 🙂

Nie wiem, może ten wpis jest zbyt mało szczegółowy ale uwierz mi, że przygotowanie nawet takiego materiału jest baaardzo czasochłonne… Generalnie się staram.

Kto wie może wejdę juz w takie mega szczegóły przy okazji wpisu o zaawansowanych algorytmach? Kierując się zasadą więcej a mniej?

Podsumowanie

Dzisiaj zobaczyłeś/aś kilka nowych sposobów jak radzić sobie z zadaniami programistycznymi. Było sporo pracy na liczbach, stringach i tablicach.

Każdy problem można rozwiązać na wiele sposobów i to zależy od celu / kontekstu. To jak? Uważasz, że to dobre zadania dla Mid Developera?

Podziel się z innymi 🙂

Cześć jestem Bartek.

Na tym blogu wprowadzę Cię w tajniki Front-Endu i programowania webowego.

Warto
Social media & sharing icons powered by UltimatelySocial