Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

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 15.5.2013 11:13
Odpovědět 13.5.2013 9:05
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Luboš Běhounek (Satik):

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

Nahoru Odpovědět 13.5.2013 9:54
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

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

Nahoru Odpovědět 13.5.2013 10:39
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Kit
Redaktor
Avatar
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):

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

Nahoru Odpovědět 13.5.2013 11:28
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

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 13.5.2013 11:34
Nahoru Odpovědět 13.5.2013 11:33
:)
Avatar
Michal Žůrek (misaz):

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

Nahoru Odpovědět 13.5.2013 11:38
Nesnáším {}, proto se jim vyhýbám.
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 13.5.2013 11:45
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

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 Čápka
Tým ITnetwork
Avatar
Odpovídá na Michael Olšavský
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

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 13.5.2013 21:17
 
Nahoru Odpovědět 13.5.2013 21:14
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Michael Olšavský
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

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

 
Nahoru Odpovědět 14.5.2013 14:54
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Michael Olšavský
David Čápka:

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

Nahoru Odpovědět  +1 14.5.2013 16:05
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

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

 
Nahoru Odpovědět 14.5.2013 17:08
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 14.5.2013 17:17
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

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
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Michael Olšavský:

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

Editováno 14.5.2013 18:59
 
Nahoru Odpovědět 14.5.2013 18:59
Avatar
Honza Bittner
Redaktor
Avatar
Odpovídá na Michael Olšavský
Honza Bittner:

asi ne :P

Editováno 14.5.2013 19:53
Nahoru Odpovědět 14.5.2013 19:53
Ptejte se mě na cokoli na https://github.com/HoBi/ama a followujte mě na Twitteru https://twitter.com/tenhobi. :-)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Michael Olšavský:

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 14.5.2013 20:11
 
Nahoru Odpovědět 14.5.2013 20:08
Avatar
Michal Žůrek (misaz):

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
Nesnáším {}, proto se jim vyhýbám.
Avatar
Martin Horáček:

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
Odpovídá na Martin Horáček
Luboš Běhounek (Satik):

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
:)
Avatar
Luboš Běhounek (Satik):

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 14.5.2013 22:16
Nahoru Odpovědět  +2 14.5.2013 22:16
:)
Avatar
Nahoru Odpovědět 15.5.2013 6:19
Nesnáším {}, proto se jim vyhýbám.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

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

Nahoru Odpovědět 15.5.2013 8:35
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

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 Čápka
Tým ITnetwork
Avatar
Odpovídá na Kit
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
 
Nahoru Odpovědět 15.5.2013 9:48
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

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
Redaktor
Avatar
Odpovídá na David Čápka
Sc077y:

A na kterém procesoru se to bude testovat?

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

kam to mam poslat?

 
Nahoru Odpovědět 15.5.2013 11:07
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

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

Nahoru Odpovědět 15.5.2013 11:13
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Sc077y
David Čápka:

Testovat budu na AMD Athlon II X4 - 2.8 GHz.

Nahoru Odpovědět 15.5.2013 11:15
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na kucerm2
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Sc077y
Redaktor
Avatar
Odpovídá na David Čápka
Sc077y:

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
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

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
Odpovídá na Kit
Luboš Běhounek (Satik):

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

Nahoru Odpovědět  +1 15.5.2013 13:57
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 15.5.2013 15:16
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

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

Nahoru Odpovědět  +1 15.5.2013 15:19
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Kit
David Čápka:

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

Nahoru Odpovědět 15.5.2013 15:31
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na Kit
Luboš Běhounek (Satik):

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

Nahoru Odpovědět 15.5.2013 15:49
:)
Avatar
Kit
Redaktor
Avatar
Odpovídá na Luboš Běhounek (Satik)
Kit:

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ů.
Avatar
Odpovídá na Kit
Libor Šimo (libcosenior):

Po tejto úprave je to trošinku rýchlejšie.

#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 & (unsigned int)1;
        }
    }
    printf("\n%8d\n", soucet);
}
Nahoru Odpovědět  +1 15.5.2013 18:00
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior):

Do pekla. Nakoniec to nie je pravda, po viacerých testoch mi vyšlo to tvoje rýchlejšie.

