Comments on Zont: PR0GR4M470R5K4 UL0H4

OpenID test...

2009-07-16T12:08:05.856+02:00

OpenID test...

Ja som to tiez riesil ale nestihol som to poslat :...

2009-07-16T09:58:57.213+02:00

Ja som to tiez riesil ale nestihol som to poslat :( navyse to malo jednu chybu - pascal stringy - iba 255 znakov takze setko orezava... ale inak fajne... uz sa tesim na dalsiu ulohu :) (snad nezmeskam)

P.S. - admini mate nieco s open ID "Poverenia pre váš identifikátor OpenID sa nedali overiť." co to ma byt?

ja nie, ale bol som tam na exkurzii a majú tam pek...

2009-06-22T08:25:13.157+02:00

ja nie, ale bol som tam na exkurzii a majú tam pekný výhľad...

...taktiež tam majú "Control Room" skoro ako v Houston-e, už iba odpaľovacie zariadenie na rakety a môžu posielať satelity na obežnú dráhu :)

...a ešte špeciálne antivírové rohožky, ktoré zrejme zabraňujú šíreniu vírusov medzi miestnosťami :)

inak niekto z Vas ide pracovat pre eset?

2009-06-21T18:14:27.593+02:00

inak niekto z Vas ide pracovat pre eset?

uz je vonku aj analyticka uloha - http://3537.sk/v...

2009-06-18T13:09:13.159+02:00

uz je vonku aj analyticka uloha - http://3537.sk/virusovy-analytik.html

re Rori: diq, pisanie blogov je celkom zabava, ak...

2009-05-29T12:43:19.498+02:00

re Rori:

diq, pisanie blogov je celkom zabava, ak budem mat nieco co by mohlo zaujat inych, urcite napisem clanok

re Vyhodnotenie vysledkov:

prijemne ma prekvapilo kolko roznych programovacich jazykov bolo pouzitych, chcel by som vediet vsetky :)

pobavilo ma, ze som sa dostal medzi renegatov, nebolo to mojim zamerom, trosku som cakal, ze medzi renegatmi budu riesenia vyuzivajuce kombinacie neuronovych sieti a genetickych algoritmov :)

super, konecne som nasiel spravne vysledky a este ...

2009-05-28T20:47:22.499+02:00

super, konecne som nasiel spravne vysledky a este lepsie ze mne to vyslo rovnako :)

kedze som to zbuchal v Pythone a nechcelo sa mi optimalizovat kym neviem ci mam dobre vysledky,, ostal vykon na 2 sekundach a cca 50MB (set_large.dat)

http://aprilboy.e404.sk/PH_3537_uloha.py.txt

museli to dat v poslednych dvoch dnoch ... A grat...

2009-05-28T08:52:59.558+02:00

museli to dat v poslednych dvoch dnoch ...

A gratulujem k priamej linke na tento blog :)

Inak, neviem ci viete, ja som si to az teraz vsimo...

2009-05-27T23:57:37.123+02:00

Inak, neviem ci viete, ja som si to az teraz vsimol, ale akutalizovali stanku sutaze:
http://www.3537.sk/programator.html

Mimochodom, Eset, bolo by velmi zaujimave, keby ste zverejnili vsetky spravne riesenia, prosim..?

Ma to az nieco cez 30MB ak si dobre pamatam...

2009-05-18T10:24:00.000+02:00

Ma to az nieco cez 30MB ak si dobre pamatam...

No, a ma menej ako 2MB?

2009-05-12T21:59:00.000+02:00

No, a ma menej ako 2MB?

Ja ho mam :) ale nechcem ho zverejnovat na webe - ...

2009-05-12T09:15:00.000+02:00

Ja ho mam :) ale nechcem ho zverejnovat na webe - neviem ako s autorskymi pravami - a zaroven nechcem nejak zverejnovat svoju email adresu :) uz mam spamu dost :) ale ak sa nebojis postni email adresu (aj do mojho blogu :) )

Neviete nahodou niekto kde by sa dal zohnat ten su...

2009-05-11T19:55:00.000+02:00

