Wątek przeniesiony 2022-05-05 15:37 z Algorytmy i struktury danych przez somekind.

Zacząłem grindować leetcode żeby zmienić pracę i nie żałuję

10

Chcąc zmienić pracę na bardziej dochodową zacząłem grindować leetcode. Jak zapewne większość z was przestałem mieć styczność z jakąkolwiek algorytmiką z dniem zakończenia szkoły. W szkole byłem nawet dobry, ale 10 lat crudowania jednak robi swoje i w głowie miałem tylko informacje, że jakieś tam O istnieje, ale nie ma co się przejmować, bo i dane zawsze małe i serwery dobre. Jakieś tam drzewa są, ale robisz indeks na bazie i nie ma problemu. W sumie i tak wszystko się do bazy ładuje to ważniejsze dobrego joina zrobić niż przejmować się wrzucaniem elementu zawsze na początek array listy. I tak się żyło na tej wsi.
W samej pracy zdarzyło mi się kilka razy użyć wiedzy algorytmicznej, tzn wiedziałem, że jest graf potrzebny i szukałem odpowiedniej biblioteki do grafów. Albo kiedyś parsować drzewo mi się zdarzyło, ale w praktyce było to całkowicie losowe chodzenie po drzewie, debugowanie i jakoś tam działało.

Teraz robiąc zadania leetcode przypominam sobie zadania, które były co prawda raz na rok, ale były. I widzę, że przez moją ignorancję i leniwe przyzwyczajenia zrobiłem w życiu kilkanaście tasków, które działają głównie dlatego, że nikt tych crudów nie używa (albo używa, ale mało danych i nie ma problemu wydajnościowego).
I, prawdę mówiąc, trochę się wstydzę. Wszyscy moi współpracownicy mało się znają na algorytmice, więc zawsze przechodziło i nikt nie miał pretensji o te pętle w pętli. Niby jeden czy dwa taski na rok zrobione źle to nie tragedia. Reszta była programistycznie poprawna, było i TDD i hexagonal architecture i DDD i rekruterka majtki musiała zmienić jak słuchała tych skrótów.

Ale co z tego, co dalej? Osiągnąłem pewien poziom, że moja architektura jest poprawna, kod czytelny i otestowany. Teraz muszę pracować nad wydajnością nie tylko zapytań sql, ale też moich ifów i forów. Chciałbym z dumą powiedzieć raz do roku - patrzcie, udało się zejść z O(n^2) do O(nlogn).

Finalnie trochę żałuję i trochę mi wstyd, że tak olewałem wiedzę algorytmiczną. Niby poświęciłem czas na inne zagadnienia typu czyste testy i czysta architektura. Ale widzę braki, w jakby nie patrzeć, podstawach i jestem zadowolony, z tego, że rozpocząłem grindowanie leetcode - nawet jeśli nie uda się wynegocjować 15k$.

Patrzę też na strony typu ebilet gdzie przez większość czasu działa poprawnie, ale raz na rok jest duży festiwal i zwyczajnie strona nie wyrabia - myślę sobie, że pewnie tam też jest programista podobny do mnie, programista który olał algorytmikę, uznał, że n kwadrat jest wystarczające. Który poświęcił czas i zasoby na inne zagadnienia typu DDD z event soursingiem. Programista, który zrobił tego jednego w roku taska jako tako, byle działało. I przez 364 dni w roku działa poprawnie.

1

Chcąc zmienić pracę na bardziej dochodową zacząłem grindować leetcode.

Czy firmy, do których chcesz aplikować, faktycznie będą tego wymagać? Grindowanie algorytmów to chyba bardziej USA (ale może tam właśnie chcesz aplikować)?

I widzę, że przez moją ignorancję i leniwe przyzwyczajenia zrobiłem w życiu kilkanaście tasków, które działają głównie dlatego, że nikt tych crudów nie używa (albo używa, ale mało danych i nie ma problemu wydajnościowego).

