jak být inženýrem algoritmů


Odpověď 1:

Nejprve mi dovolte pochválit vás za to, že chcete zlepšit své zvládnutí algoritmů, abyste se mohli stát lepším softwarovým inženýrem. Jak jsem viděl příliš často - na Quoře i jinde - někteří lidé si myslí, že softwarové inženýrství je jen programování, aniž by se museli učit techniky řešení problémů.

Pokud se chcete stát guru v algoritmech, musíte se o této oblasti dozvědět do té míry, že ji můžete naučit. Koneckonců, guru znamená učitel nebo mistr a nic vám nepomůže zvládnout předmět, jako je jeho učení. Doporučuji začít v malém. Vyberte si algoritmus nebo několik souvisejících algoritmů (možná nějaké třídicí algoritmy) a pokuste se je někoho naučit. Tímto způsobem získáte hlubší pochopení těchto algoritmů. Samozřejmě byste měli vysvětlovat nejen algoritmy, ale také to, proč fungují a jak rychle běží (tj. Asymptotická analýza). Možná narazíte, ale to je v pořádku; mnoho lidí, kteří se stali dobrými učiteli, nebylo na začátku hladké jako hedvábí. Snažte se, dokud nebudete schopni dobře vysvětlit algoritmy; v tom okamžiku jim porozumíte.

Pak to zkuste znovu s různými algoritmy. Udělejte to několikrát, dokud se nedostanete do bodu, kdy si budete skutečně jisti, že rozumíte algoritmům. V tom okamžiku budete vědět, zda rozumíte algoritmům. Jakmile zjistíte, zda materiálu skutečně rozumíte, budete na cestě stát se guru.

Ale to není všechno. Měli byste také být schopni přijít s algoritmy sami. Jelikož jste mě konkrétně požádali o odpověď na vaši otázku, předpokládám, že jste obeznámeni

Úvod do algoritmů

. U třetího vydání jsme zveřejnili veřejně dostupné odpovědi na vybraná cvičení a problémy; najdete je

tady.

Zkuste tato cvičení a problémy vyřešit, aniž byste se podívali na naše řešení. Pak porovnejte svá řešení s našimi.

Přeji vám úspěch, abyste se stali guru algoritmů!


Odpověď 2:

Pokud uvažujete

Bloomova taxonomie

v kognitivní doméně si uvědomíte, že odvozování algoritmů vyžaduje „

syntéza

. “

Syntéza

je druhá nejvyšší úroveň v taxonomii, což znamená, že přirozeně přichází po všem před ní:

Znalost

,

Chápání

,

aplikace

, a

Analýza

.

Právě teď se zdá, že jste dobří v získávání znalostí a porozumění. Zdá se, že dokážete aplikovat to, co jste se naučili. Stále však máte dvě úrovně ještě vyššího učení, abyste mohli vyřešit problémy s algoritmem / programováním. Musíte použít analýzu a poté pracovat na syntéze.

Co zahrnuje analýza? Podle Wikipedie to vyžaduje, abyste začali „rozdělovat informace na části určením motivů nebo příčin“. Udělali jste to sloučením? Víte, proč opakovaně rozdělujeme původní seznam na dvě části? Zvažovali jste, proč akce sloučení vedou k běhu O (nlgn)? Rozumíte tomu, proč musíte sloučit každý podseznam do skupin po dvou? Analyzovali jste, jaké vlastnosti platí v každém bodě algoritmu? Víte, proč tyto vlastnosti musí platit? Wikipedia říká, že s analýzou byste měli vzít v úvahu prvky, vztahy a organizační principy. Jakmile něco analyzujete, budete lépe připraveni na syntézu.

Budete lépe připraveni na syntézu, protože pochopíte, proč John von Neumann navrhl sloučení tak, jak to udělal. Jakmile pochopíte jeho návrhové motivace, budete lépe připraveni upravit algoritmus tak, aby splňoval měnící se požadavky.

A to je klíč k řešení problémů s algoritmy. Nejprve si osvojíte znalosti věcí, jako jsou datové struktury / algoritmy / paradigmata / analýza běhu / důkazy / atd. Poté strávíte čas pochopením toho, jak fungují / jaké jsou jejich výhody / jaké jsou jejich použití / jak byly odvozeny / atd. Udělal jste to, upevníte své porozumění uplatněním toho, co jste se naučili. Možná kódujete hašovací stůl od nuly. Možná implementujete efektivní řešení problému maximální mezery, o kterém jste si přečetli online. Doufejme, že budete trávit čas analyzováním věcí, které jste se naučili dál. Rozdělte je na jejich části. Opravdu jim rozumíte. Pochopte, proč kromě toho, jak. Udělejte z nich svůj vlastní, jako by to byly vaše vlastní vynálezy. Poznejte je uvnitř i venku.