Neviete nahodou niekto kde by sa dal zohnat ten subor set_large.dat bo by som si to chcel aj ja skusit otestovat ale neviem kde ho najst

Samozrejme, poslal som to presne: Mon, Apr 13, 200...

2009-04-21T11:28:00.000+02:00

Samozrejme, poslal som to presne: Mon, Apr 13, 2009 at 2:36 PM.

Mozem sa spytat kedy si im to posielal?

2009-04-21T11:20:00.000+02:00

Mozem sa spytat kedy si im to posielal?

Update: Opravujem, dostal som odpoved z ESET-u a v...

2009-04-21T10:52:00.000+02:00

Update: Opravujem, dostal som odpoved z ESET-u a vcelku ma potesila. Ak si najdem cas urcite sa pozriem aj na druhu ulohu.

predosli koment je moj, len som sa zabudol prihlas...

2009-04-20T11:16:00.000+02:00

predosli koment je moj, len som sa zabudol prihlasit :(

ahoj vsetci ...stratil som mierne prehlad, ktore ...

2009-04-20T11:14:00.000+02:00

ahoj vsetci

...stratil som mierne prehlad, ktore komentare sa tykaju ktorych algoritmov, mozno by bolo dobre to explicitne napisat v kazdom komente

...kazdopadne, neberte moj kod ako finalny vysledok, je to skor len taka studia uskutocnitelnosti a ide skor o ten princip ako o implementaciu

...vacsinou vsetko robim tak iterativne, cestou najmensieho odporu a najrychlejsieho vysledku a potom ked treba tak to optimalizujem, ale k tomu som sa v tomto pripade nedostal

...netusim kolko pamate prve dva algoritmy potrebuju, pretoze tak daleko aby som pustil profiler som neprisiel, tie nastavenia pamate pre jvm som urobil len tak zbrucha

...samozrejme keby som nepouzil ako nositel dat triedy, v ktorych je meno suboru, ktore vlastne ani nepotrebujem, ale pouzil by som len pole obsahujuce polia int-ov podla navodu v komente vyssie:

http://antaran13.blogspot.com/2009/04/pr0gr4m470r5k4-ul0h4.html?showComment=1239783240000#c1546353362369214875

...tak by sa tie naroky na pamat velmi znizili a aj implementacia by bola asi nepomerne rychlejsia (okrem nacitania dat zo suboru a rozparsovania, to by trvalo dlhsie, ale to som ani nestopoval, pretoze keby bolo cielom testu to ako najrychlejsie rozparsovat ten subor, tak by bol subor navrhnuty asi uplne inak)

...taktiez ak niekto viete ako spristupnit zvyraznovanie syntaxe v komentoch bloggeru, tak napiste ako sa to robi

RE: Uz sa Vam niekomu ozval Eset?

...ja som im napisal len jednoduchu otazku, ze ci mam dobre vysledky a dal som im link na tento blog, ale mi neodpovedali a myslim si, ze sa odpovede ani nedockam, ale vzhladom na to, ze ostatnym to vyslo tak isto, tak si myslim, ze je to dobre

Riesili ste niekto aj tu druhu ulohu?
http://www.3537.sk/virusovy-analytik.html

Snad posledny prispevok pre teraz :) Uz sa Vam ni...

2009-04-20T09:54:00.000+02:00

Snad posledny prispevok pre teraz :)

Uz sa Vam niekomu ozval Eset?

"pretoze set_large.dat nevyzadoval nastavenie velk...

2009-04-20T09:53:00.000+02:00

"pretoze set_large.dat nevyzadoval nastavenie velkosti pamati, tzn zmestil sa do 64MB, nezaoberal som sa takouto alternativou. ani v zadani sa takto poziadavka nevyskytla."

Hmm, a v zadani bolo, ze to ma fungovat pre set_large.dat :) ? Ani nie - to bol len jeden z testovacich suborov... Takyto pristup k problemu nie je velmi rozumny.

Este raz k Stanovy - preco by to malo byt 5-6s? To...

2009-04-20T09:50:00.000+02:00

