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í
×
včera 11:55 | Komunita

Vývojový tým OpenSSL ve spolupráci s iniciativou Core Infrastructure konsorcia Linux Foundation spustil proces přelicencování této kryptografické knihovny ze současné licence na licenci Apache Licence v 2.0 (ASLv2). Nová licence usnadní začleňování OpenSSL do dalších svobodných a open source projektů. Všichni dosavadní vývojáři OpenSSL (Authors) obdrží v následujících dnech email s prosbou o souhlas se změnou licence.

Ladislav Hagara | Komentářů: 7
včera 01:11 | Komunita

Před třemi týdny Mozilla.cz představila projekt Photon, jehož cílem je návrh a implementace nového vzhledu Firefoxu. Včera zveřejnila první náhled vzhledu Photon. Práce na projektu Photon jsou rozděleny do pěti týmů, které celkem čítají 19 lidí. Zaměřují se na zlepšení prvního spuštění Firefoxu a zaujetí nových uživatelů, celkovou úpravu vzhledu, zlepšení animací, zrychlení odezvy uživatelského rozhraní a také upravení nabídek. Vývoj lze sledovat v Bugzille.

Ladislav Hagara | Komentářů: 28
23.3. 20:00 | Komunita

OneDrive pro firmy je již ve webových prohlížečích na Linuxu stejně rychlý jako na Windows. Microsoft opravil chybu z listopadu loňského roku. OneDrive pro firmy běžel na Linuxu mnohem pomaleji než na Windows. V popisu chyby bylo uvedeno, že stačilo v prohlížeči na Linuxu nastavit v user-agentu Windows a vše se zrychlilo. Odpovědí Microsoftu bylo (Internet Archive: Wayback Machine), že Linux není podporován. Po bouřlivých diskusích na redditu i Hacker News byla chyba nalezena a opravena.

Ladislav Hagara | Komentářů: 6
23.3. 19:00 | Zajímavý projekt

Byla vyhlášena soutěž Hackaday Prize 2017. Soutěž je určena vývojářům open source hardwaru. Pro výherce je připraveno celkově 250 tisíc dolarů. Každý ze 120 finalistů získá tisíc dolarů. Nejlepší pak navíc 50, 30, 20, 15, 10 a 5 tisíc dolarů. Jedná se již o čtvrtý ročník soutěže. V roce 2014 zvítězil projekt globální sítě open source pozemních satelitních stanic SatNOGS. V roce 2015 zvítězil open source systém pro řízení elektrických invalidních vozíků pohybem očí Eyedriveomatic. V roce 2016 zvítězil modulární robot Dtto.

Ladislav Hagara | Komentářů: 0
23.3. 15:00 | Bezpečnostní upozornění

Byla vydána Samba ve verzích 4.6.1, 4.5.7 a 4.4.12. Řešen je bezpečnostní problém CVE-2017-2619. Pomocí symbolických odkazů a souběhu (symlink race) lze "teoreticky" získat přístup k souborům, které nejsou sdíleny. Linuxové distribuce jsou postupně aktualizovány (Debian).

Ladislav Hagara | Komentářů: 0
23.3. 07:43 | Nová verze

Na Steamu se objevil port hry Arma: Cold War Assault (Operation Flashpoint) pro Mac a Linux. … více »

creon | Komentářů: 29
23.3. 05:55 | Nová verze

Po 18 měsících od vydání verze 8.0 byla vydána verze 9.0 open source alternativy GitHubu, tj. softwarového nástroje s webovým rozhraním umožňujícího spolupráci na zdrojových kódech, GitLab. Představení nových vlastností v příspěvku na blogu a na YouTube.

Ladislav Hagara | Komentářů: 0
23.3. 03:33 | Komunita

Platnost posledního patentu souvisejícího s Dolby Digital (AC-3) vypršela. Po MP3 se tak do Fedory oficiálně dostane také kodek AC-3.

Ladislav Hagara | Komentářů: 5
23.3. 00:44 | Komunita

Feral Interactive, společnost zabývající se vydáváním počítačových her pro operační systémy macOS a Linux, nabízí své hry na Steamu vývojářům open source 3D grafické knihovny Mesa zdarma. Podmínkou je minimálně 25 commitů za posledních 5 let. Stejnou nabídku dostali vývojáři knihovny Mesa v roce 2015 od Valve. O rok dříve dostali od Valve tuto nabídku vývojáři Debianu a Ubuntu.

Ladislav Hagara | Komentářů: 0
22.3. 23:55 | Nová verze

Opera 44, verze 44.0.2510.857, byla prohlášena za stabilní. Nejnovější verze tohoto webového prohlížeče je postavena na Chromiu 57. Z novinek vývojáři Opery zdůrazňují podporou Touch Baru na nejnovějších MacBoocích Pro (gif). Přehled novinek pro vývojáře na blogu Dev.Opera.

