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 15:33 | Nová verze

    Open source platforma Home Assistant (Demo, GitHub, Wikipedie) pro monitorování a řízení inteligentní domácnosti byla vydána v nové verzi 2025.8.

    Ladislav Hagara | Komentářů: 3
    včera 14:22 | IT novinky

    Herní studio Hangar 13 vydalo novou Mafii. Mafia: Domovina je zasazena do krutého sicilského podsvětí na začátku 20. století. Na ProtonDB je zatím bez záznamu.

    Ladislav Hagara | Komentářů: 0
    včera 13:22 | IT novinky

    Operátor O2 má opět problémy. Jako omluvu za pondělní zhoršenou dostupnost služeb dal všem zákazníkům poukaz v hodnotě 300 Kč na nákup telefonu nebo příslušenství.

    Ladislav Hagara | Komentářů: 8
    včera 05:55 | IT novinky

    Společnost OpenAI představila GPT-5 (YouTube).

    Ladislav Hagara | Komentářů: 1
    včera 05:00 | Nová verze

    Byla vydána (𝕏) červencová aktualizace aneb nová verze 1.103 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a videi v poznámkách k vydání. Ve verzi 1.103 vyjde také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.

    Ladislav Hagara | Komentářů: 0
    7.8. 17:33 | IT novinky

    Americký prezident Donald Trump vyzval nového generálního ředitele firmy na výrobu čipů Intel, aby odstoupil. Prezident to zdůvodnil vazbami nového šéfa Lip-Bu Tana na čínské firmy.

    Ladislav Hagara | Komentářů: 8
    7.8. 16:55 | Nová verze

    Bylo vydáno Ubuntu 24.04.3 LTS, tj. třetí opravné vydání Ubuntu 24.04 LTS s kódovým názvem Noble Numbat. Přehled novinek a oprav na Discourse.

    Ladislav Hagara | Komentářů: 0
    7.8. 16:44 | Nová verze

    Byla vydána verze 1.89.0 programovacího jazyka Rust (Wikipedie). Podrobnosti v poznámkách k vydání. Vyzkoušet Rust lze například na stránce Rust by Example.

    Ladislav Hagara | Komentářů: 0
    7.8. 12:22 | IT novinky

    Americká technologická společnost Apple uskuteční v USA další investice ve výši sta miliard dolarů (2,1 bilionu korun). Oznámil to ve středu šéf firmy Tim Cook při setkání v Bílém domě s americkým prezidentem Donaldem Trumpem. Trump zároveň oznámil záměr zavést stoprocentní clo na polovodiče z dovozu.

    Ladislav Hagara | Komentářů: 5
    7.8. 04:55 | Nová verze

    Zálohovací server Proxmox Backup Server byl vydán v nové stabilní verzi 4.0. Založen je na Debianu 13 Trixie.

    Ladislav Hagara | Komentářů: 0
    Kolik tabů máte standardně otevřeno ve web prohlížeči?
     (47%)
     (21%)
     (4%)
     (5%)
     (3%)
     (1%)
     (1%)
     (18%)
    Celkem 315 hlasů
     Komentářů: 23, poslední 4.8. 13:01
    Rozcestník
    Štítky: není přiřazen žádný štítek

    Tail rekurze v erlangu

    14.4.2007 10:06 | Přečteno: 1218× | erlang | Výběrový blog

    Ve funkcionálních jazycích se spousta (většina?) algorimů zapisuje jako rekurze. Nejinak je tomu i u erlangu. Jenže rekurze je pro normální dnešní CPU fuj a tak se to řeší (a nejen ve funkcionálních jazycích) tzv. tail rekurzí. Prakticky jde o nahrazení rekurze cyklem a nealokuje se kvůli tomu další paměť na zásobníku, ale různé jazyky se s tím umí vyrovnat různě.

    Například výpočet faktoriálu:

    -module(fact).
    -export([fact/1, fact2/1]).
    
    fact(N) when N>0 -> N*fact(N-1);
    fact(0) -> 1.
    
    fact2(0) -> 1;
    fact2(N) when N>0 -> fact2(N-1, N).
    
    fact2(0, Res) -> Res;
    fact2(N, Res) -> fact2(N-1, N*Res).
    Varianta fact bohužel v erlangu skončí skutečnou rekurzí, kdežto fact2 udělá cyklus kolem fact2/2 kódu. Například Haskel se tuším vypořádá dokonce i s ekvivalentem zápisu fact. Pokud si to chcete vyzkoušet, tak si zkuste vypočítat fact2(50000) a pak fact(50000). To druhé začne velmi záhy swapovat a následně to shodí BEAN pod nímž to spustíte (pokud máte opravdu hodně swapu a paměti, tak si zvolte ještě větší číslo :-))

           

    Hodnocení: 86 %

            špatnédobré        

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

    Komentáře

    Vložit další komentář

    14.4.2007 18:03 Messa | skóre: 39 | blog: Messa
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Tohle umí gcc -O2 taky. (Možná pro někoho samozřejmost, ale mě to překvapilo.)
    14.4.2007 20:49 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Na úrovni haskelu nebo erlangu? Předpokládám, že spíš to druhé, ne?
    XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
    14.4.2007 21:03 Messa | skóre: 39 | blog: Messa
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Konkrétně u tohoto příkladu na úrovni Haskelu.
    int fact (int n) {
    	if (n == 0) return 1;
    	return n * fact (n-1); }
    a v assembleru je vidět krásná smyčka, žádný call.

    Snad nikoho neurážím, že vám sem do funkcionálního programování tahám C :-)
    14.4.2007 21:48 Hynek (Pichi) Vychodil | skóre: 43 | blog: Pichi | Brno
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Snad nikoho neurážím, že vám sem do funkcionálního programování tahám C :-)
    Nene, dík za informaci. To se hodí vědět.
    XML je zbytečný, pomalý, nešikovný balast, znovu vynalézané kolo a ještě ke všemu šišaté, těžké a kýčovitě pomalované.
    14.4.2007 23:26 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Otázka je, jak toho dosahuje. Zkusil jsem rekurzi mezi dvěma funkcemi, a zdá se, že nedělá tail call vždy:
    int foo (int a, int b);
    int bar (int c, int a, int b)
    {
            return (0==b) ? a : foo(a, --b);
    }
    
    int foo (int a, int b)
    {
            return bar(1, a, b);
    }
    
    gcc -S -O2 --omit-frame-pointer test.c
    
    foo:
            subl    $12, %esp
            movl    20(%esp), %eax
            movl    $1, 8(%esp)
            movl    %eax, 4(%esp)
            movl    16(%esp), %eax
            movl    %eax, (%esp)
            call    bar
            addl    $12, %esp
            ret
    
    bar:
            movl    8(%esp), %eax
            movl    4(%esp), %edx
            testl   %eax, %eax
            jne     .L8
            movl    %edx, %eax
            ret
    .L8:
            subl    $1, %eax
            movl    %eax, 8(%esp)
            jmp     foo
    
    Jinými slovy, je to hezká optimalizace, ale plně bych se na ní při rekurzivním psaní programu nespoléhal (ostatně, norma C nic takového nepožaduje).
    14.4.2007 23:44 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    v jake verzi to je? v gcc 3.4.6 to nejde ani s -O2 ani s -O3... porad pouziva call...
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    15.4.2007 00:02 Tom.š Ze.le.in | skóre: 21 | blog: tz
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Mně to funguje v 4.1.1, ale podle changelogu to bylo už v 3.0.1.
    15.4.2007 01:17 Kyosuke | skóre: 28 | blog: nalady_v_modre
    Rozbalit Rozbalit vše Re: Tail rekurze v erlangu
    Chm, chmm, ten patch poslal už v květnu 2000 Jan Hubička a objevilo se to už v tom úchylném „GCC 2.96“. ;-)

    Založit nové vláknoNahoru

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