Este raz k Stanovy - preco by to malo byt 5-6s? To by uz fakt musel byt pomalý disk a cital iba 5-6MB/s.

Stano : k n^2 - nie som si istý ako si na to doši...

2009-04-20T09:47:00.000+02:00

Stano :

k n^2 - nie som si istý ako si na to došiel. Ale v Tvojom popisovanom prípade zaberie hash a je to ( n * log n) x k, pričom k je max dĺžka podpisu. Horšie je to keď sú rovnaké prvé prvky podpisu a nezaberie hash - ale na to je jednoduchá úprava - vytvárať hash pre prvky kde prekročíme určitý treshold. Potom si stále udržím danú rýchlosť.

A inak sortovanie v najhoršom prípade je (n * k).log n. A to preto lebo sortovanie keď porovnanie trvá jeden krok je n.log n, lenže tu musíš porovnávať v najhoršom prípade k prvkov ak sa podpisy zhodujú. Takže ak sú všetky rovnaké tak nastáva problém. Riešením by bolo robiť niečo ako insert sort pričom už rovno rozpoznať prefix a nepridávať do zoznamu. potom sa dostaneš na n * k pri všetkých rovnakých prvkoch.

ahoj stano. toto je postata mojej implementacie: ...

2009-04-17T15:30:00.000+02:00

ahoj stano.

toto je postata mojej implementacie:

private void test() {
long start = System.nanoTime();

Collections.sort(files); // order is defined by FileDescriptor.compareTo()
int n = files.size();
int unique = 0, duplicate = 0;
for (int i=0; i<n; ++i) {
FileDescriptor f = files.get(i);
unique++;
while ((i+1<n) && files.get(i+1).isPrefixOf(f)) {
duplicate++;
i++;
}
}

long stop = System.nanoTime();
System.out.println("unique=" + unique + ", duplicate=" + duplicate + ", in " + (stop-start)/1000000 + " ms");
}

// this is more tricky than it looks:
// 1. use descending lexicographical order
// 2. compare ints using substraction may result in overflow
public int compareTo(FileDescriptor other) {
int n = Math.min(signature.length, other.signature.length);
for (int i=0; i<n; ++i) {
int a = signature[i];
int b = other.signature[i];
if (a<b)
return 1;
if (a>b)
return -1;
}
return other.signature.length - signature.length;
}

ked zbehne sort(), zvysok je linearna zalezitost (vid i++ vo vnutornom cykle).
co sa tyka disku ... parsovanie mi trva >20sec, takze tieto efekty nepozorujem :-D.

s pozdravom, martin

Hladajuci muz: podla mojho zbezneho nahladu ma tv...

2009-04-17T11:48:00.000+02:00

Hladajuci muz:

podla mojho zbezneho nahladu ma tvoje riesenie worst case (kazdy prvok unikatny) zlozitost n^2.

A co sa tyka nacitania, tak ta 1s nie je z disku, ale uz nacachovane z pamate :) z disku je to podstatne pomalsie (5-6s) ale to zaregistrujes len pri prvom nacitani, potom OS uz ten file podrzi v RAM-ke)

Stano

> k prispevku predo mnou - v tych 360ms je aj naci...

2009-04-16T09:47:00.000+02:00

> k prispevku predo mnou - v tych 360ms je aj nacitanie suboru?

nie. 360ms trvali body 2 a 3 (spracovanie nacitanych dat) na subore set_large.dat

> A pri takom sposobe riesenia sa moze stat ze pri este vacsich suboroch nebude stacit pamat

jojo. ak sa data nevmestia do pamate, algoritmy treba vzdy radikalne zmenit :-)
pretoze set_large.dat nevyzadoval nastavenie velkosti pamati, tzn zmestil sa do 64MB, nezaoberal som sa takouto alternativou. ani v zadani sa takto poziadavka nevyskytla.

> zaroven sortovanie rastie n.log n

spravne, zlozitost algoritmu je dana krokom 2. ja povazujem n.log n za dobre. ak ma niekto lepsie, klobuk dolu