Programátorský úkol

Aoidhghean

Re:Programátorský úkol
« Odpověď #30 kdy: 10. 09. 2017, 15:37:57 »
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Těžko říct, jestli je pomalejší Java nebo Python zkompilovaný do nativního kódu. V každém případě jsou z principu pomalé fintovní řešení v Pythonu v tomto vláknu diskuze, protože mají kvadratickou větší složitost. Mě se zde líbilo pouze řešení je v Javě od Kolemjdoucího, které je čitelné a zároveň má lineární složitost. Podobně by to šlo Pythonu, kdyby se chtělo.
Kvadratickou v čem?


wefasdfasdfas

Re:Programátorský úkol
« Odpověď #31 kdy: 10. 09. 2017, 15:45:56 »
https://projecteuler.net/recent

me bavi obcas si vyresit nejaky problem na strance "euler projekt", clovek se nema srovnavat s jinyma,
ale zlepsovat sam sebe.

Kolemjdouci

Re:Programátorský úkol
« Odpověď #32 kdy: 10. 09. 2017, 16:29:36 »
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Těžko říct, jestli je pomalejší Java nebo Python zkompilovaný do nativního kódu. V každém případě jsou z principu pomalé fintovní řešení v Pythonu v tomto vláknu diskuze, protože mají kvadratickou větší složitost. Mě se zde líbilo pouze řešení je v Javě od Kolemjdoucího, které je čitelné a zároveň má lineární složitost. Podobně by to šlo Pythonu, kdyby se chtělo.
Kvadratickou v čem?

Kvadratickou vzhledem k počtu prvků v matici a záleží na implementaci toho otáčení matice zda půjde o zátěž CPU nebo alokaci paměti nebo obojí. Nechtěl jsem si svůj algoritmus chválit, když na první pohled vypadá komplikovaněji, ale je fakt že má optimální složitost protože nealokuje zbytečnou paměť a pouze jednou projde potřebná data. Implementační detail je že jsem to kvůli čitelnosti udělal v dvourozměrném poli, což Java implementuje jako pole polí a to je méně efektivní než jedno velké pole.

Všichni ti co kvůli přečtení jedné strany matice tu celou matici otáčejí (což může sice být jedno volání knihovny, ale není to levné) mi připadají jako že úplně ignorují efektivitu, jen aby výsledný kód vypadal na první pohled zajímavěji. Pokud by tento příklad byl součástí přijímacího pohovoru tak předpokládám že by hned další krok by byla diskuse o efektivitě různých řešení, a ta by mi o kandidátovi řekla pravděpodobně víc než konkrétní navržené řešení.

Mimochodem, měl jsem tam chybu která se někdy projevovala při lichých počtech řádků nebo sloupců (speciální případ je 1xN nebo Nx1 jak tu někdo psal), správně je to takhle:

Kód: [Vybrat]
public class Snake {