Ale czy chcesz się nauczyć tego pod rekrutację (jedna bajka), czy po to, żeby samemu więcej wiedzieć i umieć (druga bajka)?

Jak to drugie, to nie lepiej wziąć jakąś książkę albo kurs z Coursera czy nawet z Youtube, gdzie będziesz miał to głębiej wytłumaczone niż tylko zadanko? Uczelnie wrzucają całe wykłady do sieci.

A zamiast abstrakcyjnych zadanek, nie lepiej robić jakichś własnych projektów, które coś robią?

8

Odnośnie e-biletu - zwykle w przypadku takich peeków ruchu dają o sobie znać inne wąskie gardła, np. jakiś „SELECT FOR UPDATE” na bazie danych albo niewyskalowanie pól wątków czy serwerów.

W przypadku jakichś list, które maja <10 elementów (pewnie z 99% przypadków) nie ma znaczenia, czy tam są 2 zagnieżdżone pętle czy jedna. Więcej czasu schodzi na paesowanie JSON-ów ;)

3
LukeJL napisał(a):

Czy firmy, do których chcesz aplikować, faktycznie będą tego wymagać? Grindowanie algorytmów to chyba bardziej USA (ale może tam właśnie chcesz aplikować)?

Tak, wymagają. Zachodnie firmy raczej w standardzie to mają z tego co zauważyłem. Nawet jak przez kontraktowanie chcesz to i tak dają do rozwiązania leetcode (albo coś podobneog)

Ale czy chcesz się nauczyć tego pod rekrutację (jedna bajka), czy po to, żeby samemu więcej wiedzieć i umieć (druga bajka)?

Zacząłem klasyczny grind pod rekrutację, ale skończyło się na tym, że czytam książki i analizuje algorytmy, żeby rozumieć co robię :) Więc chciałem tylko tylko pierwszy etap rekrutacji przechodzić, ale jakoś tak wyszło, że korzystam na tym i zyskuje sporo wiedzy.

2

Drobny off-topic: grind to po polsku "mielić".

1

@szprotki_w_oleju: jaki finalny efekt po 15 miesiącach?

3

Nie no, jak na to się nabraliście to dla mnie wstyd xD. To już bardziej jak pasta z wykopu wygląda.

Zastanawiam się czy to jeden gościu robi i jakaś ekipa.

1

@Czitels:

W sumie czemu?

Taka jest prawda, to czy twój kod jest SOLID compliant ( :D ) zazwyczaj ma małe znaczenie i jest bardzo umowne, a algo to już skillsy z którymi ciężko dyskutować

3
WeiXiao napisał(a):

@Czitels:

W sumie czemu?

Taka jest prawda, to czy twój kod jest SOLID compliant ( :D )

Tego nie wie nikt tak naprawdę. To czy coś jest zgodne z SOLID to kwestia intuicji, estetyki, zdrowego rozsądku, a nie jakichś ścisłych ustaleń.
Gdyby potraktować te zasady dosłownie, to raz napisanej klasy nie można byłoby już zmodyfikować, bo przecież łamałoby to zasadę open-close, jeśli klasa byłaby otwarta do modyfikacji.

1

Po 200 zadankach pisze kod szybciej, wydajniej i z mniejszą iloscią błedów, więc popieram jak najbardziej.

1

Nie wątpię że są benefity letcoode i algorytmiki których większość nie docenia, ale czy w Polsce (nie licząc jakiś google wannabe januszeksow) to coś pomoże przy szukaniu pracy to już wątpię. Bardziej doceniona zostanie znajomość clouda czy jakiegoś modnego aktualnie frameworka frontend. Chyba że kogoś przerasta fizbuzz czy odwrócenie tablicy na kartce,
to warto poćwiczyć bo trudniejsze zadania ciężko uświadczyć.

0

