abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×

dnes 11:33 | IT novinky

Red Hat kupuje společnost Codenvy stojící za stejnojmenným webovým (cloudovým) integrovaným vývojovým prostředím (WIDE) postaveném na Eclipse Che.

Ladislav Hagara | Komentářů: 0
dnes 08:55 | Nová verze

V listopadu 2014 byl představen fork Debianu bez systemd pojmenovaný Devuan. Po dva a půl roce jeho vývojáři oznámili vydání první stabilní verze 1.0. Jedná se o verzi s dlouhodobou podporou (LTS) a její kódové jméno je Jessie, podle planetky s katalogovým číslem 10 464.

Ladislav Hagara | Komentářů: 4
včera 20:22 | Zajímavý článek

Nadace Raspberry Pi vydala již osmapadesáté číslo (pdf) stostránkového anglicky psaného časopisu MagPi věnovanému Raspberry Pi a projektům postaveným na tomto jednodeskovém počítači a druhé číslo (pdf) časopisu Hello World primárně určeného pro učitele informatiky a výpočetní techniky.

Ladislav Hagara | Komentářů: 0
včera 19:55 | Humor

Portál Stack Overflow informuje na svém blogu, že pomohl ukončit editor Vim už více než milionu vývojářů. V loňském roce například hledal odpověď na otázku Jak ukončit editor Vim v průměru 1 z 20 000 návštěvníků.

Ladislav Hagara | Komentářů: 7
včera 19:22 | Nová verze

Po pěti měsících od vydání verze 3.5.0 byla vydána nová stabilní verze 3.6.0, tj. první z nové řady 3.6, minimalistické linuxové distribuce zaměřené na bezpečnost Alpine Linux (Wikipedie). Z novinek lze zmínit například podporu dvou nových 64bitových platforem little-endian POWER machines (ppc64le) a IBM z Systems (s390x) nebo nové balíčky Rust 1.17.0, Cargo 0.18.0, GHC 8.0.2 a Julia 0.5.2.

Ladislav Hagara | Komentářů: 0
24.5. 21:33 | Bezpečnostní upozornění

V Sambě byla nalezena a opravena bezpečnostní chyba CVE-2017-7494. Má-li útočník právo ukládat soubory na vzdálený server, může tam uložit připravenou sdílenou knihovnu a přinutit smbd server k jejímu načtení a tím pádem ke spuštění libovolných příkazů. Chyba je opravena v upstream verzích 4.6.4, 4.5.10 a 4.4.14. Chyba se týká všech verzí Samby od verze 3.5.0 vydané 1. března 2010.

Ladislav Hagara | Komentářů: 4
24.5. 20:44 | Nová verze

Byla vydána nová stabilní verze 4.3.0 integrovaného vývojového prostředí (IDE) Qt Creator. Z novinek lze zmínit například integraci editoru kódu do Qt Quick Designeru.

Ladislav Hagara | Komentářů: 1
24.5. 20:11 | Bezpečnostní upozornění

Společnost Check Point informuje na svém blogu o novém vektoru útoku. Pomocí titulků lze útočit na multimediální přehrávače VLC, Kodi, Popcorn Time, Stremio a pravděpodobně i další. Otevření útočníkem připraveného souboru s titulky v neaktualizovaném multimediálním přehrávači může vést ke spuštění libovolných příkazů pod právy uživatele. Ukázka na YouTube. Chyba je opravena v Kodi 17.2 nebo ve VLC 2.2.6.

Ladislav Hagara | Komentářů: 11
23.5. 15:18 | Zajímavý software

CrossOver, komerční produkt založený na Wine, je dnes (23. 5. 2017) dostupný ve slevě. Roční předplatné linuxové verze vyjde s kódem TWENTYONE na $21, resp. $1 v případě IP z chudších zemí. Firma CodeWeavers, která CrossOver vyvíjí, významně přispívá do Wine. Přidaná hodnota CrossOver spočívá v přívětivějším uživatelském rozhraní, integraci do desktopu a podpoře.

Fluttershy, yay! | Komentářů: 26
23.5. 15:11 | Zajímavý projekt

