Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: kojot4 09. 09. 2017, 21:47:41
-
Řešil jsem to před lety na pohovoru v Javě, je to úkol, který jsem tehdá napsal snad na 3 třídy, přes 100 řádek kódu, a psal jsem to den. Teď jsem to po 3 letech, kdy si nepamatuji původní koncept zkusil znovu v Pythonu, a napsal jsem to na 17 řádek (podle mě by to šlo i kratší, ale to nebyl cíl), a podle mě jsem zvolil mnohem lepší koncept řešení.
Problém
Máte obdelník/čtverec složený z čísel, a ten prolézáte jako had po směru hodinových ručiček do středu, a vypisujete čísla za sebou jako posloupnost. Důležité je to, že to nemusí být nutně čtverec, ale může to být i obdelník. Jazyk je na vás.
Příklad 1
print(snake(
[[1,2],
[3,4]]
))Výsledek:
[1, 2, 4, 3]
Příklad 2
print(snake(
[[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]]
))
Výsledek:
[1, 3, 5, 7, 6, 5, 2, 2, 6, 2, 4, 5, 6, 8, 4, 5, 9, 2, 5, 8, 2, 6, 1, 5, 3, 2, 7, 2, 4, 8]
Moje řešení - Python
def snake(mya):
column = lambda a: [x[a] for x in mya]
right = lambda inside : mya[inside][inside:-1-inside]
down = lambda inside : column(len(mya[0]) - inside - 1)[inside:-1-inside]
left = lambda inside : list(reversed(mya[len(column(0)) - inside - 1]))[inside:-1-inside]
up = lambda inside : list(reversed(column(inside)))[inside:-1-inside]
output = []
inside = 0
while True:
add = right(inside) + down(inside) + left(inside) + up(inside)
if add:
output += add
inside += 1
else:
return output
Moje dotazy
- Opravdu je možné se zlepšit v programování cvičením třeba na www.codewars.com (http://www.codewars.com). Udělal jsem si tam asi 20 cvičení na různé algoritmy, a najednou mi přišlo, že mi to jde lépe a lépe. Přičemž jsem si vždycky myslel, že na to jako linux admin mozek nemám, teď prostě začínám pomalu přicházet na to, že to možná je hodně o cviku, že to že jsem to před lety dost mizerně zvládal je možná fakt, že jsem prostě málo cvičil a nemám v tom praxi, ne že jsem hloupej - což mě napadlo jako první.
- Trvalo mi to napsat 3-4 hodiny, jak si vedu?
- Co bych na tomhle kódu mohl zlepšit?
- Kdyžtak můžete nasdílet vlastní řešení v libovolném jazyce
Jo před lety mě jako programátora nevzali. Stále o programování uvažuji, i když dělám admina, ale je podle mě těžké být samouk. Ty codewars mi přijdou bezvadné v tom, že je tam úloha, člověk se to pokusí vyřešit, a pak se podívá, jak to vyřešili ostatní, ale zas je to jen na algoritmy, a přeci jenom programování je dnes ekosystém (frameworky, prostředí, testování, scrum)... Nicméně rád bych se naučil alespoň na úroveň mírně pokročilého v Pythonu, protože ten mě baví víc než Java, a částečně mě zajímá AI a BigData, kde je Python lídrem.
-
Zajimava uloha.
1. Opravdu je možné se zlepšit v programování cvičením
Ano :P
2. 30 minut, cekal jsem od sebe lepsi vykon.. holt uz je po pulnoci..
3. Prijde mi to celkem v pohode. Zlepsit muzes testovani (nefunguje to treba dobre pro lichy pocet radku)
4. Prikladam svoje reseni. V podstate to same, akorat misto hlidani "inside" se pouzije rekurze.
def snake(mya):
if not mya: return [] # empyt list
if len(mya)==1: return mya[0][:] # e.g. [[1,2,3]]
if len(mya[0])==1: return [row[0] for row in mya] # e.g. [[1],[2],[3]]
ret = mya[0][:] # top row
ret += [row[-1] for row in mya[1:-1]] # right col (without 1st and last elem)
ret += mya[-1][::-1] # reversed bottom row
ret += [row[0] for row in mya[::-1][1:-1]] # rev. left col (without 1st and last elem)
mya2 = [row[1:-1] for row in mya[1:-1]] # mya without "top layer"
ret += snake(mya2)
return ret
-
Moje dotazy
- Opravdu je možné se zlepšit v programování cvičením třeba na www.codewars.com (http://www.codewars.com). Udělal jsem si tam asi 20 cvičení na různé algoritmy, a najednou mi přišlo, že mi to jde lépe a lépe. Přičemž jsem si vždycky myslel, že na to jako linux admin mozek nemám, teď prostě začínám pomalu přicházet na to, že to možná je hodně o cviku, že to že jsem to před lety dost mizerně zvládal je možná fakt, že jsem prostě málo cvičil a nemám v tom praxi, ne že jsem hloupej - což mě napadlo jako první.
Cvičení dělá mistra, a platí to i u "computer science". Na univerzitách je běžný postup že k naučení teorie jsou přednášky, ale prakticky si to osvojíte až na cvičeních - a bez cvičení složitou teorii buď nepochopíte vůbec, nebo jen velmi povrchně či špatně. Bez toho abyste odladil program (nebo spíš spoustu programů) který funguje na základě algoritmů sestavených podle teorie z přednášek si nemůžete být jistý že tu teorii chápete správně. A často bez odladěných programů nedostanete zápočet, a bez zápočtu nemůžete na zkoušku. Codewars mi připadají že mohou fungovat jako ta cvičení, ale obávám se že bez znalosti patřičné teorie se u složitějších problémů zaseknete a buď na tu teorii nakonec přijdete sám (bude to zdlouhavé), nebo si ji odněkud dostudujete, nebo to nevyřešíte vůbec.
- Trvalo mi to napsat 3-4 hodiny, jak si vedu?
S trochou cviku by to mělo mohlo být rychlejší, ale důležité je že se to nakonec podařilo.
- Co bych na tomhle kódu mohl zlepšit?
Python neznám, odpověď nechám na jiných.
- Kdyžtak můžete nasdílet vlastní řešení v libovolném jazyce
Tady je standardní ukecaná Java (ale použitá tak základním způsobem že by to šlo přímočaře přepsat do C):
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];
int res = 0;
int iterations = (Math.min(width, height) + 1) / 2;
for (int i=0; i<iterations; 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];
}
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];
}
}
if (res != result.length) {
throw new IllegalStateException("res="+res+" != "+result.length);
}
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);
}
}
}
-
Tak já ti dám jedno řešení, abys měl o čem přemýšlet ;):
def snake(mya):
output = []
while mya:
output.extend(mya[0])
mya = map(list, zip(*mya[1:]))[::-1]
return output
Upozorňuju, že je to python2, v pythonu3 by se to muselo napsat lehce jinak.
Je to dobré a elegantní řešení? Asi ne, takový kód si vyslouží pár WTF od člověka, který to bude studovat a navíc to není ani moc efektivní. Ale na pohovor asi dobré, zkoušející se alespoň nebudou nudit ;).
-
Hezky ukol, donutil me si zase sahnout na Haskell. Tady je moje ctvrhodinka snazeni:
import Data.List
snakeWalk :: [[Integer]] -> [Integer]
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []
-
Hezky ukol, donutil me si zase sahnout na Haskell. Tady je moje ctvrhodinka snazeni:
import Data.List
snakeWalk :: [[Integer]] -> [Integer]
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []
Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).
-
...
Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).
Jop, to to dela. Ne no, neni to asi prehnane efektivni z pohledu vykonu* a asi ne ani nejvice idiomaticky Haskell (tipuju, ze pujde pouzit nejaka higherorder funkce, pripadne prepsat pointfree styl).
*: Pochybuji, ze to prekladac zvladne optimalizovat na uroven pruchodu polem v cyklu a vypisem primo pri provadeni.
PS: Tak nejaky pointfree convertor mi vytvoril tohle monstrum:
snakeWalk = fix ((`ap` tail) . (. head) . flip ((.) . (++)) . (. (reverse . transpose)))Osobne si myslim, ze neni vsude nutne cpat point-free, pokud to nezlepsi citelnost kodu.
-
Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).
noef neopisovat! :) Tak se zamysli, co dělá ten můj python, to stejné, jenom bez rekurze:
mya = map(list, zip(*mya[1:]))[::-1]
map(list, zip(*mya[1:])) je transpozice matice bez prvního řádku, [::-1] je otočení.
-
Po pravde jsem si nebyl jisty co to Pythoni reseni dela (z fci map a zip bych to moc necekal, ze je to to stejne jako ten snippet z Haskellu). Na to, ze se v Pythonu udajne jede na citelnost, mi tohle jako nezasvecenemu moc citelne neprislo :D.
-
Pochybuji, ze to prekladac zvladne optimalizovat na uroven pruchodu polem v cyklu a vypisem primo pri provadeni.
co knihovna stream-fusion?
-
2. Trvalo mi to napsat 3-4 hodiny, jak si vedu?
Na pohovore chceme aspon myslienku niecoho takeho za 30 minut, takze by to chcelo zrychlit.
Vacsina algoritmickych problemov je o rozdeleni vstupu na mensie casti a poslani rovnakeho algoritmu na tieto casti. To nerobis, takze sa nadries s indexami a nie je na prvy pohlad zrejme, ze to funguje v kazdej situacii. Honzik sa o to snazi, ale riesi 4 strany namiesto jednej - to ma hned nuti zamysliet sa, ako funguje ten vstup, ktory nezvladas ty.
Najjednoduchsie riesenie je zobrat prvy riadok a otocit vstup o 90 stupnov, ako tu uz ti posledni robia.
Algoritmy su o korektnosti. Vzdy si skus najskor napisat nieco aj exponencialne, co zrejme funguje a az nasledne ries ako to spravit lepsie. Zrejme fungujuci algoritmus velmi pomoze pri testoch, ked ti staci vymysliet si vstupy a porovnat vystupy algoritmov, netreba pisat vystupy.
3. Co bych na tomhle kódu mohl zlepšit?
Hlavne otestovat ho, ako sa chova na obdlzniky ako 1xN a Nx1 a opravit to.
-
Hezky ukol, donutil me si zase sahnout na Haskell. Tady je moje ctvrhodinka snazeni:
import Data.List
snakeWalk :: [[Integer]] -> [Integer]
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []
Haskell sice vubec neznam, ale jestli ten zapis znamena: vrat prvni radek pole spojeny s vysledkem rekurzivniho volani na otocenem poli bez prvniho radku, tak je to prudce elegantni a asi nejlepsi (ne nejefektivnejsi, ale to tady neva).
Mě by docela zajímalo, jestli ty vývojáře, co tu odstraňují první řádek a otáčí čtverec, jestli už někdy nějaký podobný algoritmus viděli, nebo jeho části a jenom to rychle zkombinovali, případně jestli to mají z nějaké teorie jak to řešit, nebo je to fakt za 10 minut napadlo jako úplně z nuly.
I když se zamýšlím, že třeba hodně dělá i to, že člověk zná možnosti, mě by nenapadlo, že je nějaký jednoduchý způsob jak celé to pole otočit o 90 stupňů, v životě jsem to neviděl, že by se to dělalo, tak prostě moje myšlenky ani tímto směrem nemohly jít.
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
Jen pro pořádek: tady se nepoužívá transpozice matice ale otočení, to jsou úplně jiné věci.
-
Pravda. Ale nic to nemění na tom, že si řešení představí rychle ten, který v tom dvourozměrném poli vidí matici :)
Jsem si dovolil to řešení v Haskellu přepsat do Elixiru.
defmodule Snake do
def snake_walk([]), do: []
def snake_walk([head | tail]) do
head ++ (tail |> rotate_field |> snake_walk)
end
defp rotate_field(field) do
field
|> List.zip
|> Enum.map(fn(x) -> Tuple.to_list(x) end)
|> Enum.reverse
end
end
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
Jen pro pořádek: tady se nepoužívá transpozice matice ale otočení, to jsou úplně jiné věci.
Nejsou, otočení je (reverse . transpose).
-
Přidávám jiný zápis již popsaného řešení v Pythonu s využitím knihovny numpy. Doplněno o generátor zadání.
import numpy as np
import time
def gen_input(r=3, c=3):
'''Generate input
>>> a = gen_input(r=3, c=3)
>>> print(a)
[[ 1. 2. 3.]
[ 8. 9. 4.]
[ 7. 6. 5.]]
'''
a = np.zeros((r, c))
ind = np.indices((r, c))
rind = snake(ind[0])
cind = snake(ind[1])
a[rind, cind] = np.arange(r * c) + 1
return a
def snake(a):
a = np.asarray(a)
ret = []
while a.size != 0:
ret.extend(a[0, :])
a = a[1:, ::-1].T
return ret
rows = 1000
cols = 1000
t = time.clock()
a = gen_input(rows, cols)
# to convert "a" to list use "a = a.tolist()"
print('time to generate input =', time.clock() -t)
t = time.clock()
r = snake(a)
print('time to snake =', time.clock() -t)
print('check =', np.all(r==np.arange(rows * cols) + 1))
-
Pokud jsi dělal admina, tak je šance, že ti vývoj půjde a zároveň algoritmy nejsou dobrý začátek. Jako admin musíš mít velký přehled a chápat souvislosti. Algoritmy jsou fajn pro začátečníky a běžné lopaty. Podstatná je architektura, stejně jako u systémů. Kde se třeba zálohuje, jak často, jak moc, po jaké síti, na čem to běží, co dělat při výpadku pěti věcí, atd. To jsou věci, které jsou pak i u vývoje podstatné, jen samozřejmě jiné. Na Python bych se vykašlal, to je dobré pro adminy na patlání, ale nic většího v tom neuděláš. Vždy můžeš přejít na pořádný jazyk, ale proč rovnou nezačít s tím nejlepším.
Na začátek máš ideální řešení vlastních problémů. To můžeš použít i v práci a během půl roku najít dobrý job jako vývojář.
-
není to uplně čisté, protože to mění původní pole... a taky se mi tam nelíbí ten copy-paste způsob kontrolování konce pole
def mackat_hada(m)
o=[];
loop do
o.push(*m.shift); break unless (m[0] && m[0][0]);
o.push(*m.map{|row|row.pop}); break unless (m[0] && m[0][0]);
o.push(*m.pop.reverse); break unless (m[0] && m[0][0]);
o.push(*m.map{|row|row.shift}.reverse); break unless (m[0] && m[0][0]);
end
o
end
print mackat_hada([[1,2,3,4],[5,6,7,8],[9,10,11,12]]).join(",")
-
Na Python bych se vykašlal, to je dobré pro adminy na patlání, ale nic většího v tom neuděláš.
Tak tajle v tom delaji Star Wars: https://www.python.org/about/success/ilm/
Dalsi priklady: https://www.python.org/about/success/
Ted je otazka, cemu rikate "neco vetsiho". Necelych 200000 radek by stacilo? https://wiki.python.org/moin/LargePythonProjects
-
Mě by docela zajímalo, jestli ty vývojáře, co tu odstraňují první řádek a otáčí čtverec, jestli už někdy nějaký podobný algoritmus viděli, nebo jeho části a jenom to rychle zkombinovali, případně jestli to mají z nějaké teorie jak to řešit, nebo je to fakt za 10 minut napadlo jako úplně z nuly.
I když se zamýšlím, že třeba hodně dělá i to, že člověk zná možnosti, mě by nenapadlo, že je nějaký jednoduchý způsob jak celé to pole otočit o 90 stupňů, v životě jsem to neviděl, že by se to dělalo, tak prostě moje myšlenky ani tímto směrem nemohly jít.
U mna bol postup bez triku hned. Nechcelo sa mi osetrovat 4 strany, ked staci osetrit jednu a otocit to. To by bolo otacanie, kde by som isiel podla indexov a prepisoval to do noveho pola.
Implementovat otacanie o 90 stupnov sa mi tiez nechcelo a tu nastupila teoria. Napadlo ma, ze vela prostredi zvlada rychlo transpoziciu - to zameni riadky za stlpce a nieco take chcem. Po zamene riadkov za stlpce uz to chce iba malu upravu, ktoru som si nakreslil na papier.
Na transpoziciu som nasiel odpoved na https://stackoverflow.com/a/17037588 a ostatne uz ide lahko.
-
Na Python bych se vykašlal, to je dobré pro adminy na patlání, ale nic většího v tom neuděláš.
Tak tajle v tom delaji Star Wars: https://www.python.org/about/success/ilm/
Dalsi priklady: https://www.python.org/about/success/
Ted je otazka, cemu rikate "neco vetsiho". Necelych 200000 radek by stacilo? https://wiki.python.org/moin/LargePythonProjects
Nuda. Až budeš dělat vývojáře, tak se ozvi. Ten jazyk nemá podporu na velké projekty. Není rychlý. Nemá ani nástroje. Admin to nepozná, protože je to lepší než Bash, ale na větší vývoj to není vhodné.
-
x = [[1,2,3],
[4,5,6],
[7,8,9],
[70,80,90]]
y = []
while len(x) is not 0:
y += list(x[0])
x = zip(*x[1:])[::-1]
print y
Řešení na 3 řádky. Pravda, funkcionální, ale jinak to snadno nejde.
-
Na Python bych se vykašlal, to je dobré pro adminy na patlání, ale nic většího v tom neuděláš.
Tak tajle v tom delaji Star Wars: https://www.python.org/about/success/ilm/
Dalsi priklady: https://www.python.org/about/success/
Ted je otazka, cemu rikate "neco vetsiho". Necelych 200000 radek by stacilo? https://wiki.python.org/moin/LargePythonProjects
Nuda. Až budeš dělat vývojáře, tak se ozvi. Ten jazyk nemá podporu na velké projekty. Není rychlý. Nemá ani nástroje. Admin to nepozná, protože je to lepší než Bash, ale na větší vývoj to není vhodné.
Aha, proto se v tom dělá ML, ... hold, je to na malí blbosti.
-
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
-
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Ne, to se fakt nedá.
-
Není rychlý.
Minimalne toto se da rici i o Jave, ktera je po svete dost rozlezla.
Ne, to se fakt nedá.
Di si honit nad holkou, ne nad jazykem prosimtě.
-
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í.
-
kojote, to je pro tebe, di do pythonu, jazykovědec je blbec ...
-
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.
-
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?
-
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.
-
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:
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);
}
}
}
-
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)
-
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:
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 ...
-
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.
-
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.
-
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ě.
-
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.
-
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.
-
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ě.
-
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.
-
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.
-
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.
-
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.
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
-
Moje řešení... asi je podobné nějakému co tu už bylo. Zabralo mi to asi 25 minut, z toho 10 minut jsem jen přemýšlel jak na to ;D
def print_circuit(input, start):
limit_x = len(input[0]) - start
limit_y = len(input) - start
for x in range(start,limit_x):
print(input[start][x], end=' ')
for y in range(start+1, limit_y):
print(input[y][x], end=' ')
for x in reversed(range(start,limit_x-1)):
print(input[y][x], end=' ')
for y in reversed(range(start+1, limit_y-1)):
print(input[y][x], end=' ')
def snake(input):
start = 0
while start < len(input)/2:
print_circuit(input, start)
start += 1
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Vzít podmatici je O(1). U rotace se dá obrátit jen třikrát, pak se vrátím na 0 stupňů, takže u těch transformací je nárůst složitosti přinejhorším krát konstanta bez ohledu na velikost vstupu.
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Vzít podmatici je O(1). U rotace se dá obrátit jen třikrát, pak se vrátím na 0 stupňů, takže u těch transformací je nárůst složitosti přinejhorším krát konstanta bez ohledu na velikost vstupu.
OK, takže obalovat nebudeme - dostáváme se tedy vlastně k tomu řešení řešení co tu prezentoval Kolemjdoucí, chápu to správně?
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Vzít podmatici je O(1). U rotace se dá obrátit jen třikrát, pak se vrátím na 0 stupňů, takže u těch transformací je nárůst složitosti přinejhorším krát konstanta bez ohledu na velikost vstupu.
OK, takže obalovat nebudeme - dostáváme se tedy vlastně k tomu řešení řešení co tu prezentoval Kolemjdoucí, chápu to správně?
Ne, ten kód bude pořád “vypiš první řádek, vezmi podmatici bez prvního řádku, rotuj, opakuj” (samozřejmě s kontrolou konce rekurze). Akorát to bude lineární díky “chytré” knihovně.
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Vzít podmatici je O(1). U rotace se dá obrátit jen třikrát, pak se vrátím na 0 stupňů, takže u těch transformací je nárůst složitosti přinejhorším krát konstanta bez ohledu na velikost vstupu.
OK, takže obalovat nebudeme - dostáváme se tedy vlastně k tomu řešení řešení co tu prezentoval Kolemjdoucí, chápu to správně?
Ne, ten kód bude pořád “vypiš první řádek, vezmi podmatici bez prvního řádku, rotuj, opakuj” (samozřejmě s kontrolou konce rekurze). Akorát to bude lineární díky “chytré” knihovně.
Vzdávám se, nerozumím. Šlo by ukázat konkrétní kód, včetně té "chytré" knihovny?
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
Tak ja se priznam, ze pri cteni zadani by me ani nenapadlo ze by nekdo nad tim premyslel jinak jak o matici. A po jeho precteni, cca 30s, jsem okamzit vedel ze pokud bych to chtel napsat v jazyce D, tak budu hledat knihovnu co podporuje transpozici :D.
Tento pochod myslenek bych ocekaval snad od kazdeho vysokoskolaka(samozrejme technickeho oboru), a dost mozna i stredoskolaka (v mem pripade nych to po stredni nevidel, jelikoz jsme matice na gymplu v podstate nebrali).
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Vzít podmatici je O(1). U rotace se dá obrátit jen třikrát, pak se vrátím na 0 stupňů, takže u těch transformací je nárůst složitosti přinejhorším krát konstanta bez ohledu na velikost vstupu.
OK, takže obalovat nebudeme - dostáváme se tedy vlastně k tomu řešení řešení co tu prezentoval Kolemjdoucí, chápu to správně?
Ne, ten kód bude pořád “vypiš první řádek, vezmi podmatici bez prvního řádku, rotuj, opakuj” (samozřejmě s kontrolou konce rekurze). Akorát to bude lineární díky “chytré” knihovně.
Vzdávám se, nerozumím. Šlo by ukázat konkrétní kód, včetně té "chytré" knihovny?
Matice bude něco jako
type Matrix {
array Array
height, width, stride int
rotation Rotation
}
Takže výroba matice je O(1) (z pole se udělá slice, nemusí se nic kopírovat) a otočení bude enum ze čtyř hodnot pro úhly. První řádek je taky podmatice, takže budu mít sérii O(1) operací, jen v těch operacích s maticemi bude switch přes ty 4 úhly. Není tam žádný stacking operací, stačí jen jednorozměrné slices (má to české jméno)?
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
Tak ja se priznam, ze pri cteni zadani by me ani nenapadlo ze by nekdo nad tim premyslel jinak jak o matici. A po jeho precteni, cca 30s, jsem okamzit vedel ze pokud bych to chtel napsat v jazyce D, tak budu hledat knihovnu co podporuje transpozici :D.
Tento pochod myslenek bych ocekaval snad od kazdeho vysokoskolaka(samozrejme technickeho oboru), a dost mozna i stredoskolaka (v mem pripade nych to po stredni nevidel, jelikoz jsme matice na gymplu v podstate nebrali).
Mě třeba napadla jako první rekurze se čtyřmi cykly (kvůli efektivitě), než jsem si ujasnil, že transpozice se dá udělat O(1) při použití “vhodných struktur”.
-
Porovnání výpočetního času:
Můj code:
import numpy as np
def linsp(m,n):
r=np.linspace(0,m*n-1,m*n)
return r.reshape(m,n).astype(np.int)
def passV(arr,ll,rowSpan,c):
if len(ll)< np.size(arr):
return arr[rowSpan[0]:rowSpan[1],c].tolist()
else:
return []
def passH(arr,ll,colSpan,r):
if len(ll)< np.size(arr):
return arr[r,colSpan[0]:colSpan[1]].tolist()
else:
return []
def passRH(arr,ll,rowSpan,colSpan):
ll+=passH(x,ll,colSpan,rowSpan[0])
rowSpan[0]+=1
ll+=passV(x,ll,rowSpan,colSpan[1]-1)
colSpan[1]-=1
ltmp=passH(x,ll,colSpan,rowSpan[1]-1)
ltmp.reverse()
ll+=ltmp
rowSpan[1]-=1
ltmp=passV(x,ll,rowSpan,colSpan[0])
ltmp.reverse()
ll+=ltmp
colSpan[0]+=1
return rowSpan,colSpan
def snakeNP(x):
rowSpan=[0,x.shape[0]]
colSpan=[0,x.shape[1]]
ll=[]
while len(ll)<np.size(x):
rowSpan,colSpan=passRH(x,ll,rowSpan,colSpan)
return ll
Původní kod:
def snakeOP(mya):
column = lambda a: [x[a] for x in mya]
right = lambda inside : mya[inside][inside:-1-inside]
down = lambda inside : column(len(mya[0]) - inside - 1)[inside:-1-inside]
left = lambda inside : list(reversed(mya[len(column(0)) - inside - 1]))[inside:-1-inside]
up = lambda inside : list(reversed(column(inside)))[inside:-1-inside]
output = []
inside = 0
while True:
add = right(inside) + down(inside) + left(inside) + up(inside)
if add:
output += add
inside += 1
else:
return output
Kod měnící pole:
def snakeMAP(mya):
output = []
while mya:
output.extend(mya[0])
mya = map(list, zip(*mya[1:]))[::-1]
return output
Porovnání na malém a velkém poli:
xSmall=linsp(5,5)
xxSmall=xSmall.tolist()
xLarge=linsp(100,100)
xxLarge=xLarge.tolist()
Malé pole:
%time snakeOP(xxSmall)
%time snakeMAP(xxSmall)
%time snakeNP(xSmall)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 93 us
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 75.1 us
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 145 us
Velké pole:
%time snakeOP(xxLarge)
%time snakeMAP(xxLarge)
%time snakeNP(xLarge)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 4.32 ms
CPU times: user 32 ms, sys: 0 ns, total: 32 ms
Wall time: 28.8 ms
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.63 ms
-
Kurva, mohl by mi nekdo vysvetlit, proc na trivialni ulohu, jakou programuji skauti z IT krouzku pomocne skoly za par minut na par radku, chce hned nekdo tahat knihovnu? To se pak clovek nesmi divit, ze i trivialni aplikace zabere na disku pul gigabajtu.
A kdyz uz musite tocit maticemi, aby se co nejvice zvysila vypoctova narocnost, nebylo by lepsi tu matici okopirovat, otocit a pak vypisovat radky na stridacku z jedne a druhe?
-
Už chápete jak sem to myslel ?
Moje (a mnoha dalších) řešení bylo na 5 minut.
Vy začnete teoretizovat, stahovat knihovny ... ve výsledku budete dělat práci na 5 minut celej den, a ještě k tomu to bude zabugovaný jak prase.
Gratulace.
Proboha, optimalizujte až ve chvíli, kdy se to ukáže jako nutný ... kdo se má pak v tom stašně chytře optimalizovanym kodu hrabat ? Sem snad opravář hajzlů nebo co ???
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
Tak ja se priznam, ze pri cteni zadani by me ani nenapadlo ze by nekdo nad tim premyslel jinak jak o matici. A po jeho precteni, cca 30s, jsem okamzit vedel ze pokud bych to chtel napsat v jazyce D, tak budu hledat knihovnu co podporuje transpozici :D.
Tento pochod myslenek bych ocekaval snad od kazdeho vysokoskolaka(samozrejme technickeho oboru), a dost mozna i stredoskolaka (v mem pripade nych to po stredni nevidel, jelikoz jsme matice na gymplu v podstate nebrali).
Mě třeba napadla jako první rekurze se čtyřmi cykly (kvůli efektivitě), než jsem si ujasnil, že transpozice se dá udělat O(1) při použití “vhodných struktur”.
Tak nad tim jsem nepremyslel, ja spis premyslel jak rozumne a citelne to zapsat. Jenomze to je problem, protoze to co mne prijde rozumne a citelne muze druhemu prijit slozite. Co se rychlosti a efektivity tyce tak to resim az ve druhe fazi (a to jen v pripade ze to ma vyznam).
-
To je o matematickém základu. Pokud v dvourozměrném poli automaticky vidíš matici, tak k transpozici v tomto případě dojdeš během pár minut.
Tak ja se priznam, ze pri cteni zadani by me ani nenapadlo ze by nekdo nad tim premyslel jinak jak o matici. A po jeho precteni, cca 30s, jsem okamzit vedel ze pokud bych to chtel napsat v jazyce D, tak budu hledat knihovnu co podporuje transpozici :D.
Tento pochod myslenek bych ocekaval snad od kazdeho vysokoskolaka(samozrejme technickeho oboru), a dost mozna i stredoskolaka (v mem pripade nych to po stredni nevidel, jelikoz jsme matice na gymplu v podstate nebrali).
Mě třeba napadla jako první rekurze se čtyřmi cykly (kvůli efektivitě), než jsem si ujasnil, že transpozice se dá udělat O(1) při použití “vhodných struktur”.
Tak nad tim jsem nepremyslel, ja spis premyslel jak rozumne a citelne to zapsat. Jenomze to je problem, protoze to co mne prijde rozumne a citelne muze druhemu prijit slozite. Co se rychlosti a efektivity tyce tak to resim az ve druhe fazi (a to jen v pripade ze to ma vyznam).
Nejlepší je v tomto ohledu literate programming.
-
nic moc, ale 10sek rozmyslania a 10min pisania:
#include <stdlib.h>
int *gen(int m, int n) {
int *out = new int[m * n];
for (int i = 0; i < m * n; ++i) {
out[i] = i;
}
return out;
}
int main() {
int m = 1000, n = 1000;
int stride = m;
int *arr = gen(m, n);
int *res = new int[m * n];
int pos = 0;
int x = -1;
int y = 0;
int d = 1;
--n;
while (m || n) {
for (int i = 0; i < m; ++i) {
x += d;
res[pos++] = arr[x + y * stride];
}
if (m) --m;
for (int i = 0; i < n; ++i) {
y += d;
res[pos++] = arr[x + y * stride];
}
if (n) --n;
d *= -1;
}
delete res;
delete ar
return 0;
}
-
Obrovsky dik za odkaz na www.codewars.com
-
nic moc, ale 10sek rozmyslania a 10min pisania:
#include <stdlib.h>
int *gen(int m, int n) {
int *out = new int[m * n];
for (int i = 0; i < m * n; ++i) {
out[i] = i;
}
return out;
}
int main() {
int m = 1000, n = 1000;
int stride = m;
int *arr = gen(m, n);
int *res = new int[m * n];
int pos = 0;
int x = -1;
int y = 0;
int d = 1;
--n;
while (m || n) {
for (int i = 0; i < m; ++i) {
x += d;
res[pos++] = arr[x + y * stride];
}
if (m) --m;
for (int i = 0; i < n; ++i) {
y += d;
res[pos++] = arr[x + y * stride];
}
if (n) --n;
d *= -1;
}
delete res;
delete ar
return 0;
}
To by u zkoušky neprošlo.
-
Stačilo by d = -d.
-
Jak pise cumil, v praxi predcasna optimalizace jen skodi - ve vetsine pripadu je totiz zcela zbytecna, protoze realne bottlenecky byly/jsou jinde (napr. db, disk, sit). Optimalizaci se akorat zavlece spousta chyb a celkove cena bude vyrazne vyssi. Nevim, co resite s knihovnami, me reseni, ktere lze zkratit takto (mozna to pujde i vic):
import Data.List
snakeWalk (x:xs) = x ++ snakeWalk (reverse $ transpose xs)
snakeWalk [] = []
Pouziva to jen std. knihovnu, je to velmi citelne na rozdil od tech rucnich prochazeni matici, a pro zadana data to nebude mit snad ani meritelny horsi vykon oproti tem "optimalnim" necitelnym resenim (v zadani neni pozadavek na rychlost/pametovou narocnost; navic nekdo pokrocilejsi uvdel nejakou knihovnu, ktera mozna resi i ten problem s vykonem). Take k tomuto kodu nemusim pomalu psat testy, nebo jen velmi malo. Kdyz caruji s indexy, bodam na pameti a mam nekolik vetvi, tak bude potreba dost testu, abych si byl jisty, ze to opravdu funguje vzdy. A svete div se, ne vsude se testuje (nekde jsou dokonce testy prisne zakazane jako ztrata casu), tam je pak muj naivni FP pristup nejvhodnejsi, protoze kod je tak kratky, ze sance na chyby je mala (vzpominam na studie, ze pocet bugu roste se delkou [znaky/radky] zdrojaku).
PS: Za nepouziti knihoven a matlani si hranatych kol se bezne vyhazuje. Bavime se snad o praci, ne o skole, ne?
-
Jak pise cumil, v praxi predcasna optimalizace jen skodi - ve vetsine pripadu je totiz zcela zbytecna, protoze realne bottlenecky byly/jsou jinde (napr. db, disk, sit). Optimalizaci se akorat zavlece spousta chyb a celkove cena bude vyrazne vyssi.
... Bavime se snad o praci, ne o skole, ne?
Myslim, ze jde hlavne o to zamyslet se nad danym pouzitim. Kolega napsal krasny parser souboru presne timto minimalstickym (pythonickym) stylem. Fungovalo to na testovaci priklady do 100MB. Soubory ktere zkoumame maji 8GB a vic, pythonicky parser nacita data nekolik hodin. FORTRANicky napsany parser to zvladne za par minut. Myslite, ze nekdo jiny krome autora toho pythonickeho parseru jej oceni? Ne, protoze takovy program je k nicemu.
-
Jak pise cumil, v praxi predcasna optimalizace jen skodi - ve vetsine pripadu je totiz zcela zbytecna, protoze realne bottlenecky byly/jsou jinde (napr. db, disk, sit). Optimalizaci se akorat zavlece spousta chyb a celkove cena bude vyrazne vyssi. Nevim, co resite s knihovnami, me reseni, ktere lze zkratit takto (mozna to pujde i vic):
Hezky si protiřečíte – nejprve odsuzujete předčasnou optimalizaci, a pak hned jednu předvedete (zkracování kódu).
pro zadana data to nebude mit snad ani meritelny horsi vykon oproti tem "optimalnim" necitelnym resenim (v zadani neni pozadavek na rychlost/pametovou narocnost; navic nekdo pokrocilejsi uvdel nejakou knihovnu, ktera mozna resi i ten problem s vykonem).
Vaše řešení je ovšem také nečitelné, zejména proto, že dělá něco úplně jiného, než je v zadání. V zadání není ani slůvko o otáčení matice. Jistě, lze relativně snadno dokázat, že řešení s transpozicí matice je ekvivalentní zadání, ale to už je něco, co v tom vašem řešení není vůbec vidět.
Tohle je nevýhoda školních úloh, že známe jenom malinkou část zadání, takže není možné rozhodnout, které řešení je nejlepší. Možná by to byl jen nějaký prototyp nad malými daty, takže nevadí, že pracuje s daty neoptimálně a není jasné, co dělá. Možná máme k dispozici knihovnu, která transpozici provádí tak, že nechá data na místě a změní implementaci metod, které se nad maticí volají. Nebo je možné, že „šnekovité“ procházení je jen jeden z více požadovaných průchodů maticí a další bude třeba procházení cik-cak, kde transpozice nepomůže, takže je správné implementovat různé způsoby průchodu maticí.
-
Jak pise cumil, v praxi predcasna optimalizace jen skodi - ve vetsine pripadu je totiz zcela zbytecna, protoze realne bottlenecky byly/jsou jinde (napr. db, disk, sit). Optimalizaci se akorat zavlece spousta chyb a celkove cena bude vyrazne vyssi. Nevim, co resite s knihovnami, me reseni, ktere lze zkratit takto (mozna to pujde i vic):
Hezky si protiřečíte – nejprve odsuzujete předčasnou optimalizaci, a pak hned jednu předvedete (zkracování kódu).
Kdybych chtel jet na delku, tak tohle je kratsi:
import Data.List
snakeWalk2 y = case y of (x:xs) -> x ++ snakeWalk2 (reverse $ transpose xs); [] -> []
Ale asi mate castecne pravdu, moje puvodni reseni je nejlepsi z hlediska udrzovatelnosti a splneni pozadavku zadani. Tohle^ reseni je horsi, prestoze ma mene radku (ma vice znaku na radek, horsi citelnost, ale mozna z pohledu pravdepodobnosti mnozstvi chyb to vychazi lepe). Programator se IMO ma snazit nemit svuj program zbytecne dlouhy (vhodne pouziti podmineneho vyrazu, preferovani fluent interface, pouzivani FP pristupu, kde to dava smysl atd.), smozrejme, se to nesmi prehnat, aby zase neutrpela citelnost. Po pravde vice necitelne mi prijde treba if-else roztahane na 5 radku, prestoze obe vetve vraci trivialni vyraz -> po prevedeni na podm. vyraz v return je to na jeden radek misto 5, kde vice jak polovina jsou zbytecne (priklad z pouzivani JS a bezneho stylu vynucenych slozenych zavorek u if a else). Podobne case classy ve Scale (casto 1 radek) vs. ty hruzy v Jave (desitka radku a vic, protoze fieldy+gettery+settery).
pro zadana data to nebude mit snad ani meritelny horsi vykon oproti tem "optimalnim" necitelnym resenim (v zadani neni pozadavek na rychlost/pametovou narocnost; navic nekdo pokrocilejsi uvdel nejakou knihovnu, ktera mozna resi i ten problem s vykonem).
Vaše řešení je ovšem také nečitelné, zejména proto, že dělá něco úplně jiného, než je v zadání. V zadání není ani slůvko o otáčení matice. Jistě, lze relativně snadno dokázat, že řešení s transpozicí matice je ekvivalentní zadání, ale to už je něco, co v tom vašem řešení není vůbec vidět.
Tohle je nevýhoda školních úloh, že známe jenom malinkou část zadání, takže není možné rozhodnout, které řešení je nejlepší. Možná by to byl jen nějaký prototyp nad malými daty, takže nevadí, že pracuje s daty neoptimálně a není jasné, co dělá. Možná máme k dispozici knihovnu, která transpozici provádí tak, že nechá data na místě a změní implementaci metod, které se nad maticí volají. Nebo je možné, že „šnekovité“ procházení je jen jeden z více požadovaných průchodů maticí a další bude třeba procházení cik-cak, kde transpozice nepomůže, takže je správné implementovat různé způsoby průchodu maticí.
Jak jsem psal - zadani to splnuje, pro zadana data to funguje, o nejakem skalovani ci omzenenich neni v zadani ani slovo. To, co pise nekdo s parserem v Pythonu, to vidim jako chybu zadani - chybela zminka o tom, ze povaha testovacich dat neodpovida datum v produkci a take jak to ma byt rychle (asi se mely dodat testovaci data podobna tem v produkci, pripadne predepsat omezeni - napr. 1GB dat za minutu), nebo chyba na strane programatora - nedodrzeni zadani. V praxi se nesetkavam s tim, ze mam presne predepsany algoritmus (ale priznavam, ze to se muze dost lisit, asi jsem spis dev, nez programator, pracuju v male firme, na projektu doslova par lidi, klient setri jak muze a asi bude hrat roli jeste vice faktoru) - vetsinou jde o vyreseni ukolu, ne o implementaci presne zadaneho algoritmu. Stejne tak nemivam zadane vnitrni struktury, omezeni na pouzivane oprace atp. Pokud knihovna vyrazne zkrati dobu implementace, tak navrhnu jeji pouziti a ve vetsine pripadu je to schvalene (maloco z obecnych veci si opravdu musim implementovat sam).
-
Skusky, ako na skole? To niekoho zaujima?
Pisal som to na dobru noc 10min o 1 v noci. Takze verim, ze su tam dake chyby.
nic moc, ale 10sek rozmyslania a 10min pisania:
#include <stdlib.h>
int *gen(int m, int n) {
int *out = new int[m * n];
for (int i = 0; i < m * n; ++i) {
out[i] = i;
}
return out;
}
int main() {
int m = 1000, n = 1000;
int stride = m;
int *arr = gen(m, n);
int *res = new int[m * n];
int pos = 0;
int x = -1;
int y = 0;
int d = 1;
--n;
while (m || n) {
for (int i = 0; i < m; ++i) {
x += d;
res[pos++] = arr[x + y * stride];
}
if (m) --m;
for (int i = 0; i < n; ++i) {
y += d;
res[pos++] = arr[x + y * stride];
}
if (n) --n;
d *= -1;
}
delete res;
delete ar
return 0;
}
To by u zkoušky neprošlo.
-
Pisal som to na dobru noc 10min o 1 v noci. Takze verim, ze su tam dake chyby.
Kdyby jenom chyby, ten kód je úplně hrozný. Syntaxticky C++, sémanticky C. Odstrašující příklad, jak by se to nemělo dělat.
-
Programator se IMO ma snazit nemit svuj program zbytecne dlouhy
Podstatné je tam to zbytečně (což se zároveň těžko měří). Ale stejně, jako by program neměl být zbytečně dlouhý, neměl by být ani zbytečně neefektivní. Podle mého názoru je z tohohle pohledu ta transpozice matice už za hranou (pokud by nešlo o prototyp).
smozrejme, se to nesmi prehnat, aby zase neutrpela citelnost
Já to vnímám spíš opačně – program by se měl zkrátit, pokud se tím zlepší čitelnost. A pokud se tím zlepší čitelnost, měl by se naopak prodloužit (pokud to není místo kritické na výkon). Proto by ty výše uvedené příklady, které matici procházejí pomocí cyklů, byly mnohem čitelnější, kdyby tam místo vnořených cyklů byly čtyři funkce pro procházení pole ve čtyřech směrech.
Po pravde vice necitelne mi prijde treba if-else roztahane na 5 radku, prestoze obe vetve vraci trivialni vyraz -> po prevedeni na podm. vyraz v return je to na jeden radek misto 5, kde vice jak polovina jsou zbytecne (priklad z pouzivani JS a bezneho stylu vynucenych slozenych zavorek u if a else).
Tohle já vnímám přesně opačně. Podmíněným výrazům se vyhýbám, pokud to není jednoduchá podmínka a dvě konstanty. Jinak z toho vznikají tři složité výrazy na jednom řádku, je to nepřehledné, musí se řešit priorita operátorů, špatně se to debuguje nebo upravuje. Vynechání složených závorek u triviálních výrazů považuju za chybu – už jsem viděl tolik chyb způsobených tím, že to vypadalo, že je v podmínce složený příkaz, ale on to byl jednoduchý výraz a zbytek pokračoval za ifem…
Jak jsem psal - zadani to splnuje, pro zadana data to funguje, o nejakem skalovani ci omzenenich neni v zadani ani slovo.
Ano, ale to je problém školních úloh, že zadání splňují i velmi hloupá řešení, a často naopak chytrá řešení zadání školní úlohy nesplní (přestože by se v praxi dala použít).
To, co pise nekdo s parserem v Pythonu, to vidim jako chybu zadani
Tohle je ovšem věc, kterou musí umět každý analytik, a také každý programátor, který není jen lepič kódu – rozpoznat, co v zadání je špatně nebo co by tam mohlo chybět, a případně si to se zadavatelem vyjasnit. Zadavatel vždy v zadání požaduje něco jiného, než co chce, a chce něco jiného, než co potřebuje. Ideální je, když nakonec dostane to, co potřebuje, ne to, co chtěl nebo co požadoval.
V praxi se nesetkavam s tim, ze mam presne predepsany algoritmus (ale priznavam, ze to se muze dost lisit, asi jsem spis dev, nez programator, pracuju v male firme, na projektu doslova par lidi, klient setri jak muze a asi bude hrat roli jeste vice faktoru) - vetsinou jde o vyreseni ukolu, ne o implementaci presne zadaneho algoritmu. Stejne tak nemivam zadane vnitrni struktury, omezeni na pouzivane oprace atp. Pokud knihovna vyrazne zkrati dobu implementace, tak navrhnu jeji pouziti a ve vetsine pripadu je to schvalene (maloco z obecnych veci si opravdu musim implementovat sam).
Ano, tohle je dost podstatné a moc nechápu, proč se dnes u programátorů často řeší jenom algoritmy, když už jsou stejně všechny naprogramované v knihovnách a programátor často potřebuje vědět především to, kde tu implementaci najde hotovou a hlavně jak si ověřit předpoklady té knihovny a jak ji správně propojit se svým kódem a s dalšími knihovnami.
-
Pisal som to na dobru noc 10min o 1 v noci. Takze verim, ze su tam dake chyby.
Kdyby jenom chyby, ten kód je úplně hrozný. Syntaxticky C++, sémanticky C. Odstrašující příklad, jak by se to nemělo dělat.
Mal som tu pre teba nieco dlhsie rozpisane, ale nakoniec len napisem, ze zero fuck given. Bo ked takto kritizujes 10min prototyp nema zmysel nic pisat.
-
Kam se podelo programovani? To jako fakt vyuzit lambda, list na tak trivialni ukol jako je prace s polem?! Ja bych zakazal ve skolach pythony, javy, C# a pekne se vsichni naucte prvni strukturovane programovani napr. v Cecku. Za mich mladych let se vsechno muselo psat a nebylo to od veci. Dneska kazdy napere na trivialni problem x frameworku, protoze pameti je dost tak proc bych to resil.
-
Ke codewars a project euler bych doplnil jeste https://adventofcode.com (posledni verzi jsem nedelal, ale predposledni se mi hodne libila - kratke pribehy za ulohami byly skvele :D) a https://www.codingame.com (to jsem moc nezkousel, ale minimalne zacatky to vypada zajimave).
-
Mal som tu pre teba nieco dlhsie rozpisane, ale nakoniec len napisem, ze zero fuck given. Bo ked takto kritizujes 10min prototyp nema zmysel nic pisat.
Podívej, ten tvůj kód je špatný. Je úplně jedno, jestli jsi ho dělal 10 minut nebo 10 hodin, pořád je stejně špatný. Takový kód nemá cenu prezentovat.
-
Kam se podelo programovani? To jako fakt vyuzit lambda, list na tak trivialni ukol jako je prace s polem?! Ja bych zakazal ve skolach pythony, javy, C# a pekne se vsichni naucte prvni strukturovane programovani napr. v Cecku. Za mich mladych let se vsechno muselo psat a nebylo to od veci. Dneska kazdy napere na trivialni problem x frameworku, protoze pameti je dost tak proc bych to resil.
nechtěl bych být tvůj zaměstnavatel.
-
Skusky, ako na skole? To niekoho zaujima?
Pisal som to na dobru noc 10min o 1 v noci. Takze verim, ze su tam dake chyby.
nic moc, ale 10sek rozmyslania a 10min pisania:
#include <stdlib.h>
int *gen(int m, int n) {
int *out = new int[m * n];
for (int i = 0; i < m * n; ++i) {
out[i] = i;
}
return out;
}
int main() {
int m = 1000, n = 1000;
int stride = m;
int *arr = gen(m, n);
int *res = new int[m * n];
int pos = 0;
int x = -1;
int y = 0;
int d = 1;
--n;
while (m || n) {
for (int i = 0; i < m; ++i) {
x += d;
res[pos++] = arr[x + y * stride];
}
if (m) --m;
for (int i = 0; i < n; ++i) {
y += d;
res[pos++] = arr[x + y * stride];
}
if (n) --n;
d *= -1;
}
delete res;
delete ar
return 0;
}
To by u zkoušky neprošlo.
Explicitní použití new je na přesdržku i po celodenním kopání studny. Nicméně ten kód má hodnotu jako odstrašující příklad. Doporučuji dát ho na “hovnokód”.
-
...
Explicitní použití new je na přesdržku i po celodenním kopání studny. Nicméně ten kód má hodnotu jako odstrašující příklad. Doporučuji dát ho na “hovnokód”.
nech sa paci, smelo do toho
-
Explicitní použití new je na přesdržku i po celodenním kopání studny. Nicméně ten kód má hodnotu jako odstrašující příklad. Doporučuji dát ho na “hovnokód”.
Ty bys jako správný programátor C++ zřejmě napsal std::vector<std::vector<int>>(m,{n}) bez ohledu na čitelnost a časovou složitost.
-
Explicitní použití new je na přesdržku i po celodenním kopání studny. Nicméně ten kód má hodnotu jako odstrašující příklad. Doporučuji dát ho na “hovnokód”.
Ty bys jako správný programátor C++ zřejmě napsal std::vector<std::vector<int>>(m,{n}) bez ohledu na čitelnost a časovou složitost.
jeden řádek je pro většinu lidí čitelnější než 40 řádků.
-
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í.
to řešení v numpy nic nealokuje, a = a[1:, ::-1].T pouze vytvoří pohled na tu stejnou matici. Složitost má lineární.
-
Explicitní použití new je na přesdržku i po celodenním kopání studny. Nicméně ten kód má hodnotu jako odstrašující příklad. Doporučuji dát ho na “hovnokód”.
Ty bys jako správný programátor C++ zřejmě napsal std::vector<std::vector<int>>(m,{n}) bez ohledu na čitelnost a časovou složitost.
Píšu tak, aby byl kód bezpečný. Zvlášť když vector není pomalejší než raw pole. Ostatně v tom stupidním kódu je chyba právě ve správě paměti, pro pole se používá delete[].
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
přesně tak funguje numpy. Slicování a transpozice nic nekopíruje, pouze mějí pohled na data.
-
přesně tak funguje numpy. Slicování a transpozice nic nekopíruje, pouze mějí pohled na data.
Tak v tom pripade naprosto bez ironie dekuji za doplneni vzdelani.
(Moje jedina zkusenost s numpy je zatim pouze takova, ze jsem ho musel pribalit k matplotlib a tim padem mi binarka pro zakaznika povyskocila o 13 MB, coz je pro me "starou skolu" docela dost.)
Ale jak to je s nejakym uvolnovanim pameti, kdyz si z matice 1000000x1000000 vezmu vyrez 10x10 a vim, ze ten zbytek uz nikdy potrebovat nebudu?
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Ty objekty se nemusí vnořovat. V objektu budete mít dva prvky – odkaz na data, a konfiguraci, jak se má s daným pohledem zacházet. Když vytvoříte nový pohled, vytvoříte nový objekt, vložíte do něj odkaz na stejná data a novou konfiguraci. Na tom původním pohledu tento nový nijak nezávisí. Samozřejmě to nelze použít tehdy, kdybyste ty transformace objektů skládal (třeba v geometrii – něco otočíte, otočený objekt zmenšíte a otočený a zmenšený objekt překlopíte podle svislé osy). Ale v případě transpozice matice není skládání potřeba, mnohem jednodušší je z aktuálního pohledu a požadované transformace odvodit konfiguraci nového pohledu.
-
přesně tak funguje numpy. Slicování a transpozice nic nekopíruje, pouze mějí pohled na data.
Tak v tom pripade naprosto bez ironie dekuji za doplneni vzdelani.
(Moje jedina zkusenost s numpy je zatim pouze takova, ze jsem ho musel pribalit k matplotlib a tim padem mi binarka pro zakaznika povyskocila o 13 MB, coz je pro me "starou skolu" docela dost.)
Ale jak to je s nejakym uvolnovanim pameti, kdyz si z matice 1000000x1000000 vezmu vyrez 10x10 a vim, ze ten zbytek uz nikdy potrebovat nebudu?
vyrobite si kopii toho vyrezu. Treba takto
a = np.copy(a[:10,:10])
to puvodni pole bude odalokovano jakmile na něj přestane existovat reference.
-
vyrobite si kopii toho vyrezu. Treba takto
Ok, dik.
-
přesně tak funguje numpy. Slicování a transpozice nic nekopíruje, pouze mějí pohled na data.
Tak v tom pripade naprosto bez ironie dekuji za doplneni vzdelani.
(Moje jedina zkusenost s numpy je zatim pouze takova, ze jsem ho musel pribalit k matplotlib a tim padem mi binarka pro zakaznika povyskocila o 13 MB, coz je pro me "starou skolu" docela dost.)
Ale jak to je s nejakym uvolnovanim pameti, kdyz si z matice 1000000x1000000 vezmu vyrez 10x10 a vim, ze ten zbytek uz nikdy potrebovat nebudu?
vyrobite si kopii toho vyrezu. Treba takto
To už pak ale není nový pohled na původní data. Princip pohledů je právě v tom, že neměníte data ale jenom způsob, jak se na ně díváte. Samozřejmě je nutné vždy zvážit, zda je lepší ponechat data v původní podobě (protože jejich transformace by byla drahá a s pohledem se bude pracovat jen málo), nebo zda je lepší je transformovat (protože se s nimi dále bude hodně pracovat a režie spojená s transformací se vrátí v následném lepším zpracování).
Pokud máte matici projít a pak se celá zahodí, nevadí, že se během procházení drží v paměti data, která už jsou k ničemu. Pokud vám vznikne výřez 10×10, se kterým budete dále pracovat, vyplatí se ten výřez si zkopírovat do nové datové struktury a tu původní velkou matici zahodit.
-
Stále čekám na řešení od Kita...
-
přesně tak funguje numpy. Slicování a transpozice nic nekopíruje, pouze mějí pohled na data.
Tak v tom pripade naprosto bez ironie dekuji za doplneni vzdelani.
(Moje jedina zkusenost s numpy je zatim pouze takova, ze jsem ho musel pribalit k matplotlib a tim padem mi binarka pro zakaznika povyskocila o 13 MB, coz je pro me "starou skolu" docela dost.)
Ale jak to je s nejakym uvolnovanim pameti, kdyz si z matice 1000000x1000000 vezmu vyrez 10x10 a vim, ze ten zbytek uz nikdy potrebovat nebudu?
vyrobite si kopii toho vyrezu. Treba takto
To už pak ale není nový pohled na původní data. Princip pohledů je právě v tom, že neměníte data ale jenom způsob, jak se na ně díváte. Samozřejmě je nutné vždy zvážit, zda je lepší ponechat data v původní podobě (protože jejich transformace by byla drahá a s pohledem se bude pracovat jen málo), nebo zda je lepší je transformovat (protože se s nimi dále bude hodně pracovat a režie spojená s transformací se vrátí v následném lepším zpracování).
Pokud máte matici projít a pak se celá zahodí, nevadí, že se během procházení drží v paměti data, která už jsou k ničemu. Pokud vám vznikne výřez 10×10, se kterým budete dále pracovat, vyplatí se ten výřez si zkopírovat do nové datové struktury a tu původní velkou matici zahodit.
asi jsem se nevyjádřil přesně. Nechci se hádat o názvosloví. Chtěl jsem jen napsat, že kelidasovo řešení nevytváří novou kopii v každém kroku.
-
toto je mozne naozaj len na roote. zacinam pochybovat, ze tu chodia odbornici. skor su to len "odbornici" dokazujuci si ego.
-
toto je mozne naozaj len na roote. zacinam pochybovat, ze tu chodia odbornici. skor su to len "odbornici" dokazujuci si ego.
první 3 řešení jsou dobrá. Pokud pracujete jako freelancer je dobré podobné úlohy trénovat, občas se stane, že si vás potenciální zákazník na něčem podobném prověří.
-
toto je mozne naozaj len na roote. zacinam pochybovat, ze tu chodia odbornici. skor su to len "odbornici" dokazujuci si ego.
první 3 řešení jsou dobrá. Pokud pracujete jako freelancer je dobré podobné úlohy trénovat, občas se stane, že si vás potenciální zákazník na něčem podobném prověří.
Co se vam nelibi na mem 4tem reseni? Jestli to chapu spravne, tak to dela to stejne*, co treba to treti a ma nizsi wtf-faktor ;D.
*: Teda je to cyklus vs rekurze, kterou asi stejne prekladac transformuje do cyklu, takze tam asi rozdil moc nebude.
-
toto je mozne naozaj len na roote. zacinam pochybovat, ze tu chodia odbornici. skor su to len "odbornici" dokazujuci si ego.
první 3 řešení jsou dobrá. Pokud pracujete jako freelancer je dobré podobné úlohy trénovat, občas se stane, že si vás potenciální zákazník na něčem podobném prověří.
Co se vam nelibi na mem 4tem reseni? Jestli to chapu spravne, tak to dela to stejne*, co treba to treti a ma nizsi wtf-faktor ;D.
*: Teda je to cyklus vs rekurze, kterou asi stejne prekladac transformuje do cyklu, takze tam asi rozdil moc nebude.
Asi jsem spletl pořadí řešení. To vaše se mi líbí. Ta ukecaná se mi nelíbí.
-
toto je mozne naozaj len na roote. zacinam pochybovat, ze tu chodia odbornici. skor su to len "odbornici" dokazujuci si ego.
Je lahsie buzerovat ako byt konstruktivny. Tiez tu badam podobny trend, co je celkom skoda :(
-
Abych byl uprimny, tak si myslim, ze vse bude tezce zaviset na tom, kam a na jakou pozici se clovek hlasi - podle toho budou lepe hodnocena elegantni abstraktni jednoducha reseni (napr. vyssi prog. a FP jazyky) versus rychla ukecana reseni (asi "nizsi" jazyky typu C, programovani krabicek atp.). Mozna by to clovek u pohovoru mel spise brat neutralne (nekdo to uz myslim psal) a dalsi otazka by mela byt na vykon zvoleneho reseni, pobavit se o tom, proc zvolil takovy postup/dat. strukturu/jazyk, atp.
Osobne bych se trosku bal, ze programator, ktery si to zacne vse psat od podlahy bude mit problem v praxi pouzivat knihovny a bude si radeji vse psat sam (nema prehled o std. knihovne ci ekosystemu) a tedy plytvat penize zamestnavateli. Ale to je dost mozna jen muj subjektivni pohled na vec zkresleny z Haskellu, vyssich jazyku a prace, kde se silne preferuje klidne velmi suboptimalni reseni, pokud to usetri cas vyvoje.
Na skolni ulohu bez nastavenych limitu s trivialnimi vstupnimi daty jsou IMO ta jednoducha reseni spravna, v realnem svete bude zalezet na zadani a tedy na projektu, jazyku, povolenych knihovnach a bambilionu dalsich veci.
PS: Ja pridal dve hezke sajty podobne eurlerovi/codewars (nikdo na to myslim nereagoval), asi to zapadlo ve zbytku prispevku. :-\
-
Tak jsem zvolil Haskell, akorát jsem použil Data.Vector, kde není v knihovně "transpose" (ani jsem netušil, že to v Prelude je), a že otočení je "reverse . transpose" mě nenapdlo... :-[ Nojo, premature optimization, možná kdybych viděl transpose, tak mě to napadne...(a možná ne).
IMO tohle je vyloženě úloha na to, jestli v tom člověk to otočení vidí nebo ne. A kdo nezačal programovat, ale vzal si nejdřív papír, tak to tam našel... a "ideální" kód vypadá přesně tak, jak to je v tom haskellu (nebo ekvivalent v NumPy), akorát kolem toho eventuálně bude knihovna, která pořeší ty view.
Otázka je, jestli se to dá nacvičit. Řekl bych, že ano. Je to stejné, jako když řešíte různé matematické prostocviky nebo vymýšlíte matematické důkazy. Když jich pár stovek horkotěžko dáte dohromady (projdete si spoustu slepých uliček) a pak různá elegantní řešení, tak při nových úlohách najednou vidíte, kam se kouknout, jestli tam nevede jednodušší cesta..
Programování je jen spousty triků, a když jich budete pár znát, tak je snadno budete umět použít...
-
Abych byl uprimny, tak si myslim, ze vse bude tezce zaviset na tom, kam a na jakou pozici se clovek hlasi - podle toho budou lepe hodnocena elegantni abstraktni jednoducha reseni (napr. vyssi prog. a FP jazyky) versus rychla ukecana reseni (asi "nizsi" jazyky typu C, programovani krabicek atp.). Mozna by to clovek u pohovoru mel spise brat neutralne (nekdo to uz myslim psal) a dalsi otazka by mela byt na vykon zvoleneho reseni, pobavit se o tom, proc zvolil takovy postup/dat. strukturu/jazyk, atp.
Osobne bych se trosku bal, ze programator, ktery si to zacne vse psat od podlahy bude mit problem v praxi pouzivat knihovny a bude si radeji vse psat sam (nema prehled o std. knihovne ci ekosystemu) a tedy plytvat penize zamestnavateli. Ale to je dost mozna jen muj subjektivni pohled na vec zkresleny z Haskellu, vyssich jazyku a prace, kde se silne preferuje klidne velmi suboptimalni reseni, pokud to usetri cas vyvoje.
Na skolni ulohu bez nastavenych limitu s trivialnimi vstupnimi daty jsou IMO ta jednoducha reseni spravna, v realnem svete bude zalezet na zadani a tedy na projektu, jazyku, povolenych knihovnach a bambilionu dalsich veci.
PS: Ja pridal dve hezke sajty podobne eurlerovi/codewars (nikdo na to myslim nereagoval), asi to zapadlo ve zbytku prispevku. :-\
Stačí vidět to ve správném kontextu. To dvouřádkové řešení v Haskellu je objektivně nejhezčí, jen místo pole polí by se měl použít příhodnější typ (Matrix). Fungovat to bude úplně stejně a když se pak ukáže, že dat jsou gigabajty, udělá se z toho typová třída a algoritmus - zapsaný úplně stejně elegantně - bude mít lineární implementaci pomocí náhledů. Příklad par excellence přístupu “the art of programming”.
-
Otázka je, jestli se to dá nacvičit. Řekl bych, že ano. Je to stejné, jako když řešíte různé matematické prostocviky nebo vymýšlíte matematické důkazy. Když jich pár stovek horkotěžko dáte dohromady (projdete si spoustu slepých uliček) a pak různá elegantní řešení, tak při nových úlohách najednou vidíte, kam se kouknout, jestli tam nevede jednodušší cesta..
Aneb není nad tvůrčí činnost.
-
PS: Ja pridal dve hezke sajty podobne eurlerovi/codewars (nikdo na to myslim nereagoval), asi to zapadlo ve zbytku prispevku. :-\
Jsem to nějak hledal a nemůžu ty sajty najít, docela by mě to zajímalo, můžeš je znovu zveřejnit?
-
Byly to http://adventofcode.com a https://www.codingame.com. Ten prvni jsem zkousel predchozi verzi (rok zpet) a je to podobne tomu eurlerovi (navic s tematickym textem). Druhe jsem moc nezkousel a nevim, jestli to bude pro vas, je to mozna pro uplne zacatecniky a mozna cilene spise na mladsi (tematika komisku, her a tak, asi to nemusi kazdemu sednout; ale mozna kecam, moc jsem od tam nezkousel). Na rozdil od codewars ale (minimalne ten advent of code) nemaji zadne srovnavani kodu s ostatnimi lidmi.
Asi jich par zkuste a uvidite, co vam nejvice sedne. Pripadne prostridat, nebo si ty bez vzorovych reseni nechat az udelate par nizsich urovni v codewars, a pak jimi procvicovat spise algoritmy/mysleni nez jazyk/std. knihovnu.
-
Pokud pracujete jako freelancer je dobré podobné úlohy trénovat, občas se stane, že si vás potenciální zákazník na něčem podobném prověří.
To potom není zákazník, ale švarcový zaměstnavatel.
-
Byly to http://adventofcode.com a https://www.codingame.com. Ten prvni jsem zkousel predchozi verzi (rok zpet) a je to podobne tomu eurlerovi (navic s tematickym textem).
Ten adventofcode nemá právě ty řešení, což mi přijde, že když se člověk nepodívá na konkurenci, tak se nic nenaučí. To codingame je lepší, jsou tam i řešení, i když to není tak dobře zorganizováno jako na codewars, kde jsou řešení dost přehledně podle počtu hlasů atd.
Ale je to rozhodně zajímavé. Jsem dlouho netušil, že takovéhle weby vůbec jsou... A většina kurzů mi přišla na nic, protože většinou učí jen syntaxi.
-
doporucil uz nekdo https://www.hackerrank.com/ ?
-
nepochopim, jakej vyznam maji tyhle ukoly na pohovoru. nekoho nemusi napadnout prace s matici. je horsi? ne. kdyby mi nekdo dal takovej ukol, poslal bych ho do zadeke
-
Píšu tak, aby byl kód bezpečný. Zvlášť když vector není pomalejší než raw pole. Ostatně v tom stupidním kódu je chyba právě ve správě paměti, pro pole se používá delete[].
Ved som povedal, ze su tam chyby, ale islo mi o jednoduchost, spatne zmenit to uz neviem. Kazdopadne algoritmus samotny funguje, je najrychlejsi a pouziva najmenej pamate z tu zverejnenych. Pises tu vacsinou v tomto vlakne techicky dobre veci, ale preco si sa namiesto normalnej kritiky priklonil k arogancii to je len o tebe...
Spat k teme:
Sice taketo priklady sice pomahaju zlepsit rozmyslanie programatora, ale to nie je vsetko ako to Noef dobre napisal. Viac pomaha riesenie kazdodennych problemov.
Najlahsie je skusit si napisat par malych projektov z oblasti o ktoru mas zaujem. Tam ziskas vedomosti aj z kniznic/frameworkov a budes riesit realne problemy s vyvojom. Teda veci to co vacsinou zamestnavatelov zaujimaju.
Tieto priklady sluzia len na zistnie akym sposobom uchadzac rozmysla pri riesni problemov (a niekedy ho dostat pod tlak, zalezi od pohovoru).
Tu je viac takych podobnych stranok s ktorymi som sa stretol a este tu neboli, ale ci su tam riesenia, to neviem:
- https://topcoder.com/
- https://codefights.com/
- https://www.reddit.com/r/dailyprogrammer/
- http://exercism.io/
- https://open.kattis.com/
- https://www.codechef.com/
- http://codeforces.com/
-
Píšu tak, aby byl kód bezpečný. Zvlášť když vector není pomalejší než raw pole. Ostatně v tom stupidním kódu je chyba právě ve správě paměti, pro pole se používá delete[].
Ved som povedal, ze su tam chyby, ale islo mi o jednoduchost, spatne zmenit to uz neviem. Kazdopadne algoritmus samotny funguje, je najrychlejsi a pouziva najmenej pamate z tu zverejnenych. Pises tu vacsinou v tomto vlakne techicky dobre veci, ale preco si sa namiesto normalnej kritiky priklonil k arogancii to je len o tebe...
Třeba mi vadí, když někdo neuzná chybu. Nejde o delete[], ale o fakt explicitního použití new. Ovšem je na každém, chce-li se poučit z vlastních chyb, na než byl upozorněn.
-
Píšu tak, aby byl kód bezpečný. Zvlášť když vector není pomalejší než raw pole. Ostatně v tom stupidním kódu je chyba právě ve správě paměti, pro pole se používá delete[].
Ved som povedal, ze su tam chyby, ale islo mi o jednoduchost, spatne zmenit to uz neviem. Kazdopadne algoritmus samotny funguje, je najrychlejsi a pouziva najmenej pamate z tu zverejnenych. Pises tu vacsinou v tomto vlakne techicky dobre veci, ale preco si sa namiesto normalnej kritiky priklonil k arogancii to je len o tebe...
Třeba mi vadí, když někdo neuzná chybu. Nejde o delete[], ale o fakt explicitního použití new. Ovšem je na každém, chce-li se poučit z vlastních chyb, na než byl upozorněn.
Mas pravdu, ze raw pointer a takyto explicitny new nie je vacsinou spravna cesta pre normalne projekty. Ale na druhu stranu, nie vzdy mas stl alebo smart pointer, kazdy c/c++ projekt ma svoje specifika a pravidla, niekto stl, niekto ma tie smart pointre, niekto ma gc, niekto ma overloadnuty new operator a vlastne alokatory, niekto pouziva inplace new, videl som vela projektov a kazdy to mal inak, ja som volil citatelnost a mi to prislo mi to citalnejsie ako stl alebo malloc.
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
-
Píšu tak, aby byl kód bezpečný. Zvlášť když vector není pomalejší než raw pole. Ostatně v tom stupidním kódu je chyba právě ve správě paměti, pro pole se používá delete[].
Ved som povedal, ze su tam chyby, ale islo mi o jednoduchost, spatne zmenit to uz neviem. Kazdopadne algoritmus samotny funguje, je najrychlejsi a pouziva najmenej pamate z tu zverejnenych. Pises tu vacsinou v tomto vlakne techicky dobre veci, ale preco si sa namiesto normalnej kritiky priklonil k arogancii to je len o tebe...
Třeba mi vadí, když někdo neuzná chybu. Nejde o delete[], ale o fakt explicitního použití new. Ovšem je na každém, chce-li se poučit z vlastních chyb, na než byl upozorněn.
Mas pravdu, ze raw pointer a takyto explicitny new nie je vacsinou spravna cesta pre normalne projekty. Ale na druhu stranu, nie vzdy mas stl alebo smart pointer, kazdy c/c++ projekt ma svoje specifika a pravidla, niekto stl, niekto ma tie smart pointre, niekto ma gc, niekto ma overloadnuty new operator a vlastne alokatory, niekto pouziva inplace new, videl som vela projektov a kazdy to mal inak, ja som volil citatelnost a mi to prislo mi to citalnejsie ako stl alebo malloc.
Mám za to, že STL je standard a předpokládá se, ale budiž, nechci se hádat, jen bych u jednoduchého prototypického příkladu očekával “štábní kulturu”. V C++11/14/17 je vše potřebné pro vytvoření hezkého kódu. Možná jako cvičení by stálo za to přepsat tu haskellí verzi do (víceméně funkcionálního) C++.
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
O(n) (při použití náhledů)
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
O(n) (při použití náhledů)
Tak to asi tezko, kdyz jenom projit vsechny prvky ctvercove matice trva O(n^2), pripadne O(m*n) u nectvercove
Co jsou to ty nahledy?
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
O(n) (při použití náhledů)
Tak to asi tezko, kdyz jenom projit vsechny prvky ctvercove matice trva O(n^2), pripadne O(m*n) u nectvercove
Co jsou to ty nahledy?
Jenže tady někdo zavedl, že n je počet prvků (a chybně tvrdil, že ten algoritmus je kvadratický). Doporučuju zjistit kontext před psaním.
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
O(n) (při použití náhledů)
Tak to asi tezko, kdyz jenom projit vsechny prvky ctvercove matice trva O(n^2), pripadne O(m*n) u nectvercove
Co jsou to ty nahledy?
Jenže tady někdo zavedl, že n je počet prvků (a chybně tvrdil, že ten algoritmus je kvadratický). Doporučuju zjistit kontext před psaním.
No tak to si myslim, ze zavedl chybne. To taky muzu rict, ze algoritmus je O(1), protoze na vstupu je 1 matice (kdyz to prezenu :) )
Me prave zajimala ta slozitost maticovych operaci.....
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
Ked su strany tej matice a,b a a<b, tak O(a2b). Teda vzhladom k poctu prvkov pre stvorec O(n3/2), ako sem uz niekto spravne napisal.
Vychadzal som z toho, ze pri obracani matice operacia trva konstantny cas na kazdy zostavajuci prvok, potom uz iba matika.
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
O(n) (při použití náhledů)
Tak to asi tezko, kdyz jenom projit vsechny prvky ctvercove matice trva O(n^2), pripadne O(m*n) u nectvercove
Co jsou to ty nahledy?
Jenže tady někdo zavedl, že n je počet prvků (a chybně tvrdil, že ten algoritmus je kvadratický). Doporučuju zjistit kontext před psaním.
No tak to si myslim, ze zavedl chybne. To taky muzu rict, ze algoritmus je O(1), protoze na vstupu je 1 matice (kdyz to prezenu :) )
Me prave zajimala ta slozitost maticovych operaci.....
Zavedl to korektně, je to prostě parametr pro analýzu, jen se to musí říct. Když budu chtít O vzhledem k n x m (tak jsem to původně chápal i já), bude to O(nm).
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
Ked su strany tej matice a,b a a<b, tak O(a2b). Teda vzhladom k poctu prvkov pre stvorec O(n3/2), ako sem uz niekto spravne napisal.
Vychadzal som z toho, ze pri obracani matice operacia trva konstantny cas na kazdy zostavajuci prvok, potom uz iba matika.
V naivní implementaci O(n**3/2), v optimální O(n), resp. O(ab), jak už tu bylo vysvětleno asi třikrát.
-
Hm, tohle byl zcela trivialni ukol. Jesteze to neni treba o naprogramovani piskvorku, to by si urcite vyzadalo alespon tri vedecka sympozia.
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
Ked su strany tej matice a,b a a<b, tak O(a2b). Teda vzhladom k poctu prvkov pre stvorec O(n3/2), ako sem uz niekto spravne napisal.
Vychadzal som z toho, ze pri obracani matice operacia trva konstantny cas na kazdy zostavajuci prvok, potom uz iba matika.
V naivní implementaci O(n**3/2), v optimální O(n), resp. O(ab), jak už tu bylo vysvětleno asi třikrát.
Pytal sa na otacacie riesenie. Ze pri nahladoch sa nic neotaca, meni sa iba pohlad na data.
-
Hm, tohle byl zcela trivialni ukol. Jesteze to neni treba o naprogramovani piskvorku, to by si urcite vyzadalo alespon tri vedecka sympozia.
Snad “piškvorek”, nebo si už pleteš i rody?
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
Ked su strany tej matice a,b a a<b, tak O(a2b). Teda vzhladom k poctu prvkov pre stvorec O(n3/2), ako sem uz niekto spravne napisal.
Vychadzal som z toho, ze pri obracani matice operacia trva konstantny cas na kazdy zostavajuci prvok, potom uz iba matika.
V naivní implementaci O(n**3/2), v optimální O(n), resp. O(ab), jak už tu bylo vysvětleno asi třikrát.
Pytal sa na otacacie riesenie. Ze pri nahladoch sa nic neotaca, meni sa iba pohlad na data.
To je pořád otáčecí řešení - jde o sémantiku (x ++ snail $ rotate xs).
-
Hm, tohle byl zcela trivialni ukol. Jesteze to neni treba o naprogramovani piskvorku, to by si urcite vyzadalo alespon tri vedecka sympozia.
Snad “piškvorek”, nebo si už pleteš i rody?
http://www.pravidla.cz/hledej/?qr=pi%9Akvorky
https://cs.wiktionary.org/wiki/pi%C5%A1kvorky#sklo.C5.88ov.C3.A1n.C3.AD
Trhni si nohou, zretelne existuji oba tvary.
-
Hm, tohle byl zcela trivialni ukol. Jesteze to neni treba o naprogramovani piskvorku, to by si urcite vyzadalo alespon tri vedecka sympozia.
Snad “piškvorek”, nebo si už pleteš i rody?
http://www.pravidla.cz/hledej/?qr=pi%9Akvorky
https://cs.wiktionary.org/wiki/pi%C5%A1kvorky#sklo.C5.88ov.C3.A1n.C3.AD
Trhni si nohou, zretelne existuji oba tvary.
Dík za odkaz, Tatare, wiktionary potvrzuje rod ženský.
-
Hm, tohle byl zcela trivialni ukol. Jesteze to neni treba o naprogramovani piskvorku, to by si urcite vyzadalo alespon tri vedecka sympozia.
Snad “piškvorek”, nebo si už pleteš i rody?
http://www.pravidla.cz/hledej/?qr=pi%9Akvorky
https://cs.wiktionary.org/wiki/pi%C5%A1kvorky#sklo.C5.88ov.C3.A1n.C3.AD
Trhni si nohou, zretelne existuji oba tvary.
Pravidla.cz jsou nesmysl, používat slovník spellcheckeru jako slovník opravdu není dobrý nápad. Oficiální slovník češtiny máte zde: http://prirucka.ujc.cas.cz/?slovo=pi%C5%A1kvorky
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Ty objekty se nemusí vnořovat. V objektu budete mít dva prvky – odkaz na data, a konfiguraci, jak se má s daným pohledem zacházet. Když vytvoříte nový pohled, vytvoříte nový objekt, vložíte do něj odkaz na stejná data a novou konfiguraci. Na tom původním pohledu tento nový nijak nezávisí. Samozřejmě to nelze použít tehdy, kdybyste ty transformace objektů skládal (třeba v geometrii – něco otočíte, otočený objekt zmenšíte a otočený a zmenšený objekt překlopíte podle svislé osy). Ale v případě transpozice matice není skládání potřeba, mnohem jednodušší je z aktuálního pohledu a požadované transformace odvodit konfiguraci nového pohledu.
Když se objekty nebudou vnořovat tak bude o to složitější ta konfigurace jak se má s daným pohledem zacházet - můžete totiž celkem jednoduše udělat 4 pohledy pro různé otočení matice, ale vybrání patřičných prvků nebude úplně jednoduché (protože tam nebude Xkrát vnořeno odříznutí prvního řádku), budou tam potřeba vzorečky podobně jako byly v tom řešení od Kolemjdoucího, čímž se ta rádoby krásnost krátkých řešení poněkud vytratí.
-
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.
Šlo by prosím nějak rozepsat to "slices" nebo "view onto"? Mě jediné co napadá je mít data pořád stejná, jen je obalovat objekty které budou realizovat ty požadované transformace - takže na střídačku odříznutí prvního řádku a otočení. I to ale povede ke zhoršení výkonu, protože čím dál se to dostane tím větším počtem objektů budu mít ta data obalená a přestane platit že přístup k prvku v matici je O(1).
Ty objekty se nemusí vnořovat. V objektu budete mít dva prvky – odkaz na data, a konfiguraci, jak se má s daným pohledem zacházet. Když vytvoříte nový pohled, vytvoříte nový objekt, vložíte do něj odkaz na stejná data a novou konfiguraci. Na tom původním pohledu tento nový nijak nezávisí. Samozřejmě to nelze použít tehdy, kdybyste ty transformace objektů skládal (třeba v geometrii – něco otočíte, otočený objekt zmenšíte a otočený a zmenšený objekt překlopíte podle svislé osy). Ale v případě transpozice matice není skládání potřeba, mnohem jednodušší je z aktuálního pohledu a požadované transformace odvodit konfiguraci nového pohledu.
Když se objekty nebudou vnořovat tak bude o to složitější ta konfigurace jak se má s daným pohledem zacházet - můžete totiž celkem jednoduše udělat 4 pohledy pro různé otočení matice, ale vybrání patřičných prvků nebude úplně jednoduché (protože tam nebude Xkrát vnořeno odříznutí prvního řádku), budou tam potřeba vzorečky podobně jako byly v tom řešení od Kolemjdoucího, čímž se ta rádoby krásnost krátkých řešení poněkud vytratí.
Odříznutí se dělá vytvořením nového náhledu přímo nad daty, nemůže tam být víckrát. A v tomto případě se náhledy nevrší, je tam jen jedna rotace.
-
Dík za odkaz, Tatare, wiktionary potvrzuje rod ženský.
Ano, proto jsem ho tam dal, jako ukazku, ze existuji oba tvary.
Jinak az budes nekomu zase kritizovat cestinu, tak pred "nebo" se nepise carka a to uz drahne let.
-
Jinak az budes nekomu zase kritizovat cestinu, tak pred "nebo" se nepise carka a to uz drahne let.
Jak kdy:
http://prirucka.ujc.cas.cz/?id=155
-
Jak kdy:
http://prirucka.ujc.cas.cz/?id=155
Na tento pripad se nevztahuje.
-
Dík za odkaz, Tatare, wiktionary potvrzuje rod ženský.
Ano, proto jsem ho tam dal, jako ukazku, ze existuji oba tvary.
Jinak az budes nekomu zase kritizovat cestinu, tak pred "nebo" se nepise carka a to uz drahne let.
Někdy píše, musíš znát přesná pravidla.
-
Dík za odkaz, Tatare, wiktionary potvrzuje rod ženský.
Ano, proto jsem ho tam dal, jako ukazku, ze existuji oba tvary.
Jinak az budes nekomu zase kritizovat cestinu, tak pred "nebo" se nepise carka a to uz drahne let.
Z toho tvého odkazu: “V pravidlech neodpovídá žádné klíčové slovo vašemu zadání piškvorek.” Sám jsi vyvrátil své tvrzení. Ale furt lepší, než když tu nějaký ještě větší Tatar psal “ten monád”. OMG
-
Někdy píše, musíš znát přesná pravidla.
Jak jsem napsal, na dany pripad se pravidlo od ehmmm nevztahuje. Tak se nauc presna pravidla a pak kritizuj.
Z toho tvého odkazu: “V pravidlech neodpovídá žádné klíčové slovo vašemu zadání piškvorek.” Sám jsi vyvrátil své tvrzení. Ale furt lepší, než když tu nějaký ještě větší Tatar psal “ten monád”. OMG
SLOVNÍ TVARY: piškvorek ~ piškvorcích ~ piškvorkem ~ piškvorku ~ piškvorkům ~ piškvorky
Ke je receno, ze jsou v seznamu *vsechny* slovni tvary? Vyse uvedene tvary jsou zretelne v muzskem rodu. Jestlize existuje treba tvar piškvorkům tam, kde druhy odkaz uvadi piškvorkám, logicky exituje i tvar piskvorku. Chapu, ten tvar tam nebyl vyslovne uveden, takze by nekdo musel premyslet.
-
Někdy píše, musíš znát přesná pravidla.
Jak jsem napsal, na dany pripad se pravidlo od ehmmm nevztahuje. Tak se nauc presna pravidla a pak kritizuj.
Bla bla, kecy v kleci. Když neumíš přiznat chybu, tak aspoň nepruď.
-
Z toho tvého odkazu: “V pravidlech neodpovídá žádné klíčové slovo vašemu zadání piškvorek.” Sám jsi vyvrátil své tvrzení. Ale furt lepší, než když tu nějaký ještě větší Tatar psal “ten monád”. OMG
SLOVNÍ TVARY: piškvorek ~ piškvorcích ~ piškvorkem ~ piškvorku ~ piškvorkům ~ piškvorky
Ke je receno, ze jsou v seznamu *vsechny* slovni tvary? Vyse uvedene tvary jsou zretelne v muzskem rodu.
To je jak u Zemana na dvorku :o Argumentuješ tvarem generovaným automaticky nějakým morfologickým modulem. To takhle jeden zadal do analyzátoru ruštiny vyvinutém na MFF UK v 80. letech кровать a vypadlo mu я кроваю, ты кроваешь... Tolik k argumentaci za použití něčeho, o čem víš kulový.
-
Nemel jsem uplne cas cist cele vlakno, jak je tedy slozitost reseni v big O notaci pro to "otaceci" reseni?
Jinak i když v tomto případě je to jednoduché a všechny ty manipulace jsou O(1) a “nekupí” se (nezhoršují tedy časovou složitost, je-li algoritmus aspoň lineární), v obecném případě se jejich řetězení a jeho optimalizace řeší word problémem - tam teprve začíná legrace.
-
Začal jsem se učit programovat ve Visual Basicu, s tím že jsem nikdy předtím neprogramoval. A mám asi za sebou 6 hodin učení čistého času.
Skusil jsem si jednoduchou variantu, kdy člověk zadá A a B a tím určí velikost "číselného" čtverce/obdélníku s posloupností +1 po řádcích. No a ono to vyhodí toho "číselného hada". Tak se chci pochlubit - trvalo mi to asi 2 hodiny. :D
Sub main()
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
Dim z As Integer
Dim x As String
Dim y As Integer
Dim i As Integer
a = InputBox("Zadej A")
b = InputBox("Zadej B")
c = a
d = b
z = 0
Do Until c <= 2
c = a - i
d = b - y
Do Until c < 1
z = z + 1
x = x + Str(z) + " "
c = c - 1
Loop
c = a - i
Do Until d < 2
z = z + a
x = x + Str(z) + " "
d = d - 1
Loop
d = b - y
Do Until c < 2
z = z - 1
x = x + Str(z) + " "
c = c - 1
Loop
c = a - i
Do Until d < 3
z = z - a
x = x + Str(z) + " "
d = d - 1
Loop
i = i + 2
y = y + 2
Loop
MsgBox x
End Sub
-
Sice možná trochu delší na řádky, ale 100% funkcionální bez závislostí na ES2017 (core logika je jen v getSnakePath):
function getSnakePath(playGround, point = { x: 0, y: 0 }, direction = directions[0]) {
const current = playGround[point.y][point.x];
const nextPlayGround = removeXY(playGround, point);
const nextDirection = isInPlayGround(nextPlayGround, point.x + direction.x, point.y + direction.y)
? direction
: turnDirectionRight(direction);
const nextPoint = { x: point.x + nextDirection.x, y: point.y + nextDirection.y };
return [
current,
...isInPlayGround(nextPlayGround, nextPoint.x, nextPoint.y) ? getSnakePath(nextPlayGround, nextPoint, nextDirection) : [],
];
}
const directions = [
{ x: 1, y: 0 },
{ x: 0, y: 1 },
{ x: -1, y: 0 },
{ x: 0, y: -1 },
];
function turnDirectionRight(direction) {
return directions[(directions.indexOf(direction) + 1) % directions.length]
}
function removeXY(array, point) {
return array.reduce((nextArray, subArray, y) => [
...nextArray, y === point.y ? subArray.reduce((nextSubArray, value, x) => [
...nextSubArray, x === point.x ? undefined : value
], []) : subArray
], []);
}
function isInPlayGround(playGround, x, y) {
return y < playGround.length && y >= 0 && x < playGround[y].length && x >= 0 && typeof playGround[y][x] !== 'undefined';
}
-
Když se objekty nebudou vnořovat tak bude o to složitější ta konfigurace jak se má s daným pohledem zacházet - můžete totiž celkem jednoduše udělat 4 pohledy pro různé otočení matice, ale vybrání patřičných prvků nebude úplně jednoduché (protože tam nebude Xkrát vnořeno odříznutí prvního řádku), budou tam potřeba vzorečky podobně jako byly v tom řešení od Kolemjdoucího, čímž se ta rádoby krásnost krátkých řešení poněkud vytratí.
Otočení matice je dané pouze pořadím, v jakém se má procházet (zda nejprve sloupce nebo řádky) plus směrem procházení (vpřed nebo vzad). Oříznutí znamená, že se pole bude místo od nuly do délka pole - 1 procházet od zadané hodnoty po zadanou hodnotu. Znamená to tedy pamatovat si příznak osa X nebo osa Y, směr (+1 nebo -1) a 4 hodnoty ohraničující pole. Jediné vzorečky použité při procházení budou for cyklus a přičtení hodnoty (+1 nebo -1) k indexu.
-
trocha javascript hatmatilky a je to :-)
const snake = (m, out = [], s = 0) => {
if (m.length === 0) return out;
let f = [['shift', 'concat'], ['pop', 'concat'], ['pop', 'reverse'], ['shift', 'reverse']][s % 4];
return snake(m, out.concat([].concat.apply([], ([[m], m][Math.floor(s % 2)]).map(p => p[f[0]]()))[f[1]]()), s + 1);
};
console.log(snake(example1).join(', '));