    public static int[] solve(int[][] input) {
        int height = input.length;
        int width = height == 0 ? 0 : input[0].length;
        int[] result = new int[width * height];
        for (int i = 0, res = 0; res != result.length; i++) {
            for (int j = i; j < width - i; j++) {
                result[res++] = input[i][j];
            }
            for (int j = i + 1; j < height - i; j++) {
                result[res++] = input[j][width - 1 - i];
            }
            if (res == result.length) {
                // odd number of rows or columns
                break;
            }
            for (int j = width - 2 - i; j >= i; j--) {
                result[res++] = input[height - 1 - i][j];
            }
            for (int j = height - 2 - i; j > i; j--) {
                result[res++] = input[j][i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] input = new int[][] {
            {1,3,5,7,6},
            {2,5,8,2,5},
            {9,2,4,6,2},
            {5,7,8,1,2},
            {4,2,3,5,6},
            {8,6,5,4,2}
        };
        int[] result = solve(input);
        for (int i : result) {
            System.out.println(i);
        }
    }
}

Aoidhghean

Re:Programátorský úkol
« Odpověď #33 kdy: 10. 09. 2017, 16:37:30 »
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Těžko říct, jestli je pomalejší Java nebo Python zkompilovaný do nativního kódu. V každém případě jsou z principu pomalé fintovní řešení v Pythonu v tomto vláknu diskuze, protože mají kvadratickou větší složitost. Mě se zde líbilo pouze řešení je v Javě od Kolemjdoucího, které je čitelné a zároveň má lineární složitost. Podobně by to šlo Pythonu, kdyby se chtělo.
Kvadratickou v čem?
Kvadratickou vzhledem k počtu prvků v matici   
To pak bude spíše O(n**3/2)

čumil

Re:Programátorský úkol
« Odpověď #34 kdy: 10. 09. 2017, 17:35:29 »
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Těžko říct, jestli je pomalejší Java nebo Python zkompilovaný do nativního kódu. V každém případě jsou z principu pomalé fintovní řešení v Pythonu v tomto vláknu diskuze, protože mají kvadratickou větší složitost. Mě se zde líbilo pouze řešení je v Javě od Kolemjdoucího, které je čitelné a zároveň má lineární složitost. Podobně by to šlo Pythonu, kdyby se chtělo.
Kvadratickou v čem?

Kvadratickou vzhledem k počtu prvků v matici a záleží na implementaci toho otáčení matice zda půjde o zátěž CPU nebo alokaci paměti nebo obojí. Nechtěl jsem si svůj algoritmus chválit, když na první pohled vypadá komplikovaněji, ale je fakt že má optimální složitost protože nealokuje zbytečnou paměť a pouze jednou projde potřebná data. Implementační detail je že jsem to kvůli čitelnosti udělal v dvourozměrném poli, což Java implementuje jako pole polí a to je méně efektivní než jedno velké pole.

Všichni ti co kvůli přečtení jedné strany matice tu celou matici otáčejí (což může sice být jedno volání knihovny, ale není to levné) mi připadají jako že úplně ignorují efektivitu, jen aby výsledný kód vypadal na první pohled zajímavěji. Pokud by tento příklad byl součástí přijímacího pohovoru tak předpokládám že by hned další krok by byla diskuse o efektivitě různých řešení, a ta by mi o kandidátovi řekla pravděpodobně víc než konkrétní navržené řešení.

Mimochodem, měl jsem tam chybu která se někdy projevovala při lichých počtech řádků nebo sloupců (speciální případ je 1xN nebo Nx1 jak tu někdo psal), správně je to takhle:

Kód: [Vybrat]
public class Snake {

    public static int[] solve(int[][] input) {
        int height = input.length;
        int width = height == 0 ? 0 : input[0].length;
        int[] result = new int[width * height];
        for (int i = 0, res = 0; res != result.length; i++) {
            for (int j = i; j < width - i; j++) {
                result[res++] = input[i][j];
            }
            for (int j = i + 1; j < height - i; j++) {
                result[res++] = input[j][width - 1 - i];
            }
            if (res == result.length) {
                // odd number of rows or columns
                break;
            }
            for (int j = width - 2 - i; j >= i; j--) {
                result[res++] = input[height - 1 - i][j];
            }
            for (int j = height - 2 - i; j > i; j--) {
                result[res++] = input[j][i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] input = new int[][] {
            {1,3,5,7,6},
            {2,5,8,2,5},
            {9,2,4,6,2},
            {5,7,8,1,2},
            {4,2,3,5,6},
            {8,6,5,4,2}
        };
        int[] result = solve(input);
        for (int i : result) {
            System.out.println(i);
        }
    }
}
pán je ňákej chytrej. Optimalizuje se až když se ukáže problém jako bottleneck. Zadání znělo jasně. Za 5 minut a ve 3 řádcích má člověk hotové robustní řešení bez chyb. Kdyby se to ukázalo jako brzda, vždy to člověk může přepsat.
Jasně že to řešení, kupříkladu moje, alokovalo a kopírovalo paměť jak diví, taky, co bys čekal od funkcionálního přístupu?

Tydle premature optimalizátoři problémů jsou osina v řiti, zapamatujte si to děcka ...


borekz

  • ****
  • 492
    • Zobrazit profil
    • E-mail
Re:Programátorský úkol
« Odpověď #35 kdy: 10. 09. 2017, 18:05:04 »
To pak bude spíše O(n**3/2)
V případě čtverce ano. Zaznělo tu, že to může být obdélník. V případě "obdélníku" 1xn ta složitost bude n**2.

JardaP .

  • *****
  • 11 064
    • Zobrazit profil
    • E-mail
Re:Programátorský úkol
« Odpověď #36 kdy: 10. 09. 2017, 18:07:54 »
pán je ňákej chytrej. Optimalizuje se až když se ukáže problém jako bottleneck.
......
Tydle premature optimalizátoři problémů jsou osina v řiti, zapamatujte si to děcka ...

Hm, podeziram, ze je tohle rozsireny pristup. Naprogramovat bez mysleni, aby to nejak fungovalo. Vznikne tak aplikace, kde kazdy treti radek je bottleneck, tak se neco prepise, i kdyz by to chtelo prepsat cele. Jenze to se nestiha a vsichni by se z toho posrali. Takze na to, co se neprepsalo, se pak doporuci sestnactijadro a 256 GB RAM a modleme se, aby aplikace skutecne dokazala vyuzit vic, jak jedno jadro.

borekz

  • ****
  • 492
    • Zobrazit profil
    • E-mail
Re:Programátorský úkol
« Odpověď #37 kdy: 10. 09. 2017, 18:08:44 »
pán je ňákej chytrej. Optimalizuje se až když se ukáže problém jako bottleneck. Zadání znělo jasně. Za 5 minut a ve 3 řádcích má člověk hotové robustní řešení bez chyb. Kdyby se to ukázalo jako brzda, vždy to člověk může přepsat.
Jasně že to řešení, kupříkladu moje, alokovalo a kopírovalo paměť jak diví, taky, co bys čekal od funkcionálního přístupu?
Tydle premature optimalizátoři problémů jsou osina v řiti, zapamatujte si to děcka ...
Ty patlaniny nebyly ve třech řádcích, ne všechny byly bez chyb, a pro mě méně čitelné. Za 5 minut bych spíše vymyslel stejné řešení s vnořenými cykly jako Kolemjdoucí, než kvadratické rádoby funkcionální machroviny. A pokud je pracnost víceméně stejná, je výhodnější to napsat rovnou pořádně.

ehmmm

Re:Programátorský úkol
« Odpověď #38 kdy: 10. 09. 2017, 18:16:20 »
Hlasuji pro to hezky prochazet a posunovat si index x a y, nez furt dokola otacet matici a zmensovat.
Finta to je sice elegantni, ale z hlediska plytvani vypocetnim vykonem to je totalni ulet.
To proste v praxi nesmi nikoho napadnout, za tech cca 20 usetrenych radku to podle me nestoji.

kojot4

  • ***
  • 217
    • Zobrazit profil
    • E-mail
Re:Programátorský úkol
« Odpověď #39 kdy: 10. 09. 2017, 18:27:32 »
To byl tip pro kojota a ne pro nějaké patlaly, kteří si myslí, že Java je pomalá a Python se hodí na velké věci. Ať si z toho veme, co se mu líbí.

Se to tu nějak rozjelo, tak já se vyjádřím. Dřív jsem zkoušel programovat i v Javě, Java mi opravdu přijde vhodnější pro větší projekty, jak říká jazykovědec, zejména statické typování, co třída to soubor, atd. atd. Prostě refactoring a vůbec údržba stávajícího kódu mi přijde, že se v Javě dělá lépe.

Co mě trošku na Javě zneklidňuje je pár věcí, prototypování, webový vývoj, machine learning, AI, systémové věci, na to je lepší Python. U toho Pythonu vidím, že bych poměrně mohl využít praxi z adminování, a taky mi přijde, že je to přeci jenom jazyk, který podle mě půjde lépe dělat freelance, což je hlavní cíl / úvaha. Úplně nejlépe na freelance by šlo PHPko či Javascript, ale ani jeden z těchto jazyků se mi nelíbí, Python mám rád, píšu si v něm i vlastní věci a mám v plánu si v něm napsat i vlastní projekt.

Spíše uvažuji se pohybovat směrem BigData/AI/ML/Web/Infrastructure než jít směrem korporátních aplikací, rád bych se v budoucnu přestěhoval do Liberce či okolí a tam jak vidno moc korporátů není.

Souhlasím s tím co tu padlo, že Java je rychlá a efektivní na velké projekty, na druhou stranu je to jazyk korporátů, a můj cíl je spíše freelance.

kojot4

  • ***
  • 217
    • Zobrazit profil
    • E-mail
Re:Programátorský úkol
« Odpověď #40 kdy: 10. 09. 2017, 18:34:55 »
Hlasuji pro to hezky prochazet a posunovat si index x a y, nez furt dokola otacet matici a zmensovat.
Finta to je sice elegantni, ale z hlediska plytvani vypocetnim vykonem to je totalni ulet.
To proste v praxi nesmi nikoho napadnout, za tech cca 20 usetrenych radku to podle me nestoji.

A já bych klidně otáčel tu matice, přijde mi to přehlednější, spíše v tom člověk neudělá chybu. V tom mém prvotním řešení jsem měl furt pocit, že člověk si nemůže být jistý, že tam neudělá nějakou chybu,..

I tu padlo to, že v mém řešení, a řešení tady někoho dalšího bylo zaznamenáno podivné chování při lichém počtu řádků. Člověk se tam prostě snadněji sekne.

Samozřejmě je otázkou asi i použití, pokud někdo bude řešit matici o 100 řádcích jednou za hodinu, tak bych použil nejčitelnější řešení pro člověka. Pokud to bude součástí MPEG enkodéru, tak bych se přikláněl ke strojové efektivitě.

Aoidhghean

Re:Programátorský úkol
« Odpověď #41 kdy: 10. 09. 2017, 19:03:22 »
To pak bude spíše O(n**3/2)
V případě čtverce ano. Zaznělo tu, že to může být obdélník. V případě "obdélníku" 1xn ta složitost bude n**2.
Nebude.

Aoidhghean

Re:Programátorský úkol
« Odpověď #42 kdy: 10. 09. 2017, 19:12:22 »
Hlasuji pro to hezky prochazet a posunovat si index x a y, nez furt dokola otacet matici a zmensovat.
Finta to je sice elegantni, ale z hlediska plytvani vypocetnim vykonem to je totalni ulet.
To proste v praxi nesmi nikoho napadnout, za tech cca 20 usetrenych radku to podle me nestoji.

A já bych klidně otáčel tu matice, přijde mi to přehlednější, spíše v tom člověk neudělá chybu. V tom mém prvotním řešení jsem měl furt pocit, že člověk si nemůže být jistý, že tam neudělá nějakou chybu,..

I tu padlo to, že v mém řešení, a řešení tady někoho dalšího bylo zaznamenáno podivné chování při lichém počtu řádků. Člověk se tam prostě snadněji sekne.

Samozřejmě je otázkou asi i použití, pokud někdo bude řešit matici o 100 řádcích jednou za hodinu, tak bych použil nejčitelnější řešení pro člověka. Pokud to bude součástí MPEG enkodéru, tak bych se přikláněl ke strojové efektivitě.
Ono i s tím vypsáním prvního řádku a pak otočením (nebo transpozicí a reverse) může být ten algoritmus lineární, když se použijí slices nebo “view onto”. U seznamů to je běžná implementace, nicméně matice nebývají součástí standardní knihovny, takže záleží na volbě third party, ale jde to lineárně. Čili ano, s otáčením to je elegantní a jednodušší, jen člověk musí mít chytře udělané matice. I v tom Haskellu by to tak šlo.

JardaP .

  • *****
  • 11 064
    • Zobrazit profil
    • E-mail
Re:Programátorský úkol
« Odpověď #43 kdy: 10. 09. 2017, 19:17:25 »
A já bych klidně otáčel tu matice, přijde mi to přehlednější, spíše v tom člověk neudělá chybu.

By me zajimalo, kolik matic ve Widlich otaci MS, ze kazda nova verze potrebuje dvojnasobek pameti ve srovnani s predchozi.

jazykovědec

Re:Programátorský úkol
« Odpověď #44 kdy: 10. 09. 2017, 19:19:38 »
To byl tip pro kojota a ne pro nějaké patlaly, kteří si myslí, že Java je pomalá a Python se hodí na velké věci. Ať si z toho veme, co se mu líbí.

Se to tu nějak rozjelo, tak já se vyjádřím. Dřív jsem zkoušel programovat i v Javě, Java mi opravdu přijde vhodnější pro větší projekty, jak říká jazykovědec, zejména statické typování, co třída to soubor, atd. atd. Prostě refactoring a vůbec údržba stávajícího kódu mi přijde, že se v Javě dělá lépe.

Co mě trošku na Javě zneklidňuje je pár věcí, prototypování, webový vývoj, machine learning, AI, systémové věci, na to je lepší Python. U toho Pythonu vidím, že bych poměrně mohl využít praxi z adminování, a taky mi přijde, že je to přeci jenom jazyk, který podle mě půjde lépe dělat freelance, což je hlavní cíl / úvaha. Úplně nejlépe na freelance by šlo PHPko či Javascript, ale ani jeden z těchto jazyků se mi nelíbí, Python mám rád, píšu si v něm i vlastní věci a mám v plánu si v něm napsat i vlastní projekt.

Spíše uvažuji se pohybovat směrem BigData/AI/ML/Web/Infrastructure než jít směrem korporátních aplikací, rád bych se v budoucnu přestěhoval do Liberce či okolí a tam jak vidno moc korporátů není.

Souhlasím s tím co tu padlo, že Java je rychlá a efektivní na velké projekty, na druhou stranu je to jazyk korporátů, a můj cíl je spíše freelance.

Chápu to a máš pravdu. Ale na prototypy je lepší Java, protože má skvělé knihovny, které ti produktivitu zvyšují. V čisté Javě bys to psal věčnost, ale to už dávno nepotřebuješ. Tipuju, že už Java je rychlejší na na běžné prototypy než Python.

S freelance máš také pravdu. PHP asi fakt top, JS snad ještě taky. Ale Java není jen v korporacích a pokud mi nevěříš, tak se podívej na startupy a jazyky. Z 70 % to bude PHP, JS a zbytek, ale Java tam pořád také je a nebo něco nad JVM.

Dneska se dělají hlavně microservices na cokoli, takže jazyk není až tak podstatný a Java se tam používá dost často. Nikdo ale neříká, že nemůžeš udělat speciální službu třeba v JS.