Nahoru Odpovědět 15.5.2013 18:43
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Libor Šimo (libcosenior)
Luboš Běhounek (Satik):

Take jsem to zkousel, vyslo mi oboji stejne rychle, jeste bych se mohl podivat, jestli to kompilator nezkompiluje na stejny kod.

Nahoru Odpovědět 15.5.2013 19:14
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Libor Šimo (libcosenior):

Myslím, že to nebude rovnaké. Testni nasledujúci kód, sú tam obidve možnosti.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POCET 100000000
#define MAX   32000

short spocitat_dva(unsigned int cislo);
void vypis(unsigned int cislo);

int main(void)
{
    unsigned int i, j, pom;
    int *cislo;
    short vysledok = 0;
    double cas1, cas2;
    clock_t t1, t2, t3, t4;

    srand(time(0));
    cislo = (int *) malloc(POCET * sizeof(int));

    for (i = 0; i < 100; i++) {
        pom = rand()%MAX - 10000;
        printf("%3d. %6d: ", i + 1, pom);
        vypis(pom);
        printf(" = %d\n", spocitat_dva(pom));
    }

    for (i = 0; i < POCET; i++) {
        cislo[i] = rand()%MAX - 10000;
    }
    t1 = clock();
    for (i = 0; i < POCET; i++) {
        for (j = cislo[i]; j != 0; j >>= 1) {
            vysledok += j & 1;
        }
    }
    t2 = clock();
    cas1 = (double) (t2 - t1);
    printf("\n\n1. sposob: Scitanie cifier u 10.000.000 cisiel trvalo %.0f ms.\n\n", cas1);

    vysledok = 0;
    t3 = clock();
    for (i = 0; i < POCET; i++) {
        for (j = cislo[i]; j != 0; j >>= 1) {
            vysledok += j % 2;
        }
    }
    t4 = clock();
    cas2 = (double) (t4 - t3);
    printf("\n\n2. sposob: Scitanie cifier u 10.000.000 cisiel trvalo %.0f ms.\n\n", cas2);

    return 0;
}

void vypis(unsigned int cislo)
{
    short i;
    for(i = 0; i < 32; i++, cislo >>= 1)
    //printf("%d", cislo & (unsigned int)1);
    printf("%d", cislo % 2);
}

short spocitat_dva(unsigned int cislo)
{
    short i, sucet = 0;
    for(i = 0; i < 32; i++, cislo >>= 1)
    sucet += cislo % 2;
    return sucet;
}
Editováno 15.5.2013 19:35
Nahoru Odpovědět 15.5.2013 19:35
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Nahoru Odpovědět  +1 15.5.2013 20:04
Nesnáším {}, proto se jim vyhýbám.
Avatar
Libor Šimo (libcosenior):

Je to čisté céčko a neviem čo je release mód. Som absolútny samouk.

Nahoru Odpovědět 15.5.2013 20:25
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Libor Šimo (libcosenior)
Luboš Běhounek (Satik):

Ve vetsine kompilatoru se da nastavit, jestli se ma pouzit debug nebo release mod, v release modu jsou obvykle zapnute optimalizace a jsou tam vypnute ladici informace, takze je to rychlejsi.

Obcas pak muze nastat, ze kdyz treba porovnavas dve verze kodu v debugu, tak ta co byla pomalejsi je v release modu rychlejsi, takze to chce testovat v release modu.

Nahoru Odpovědět 15.5.2013 20:46
:)
Avatar
Libor Šimo (libcosenior):

OK, používam Code:Blocks, dúfam, že to niekde nájdem. :)

Nahoru Odpovědět 15.5.2013 21:37
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Зайчик
Člen
Avatar
Odpovídá na Libor Šimo (libcosenior)
Зайчик:

v code::blocks je to hned vedle build and run ;) "build target" je tam přímo takovej list kde je buď release nebo debug :)

Editováno 15.5.2013 21:39
Nahoru Odpovědět 15.5.2013 21:39
Коммунизм для нашего будущего!
Avatar
Libor Šimo (libcosenior):

Díky, už som to našiel, ale nastaviť to môžem len na projekte, nie na samotnom programe.
Už som to aj otestoval a predsa len je ten Kit-ov spôsob trochu rýchlejší.