Takže poté, co jste získali všechny tyto informace, se vraťte zpět k problému se sloučením. Po jeho analýze pochopíte, že síla typu sloučení spočívá ve skutečnosti, že můžete sloučit seznamy porovnáním dvou prvků najednou lineárním způsobem. Se změnou požadavků již nemůžete lineárně porovnávat dva prvky najednou. Místo toho musíte porovnat k prvků najednou. Pak se ptáte sami sebe, jak najdu minimum k prvků v lineárním nebo téměř lineárním čase? Dobrá věc, že ​​jste se minulý měsíc dozvěděli, že minimální binární hromady mohou dělat přesně to, co potřebujete. Pak se zeptáte, čeho potřebuji minimální hodnotu? První prvek v každém ze seznamů thek. Takže pokud uložíme první hodnotu z každého seznamu do minimální binární haldy, můžeme jen vyskočit minimum. Pak si pomyslíme, co udělal způsob oboustranného sloučení poté, co zjistil minimum. Vložil jej do seznamu a poté přesunul ukazatel v seznamu, ze kterého pochází minimální hodnota. Jak se nám to překládá? Do pole výsledků můžeme přidat minimum. Víme, ze kterého dílčího seznamu jsme vytáhli minimum, ale co znamená postup ukazatele v tomto seznamu? To znamená, že nové číslo je nyní v přední části seznamu, což znamená, že nové číslo by mělo být v naší minimální hromadě. Takže jsme vložili další číslo do hromady a opakovali. Zdá se, že tato základní myšlenka bude fungovat a pokaždé, když provedeme sloučení seznamu n položek k-way, zabere to čas O (nlgk).

Jak vidíte, jakmile budete mít velký soubor znalostí o doméně, budete připraveni syntetizovat. Vaše mysl vytvoří spojení mezi různými algoritmy a datovými strukturami, které znáte. Začnete spojovat omezení a vzory a paradigmata. Zřídka někdo vyprodukuje mistrovské dílo, aniž by se poučil od velikánů před ním. Vzhlédni k velkým myslí generace před námi. Přečtěte si spisy Knutha, Dijkstra, Rabina atd. Oceníte, co pro tuto oblast udělali ... a pak se nechte inspirovat.

A konečně, obrovská součást učení se řešení algoritmů je věřit v sebe sama.

Hodně štěstí!


Odpověď 3:

Pro mě existují 3 fáze porozumění:

  • vůbec nezná téma
  • znát téma
  • porozumění tématu

Zní to dost jednoduše, že? Problém je v tom, že většina lidí toto téma ví jen nejasně. Mají nejasnou představu o tom, co pojem znamená, ale ve skutečnosti tomu nerozumí.

Efekt Dunning-Kruger funguje takto: „Čím jste zručnější, tím více praxe procvičujete, čím více zkušeností máte, tím lépe se můžete srovnávat s ostatními. Jak se snažíte zlepšovat, začínáte lépe rozumět tomu, kde potřebujete pracovat. Začnete vidět složitost a nuance; objevíte mistry svého řemesla a porovnáte se s nimi a uvidíte, kde vám chybí.

Na druhou stranu, čím méně zručný jste, tím méně tréninku jste věnovali a čím méně zkušeností máte, tím horší je, když se srovnáváte s ostatními při plnění určitých úkolů. “

Jak tedy můžete být „skutečným softwarovým inženýrem“ nebo „guru v algoritmech“?

Nejprve se trochu seznámíte s daným tématem. Seznamte se s tématem. Gratulujeme, už jste v kroku 2. Nyní pochopte dané téma a prolomte ho. Podívejte se, kde jsou vaše znalosti díry. Nejjednodušší způsob, jak to udělat, je odpovědět na otázky, protože je to v podstatě to samé jako testování sebe sama.

Obecně opakujete tyto 3 fáze porozumění, protože jakmile budete mít dobrý přehled o myšlence, mělo by vás to vést k několika dalším konceptům, o kterých jste nikdy neslyšeli nebo o kterých rozumíte jen slabě.

Někteří lidé navrhli, že byste měli učit ostatní lidi, aby něčemu skutečně rozuměli. To by pro vás mohlo fungovat. To pro mě neplatí - prostě skončím s učením nesprávných informací. Jakmile najdu ten chink v brnění, mám mnohem snazší vysvětlovat lidem pojmy. Najděte, co vám vyhovuje.