Nikt nie każe całe życie klepać dla kogoś systemy do numerowania opakowań w magazynie czy strony wizytówki dla Januszy lub pluginy do wordpressa zmieniające konfiguracje. Oczywiście jak wam odpowiada taka praca to nie zmuszam nikogo by wychodził poza tą strefę. Całej reszcie i tym, którzy wierzą że rynek nie będzie przez 30 lat wyglądał identycznie jak teraz algorytmika się przyda. Choćby po to by się nie pchać w jakieś quadtree czy octree na kiju tam gdzie zwykła tablica będzie wystarczająco szybka a w wielu przypadkach nawet szybsza jeśli zbiór danych nie jest jakiś monstrualnie rozproszony ani liczny. To, że nie implementujesz czegoś w jakimś frameworku bo masz tam gotowca nie znaczy że wiedza jak typowe struktury danych i algorytmy działają ci się do niczego nie przyda.

0
Satanistyczny Awatar napisał(a):

Choćby po to by się nie pchać w jakieś quadtree czy octree na kiju tam gdzie zwykła tablica będzie wystarczająco szybka a w wielu przypadkach nawet szybsza

Tablice nie są złe, a przecież często są wychwalane za data locality, a drzewa krytykowane, że to latanie pointerami wszędzie. Poza tym tablice łatwiej wrzucić do GPU (nie wiem nawet czy drzewa się da).

No ale koniec końców trzeba i tak samemu to sprawdzić, czy w danym przypadku to ma znaczenie i jakie.

0

Latanie pointerami po DRAM (Dynamic RAM) jest oczywiście drogie. Intensywne latanie po trzymanym w cache zbiorze, nawet jeśli jest to cache L3 jest o wiele tańsze, bo SRAM (Static RAM) wewnątrz CPU to nawet kilkaset razy szybszy dostęp. Dyski twarde są jeszcze wolniejsze.

Problemem jest zidentyfikowanie czy to co wykonujesz na twoim zbiorze danych kwalifikuje się lepiej na trzymanie tego w prostej, by nie powiedzieć prostackiej, tablicy czy wymaga jednak organizacji typu powiedzmy drzewo. Za jednym lub drugim rozwiązaniem przemawiać będzie wiele czynników, część z nich to rozmiar danych, rodzaj operacji na danych i czas trzymania przez cache danych (na ten wpływa architektura CPU i mnogość możliwych podejść do tematu oraz sama intensywność odwiedzin poszczególnych pól w cache, każde wyrugowanie danych z cache to konieczność powtórnego ładowania z wolniejszej pamięci przy ponownym odwiedzaniu pola co trzeba brać pod uwagę gdyż wyeliminowanie rzadko odwiedzanych pól jeśli wiemy że nie będą w ogóle zawierać interesujących nas danych eliminuje konieczność "odświeżania" pól cache eliminując marnotrawienie kilkuset do kilku tysięcy cykli procesora) ale też czy twój program jest tylko jednym z wielu wykonywanych przez CPU programów czy jego wyłącznym dysponentem.

Trudno jest to często rozstrzygnąć bez benchmarków jeśli nie widać na pierwszy rzut oka jakichś dominujących przesłanek typu CPU ma 64MB cache a ty musisz bawić się ze zbiorem danych wielkości kilkudziesięciu gigabajtów (co przemawia raczej na korzyść drzewa) lub terabajtów (zdecydowanie drzewo, zwłaszcza jeśli ten rozmiar przekracza pojemność RAM i musisz to ładować porcjami z dysku). Sprawdzanie kolizji kilku tysięcy punktów opisanych parą 4bajtowych liczb to na CPU z cache wielkości kilkaset megabajtów zadanie możliwe w miarę sprawnie nawet najprymitywniejszą metodą porównywania elementów każdy z każdym. Nawet 10 tysięcy takich punktów to zaledwie 0.08MB danych. Na pytanie czy wprowadzenie dla takich danych i takiego CPU czegoś bardziej wyszukanego niż tablica wszystkich punktów pzyniesie szybsze czy znacząco szybsze wykrywanie kolizji musi już jednak raczej odpowiedzieć benchmark. Innymi kandydatami na benchmark będą przypadki gdy przeglądane w miarę prosty sposób są zbiory danych o wielkości zaledwie kilku razy rozmiar cache.

