Nové výhodné předplatné namísto kreditů je tu! Více informací. Upravili jsme také naše provozní podmínky.
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:
Nejnovější komentáře jsou na konci poslední stránky.
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger:13.5.2013 9:05

Vítám vás u dalšího kola programátorské minisoutěže Machr. Vytvořte program, který vygeneruje náhodné (pseudonáhodné) binární číslo na 32 cifer a sečte jeho cifry. Pro testovací účely vypište 100 čísel a následně jejich ciferné součty.
Druhá část programu vygeneruje 10.000.000 takových čísel a spočítá jejich ciferné součty. Program následně vypíše, jak dlouho trvalo sčítání cifer, generování se nepočítá. Čísla být vypsána nemusí.

Výstup programu tedy bude vypadat nějak takto:

10110111101101111011011110110111 = 24
00010011000100110001001100010011 = 12
(dalších 98 čísel)

Sčítání cifer u 10.000.000 čísel trvalo x ms.

Program se pokuste udělat co nejrychlejší. Hraje se tu na rychlost, takže dost pravděpodobně budete používat konstrukce, co by se v normálních programech objevit neměly. Zadání je omezeno na C# .NET, framework verze 3.5, běžet smí na více vláknech. Programy následně spustíme na stejném stroji a autor nejrychlejšího algoritmu získává placku March na C# .NET (případně March na algoritmy) a samolepky.

Několik hintů na konec:

  • Cykly mohou být pomalé, zkuste je nahradit něčím jiným
  • Výpis do konzole je poměrně časově náročná operace, počítejte s tím, že když si budete během generování něco vypisovat, bude to pomalé
  • K měření času existuje třída Stopwatch ve jmenném prostotu System.Diagnostics, bude se vám hodit

Deadline si dejme v neděli 19.5. v 15:00

Soutěž je zas něco nového a asi něco jiného, než na co jste doposud zvyklí, tak uvidíme, jak se s tím poperete :)

Editováno
Odpovědět
13.5.2013 9:05
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:13.5.2013 9:54

U 8bitu se moc optimalizaci vymyslet neda, nechces to rozsirit na cela unsigned cisla?

Nahoru Odpovědět
13.5.2013 9:54
https://www.facebook.com/peasantsandcastles/
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:13.5.2013 10:39

Dobře, změna zadání, číslo má 32 číslic.

Nahoru Odpovědět
13.5.2013 10:39
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na David Hartinger
Luboš Běhounek Satik:13.5.2013 10:51

Podporuje tvůj procesor SSE4? :D

Nahoru Odpovědět
13.5.2013 10:51
https://www.facebook.com/peasantsandcastles/
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Kit:13.5.2013 11:07

Můj ne.

Nahoru Odpovědět
13.5.2013 11:07
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:13.5.2013 11:28

A jak to je teda s tim jazykem, C# je doporuceny nebo povinny jazyk? :)

Nahoru Odpovědět
13.5.2013 11:28
https://www.facebook.com/peasantsandcastles/
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:13.5.2013 11:29

Co je SSE4 nevím :D C# je povinný, jinak by ta soutěž moc neměla smysl, vyhrál by to program v ASM :)

Nahoru Odpovědět
13.5.2013 11:29
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na David Hartinger
Luboš Běhounek Satik:13.5.2013 11:33

SSE4 je instrukcni sada, umi to novejsi procesory, tam se da tohle resit jednou instrukci :D

Ok, prave s asm by to bylo nefer - viz ta jedna instrukce :)

Editováno
Nahoru Odpovědět
13.5.2013 11:33
https://www.facebook.com/peasantsandcastles/
Avatar
Michal Žůrek - misaz
Tvůrce
Avatar
Michal Žůrek - misaz:13.5.2013 11:38

Můžu se zúčastnit tento týden obou?

 
Nahoru Odpovědět
13.5.2013 11:38
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Michal Žůrek - misaz
David Hartinger:13.5.2013 11:45

Když to zvládneš, tak klidně :)

Nahoru Odpovědět
13.5.2013 11:45
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger:13.5.2013 11:50

Tak na radu Satika ještě jedna změna, generování se nepočítá do měřeného času, jde tedy jen o algoritmus součtu cifer tak, aby to bylo co nejrychleji.

Nahoru Odpovědět
13.5.2013 11:50
New kid back on the block with a R.I.P
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
Michael Olšavský:13.5.2013 20:28

Mám výsledky ukládat nebo stačí jedna promněná, kterou vždy vypíši a pak vynuluji?

 
Nahoru Odpovědět
13.5.2013 20:28
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Michael Olšavský
David Hartinger:13.5.2013 20:50

Nemusíš ji ani vypisovat, ale musí se provést přiřazení výsledku do proměnné. Pak se může zapomenout.