Nahoru Odpovědět 15.5.2013 21:50
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Lukáš Hruda (Luckin):

Tak jsem to zkusil v C++ a dostal jsem se zatím na 10 ms u 1 000 000 čísel.

 
Nahoru Odpovědět 16.5.2013 22:09
Avatar
Lukáš Hruda (Luckin):

Mimochodem, mám asi hodně zvláštní algorytmus :D

 
Nahoru Odpovědět 16.5.2013 22:20
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Martin Bednář (xbedm01):

mno, pokud je to vážně algorytmus, tak asi zvláštní bude :D

Nahoru Odpovědět 16.5.2013 22:22
I bez motta se dá žít
Avatar
Lukáš Hruda (Luckin):

Tak jsem se dostal na 40 - 50 ms na 10 000 000 čísel. Víc už nevím jak to zrychlit, možná na to jdu úplně špatně, možná mám moc pomalý procesor :D

 
Nahoru Odpovědět 17.5.2013 16:23
Avatar
matesax
Redaktor
Avatar
matesax:

JSA -> 2ms
C/C++ -> 8ms
D -> 8ms
C# -> 12ms

 
Nahoru Odpovědět 18.5.2013 13:46
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 18.5.2013 13:48
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
matesax
Redaktor
Avatar
Odpovídá na David Čápka
matesax:

Jazyk Symbolických Adres (Takže strojový kód - po zparsování.)

Editováno 18.5.2013 13:49
 
Nahoru Odpovědět 18.5.2013 13:48
Avatar
Odpovídá na matesax
Libor Šimo (libcosenior):

Tak to teda čumím. Vážne som zvedavý na algoritmus v C. o_O

Nahoru Odpovědět 18.5.2013 18:17
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Michael Olšavský:

Ty mé první výsledky byly špatné(36ms, 48ms...). Zjistil jsem, že tam bylo pár chyb a nakonec mi to vycházelo pro 10M okolo 1000ms( dostal jsem se až k 3800ms :D). Ale nyní jsem algoritmus upravil a jsem na 30 ms(s použítím více vláken). :-) Už se těším, až uvidím Matesaxův a Satikův výtvor.

 
Nahoru Odpovědět 18.5.2013 21:09
Avatar
Libor Šimo (libcosenior):

Už niekto odovzdal svoj výtvor? 8|

Nahoru Odpovědět 19.5.2013 15:26
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Libor Šimo (libcosenior)
David Čápka:

Odevzdali jen Satik a Sc077y, brisingr na to zdá se zapomněl a nemůžu se mu dopsat :(

Editováno 19.5.2013 15:28
Nahoru Odpovědět 19.5.2013 15:27
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

U Sc077yho mám naměřeno kolem 200ms, u Satika kolem 4(!) ms. Přemýšlím, jak je to vůbec možné :O :D

  1. je tedy Luboš Běhounek (Satik) a získává placku Machr na C# .NET.
  2. je Sc077y

Oběma chválím práci s vlákny :)

