Programátorský úkol

[Aoidhghean]

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:

Kód: [Vybrat]

#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”.

[Reklama]

[mon]

...
 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

[borekz]

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.

[gll]

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ů.

[gll]

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í.

[Reklama]

[Aoidhghean]

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[].

[gll]

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.

[ehmmm]

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?

[Filip Jirsák]

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.

[gll]

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

Kód: [Vybrat]

a = np.copy(a[:10,:10])

to puvodni pole bude odalokovano jakmile na něj přestane existovat reference.

[ehmmm]

vyrobite si kopii toho vyrezu. Treba takto

Ok, dik.

[Filip Jirsák]

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.

[kitfan]

Stále čekám na řešení od Kita...

[gll]

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.

[nepochopim]

toto je mozne naozaj len na roote. zacinam pochybovat, ze tu chodia odbornici. skor su to len "odbornici" dokazujuci si ego.