Bywają też sytuacje gdy kombinowanie z własnym softwarowym cache zaimplementowanym przez siebie ma jakiś tam sens, ale to ciężko przewidzieć bez przeprowadzenie benchamrków w "warunkach bojowych" i raczej będą to już przypadki pracy z dość pokaźną ilości danych, zwłaszcza w przypadku generowanych w locie na ich podstawie danych które nie są integralną częścią podstawowego zbioru danych na których operujesz. W takich przypadkach o ile same wygenerowane dane nie mają imponujących rozmiarów o tyle sam proces ich wygenerowania jest złożony obliczeniowo. Tutaj też można dywagować czy takie cache organizować w postaci prostackiej pary zapytanie–wynik dodawanym w pierwszym wolnym miejscu czy bawić się w drzewa czy nawet drzewa samobalansujące się gdzie balansuje się na podstawie tak samego zapytania jak i częstotliwości wykonywania tego zapytania przez użytkowników. Ale to już zabawy poziomu implementujesz samodzielnie system bazy danych.

3

To tu ktoś na poważnie pisze algorytmy a nie korzysta z bibliotek?

Cringe

2
Crowstorm napisał(a):

To tu ktoś na poważnie pisze algorytmy a nie korzysta z bibliotek?

Cringe

No, autorzy tych bibliotek. Co za frajerzy, co nie? Ty też jeśli w ogóle programujesz coś innego niż jednolinijkowce implementujesz algorytmy. Pisanie kodu który realizuje wyświetlanie listy dmuchanych lalek po kliknięciu na pozycję w menu to też implementowanie algorytmu, nawet jeśli większość logiki która za tym stoi pochodzi z bibliotek. A i biblioteki też nie za często są pisane w gołym assemblerze. Nawet w C jest całkiem sporo algorytmów już zaimplementowanych na poziomie kompilatora wokół wywoływania funkcji. Nie musisz samodzielnie odkładać adresu powrotu na stos czy zdejmować/odkładać na niego argumentów funkcji. Kompilator sam generuje te części.

2
Crowstorm napisał(a):

To tu ktoś na poważnie pisze algorytmy a nie korzysta z bibliotek?

Tak. Robia to osoby zatrudnione na stanowisku "programista".
Czesto oprocz zaimplementowania algorytmu trzeba go najpierw wymyslic. Nie trudno zgadnac ze takich algorytmow w zadnej bibliotece nie ma.
Czasami algorytmy sa juz gdzies zaimplementowane, ale dzialaja tak nieprzyzwoicie powoli ze nie da sie tego uzyc. Dotyczy to tez bardzo popularnych bibliotek. A czasami sa tam po prostu bugi i w zaleznosci od licencji mozliwe ze tez nie da sie samemu zalatac i uzyc.

3

niektorzy to sie niegdy nie naucza, serwis webowy pada bo algos na nlogn nie smiga, shieeeeeeeeeeeet. Unikac takich ekspertow i razic fireballem z dystansu.

0

Zgadzam się z autorem w 100%. O dziwo grind leetcodów bardzo mocno wpływa na skill programistyczny. Tzn nie uczyni on że będziesz pisał czysty kod w dobrej architekturze, ale sprawi że ot będziesz umiał pisać kod który jest poprawny i w miarę wydajny i będziesz to robił efektywnie.
Swoja drogą to jest umiejętność której dzisiaj na rynku większość kandydatów nie ma.

@Crow To tu ktoś na poważnie pisze algorytmy a nie korzysta z bibliotek
W każdej firmie tradingowej w której pracowałem przez ostanie lata była masa custom kodu który musiał być napisany. Były tam algorytmy, struktury i inne dziwne rzeczy których nie szło nigdzie znaleźć jak i typowe algorytmy które trzeba było napisać z braku możliwości importu innych bibliotek.

Ba nawet takie rzeczy jak kolejki spsc, mpsc często trzeba napisać samemu aby były dopasowane pod konkretne rozwiązanie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1