Mrzí mě, že zapomněli odevzdat Matesax a brisingr002 :(

Nahoru Odpovědět 19.5.2013 15:36
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Martin Bartoš:

Gratulujem Satikovi a som ohromený...

Nahoru Odpovědět  +1 19.5.2013 15:43
Nejsom kreatívny...
Avatar
Luboš Běhounek (Satik):

Heh, nemam tam nakou chybu? :D

Nahoru Odpovědět 19.5.2013 15:50
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

To musíš vědět ty, ty jsi machr :D Sc077y to jen obyčejně sčítá, takže je to možné. Generuješ těch čísel 100 milionů, to mi tu vycházelo kolem 40ms.

Nahoru Odpovědět 19.5.2013 15:53
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Já ten kód neviděl, ale přijde mi to nereálné, já to zkoušel v C++ algoritmem kde se v podstatě jen sečtou 2 čísla a u 100 milionů jsem měl cca 450 ms (i když v jednom vlákně), tvůj program to udělal cca za 130 ms. Napadlo mě, jestli třeba pak ten výsledek nikam neukládáš, nebo ten uložený výsledek nikde nepoužiješ, v tomto případě totiž kompilátor běžně ten výpočet v rámci optimalizací úplně přeskočí.

 
Nahoru Odpovědět 19.5.2013 16:01
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 19.5.2013 16:06
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Lukáš Hruda (Luckin)
David Čápka:

V debugu mám naměřeno kolem 50ms, možná to opravdu přeskakuje.

Nahoru Odpovědět 19.5.2013 16:07
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Libor Šimo (libcosenior):

Satik, koľko vlákien si použil?

Nahoru Odpovědět 19.5.2013 16:19
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Nejlépe to poznáš tak, že se podíváš na samotný výpočet a pokud se ta hodnota někam ukládá, tak jí pak mimo měřeny úsek pouze vypíšeš. Je jedno že tam bude uložen pouze součet poslední hodnoty, hned pak poznáš, jestli se ta doba v releasu zvedne nebo ne.

 
Nahoru Odpovědět 19.5.2013 16:41
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Lukáš Hruda (Luckin)
David Čápka:

Je na stovce :D To je fakt zajímavé, že se to takhle optimalizuje.

Nahoru Odpovědět 19.5.2013 16:46
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Jan Vargovský
Redaktor
Avatar
Jan Vargovský:

Hmm, ja to zapoměl odevzdat, celý den jsem měl zato, že je tam deadline 19:00 ...
EDIT: Btw, ja mam v průměru 2,3ms na 107 čísel

Editováno 19.5.2013 16:50
 
Nahoru Odpovědět 19.5.2013 16:49
Avatar
Sc077y
Redaktor
Avatar
Sc077y:

Taky gratuluji vítězi. No hold mi to snad vyjde příště. :D

 
Nahoru Odpovědět 19.5.2013 16:50
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Jan Vargovský
David Čápka:

To je škoda :( Nechceš to pro zajímavost poslat, jaký budeš mít čas?

Nahoru Odpovědět 19.5.2013 16:50
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Libor Šimo (libcosenior)
David Čápka:

Zjistí si počet procesorů a tolik spustí vláken.

Nahoru Odpovědět 19.5.2013 16:51
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Na stovce u kolika čísel? :D Pokud vím tak VM C# je napsán v C++, takže by měl nejspíš provádět i stejné optimalizace. Mimochodem vyzkoušej prosím tohle, rád bych věděl čas na tvém procesoru.
http://leteckaposta.cz/494582630
Je to nastaveno na 100 milionů čísel, generování trvá dlouho, protože jsem chtěl aby to generovalo čísla na plných 32 bitů. Samotný výpočet začne, když se vypíšou tři tečky :)

 
Nahoru Odpovědět 19.5.2013 16:53
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Dělalo to, že jsi jen přiřadil do proměnné a pak ji nepoužil, ta instrukce se přeskakovala :D Máš 100ms. BTW jak jsi to pole vláken pojmenoval pool, měl jsem za to, že pool vláken je trochu něco jiného, že se tam kvůli optimalizaci smíchá několik zablokovaných vláken do jednoho a poté zas rozdělí.

Nahoru Odpovědět 19.5.2013 16:53
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Lukáš Hruda (Luckin)
David Čápka:

Já už jsem z toho úplně zblblý. Na stovce s 100M, takže je na desítce. To je furt sakra málo! :D

Nahoru Odpovědět 19.5.2013 16:54
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Lukáš Hruda (Luckin)
David Čápka:

290 ms, Satik má kolem stovky pro stejný počet čísel :D

Nahoru Odpovědět 19.5.2013 16:58
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Jan Vargovský
David Čápka:

Ten tvůj se mi nějak nedaří zkompilovat :( Přeložený vypíše 5,8 , ale jak psal Luckin, chtělo by to vypsat obsah proměnné result na konci programu.

Nahoru Odpovědět 19.5.2013 16:59
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Michael Olšavský:

Velmi se omlouvám. Neměl jsem šanci dostat se k pc. :-/ Zdrojáky sem hodím i tak dnes večer nebo zítra. Zajímalo by mě, jak dopadnu u tebe. :-)

 
Nahoru Odpovědět 19.5.2013 17:01
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Můžeš zkusit ještě tohle:
http://leteckaposta.cz/150035697
Předtím jsem ty součty zapisoval do pole, teď je tam pouze jedna proměnná pro celkový součet, je to asi o necelou třetinu rychlejší :D
Jinak 100 ms je pořád hodně málo, klobouk dolů, docela by mě zajímal použitý algoritmus :)

 
Nahoru Odpovědět 19.5.2013 17:07
Avatar
Jan Vargovský
Redaktor
Avatar
Jan Vargovský:

zkuste toto : http://leteckaposta.cz/992496810
Btw, ja to zkoušel s vlakny a spíše to bylo pomalejší, než rychlejší když jde relativně o tak málo hodnot.

 
Nahoru Odpovědět 19.5.2013 17:07
Avatar
Michael Olšavský:

Zde je program :-) https://www.dropbox.com/…0Counter.exe
(Generování je hrozně pomalé. To později nějak upravím.) --> počkejte chvíli
A tady zdroják: https://www.dropbox.com/…e/Program.cs

Editováno 19.5.2013 17:15
 
Nahoru Odpovědět 19.5.2013 17:14
Avatar
David Čápka
Tým ITnetwork
Avatar
Nahoru Odpovědět 19.5.2013 17:40
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Zbytek zkusím zítra, dnes již se k tomu nedostanu. brisingrovo vypsalo 75, ale to bude také tou optimalizací.

Nahoru Odpovědět 19.5.2013 17:43
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

To není zlé, kdybych to rozdělil dvou vláken, tak bych se k těm 100 ms asi také dost přiblížil :) Ale je to v C++, což mi dává jistou výhodu :D

 
Nahoru Odpovědět 19.5.2013 17:49
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

Jj, ja uz pak nestihal a musel jsem jet pryc, tak jsem to nestihl zkontrolovat, upravil jsem to a nahral jsem opravenou verzi, ta scita vsechny nastavene bity a nakonec je vypise, takze se optimalizace neprovede.

https://www.dropbox.com/…g/li_PK_YeRX

Nahoru Odpovědět 19.5.2013 18:24
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Lukáš Hruda (Luckin):

Můžeš sem hodit odkaz kde jsi našel algoritmus, který jsi použil? :)

 
Nahoru Odpovědět 19.5.2013 18:52
Avatar
Odpovídá na Lukáš Hruda (Luckin)
Luboš Běhounek (Satik):

Nejaky takovyhle odkaz to byl (ten alg. je stejny):
http://stackoverflow.com/…-big-integer

Prvni odkaz na
"C# fast bit count"

Nahoru Odpovědět 19.5.2013 19:04
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Teda Saťasi, tobě to lítá :D Teď jsi kolem 25ms :)

Nahoru Odpovědět 19.5.2013 20:02
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Michael Olšavský
David Čápka:

Na konci metody Do je potřeba dát Console.Write­Line(vysledek), jinak se provede ta optimalizace a nesčítá to, proto to máš tak rychlé :P

Nahoru Odpovědět 19.5.2013 20:04
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Lukáš Hruda (Luckin):

Pokud je to 25 ms pro 10M čísel, tak už bych teoreticky měl mít o něco méně nebo cca stejně :D

 
Nahoru Odpovědět 19.5.2013 20:10
Avatar
Libor Šimo (libcosenior):

Teda páni, som rád, že to riešite. Ale stále je tu ešte výzva.
matesax napísal:
JSA -> 2ms
C/C++ -> 8ms
D -> 8ms
C# -> 12ms
a to je najlepší čas.
Len neviem, či nás dokáže presvedčiť...

Nahoru Odpovědět 19.5.2013 20:15
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Nahoru Odpovědět 19.5.2013 20:20
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Libor Šimo (libcosenior)
Lukáš Hruda (Luckin):

Ne, asm moc neumím. Ale používám pointer na rozdělení čísla na horní a spodní 2 byty, takže nevím, jestli by můj algoritmus šel použít v C#, ale teoreticky by měl, protože v C# jdou pointery použít také.

Editováno 19.5.2013 20:27
 
Nahoru Odpovědět 19.5.2013 20:27
Avatar
Odpovídá na Libor Šimo (libcosenior)
Luboš Běhounek (Satik):

Predpokladam, ze je to jen ten muj kod preklopeny do tech jazyku a tedy nejspis s tou optimalizaci, ktera to uplne preskoci, jinak jsou ty casy nerealne :)