Ladislav Hagara | Komentářů: 1
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (14%)
 (2%)
 (72%)
 (3%)
 (10%)
Celkem 928 hlasů
 Komentářů: 72, poslední 1.3. 11:16
    Rozcestník

    Dotaz: Urychleni celkem jednoducheho algoritmu

    Bundas avatar 19.2.2014 20:52 Bundas | skóre: 14 | Pardubice
    Urychleni celkem jednoducheho algoritmu
    Přečteno: 457×
    Zdravim vsechny. Nenapada vas zpusob, jak podstatne urychlit tento algoritmus? The algoritmus ma nejdrive nacist ze souboru cislo p indikujici pocet ostatnich cisel z rozmezi -1 000 000 000 az 1 000 000 000. A potom je ma rozradit, resp. zjistit, kolik je kterych cisel. Rozradit 100 000 cisel mu trva hodiny. Nenapada vas zpusob, jak to urychlit? Predem moc diky za pomoc.
    
    
    
     #define NAZEV "vstup.txt"
     #define TYP "r"
     #define NAZEV2 "help"
     #define TYP2 "a+"
     #define MIN_INT -1000000000
     #define MAX_INT 1000000000
     /*--------------------------------------------------------------------------------------------------*/
     FILE *s;
     FILE *pomocnySoubor;
     int n;
     int poleCisel[100001];
    
     /*------------------------------------------------------------------------------------------------*/
     void nactiVstup(){
         s = fopen(NAZEV, TYP);
         fscanf(s, "%d\n", &n);
         int i;
         for(i=0; i < n;i++){
             fscanf(s, "%d\n", &poleCisel[i]);
         }
     puts("nascanoval sem ze souboru");
         fclose(s);
     }
     /* Druha metoda ------------------------------------------------------------------------------ */
     void najdiVyskyt(){
         pomocnySoubor = fopen(NAZEV2, TYP2);
         int i,j,tmp=0;
         int vysledek;
    
             int aktualni_cislo;
             puts("zacinam tridit");
             for(j=MIN_INT; j < MAX_INT; j++){
                 vysledek=0;
                 aktualni_cislo =j;
                 if(j == MIN_INT/2){
                     puts("jsem v pulce");
                 }
                 if(j == MIN_INT/4){
                    puts("jsem ve ctvrtine");
            }
                    if(j == MIN_INT/1000){
                    puts("jsem v jedne tisicine");
     }
             for(i=0; i < n; i++){
                 if(poleCisel[i] == aktualni_cislo){
                 vysledek++;
    
             }
    
             }
             if(vysledek > 0){
                 fprintf(pomocnySoubor, "%d %d\n", aktualni_cislo, vysledek);
                 printf("%d %d\n", aktualni_cislo, vysledek);
             }
             }
    
    
    
             printf("dotridil sem\n");
    
    
    
         fclose(pomocnySoubor);
     }
    
     /*Hlavni funkce ------------------------------------------------------------------------------------- */
     int main(void){
         nactiVstup();
         najdiVyskyt();
         printf("\n");
         return EXIT_SUCCESS;
     }
    
    btw. mozna tam jsou nejake nepouzite promenne. Kdyz sem to poprve napsal, tak to nefungovalo a tak jsem to komplet prepisoval. >> proto tam jsou mozna nejake prebytecne.
    Abe the Messiah has come.

    Řešení dotazu:


    Odpovědi

    Řešení 1× (Bundas (tazatel))
    Jendа avatar 19.2.2014 21:18 Jendа | skóre: 73 | blog: Výlevníček | JO70FB
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Odsazení!!!
    puts("zacinam tridit");
    for(j=MIN_INT; j < MAX_INT; j++){
        vysledek=0;
        aktualni_cislo =j;
        if(j == MIN_INT/2){
            puts("jsem v pulce"); 
        }
        if(j == MIN_INT/4){
           puts("jsem ve ctvrtine");
        }
        if(j == MIN_INT/1000){
           puts("jsem v jedne tisicine");
        }
        for(i=0; i < n; i++){ 
          if(poleCisel[i] == aktualni_cislo){
          vysledek++;
          }
        }
    }
    
    Pro každé číslo z <-1G; +1G> to projde všechna zadaná čísla. Pro 100k čísel to tedy udělá 2G*100k = 200T operací. Je zázrak, že to za ty hodiny vůbec projde. Složitost algoritmu je, řekněme, n^2 (pokud by pro zjednodušení ten rozsah byl závislý na n - teď je to lineární, ale s brutální multiplikativní konstantou :).

    Hint: Nebylo by lepší zadaná čísla napřed setřídit (to běží v n log n) a pak to setříděné pole projít sekvenčně?
    Nezapomeňte si příští víkend posunout časovače na svých bombách o hodinu dopředu!
    20.2.2014 00:02 Sten
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Hint: Nebylo by lepší zadaná čísla napřed setřídit (to běží v n log n) a pak to setříděné pole projít sekvenčně?
    Anebo rovnou při řazení pomocí merge sortu slučovat (a počítat výskyty) stejná čísla, tím to celé proběhne v n log n.
    20.2.2014 00:31 potato
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Příloha:
    • z.c (1601 bytů)
    Standardní způsob urychlení je použití vhodné vyhledávací datové struktury, například hashové tabulky. Buď z knihovny, případně si ji můžeš naprogramovat sám... Přiložený program využívající GHashTable z GLib spočítá počty výskytů 100000 čísel asi za 50 ms. Půlku z toho času přitom sežere parsování vstupu a vypisování výsledků.

    Pokud nechceš používat vůbec žádné datové struktury, tak to pole po načtení setřiď pomocí qsort() a pak už jen počítej délky bloků stejných čísel. To je pro hodně velká pole méně efektivní, ale pořád to bude okamžitě.
    20.2.2014 01:41 Sten
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Použití vhodné struktury ano, ale hashmapa na integery? Really?

    qsort pro tohle není moc nevhodný, protože to musíte nejdřív seřadit a až potom počítat. Doporučuji merge sort a počítat výskyty rovnou při mergování. IMO to bude i o dost rychlejší než mapa, za cenu vyšší spotřeby paměti.
    20.2.2014 17:14 Sten
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Příloha:
    Tady je verze s merge sortem
    20.2.2014 17:29 potato
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    hashmapa na integery? Really?
    Jasnačka že really.

    Integer je sám svým hashem (viz g_direct_hash), ale princip ukládání do tabulky je stejný. Pro ukázkový příklad to přece nebudu kódit zvlášť. Navíc se nestarám, jak přesně řešit velikost tabulky a její případný růst, když to udělá GHashTable sama...
    qsort pro tohle není moc nevhodný, protože to musíte nejdřív seřadit a až potom počítat. Doporučuji merge sort a počítat výskyty rovnou při mergování. IMO to bude i o dost rychlejší než mapa, za cenu vyšší spotřeby paměti.
    Jelikož každý sort má ten log(N) faktor, přijde mi toto porovnávání sortů jako poněkud plané teoretizování.

    Z praktického hlediska: qsort() je jedno volání funkce ze standardní libc. Plus potřebuješ funcki která porovná dva integery. Tečka.
    20.2.2014 18:21 lertimir | skóre: 59 | blog: Par_slov
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Určitě není pravda, že každý sort má svůj ln(N) faktor. A quick sort má svůj worst case na n^2. viz Sorting algorithm
    20.2.2014 21:18 potato
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    To jsem si mohl myslet, že bude následovat ještě více planého teoretizování a odkaz na Wikipedii.

    Ano, máš pravdu, a taky je všechno, co píšeš, irelevantní.

    Pokud řešíš benchmarky, tak jsem psal, stejně sežere tak velkou část času parsování a vypisování, že program používající quciksort můžu zrychlit o 30%, když použiji strtol() namísto scanf(). Můžeš si progratulovat, že umíš napsat funkce pro parsování čísel, ale normální člověk použije standardní knihovnu...
    20.2.2014 21:20 potato
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    A, sorry s tím parsováním. Pomíchalo se mi, že jsi autor i předchozí odpovědi, to zřejmě psal někdo jiný.
    21.2.2014 10:03 Sten
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Integer je sám svým hashem (viz g_direct_hash), ale princip ukládání do tabulky je stejný. Pro ukázkový příklad to přece nebudu kódit zvlášť. Navíc se nestarám, jak přesně řešit velikost tabulky a její případný růst, když to udělá GHashTable sama...
    Hashmapa slouží pro případy, kdy klíč má složité porovnání (např. string), potom je totiž mnohem rychlejší porovnávat hashe a plné porovnávání použít jen pro těch pár případů kolizí. Jenže to trpí mnoha problémy, mj. hash collision vede až k O(n). I proto se integer jako svůj vlastní hash většinou nepoužívá, ale počítá se nějaký odolnější hash, což zase stojí výkon. Navíc se hash mapa musí při velkém množství položek často rebalancovat, což stojí hodně výkonu Pro klíče s jednoduchým porovnáním je výrazně rychlejší nějaký binární (či n-ární, pokud se chcete přiblížit O(1)) strom.
    Jelikož každý sort má ten log(N) faktor, přijde mi toto porovnávání sortů jako poněkud plané teoretizování.
    Quick sort má average O(n log n), ale worst case O(n²). merge sort má O(n log n) obojí, stojí pouze víc paměti. Navíc u toho merge sortu se díky mergování duplicit dostanu na ještě lepší výkon, protože v průběhu výpočtu klesá počet položek. A ještě navíc vypočítám výsledky rovnou během toho řazení.
    21.2.2014 10:53 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Sorry, že se do toho pletu, ale ono zas na druhé straně fopen, scanf, scanf ve for, qsort a při zobrazení jen vypisovat při změně počet, jinak ++, odpovídá zadání, je to mnohem kratší, stojí to méně paměti, je to napsané za 10min i s ošetřením, a je to pomalejší o nějaké jednotky msec na čase, kde 80 % zabírá výstup a 19.9 % vstup (% střelená od pasu). Myslím si, že cokoliv jiného (včetně hashmapy) je dost overkill.
    To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
    wamba avatar 20.2.2014 01:53 wamba | skóre: 37 | blog: wamba
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    jo standardně se na to používá hash(ale nevěděl jsem jak se v C používají) v Perlu by řešení mohlo vypadat např.
    #!/usr/bin/perl
    use 5.010;
    use warnings;
    use strict;
    
    our $VERSION = 0.001;
    
    my %hesla;
    while (<>) {
        chomp;
        $hesla{$_}++;
    }
    
    while ( my ( $heslo, $pocet ) = each %hesla ) {
        say $heslo, q{ }, $pocet;
    }
    
    (100000 položek v pohodě zvládá)
    This would have been so hard to fix when you don't know that there is in fact an easy fix.
    20.2.2014 02:24 meggie
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    void najdiVyskyt(){
      pomocnySoubor = fopen(NAZEV2, TYP2);
      int *poleCisel_tmp;
      int *poleCisel_max = poleCisel + sizeof(poleCisel);
      int *vysledky = (int *) malloc((MIN_INT+MAX_INT+1) * sizeof(int) + 1);
      vysledky = vysledky + MIN_INT;
      
      // puts("zacinam tridit"); - strasne pomala vec :P
      
      poleCisel_tmp = poleCisel;
      for (;;) {
        vysledky[*poleCisel_tmp] = 0;
        poleCisel_tmp++;
        if (poleCisel_tmp > poleCisel_max)
          break;
      }
      
      poleCisel_tmp = poleCisel;
      for (;;) {
        vysledky[*poleCisel_tmp]++;
        poleCisel_tmp++;
        if (poleCisel_tmp > poleCisel_max)
          break;
      }
      
      poleCisel_tmp = poleCisel;
      for (;;) {
        fprintf(pomocnySoubor, "%d %d\n", *poleCisel_tmp, vysledky[*poleCisel_tmp]);
        vysledky[*poleCisel_tmp] = 0;
        poleCisel_tmp++;
        if (poleCisel_tmp > poleCisel_max)
          break;
      }
    
      fclose(pomocnySoubor);
    }
    ale nikde bych to nepouzil...
    20.2.2014 02:26 meggie
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    a jeste tam chybi if (vysledky[*poleCisel_tmp]) pred tim fprintf
    20.2.2014 02:31 meggie
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    a taky if (poleCisel_tmp > poleCisel_max) => if (poleCisel_tmp >= poleCisel_max) proste jsou tam sem tam chyby :P
    Saljack avatar 20.2.2014 21:45 Saljack | skóre: 28 | blog: Saljack | Praha
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Co je proboha tohle?
    for (;;) {
        vysledky[*poleCisel_tmp] = 0;
        poleCisel_tmp++;
        if (poleCisel_tmp > poleCisel_max)
          break;
      }
    Proc nepouzit for rovnou nez psat podminky do nej a nebo pouzit while? Nechci byt hnusny, ale vic zprasit cyklus snad nejde, navic trikrat za sebou. Mozna by stalo za to si zopakovat co vlasne for a while dela.
    Sex, Drugs & Rock´n Roll.
    Saljack avatar 20.2.2014 21:49 Saljack | skóre: 28 | blog: Saljack | Praha
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    A jeste drobny detail pojmenovani promene poleCisel_tmp neni zrovna moc vhodne. Takhle to vypada, ze je to kopie celeho pole, ale promenna je pouze "iterator".
    Sex, Drugs & Rock´n Roll.
    21.2.2014 04:59 meggie
    Rozbalit Rozbalit vše Re: Urychleni celkem jednoducheho algoritmu
    Pokud nezapne optimalizaci a ten kompilator to nejak nezoptimalizuje, tak diky tomu usetri jedno porovnani tech pointeru, ale slo by pouzit do while...

    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.