Nahoru Odpovědět
13.5.2013 20:50
New kid back on the block with a R.I.P
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
Michael Olšavský:13.5.2013 21:14

Nemáte někdo nějaký orientační výsledek? A v čem to mám měřit? Asi v uplynulých ticích. V milisekundách je to hodně málo. Možná by to chtělo zvětšit počet čísel :-)

Editováno
 
Nahoru Odpovědět
13.5.2013 21:14
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Michael Olšavský
David Hartinger:14.5.2013 8:29

Ono tam bylo předtím i to generování, tak jsem dal jen 100.000. Pro jaký počet by to dávalo lepší výsledek?

Nahoru Odpovědět
14.5.2013 8:29
New kid back on the block with a R.I.P
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
Michael Olšavský:14.5.2013 14:54

U milionu mam kolem 7 milisekund, tak treba 10m?

 
Nahoru Odpovědět
14.5.2013 14:54
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Michael Olšavský
David Hartinger:14.5.2013 16:05

Dobře, dám to na 10 milionů :)

Nahoru Odpovědět
14.5.2013 16:05
New kid back on the block with a R.I.P
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na David Hartinger
Michael Olšavský:14.5.2013 17:08

Dalši dotaz. Release nebo Debug mód?

 
Nahoru Odpovědět
14.5.2013 17:08
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Michael Olšavský
David Hartinger:14.5.2013 17:17

To je dobrá otázka :) Co myslíš Luboš Běhounek Satik?

Nahoru Odpovědět
14.5.2013 17:17
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na David Hartinger
Luboš Běhounek Satik:14.5.2013 18:57

Dal bych release :)

I kdyz ono v C# mezi nimi neni takovy rozdil jako treba v C++ a vetsinou jsou ty casy (skoro) stejne.

Nahoru Odpovědět
14.5.2013 18:57
https://www.facebook.com/peasantsandcastles/
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Michael Olšavský:14.5.2013 18:59

Má už někdo nějaký výsledek(čas)?

Editováno
 
Nahoru Odpovědět
14.5.2013 18:59
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na Michael Olšavský
Honza Bittner:14.5.2013 19:53

asi ne :P

Editováno
Nahoru Odpovědět
14.5.2013 19:53
FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Michael Olšavský
Luboš Běhounek Satik:14.5.2013 19:59

zatim asi 300ms pro 10M zaznamu

Nahoru Odpovědět
14.5.2013 19:59
https://www.facebook.com/peasantsandcastles/
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Michael Olšavský:14.5.2013 20:02

Já se dostal na 42ms! :-)

 
Nahoru Odpovědět
14.5.2013 20:02
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Michael Olšavský
Luboš Běhounek Satik:14.5.2013 20:07

Co mas za procesor? :)

Nahoru Odpovědět
14.5.2013 20:07
https://www.facebook.com/peasantsandcastles/
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Michael Olšavský:14.5.2013 20:08

Sakra :DDD To mozna bude tim. Intel Core i5 3210m

EDIT: Ale koukám, že ty taky nemáš nic starého. Podle benchmarků je to docela vyrovnané. Jednou vítězí i5, jindy 2 Quad

Editováno
 
Nahoru Odpovědět
14.5.2013 20:08
Avatar
Michal Žůrek - misaz
Tvůrce
Avatar
Michal Žůrek - misaz:14.5.2013 20:14

no tohot se asi nakonec nezúčastním

1.) sloník v PHP
2.) škola - mám za du udělat obrázky do animáku.

 
Nahoru Odpovědět
14.5.2013 20:14
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Michael Olšavský
Luboš Běhounek Satik:14.5.2013 21:42

Ja jsem na 39ms ted :D

Nahoru Odpovědět
14.5.2013 21:42
https://www.facebook.com/peasantsandcastles/
Avatar
Martin Horáček
Člen
Avatar
Martin Horáček:14.5.2013 21:44

Já nevim, asi neumím vytvořit účinný algoritmus. Mně to 1M dělá 529ms.

 
Nahoru Odpovědět
14.5.2013 21:44
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Martin Horáček
Luboš Běhounek Satik:14.5.2013 21:51

Posli kod, podivame se :)

Ono existuje par triku, jak tohle resit jinak, nez dlouhym cyklem.

A take muzes vyuzit vice jader procesoru :)

Nahoru Odpovědět
14.5.2013 21:51
https://www.facebook.com/peasantsandcastles/
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Luboš Běhounek Satik:14.5.2013 22:16

Hm, kdyz pustim ten exac mimo visual studio, tak to ma 10M cisel za 10 ms, zatimco ve VS 40 ms :/
(oboji v releasu)

Editováno
Nahoru Odpovědět
14.5.2013 22:16
https://www.facebook.com/peasantsandcastles/
Avatar
Michal Žůrek - misaz
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Michal Žůrek - misaz:15.5.2013 6:19