V únoru loňského roku bylo představeno několik útoků na celou řadu bezdrátových klávesnic a myší s názvem MouseJack. Po více než roce lze chybu opravit, tj. aktualizovat firmware, také z Linuxu. Richardu Hughesovi se podařilo navázat spolupráci se společností Logitech, získat od nich dokumentaci, přesvědčit je, aby firmware poskytovali přímo a ne jako součást .exe souboru, aby mohl být popis začleněn do služby Linux Vendor Firmware Service (LVFS) a aktualizace tak mohla proběhnou přímo z Linuxu pomocí projektu fwupd.

Ladislav Hagara | Komentářů: 2
Chystáte se pořídit CPU AMD Ryzen?
 (6%)
 (32%)
 (1%)
 (8%)
 (44%)
 (9%)
Celkem 616 hlasů
 Komentářů: 62, poslední 19.5. 01:57
    Rozcestník

    Dotaz: Problem s algoritmem

    30.9.2012 13:20 Cze.Honza | skóre: 12
    Problem s algoritmem
    Přečteno: 554×
    Příloha:
    Zdravim, mam za ukol vyresit tento problem, ale pod podminkou, ze doba behu po nahrani na server nesmi byt delsi nez 0.3 s. V priloze je program, ktery jsem napsal, bohuzel doba behu se pohybuje kolem 1 s. Byl bych rad za kazdou radu, jak program urychlit, resp. jaky jiny algoritmus na tento problem pouzit:)

    Řešení dotazu:


    Odpovědi

    30.9.2012 13:47 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem

    Vzhledem k tomu, že čísla dostáváte od nejvyšších řádů, tak to o moc lépe nepůjde. V každém případě se odnaučte alokovat velká pole na zásobníku, na rychlost to sice vliv nemá, ale je to zlozvyk, který se vám může vymstít. Dále je zbytečné udržovat si dvě pole na operandy. Místo toho bych si do jednoho pole ukládal jen součty číslic (prozatím bez ohledu na přenos) a pak je na konci zpracoval. Možná by určité urychlení přineslo i to, když si do prvku pole místo jednoho řádu uložíte rovnou víc (při 32-bitovém int zvládnete osm řádů včetně případného přenosu, s 64-bitovým long i dvojnásobek).

    Stejně mám ale temné podezření, že nejvíc času ten program stráví konverzí vstupu a výstupu.

    Mimochodem, jak jste z "Time limit: 3.000 seconds" přišel na to, že má program skončit do 0.3 sekundy?

    30.9.2012 14:00 Cze.Honza | skóre: 12
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Diky za rady:)

    Jedna se o ukol do skoly a tech 0.3 sekundy je zadani od vyucujiciho. Vzhledem ke statistikam k tomu problemu to jde zvladnout jeste rychleji (nejlepsi cas: 0.024 s).
    Řešení 1× (Cze.Honza (tazatel))
    30.9.2012 15:43 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem

    Samotné časy moc velkou vypovídací hodnotu nemají. Čas běhu pro konkrétní data bude hodně záviset na verzi a parametrech překladače a systému, na kterém se to měří.

    Ještě jeden tip: pokud se můžete spolehnout, že vstup vypadá přesně tak, jak má, můžete místo scanf() načítat jednotlivé znaky pomocí getchar() a na číselnou hodnotu převádět odečtením '0'. Podobně půjde zrychlit i výpis na konci.

    30.9.2012 20:03 Cze.Honza | skóre: 12
    Rozbalit Rozbalit vše Re: Problem s algoritmem

    Samotné časy moc velkou vypovídací hodnotu nemají. Čas běhu pro konkrétní data bude hodně záviset na verzi a parametrech překladače a systému, na kterém se to měří.

    Cas se meri prave na tom serveru, vse se praklada stejnym prekladacem a vsichni maji stejna vstupni data.

    Ještě jeden tip: pokud se můžete spolehnout, že vstup vypadá přesně tak, jak má, můžete místo scanf() načítat jednotlivé znaky pomocí getchar() a na číselnou hodnotu převádět odečtením '0'. Podobně půjde zrychlit i výpis na konci.

    Diky to je ono, pouzil jsem getchar() a putchar() a cas se zkratil z 1 sekundy na 0.2 sekundy. Ani jsem netusil, ze scanf() a printf() spotrebuji tolik casu:)
    30.9.2012 20:19 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Když si rozmyslíte, co všechno taková funkce scanf() musí kvůli své obecnosti udělat, tak to moc překvapivé není.
    wamba avatar 30.9.2012 17:44 wamba | skóre: 37 | blog: wamba
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    jedním for-em ty čísla načítáš do pole a druhým sčítáš prvky toho pole proč to nedat do jednoho for-u a těm polím se nejlépe úplně vyhnout použít něco jako result= result+(integera+integer b)*(10**j)
    This would have been so hard to fix when you don't know that there is in fact an easy fix.
    30.9.2012 18:10 Kit
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    K čemu je tam to umocňování? Může přece použít Hornerovo schéma.
    30.9.2012 18:21 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Pochybuji, že najde architekturu, kde by byl k dispozici dostatečně dlouhý celočíselný typ. :-)
    Jendа avatar 30.9.2012 20:16 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    To bude zase nějaká 4000000bitová šmejďárna.
    30.9.2012 20:09 Cze.Honza | skóre: 12
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    jedním for-em ty čísla načítáš do pole a druhým sčítáš prvky toho pole proč to nedat do jednoho for-u ...
    To prave nevim jak udelat, kdyz to musim zacit vyhodnocovat od nejnizsiho radu, a ty cisla dostavam od nejvyssiho.
    ... polím se nejlépe úplně vyhnout použít něco jako result= result+(integera+integer b)*(10**j)
    V zadani je ze ta cisla muzou byt dlouha az 1 000 000 radu.
    wamba avatar 30.9.2012 22:52 wamba | skóre: 37 | blog: wamba
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    ok, všechny připomínky beru, (soustředil jsem se moc na ten program a ne na zadání)

    nicméně Kit-em zmíněné Hornerovo schéma by se, podle mě, dalo dobře, po mírné úpravě, pro toto zadání využít
    This would have been so hard to fix when you don't know that there is in fact an easy fix.
    30.9.2012 23:35 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem

    Tady právě moc ne, protože přímá aplikace klasického postupu by ve výsledku vedla na kvadratickou časovou složitost. Pokud chcete lineární, nezbyde vám než všechno uložit. Přičemž, jak už bylo zmíněno, stačí ukládat rovnou součty číslic a projet pak jednou celé pole. Tj. asi nějak takhle (bez kontroly chyb a předčasného EOF):

      uint8_t* s = (uint8_t*) malloc((N+1) * sizeof(uint8_t));
    
      for (i=1; i<=N; i++) {
        int c;
        uint8_t digit = 0;
    
        while ((c = getchar()) != '\n')
          if (c >= '0' && c <= '9')
            digit += (c - '0');
        s[i] = digit;
      }
    
      unsigned cy = 0;
      for (i=N; i>0; i--) {
        s[i] += cy;
        if (s[i] > 9) {
          s[i] -= 10;
          cy = 1;
        } else {
          cy = 0;
        }
      }
      s[0] = cy;
    
    rADOn avatar 1.10.2012 16:03 rADOn | skóre: 44 | blog: bloK | Praha
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    V tom pripade ani nemusi ukladat cele pole ale jen cast od posledni nuly, kdyz narazi na dalsi nulu tak to proscitat a flushnout ven az po tu nulu. Rinse, repeat…
    "2^24 comments ought to be enough for anyone" -- CmdrTaco
    1.10.2012 01:49 MadCatX
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Čistě pro zajímavost přikládám alternativní řešení, které funguje jen pro hexadecimální vstup. Sčítá vždy celé bloky o velikosti unsigned int a proto by pro doopravdy velká čísla byl i s konverzí DEC->HEX a zpět nejspíš rychlejší. Na big endianových strojích by se též musel upravit ten memcpy.
    #include <assert.h>
    #include <cstring>
    #include <climits>
    #include <iomanip>
    #include <iostream>
    
    int main()
    {
        assert(sizeof(unsigned long) > sizeof(unsigned int));
    
        int digits;
        std::cin >> digits;
        digits += 1;
        int allocate = (digits / (sizeof(unsigned int) * 2)) + 1;
    
        unsigned int* addend1 = new unsigned int[allocate];
        unsigned int* addend2 = new unsigned int[allocate];
        unsigned int* sum = new unsigned int[allocate];
        memset(addend1, 0, allocate);
        memset(addend2, 0, allocate);
        memset(sum, 0, allocate);
     
        unsigned int num1 = 0;
        unsigned int num2 = 0;
        unsigned int currByte = (digits - 2) / 2;
        for (int i = digits-2; i >= 0; i--) {
            unsigned int in1, in2;
            std::cin >> std::hex >> in1 >> in2;
            if (i % 2) {
                num1 |= in1 << 4;
                num2 |= in2 << 4;
                continue;
            }
            num1 |= in1;
            num2 |= in2;
            memcpy((void*)addend1 + currByte, &num1, 1);
            memcpy((void*)addend2 + currByte, &num2, 1);
            num1 = 0;
            num2 = 0;
            currByte--;
            for (int x = allocate - 1; x >= 0; x--)
                    std::cout << "- " << std::hex << addend1[x] << " ";
    
            std::cout << std::endl;
        }
    
        std::cout << std::endl;
    
        for (int i = allocate - 1; i > = 0; i--)
            std::cout << std::hex << addend1[i] << " ";
    
        std::cout << std::endl << std::endl;
    
    
        unsigned int carry = 0;
        for (int i = 0; i < allocate; i++) {
            unsigned long result = static_cast<unsigned long>(addend1[i]) + static_cast<unsigned long>(addend2[i]) + carry;
    
            carry = result >> sizeof(unsigned int) * 8;
    
            sum[i] = result;
        }
    
        for (int i = allocate - 1; i >= 0; i--)
            std::cout << std::hex << sum[i];
        std::cout << std::endl;
        return 0;
    }
    
    (och ten parser to zprasil, snad je to i nadále funkční:) )
    1.10.2012 06:29 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    To je snad jasné každému, že v šestnáctkové soustavě by to bylo o něco jednodušší, ale to už řešíte úplně jiné zadání. Navíc už bylo v diskusi zmíněno, že ve časově nejnáročnější není vlastní sčítání ale zpracování vstupu a výstupu - tedy to, co ve vašem podání bude dost možná ještě pomalejší než scanf() a printf(). Konverzí mezi desítkovou a šestnáctkovou soustavou už byste to zabil úplně, nenapadá mne totiž způsob, jak konverzi šestnáctkového dlouhého čísla na desítkové udělat s lineární časovou složitostí (vzhledem k délce).
    1.10.2012 14:47 Jose
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Používejte jen 2 staticky alokovaná pole, alokujte je podle prvního bloku a pouze pokud bude další blok větší tak je realokujte, jinak je nechte tak jak jste je měl předtím. Nepoužívejte dvourozměrná pole, překladač nemusí být schopen je uspokojivě optimalizovat. Pokuste se to dostat je jediné smyčky.
    1.10.2012 14:53 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Používejte jen 2 staticky alokovaná pole,

    To je jak házet hrách na stěnu… Tak ještě jednou: dvě pole jsou úplně zbytečná, stačí jedno.

    staticky alokovaná pole, alokujte je podle prvního bloku a pouze pokud bude další blok větší tak je realokujte

    Jak se realokuje staticky alokované pole?

    Pokuste se to dostat je jediné smyčky.

    Jak?

    1.10.2012 16:17 Jose
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    int main()
    { int blocks;
    scanf("%d\n", &blocks);
    int length, oldlength = 10;
    int result;
    int carry = 0;
    int *i1, *i2;
    i1 = malloc (10* sizeof (int));
    i2 = malloc (10* sizeof (int));
    for (int i = 0; i < blocks; i++)
    { scanf("%d\n", &length);
    if (length > oldlength)
    { i1 = realloc(i1, length * sizeof (int));
    i2 = realloc (i2, length * sizeof (int));
    oldlength = length; }
    for (int j = 0; j < length; j++)
    scanf("%d %d\n", i1 + j, i2 + j);
    for (int j = (length - 1); j >= 0; j--)
    { result = *(i1 + j) + *(i2 + j) + carry;
    if (result > 9)
    { carry = 1; *(i1+j) = result - 10; } else
    { carry = 0; *(i1 + j) = result; }
    }
    if (i != 0) printf("\n");
    for (int j = 0; j < length; j++)
    printf("%d", *(i1 + j); printf("\n"); }
    free (i1); free (i2); return 0; }
    Samo že náhrada scanf a printf za getchar a putchar jak bylo psáno výše má také velký vliv, ale to už doplníte sám.
    Ještě jsem ostranil to dělení a modulo, což jsou také poměrně pomalé operace. 
    Na druhou stranu, podle původního zadání není délka čísel větší než 1.000.000, takže pole by asi šlo udělat rovnou tak velký a 
    dál s nima nehýbat, spolklo by to 4 Mbyte paměti což se asi dá skousnout. 
    Ta optimalizace do jednoho cyklu asi opravdu nepůjde.
    1.10.2012 16:19 Jose
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Nějak se mi to nepovedlo čitelně zformátovat, snad to nějak přelouskáte.
    1.10.2012 16:51 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem

    Takže když si to shrneme, tak pole, které realokujete, není staticky alokované, a na jednu smyčku to také nemáte. Takže mé výhrady byly zcela oprávněné. Včetně té první, kterou jste ignoroval a dál úplně zbytečně alokujete dvě pole místo jednoho.

    Navíc použití realloc() je zbytečné a neefektivní. Vy přece nepotřebujete zachovat hodnoty z minulého bloku, takže je efektivnější zavolat free() a malloc() a zbytečně nekopírovat původní obsah.

    Ještě jsem ostranil to dělení a modulo, což jsou také poměrně pomalé operace.

    Není to až tak strašné. Na současných procesorech nadělá třeba podmíněný skok s nesprávně odhadnutým výsledkem víc škody než celé násobení a dělení.

    Na druhou stranu, podle původního zadání není délka čísel větší než 1.000.000, takže pole by asi šlo udělat rovnou tak velký a dál s nima nehýbat, spolklo by to 4 Mbyte paměti což se asi dá skousnout.

    Vzhledem k tomu, že stejně pracujeme s hodnotami v rozsahu 0-19, je vašich 8 MB (používáte dvě pole) osmkrát více, než je potřeba.

    3.10.2012 10:06 Vtipnéř | skóre: 33 | blog: Vtipnéřův blog | Brno
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Je nutné ta čísla ukládat? Myslím, že by mělo jít přímo posílat na výstup jednotlivé číslice výsledku se zpožděním o jedna kvůli přenosu. Ten by se nikdy neměl dostat dál (např. z jednotek na stovky).

    Jirka
    Opening Windows is better than washing them. Clearing Windows (e.g. erasing or deleting) is much more better.
    3.10.2012 10:19 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Vážně? Tak zkuste sečíst 999...9 + 1.
    3.10.2012 10:29 Vtipnéř | skóre: 33 | blog: Vtipnéřův blog | Brno
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Jasně, došlo mi to tři minuty po odeslání.

    Jdu si dát kafe, už mi to nějak nemyslí.

    Jirka
    Opening Windows is better than washing them. Clearing Windows (e.g. erasing or deleting) is much more better.
    3.10.2012 10:26 Vtipnéř | skóre: 33 | blog: Vtipnéřův blog | Brno
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Sorry, to bylo trochu unáhlené tvrzení.

    Jirka
    Opening Windows is better than washing them. Clearing Windows (e.g. erasing or deleting) is much more better.
    3.10.2012 10:51 Vtipnéř | skóre: 33 | blog: Vtipnéřův blog | Brno
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Mimochodem, do čtyřbajtového unsigned (long) int se vejde číslo velké něco přes 4 miliardy, takže číslice by se daly sčítat ve skupinách po devíti Hornerovým schematem a pole by mohlo být devětkrát kratší.

    Jirka

    PS: Kafe už mám v sobě, tak snad to není podobná blbost jako před chvílí.
    Opening Windows is better than washing them. Clearing Windows (e.g. erasing or deleting) is much more better.
    3.10.2012 10:54 Michal Kubeček | skóre: 71 | Luštěnice
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Blbost to není, jen ta myšlenka byla zmíněna hned v první odpovědi. :-) (ale uznávám, že máte pravdu, je to devět, ne osm)
    3.10.2012 11:03 Vtipnéř | skóre: 33 | blog: Vtipnéřův blog | Brno
    Rozbalit Rozbalit vše Re: Problem s algoritmem
    Pardon, nepořádně čtu odpovědi. Ale máte patrně pravdu, že největší vliv na délku trvaní bude mít rychlost vstupu/výstupu.

    Jirka
    Opening Windows is better than washing them. Clearing Windows (e.g. erasing or deleting) is much more better.

    Založit nové vláknoNahoru

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.