V zásadě platí, že abyste se zlepšili v něčem, musíte vidět, kde vaše dovednosti zaostávají. Koneckonců, tam se zlepšujete. Dunning-Kruger s tím souhlasí - vzdělání je stejně jako učení se toho, co nevíte, jako přidání do toho, co děláte. Díky za A2A.


Odpověď 4:

Věřím, že studium algoritmů v izolaci od skutečných problémů je nudné. Stejné jako studium matematiky bez její aplikace. Myslím, že nejlepším nejlepším způsobem, jak poznat mnoho algoritmů, by bylo napsat svůj vlastní operační systém od nuly. Je to hodně práce a vyžaduje určité technické znalosti o hardwaru, ale bude vás motivovat.

Pokud potřebujete algoritmus k vyřešení problému a pokračování ve svém projektu, prostudujete ho nebo vymyslíte. Vzhledem k tomu, že děláte vše od nuly, nebude k dispozici žádná knihovna, kterou byste mohli používat na úrovni rozhraní, aniž byste pochopili, jak vnitřní algoritmus funguje.

Bohužel existuje jen velmi málo knih o aplikovaných znalostech. To platí jak pro matematiku, tak pro informatiku. Pokud procházíte knihu, která kategorizuje algoritmy podle jejich názvu, a ne podle problému, který řeší, budete jen těžko zjišťovat, jaký algoritmus potřebujete k vyřešení problému ze skutečného světa. Je také obtížné najít knihu, která popisuje pouze nejčastěji používané algoritmy. Jelikož existuje tolik algoritmů, chtěl by se člověk naučit ten nejpoužívanější z mnoha aplikačních oblastí, než se rozhodne specializovat pouze na některé oblasti.

Algoritmy jsou však všude: hráči, kteří čtou hudební skóre, používají prioritní frontu. Nějak si ve své mysli vytvoří ekvivalent fronty a naplní ji událostmi, jak postupují ve čtení skóre, zatímco vybírají události s nejvyšší prioritou, jak plyne čas (to jsou noty, které se teď mají hrát). Stejnou prioritní frontu lze použít pro plánování procesů, které se mají spustit v operačním systému (existuje mnoho strategií). Jak vidíte, stejný algoritmus lze použít v mnoha různých oblastech, takže většina knih pouze popisuje algoritmus a jeho vlastnosti, ale nezmiňují ani neuvádějí podrobnosti o jeho aplikaci. To je jen polovina legrace, IMHO.

Kartový hráč, který ji aranžuje, může používat algoritmus třídění vkládání. Vyhledejte telefonní seznam a přibližně uplatňujete binární vyhledávání. Abyste se dostali z bludiště s minimálním úsilím, budete muset sistematicky implementovat zpětný sledovací algoritmus (pokud nepodvádíte Ariadninu nití). Pokud znásobíte dvě čísla ručně, použijete numerický algoritmus založený na algebraické vlastnosti násobení a totéž platí pro další operace o sečtení dvou zlomků. Kdykoli váš počítač kreslí čáru na obrazovce, v hardwaru nyní běží další numerický algoritmus, aby bylo možné aproximovat ideální přímku v mřížce obrazových bodů pouze za použití celočíselné matematiky. Mohl bych pokračovat navždy ...


Odpověď 5:

Souhlasím s již předloženou radou, že nakonec schopnost učit tyto věci je nejlepší způsob, jak dosáhnout mistrovství.

Ale jen pro doplnění jedné věci ... Musím navrhnout začít u Stanfordových kurzů Algorithms Design and Analysis I and II (odkazy níže) na Coursera, kterou vyučuje Tim Roughgarden. Je úžasné, jak pro vás věci rozbíjí.

V posledních několika letech jsem si dal za cíl sledovat jeho přednášky, aby tyto znalosti byly aktuální. Nedělám úkoly. Ale vzhledem k vašemu cíli byste pravděpodobně chtěli.

Nyní o tom, jak to souvisí se skutečným softwarovým inženýrem. Pravdou je, že existují i ​​další věci, do kterých byste raději investovali, abyste se stali „skutečným“ softwarovým inženýrem. A neřekl bych, že ovládnutí Algoritmů do té míry, že je guru, je jedním z nich, alespoň ne obecně. Kupodivu je to obvykle důležitější než schopnost pohovoru než v práci. Jak velká hloubka znalostí algoritmu je pro vás jako softwarového inženýra skutečně vyžadována, bude záviset na vaší doméně / problémovém prostoru.

https://www.coursera.org/course/algo

https://www.coursera.org/course/algo2

Hodně štěstí!


Odpověď 6:

Velká O-notace.