VS si taky zere výkon :)

 
Nahoru Odpovědět
15.5.2013 6:19
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:15.5.2013 8:35

Nemůže, musí to jet na 1 jádru :)

Nahoru Odpovědět
15.5.2013 8:35
New kid back on the block with a R.I.P
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:15.5.2013 9:37

Aha, takže jsi diskvalifikoval ty 100jádrové Atomy, které ještě neexistují :)

Nahoru Odpovědět
15.5.2013 9:37
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Kit
David Hartinger:15.5.2013 9:46

No je pravda, že když to budeme testovat na 1 stroji, není vlastně důvod aby to nejelo na více jádrech.

Nahoru Odpovědět
15.5.2013 9:46
New kid back on the block with a R.I.P
Avatar
Michael Olšavský
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Michael Olšavský:15.5.2013 9:48

Na Pentiu E6300 sem se dostal na 32ms :-)

 
Nahoru Odpovědět
15.5.2013 9:48
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:15.5.2013 9:49

Ono to sice pojede na vícejádrovém procesoru, ale jen v jednom jádře. Takže Atom má se svým slabším výkonem v takových testech smůlu.

Nahoru Odpovědět
15.5.2013 9:49
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Sc077y
Tvůrce
Avatar
Odpovídá na David Hartinger
Sc077y:15.5.2013 10:03

A na kterém procesoru se to bude testovat?

 
Nahoru Odpovědět
15.5.2013 10:03
Avatar
kucerm2
Člen
Avatar
kucerm2:15.5.2013 11:07

kam to mam poslat?

 
Nahoru Odpovědět
15.5.2013 11:07
Avatar
David Hartinger
Vlastník
Avatar
David Hartinger:15.5.2013 11:13

Změna zadání, povolil jsem vícevláknovou aplikaci :)

Nahoru Odpovědět
15.5.2013 11:13
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Sc077y
David Hartinger:15.5.2013 11:15

Testovat budu na AMD Athlon II X4 - 2.8 GHz.

Nahoru Odpovědět
15.5.2013 11:15
New kid back on the block with a R.I.P
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na kucerm2
David Hartinger:15.5.2013 11:16

Poslat buď mě do soukromých zpráv nebo v neděli před třetí sem do vlákna.

Nahoru Odpovědět
15.5.2013 11:16
New kid back on the block with a R.I.P
Avatar
Sc077y
Tvůrce
Avatar
Odpovídá na David Hartinger
Sc077y:15.5.2013 11:17

Dík moc za odpověď. Teď si alespoň budu moct odhadnout finální čas.

 
Nahoru Odpovědět
15.5.2013 11:17
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:15.5.2013 12:22

Na tak krátkých časech to v některých případech může znamenat i časovou ztrátu. Hodně záleží na tom, jak se to do těch vláken rozdělí. Někdy je skutečně výhodnější to nechat v jednom :)

Nahoru Odpovědět
15.5.2013 12:22
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Kit
Luboš Běhounek Satik:15.5.2013 13:57

vsak nemusis mit vlakna pro kazde cislo, ale treba jen pro pulku vygenerovanych cisel :)

Nahoru Odpovědět
15.5.2013 13:57
https://www.facebook.com/peasantsandcastles/
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Luboš Běhounek Satik
David Hartinger:15.5.2013 15:16

No jsem zvědavý jak to vyjde :)

Nahoru Odpovědět
15.5.2013 15:16
New kid back on the block with a R.I.P
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:15.5.2013 15:19

Zajímavé, zkusil jsem si to v C i v Javě. C bylo jen o 16 % rychlejší.

Nahoru Odpovědět
15.5.2013 15:19
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Kit
David Hartinger:15.5.2013 15:31

To je zajímavé. Mohl bych z výsledků poté udělat článek.

Nahoru Odpovědět
15.5.2013 15:31
New kid back on the block with a R.I.P
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Kit
Luboš Běhounek Satik:15.5.2013 15:49

posli na ukazku kod, je mozne, ze by se to dalo v c nejak optimalizovat

Nahoru Odpovědět
15.5.2013 15:49
https://www.facebook.com/peasantsandcastles/
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Luboš Běhounek Satik
Kit:15.5.2013 16:28

Není to přesně podle zadání (soutěže se neúčastním) a ani to není nijak optimalizováno:

#include <stdio.h>

void main() {
    int i, j;
    int soucet = 0;
    for (i = 0; i < 10000000; i++) {
        for (j = i; j != 0; j >>= 1) {
            soucet += j%2 ;
        }
    }
    printf("%8d\n", soucet);
}
Nahoru Odpovědět
15.5.2013 16:28
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Nejnovější komentáře jsou na konci poslední stránky.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 50 zpráv z 129.