Nahoru Odpovědět 19.5.2013 20:28
:)
Avatar
Odpovídá na Libor Šimo (libcosenior)
Luboš Běhounek (Satik):

asm ma instrukci popcnt, ktera cely vypocet dela touhle jednou instrukci :)

Nahoru Odpovědět 19.5.2013 20:30
:)
Avatar
Odpovídá na Luboš Běhounek (Satik)
Libor Šimo (libcosenior):

Niekoho napadlo využiť naplno zásobník. Čo vy na to?

Nahoru Odpovědět 19.5.2013 20:37
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Libor Šimo (libcosenior)
Luboš Běhounek (Satik):

Myslis kolekci Stack<T> nebo pouzit zasobnik misto haldy?

Nahoru Odpovědět 19.5.2013 20:42
:)
Avatar
Libor Šimo (libcosenior):

Nie je to z mojej hlavy, ale zásobník miesto haldy je tá správna cesta.

Nahoru Odpovědět 19.5.2013 20:46
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Libor Šimo (libcosenior)
Luboš Běhounek (Satik):

No, myslim, ze to nijak nezrychli, protoze se tam jen cte z jednoho velkeho bloku pameti.

Nahoru Odpovědět 19.5.2013 20:53
:)
Avatar
Odpovídá na Libor Šimo (libcosenior)
Lukáš Hruda (Luckin):

Tím se zrychlí pouze alokace a dealokace paměti, ale to na rychlost výpočtu nemá vliv.

 
Nahoru Odpovědět  +1 19.5.2013 20:56
Avatar
Odpovídá na Luboš Běhounek (Satik)
Libor Šimo (libcosenior):

asi ide o to, že stack číta po jednom.
Pre mňa je to (mimo moje chápanie) niečo divné.

Nahoru Odpovědět 19.5.2013 20:59
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior):

STOP
Poprosím počkať na správnu osobu.

Nahoru Odpovědět 19.5.2013 21:01
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior):

Mňa len baví vaše súťaženie. :)

Nahoru Odpovědět 19.5.2013 21:02
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior):

Správna osoba je

Nahoru Odpovědět 19.5.2013 21:07
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Luboš Běhounek (Satik):

Luckin to napsal dobre :)

Nahoru Odpovědět 19.5.2013 21:19
:)
Avatar
Libor Šimo (libcosenior):

Určite. Je si len myslím, že príde nejaký tester a ukáže iný spôsob.

Editováno 19.5.2013 21:29
Nahoru Odpovědět 19.5.2013 21:29
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Libor Šimo (libcosenior):

Je to možné.

Nahoru Odpovědět 19.5.2013 21:37
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
Odpovídá na Libor Šimo (libcosenior)
Lukáš Hruda (Luckin):

Jiný způsob čeho? :)
Stack není nic jiného než jakási předalokovaná paměť, která se dealokuje s koncem programu. Všimni si, že když spustíš program napsaný v C/C++, tak i když vůbec nic nedělá, zabírá něco přes 1MB paměti. 1MB je tuším velikost stacku u těchhle jazyků. Když pak deklaruješ proměnnou, program použije tuhle již alokovanou paměť a pouze posune stack pointer. Kdežto když alokuješ paměť na haldě (pomocí malloc nebo new), program musí najít volnou paměť a alokovat jí, přistupuje k ní pak ale úplně stejně jako ke stacku. Můžeš si napsat i svuj vlastní stack, v C++ to pomocí šablon není žádný problém.

 
Nahoru Odpovědět  +1 19.5.2013 21:46
Avatar
Šimon Raichl
Redaktor
Avatar
Odpovídá na Michal Žůrek (misaz)
Šimon Raichl:

Myslíš, že v C# je

#include <stdio.h>

?

 
Nahoru Odpovědět 13.8.2014 20:44
Avatar
Nahoru Odpovědět  ±0 13.8.2014 20:45
Nesnáším {}, proto se jim vyhýbám.
Avatar
Šimon Raichl
Redaktor
Avatar
Odpovídá na Michal Žůrek (misaz)
Šimon Raichl:

Pokud jo, tak to nebylo jednoznačný, teď už jo.

 
Nahoru Odpovědět  -2 13.8.2014 20:48
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 129 zpráv z 129.