Programátorský úkol

[Zvědavec]

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

[Reklama]

[Gumidek]

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 

Kód: [Vybrat]

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


[Aoidhghean]

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.

[Zvědavec]

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ě?

[Aoidhghean]

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

[Reklama]

[Zvědavec]

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?

[Kozzi]

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 .

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

[Aoidhghean]

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

Kód: [Vybrat]

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)?

[Aoidhghean]

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 .

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

[Lord Zoidberg]

Porovnání výpočetního času:

Můj code:

Kód: [Vybrat]

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:

Kód: [Vybrat]

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:

Kód: [Vybrat]

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:

Kód: [Vybrat]

xSmall=linsp(5,5)
xxSmall=xSmall.tolist()

xLarge=linsp(100,100)
xxLarge=xLarge.tolist()

Malé pole:

Kód: [Vybrat]

%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:

Kód: [Vybrat]

%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

[JardaP .]

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?

[čumil]

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

[Kozzi]

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 .

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

[Aoidhghean]

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 .

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.

[mon]

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;
}