Cheat Sheet složitosti algoritmu Big-O

Algoritmy a datové struktury, které je podporují, mají tendenci pracovat na sadě dat a budou využívat určité množství času (cykly CPU) a prostoru (paměti) k přeměně vstupů na výstupy.

Jak zvýšíte počet datových prvků v sadě dat, které chcete zpracovat, bude mít každý prvek nějakou funkci, která popisuje, kolik času potřebuje, a jinou funkci, kolik více prostoru potřebuje.

Pokud se potřeby lineárně stupňují s počtem prvků, je to O (n).

Některé algoritmy jsou z hlediska využití zdrojů zjevně horší než jiné. Například nikdo nepoužívá Bubble Sort k třídění řady věcí, protože nejhorší výkon bublinového třídění je O (n ^ 2).

Třídění bublin

Naproti tomu Quicksort na stejném poli trvá pouze O (n log (n)).

Datové struktury také mají velký dopad na to, jaké algoritmy máte k dispozici. Například: Doba potřebná k nalezení něčeho v poli pomocí lineárního vyhledávání je O (n), pokud musíte zkontrolovat každou položku, abyste zjistili, zda je správná. Vkládání nových věcí do tříděného pole znamená hledání místa pro jeho vložení a posunutí všeho o pozici výše, takže také O (n).

Na druhou stranu můžete řadit pole pro O (n log (n)) a poté na něm použít binární vyhledávání, abyste získali vyhledávání v čase O (log (n)).

Ale pokud máte více prvků, než vaše pole pojme? V C byste museli vytvořit větší pole a zkopírovat všechny prvky do nového pole. Časový trest je O (n).

Pokud jste věci ukládali velmi často, mohli byste použít jednotlivě propojený seznam, kde je doba vložení O (1), což znamená, že můžete vložit prvek v seřazeném pořadí ve stejnou dobu bez ohledu na to, zda existuje velmi málo nebo velmi mnoho položek jsou v propojeném seznamu. V propojeném seznamu je doba hledání O (n) stejně jako pole.

Pokud však velmi často prohledáváte svoji datovou strukturu, můžete zvážit použití binárního vyhledávacího stromu. Binárním vyhledávacím stromům trvá vložení do datové struktury pouze O (log (n)) a nalezení O trvá jen O (log (n)).

Kompromis mezi těmito datovými strukturami je prostor:

  • Pole obsahuje pouze data, která potřebujete k uložení.
  • Singly linked list needs one pointer per node to point to the next node.
  • Binární vyhledávací strom potřebuje kromě dat dva ukazatele na každý uzel (v každém uzlu je uložen datový prvek)

Takže výběrem rychlejší datové struktury v časové složitosti (binární vyhledávací strom) spotřebujete více paměti (složitost prostoru) na stejné množství datových prvků, se kterými pracujete.

Pokaždé, když se naučíte nový algoritmus, můžete pomocí notace Big-O posoudit jeho výhody a slabosti, abyste věděli, který z nich zvolit pro svůj návrh.

Poslední úvahou je, že některé algoritmy s mimořádně dobrou časovou a prostorovou složitostí mohou být obtížně pochopitelné, což může vést k chybám v implementaci. Tyto algoritmy se nejlépe implementují jednou pomocí jazyka, který podporuje šablony, takže je můžete plně otestovat a poté je ponechat v knihovně, kde je nebudete muset příliš často upravovat.


Odpověď 7:

To jsou nesouvisející otázky. :) Ať už máte na mysli „skutečného softwarového inženýra“, nemá to nic společného s „guru v algoritmech“.

Pokud je „skutečný softwarový inženýr“ „profesionální softwarový inženýr“, pak je to jednoduché. Professional je člověk, který za svou práci dostává peníze, stačí si tedy najít programátorskou práci a jste „profesionální softwarový inženýr“.

Pokud máte na mysli „kompetentního softwarového inženýra, který produkuje vysoce kvalitní výsledky“, pak je to složitější. Musíte se naučit a implementovat správné postupy softwarového inženýrství (softwarové zpracování), jako je promyšlený modulární design (použití vhodných návrhových vzorů nebo cokoli, co má smysl pro daný úkol), testování, dokumentace, kontrola kódu atd. Kromě toho byste měli být kompetentní na „úrovni výše“, například byste měli rozumět celkové architektuře produktu, vytíženosti a technických omezeních, životním cyklu produktu a jeho správě.

Ale pokud chcete být guru v algoritmech, měli byste se naučit algoritmy a vyřešit cvičení. Jeden se stane guru algoritmů pouze implementací a analýzou složitých algoritmů.


Odpověď 8:

Pokud opravdu chcete být guru algoritmů - pak musíte nakonec „znovu vytvořit kolo“. Vím, že to zní šíleně, ale pokud „jen“ připravujete knihy a opakujete ideologii někoho jiného, ​​pak vše, co děláte efektivně, se stává mluvčím někoho jiného.

Nejprve musíte skutečně porozumět aplikacím algoritmu - což je jen fantazijní výraz pro rovnici, která řeší věci. Takže se nestanete guru v algoritmech, ale více se stanete řešitelem problémů v poli, které lze použít pomocí algoritmů.

Zadruhé, musíte najít pole, které skutečně skutečně „vrcholí“ ve vašich zájmech. Pak musíte udržovat metakognice v tomto poli do bodu, kdy skutečně porozumíte problémům, které je opravdu třeba vyřešit. Pak musíte vzít dovednosti, které jste se naučili z „nevynalézat kolo“, a stavět na nich, abyste „znovu vynalézali kolo“. V tom okamžiku budete mít tu větev daného subjektu dostatečně zvládnutou, abyste ji mohli považovat za „mistra / guru“, kde budou vaše myšlenky na předmět dobře respektovány a přijímány.

Jinak z tebe bude jen chlap, odpovídáš na otázku na Quora, haha.

dík

Brandon B.


Odpověď 9:

Pokud budete postupovat podle tohoto myšlenkového procesu, budete jen další programátor kecy, který si zapamatuje spoustu věcí, ale nemá ponětí, kde a kdy je použít, a koncept určování toho, jak vidět různé vzory v kódu, kde by mohly být užitečné. Věřte mi ... už je nepotřebujeme ... v každé společnosti, která existuje, už pracuje spousta ...

Pokud chcete být dobrým programátorem, naučíte se koncepty, nikoli kód. Mohu najít jakýkoli algoritmus, který chci, do značné míry zdokonalit pomocí Google nebo StackOverflow a jednoduše ho umístit a použít. Trvá to asi 10 sekund. Měli byste se zaměřit na učení, znát koncept, PROČ jej používáte a jak určit, KDY a KDE a co je důležitější, kdy a kde NE použít, je to, na co byste se měli zaměřit na učení.

To je důvod, proč je dobrý programátor… jeho schopnost používat informace a znalosti a aplikovat je ve všech situacích tím, že rozpozná situace, kde to bude užitečné, a ne naučit se nějaký kód, který najdete za 10 sekund online.


Odpověď 10:

Po přečtení více než 5 knih o algoritmu se stále cítím slabý v mnoha dílčích oblastech algoritmu.

Jednoho dne jsem pak vzal knihu s názvem , a nemohu to přestat číst, je to tak dobře organizované, po přečtení a kódování více než 80% jsem zjistil, že se moje úroveň algoritmu výrazně zlepšila, alespoň pro běžné algoritmy.

Navrhuji tedy, aby si někdo tuto knihu vzal, i když její název je o rozhovoru, ale ve skutečnosti jde hlavně o algoritmus z mého pohledu.

MIMOCHODEM:

  • Kniha může být pro začátečníky v algoritmu trochu obtížná.
  • Knihy nepokryly některá témata příliš hluboce, po přečtení, pokud chcete jít v nějakém aspektu hlouběji, pravděpodobně byste měli najít knihu konkrétně na toto téma.
  • Napište implementace sami, bude to dvojnásobně efektivní.

Odpověď 11:

Jelikož se nepovažuji za Guru v algoritmech, ale pouze za velmi zvědavého a pilného softwarového inženýra, doporučím vám knihu, kterou doporučuji i ostatním a kterou jsem považoval za zlatý poklad (ne méně než to). Kniha je: „úvod do algoritmů kreativní přístup“ od Udi Manbera. Je to skvělá kniha, která se zaměřuje na řešení problémů a návrh algoritmů. Důvodem, proč se mi tato kniha tolik líbí, je metodický přístup, který je zapotřebí k výuce algoritmů a který se do značné míry opírá o „matematickou indukci“. Většina knih a učitelů používá indukci jako prostředek k prokázání správnosti algoritmů. Udi Manber používá matematickou indukci jako prostředek k jejich konstrukci. Pro mě to byl revoluční způsob pohledu na návrh algoritmů. Proto důrazně doporučuji tuto knihu vyzvednout, pokud chcete zlepšit své dovednosti v řešení problémů a schopnosti algoritmického návrhu. I když vám nemohu slíbit, že se stanete „guru“, mohu vám slíbit, že se rozhodně stanete mnohem zdatnějším řešitelem problémů, než jste byli (před čtením).