Diskuze: Machr na C# .NET - Binární sčítačka

David Hartinger

Vlastník

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

Luboš Běhounek Satik

Tvůrce

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/

David Hartinger

Vlastník

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

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:13.5.2013 10:51

Podporuje tvůj procesor SSE4?

Nahoru Odpovědět

13.5.2013 10:51

https://www.facebook.com/peasantsandcastles/

Kit

Tvůrce

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

Luboš Běhounek Satik

Tvůrce

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/

David Hartinger

Vlastník

David Hartinger:13.5.2013 11:29

Co je SSE4 nevím 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

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:13.5.2013 11:33

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

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/

Michal Žůrek - misaz

Tvůrce

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

David Hartinger

Vlastník

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

David Hartinger

Vlastník

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

Michael Olšavský

Tvůrce

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

David Hartinger

Vlastník

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

Michael Olšavský

Tvůrce

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

David Hartinger

Vlastník

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

Michael Olšavský

Tvůrce

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

David Hartinger

Vlastník

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

Michael Olšavský

Tvůrce

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

David Hartinger

Vlastník

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

Luboš Běhounek Satik

Tvůrce

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/

Michael Olšavský

Tvůrce

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

Honza Bittner

Tvůrce

Honza Bittner:14.5.2013 19:53

asi ne

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.

Luboš Běhounek Satik

Tvůrce

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/

Michael Olšavský

Tvůrce

Michael Olšavský:14.5.2013 20:02

Já se dostal na 42ms! :-)

Nahoru Odpovědět

14.5.2013 20:02

Luboš Běhounek Satik

Tvůrce

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/

Michael Olšavský

Tvůrce

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

Michal Žůrek - misaz

Tvůrce

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

Luboš Běhounek Satik

Tvůrce

Luboš Běhounek Satik:14.5.2013 21:42

Ja jsem na 39ms ted

Nahoru Odpovědět

14.5.2013 21:42

https://www.facebook.com/peasantsandcastles/

Martin Horáček

Člen

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

Luboš Běhounek Satik

Tvůrce

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/

Luboš Běhounek Satik

Tvůrce

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/

Michal Žůrek - misaz

Tvůrce

Michal Žůrek - misaz:15.5.2013 6:19

VS si taky zere výkon

Nahoru Odpovědět

15.5.2013 6:19

David Hartinger

Vlastník

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

Kit

Tvůrce

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

David Hartinger

Vlastník

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

Michael Olšavský

Tvůrce

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

Kit

Tvůrce

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

Sc077y

Tvůrce

Sc077y:15.5.2013 10:03

A na kterém procesoru se to bude testovat?

Nahoru Odpovědět

15.5.2013 10:03

kucerm2

Člen

kucerm2:15.5.2013 11:07

kam to mam poslat?

Nahoru Odpovědět

15.5.2013 11:07

David Hartinger

Vlastník

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

David Hartinger

Vlastník

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

David Hartinger

Vlastník

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

Sc077y

Tvůrce

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

Kit

Tvůrce

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

Luboš Běhounek Satik

Tvůrce

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/

David Hartinger

Vlastník

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

Kit

Tvůrce

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

David Hartinger

Vlastník

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

Luboš Běhounek Satik

Tvůrce

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/

Kit

Tvůrce

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

Nejčastěji vyhledáváné

Diskuze: Machr na C# .NET - Binární sčítačka