Příspěvky

571

Vývoj / Re:Dědičnost dnes

« kdy: 02. 02. 2017, 14:26:45 »

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Tak to určitě neplatí. Čas přístupu do paměti neroste logaritmicky s velikostí vstupu programu. O(1) je jen horní odhad rychlosti operace. Stačí uvažovat nejpomalejší možný přístup. Pořád to bude reálnému hardwaru mnohem blíž než Turingův stroj.

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Jde mi o to, ze bud chces teoreticky dokazat, ze FP je vypocetne horsi - pak ano, mas pravdu, neumoznuje O(1) pristup do pameti. Jenze v praxi O(1) pristup neumoznuje nic, zadne zarizeni (jinak receno, kazde fyzikalni zarizeni bude pomalejsi pokud bude dostatecne velke).

Nebo se chces bavit o praktickych aspektech implementace FP, a pak nemusime nutne trvat na tom, aby vysledny program (strojovy kod) byl funkcionalne cisty, protoze FP pouzivame jen jako abstrakci pro popis, nikoli jako vypocetni model.

Takze at se snazis dokazat cokoli z toho, pro praxi to neni rozhodujici.

Pokud chceme slovíčkařit, tak FP neumožňuje přístup do paměti vůbec, protože žádnou nemá, když jsou vše jen funkce. Gll absolutně neví, o čem mluví, zápis funkcí v FP nevypovídá zhola nic o jejich výpočetní složitosti (ani o tom, jestli jsou vůbec vyhodnotitelné), protože si plete pojmy algoritmus a (matematická) funkce. Doporučuju nereagovat na něj, dokud se nedoučí alespoň elementární definice (aspoň - jak píšete - formální popis a výpočetní model). Dokud to nezvládne, bude pořád diskutovat na úrovni aspiranta zvláštní školy...

572

Vývoj / Re:Dědičnost dnes

« kdy: 02. 02. 2017, 14:19:47 »

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Předpokládám, že velikost paměti počítače je konstantní. Ani nevěřím tomu, že rychlost přístupu do paměti závisí na její velikosti. Určitě je rozdíl v rychlosti přístupu do cache a dohlavní paměti, ale to se nedá popsat takto jednoduše.

Bohužel je to čistá realita, sám jsem na to narazil před pár měsíci při implementaci kolaborativního filtru pro větší data (řádově GB v RAM)

Tady jsou výsledky JMH benchmarku, který testuje zápis na náhodná místa různě velkých polí, vždy milion zápisů ve (stejně) náhodném pořadí. Ve sloupečcích jsou

- velikost cílového pole
- Kolikrát se podařilo milionkrát zapsat do cílového pole za 3 vteřiny
- Jak dlouho trvá zápis miliónu položek.


             1  3898   0.769 ± 0.003  ms/op
             2  3967   0.756 ± 0.003  ms/op
             4  3882   0.773 ± 0.003  ms/op
            32  3929   0.763 ± 0.003  ms/op
           256  3974   0.754 ± 0.003  ms/op
           512  3912   0.767 ± 0.004  ms/op
          1024  3927   0.764 ± 0.003  ms/op
          2048  3986   0.752 ± 0.003  ms/op
          4096  3985   0.752 ± 0.002  ms/op
          8192  3993   0.751 ± 0.002  ms/op
         16384  3990   0.751 ± 0.004  ms/op
         65536  2278   1.318 ± 0.013  ms/op
       1048576  1094   2.741 ± 0.060  ms/op
       4194304  872   3.440 ± 0.089  ms/op
       8388608  480   6.268 ± 0.120  ms/op
      16777216  357   8.426 ± 0.158  ms/op
      33554432  316   9.533 ± 0.132  ms/op
      67108864  295  10.210 ± 0.102  ms/op
     134217728  275  10.954 ± 0.120  ms/op
     536870912  238  12.686 ± 0.343  ms/op
    1073741824  185  16.323 ± 0.680  ms/op

Je vidět, že rychlost vykonávání "algoritmu" na velikosti dat závisí poměrně významně. Zajímavé také je, že takovýhle "algoritmus" nad velkými daty na jednom počítači skoro nejde paralelizovat, protože bottleneck je přístup do RAM.

Pro úplnost



sudo dmidecode -t cache
# dmidecode 3.0
Getting SMBIOS data from sysfs.
SMBIOS 2.8 present.

Handle 0x0003, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L1 Cache
   Configuration: Enabled, Not Socketed, Level 1
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 64 kB
   Maximum Size: 64 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Parity
   System Type: Data
   Associativity: 8-way Set-associative

Handle 0x0004, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L1 Cache
   Configuration: Enabled, Not Socketed, Level 1
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 64 kB
   Maximum Size: 64 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Parity
   System Type: Instruction
   Associativity: 8-way Set-associative

Handle 0x0005, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L2 Cache
   Configuration: Enabled, Not Socketed, Level 2
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 512 kB
   Maximum Size: 512 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Single-bit ECC
   System Type: Unified
   Associativity: 4-way Set-associative

Handle 0x0006, DMI type 7, 19 bytes
Cache Information
   Socket Designation: L3 Cache
   Configuration: Enabled, Not Socketed, Level 3
   Operational Mode: Write Back
   Location: Internal
   Installed Size: 4096 kB
   Maximum Size: 4096 kB
   Supported SRAM Types:
      Synchronous
   Installed SRAM Type: Synchronous
   Speed: Unknown
   Error Correction Type: Multi-bit ECC
   System Type: Unified
   Associativity: 16-way Set-associative

To je pořád O(1).

573

Vývoj / Re:Dědičnost dnes

« kdy: 02. 02. 2017, 13:09:52 »

Zaprvé, zkratkou RAM jsem myslel https://en.wikipedia.org/wiki/Random-access_machine .

ja jsem myslel random access memory. vy neco jineho?

Z log(n) už máme "N*log(n)", tedy funkci dvou proměnných...super. Tohle už ani není vtipný, tohle bude někdy tvořit SW? 

N=n, stale je to stejny. nevim co ucili vas, ale asi nic moc, protoze neznate elementarni veci. programuji ruzne cipy, tak snad neco o tom vim

Bože, do čehos to dal duši... 

574

Vývoj / Re:Dědičnost dnes

« kdy: 02. 02. 2017, 12:51:48 »

Co má společného Turingův stroj s tím co jsem psal? Já psal o stroji s náhodným přístupem do paměti. Pomocí turingova stroje i lambda kalkulu můžete vyřešit stejné problémy, ale ne ve stejném čase a se stejnou paměťovou náročností. Běžné algoritmy jsou postupy výpočtu pro stroj RAM.

Myslim, ze to je problem v teorii, nikoli v praxi. Pominme ted to, ze FP je jen abstrakce, ktera se pak beztak preklada do von Neumannovy architektury.

Potiz je v tom, ze RAM, ktera ma pristup O(1), nelze fyzikalne zkonstruovat. I dnes se to projevuje tim, ze existuje neco jako hierarchie pameti (a ze treba nelze zvetsovat L1 cache, protoze se typicky ocekava, ze do ni pujde pristupovat v jednom cyklu). Proto se proste fakt, ze realna RAM neni O(1) zanedbava a pocita se s tim, jako by to bylo O(1), protoze to je dostatecne dobra aproximace pro velikosti RAM, ktere se typicky pouzivaji.

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Přístup do RAM je O(1). Definice Big-O se dnes už na školách neučí nebo co? Takhle se pak nedá vůbec diskutovat...

pristup do RAM je N*log(n). nevim co to tady spletate. minulej rok jsem statnicoval na CVUT, tak neco o tom vim

Z log(n) už máme "N*log(n)", tedy funkci dvou proměnných...super. Tohle už ani není vtipný, tohle bude někdy tvořit SW? 

575

Vývoj / Re:Dědičnost dnes

« kdy: 02. 02. 2017, 12:18:18 »

Co má společného Turingův stroj s tím co jsem psal? Já psal o stroji s náhodným přístupem do paměti. Pomocí turingova stroje i lambda kalkulu můžete vyřešit stejné problémy, ale ne ve stejném čase a se stejnou paměťovou náročností. Běžné algoritmy jsou postupy výpočtu pro stroj RAM.

Myslim, ze to je problem v teorii, nikoli v praxi. Pominme ted to, ze FP je jen abstrakce, ktera se pak beztak preklada do von Neumannovy architektury.

Potiz je v tom, ze RAM, ktera ma pristup O(1), nelze fyzikalne zkonstruovat. I dnes se to projevuje tim, ze existuje neco jako hierarchie pameti (a ze treba nelze zvetsovat L1 cache, protoze se typicky ocekava, ze do ni pujde pristupovat v jednom cyklu). Proto se proste fakt, ze realna RAM neni O(1) zanedbava a pocita se s tim, jako by to bylo O(1), protoze to je dostatecne dobra aproximace pro velikosti RAM, ktere se typicky pouzivaji.

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Přístup do RAM je O(1). Definice Big-O se dnes už na školách neučí nebo co? Takhle se pak nedá vůbec diskutovat...

576

Vývoj / Re:Dědičnost dnes

« kdy: 02. 02. 2017, 12:09:35 »

http://bredy.novacisko.cz/?/46
co reknete na tenhle clanek?

V ničem se neliší od jiných, stejně nešťastně napsaných úvodů do OOP. Další z textů, jejichž autor podlehl dojmu, že OOP stojí a leží na dědění. I s "povinným" prvoplánovým příkladem grafických objektů, na němž je "všechno krásně jasné", aspoň do doby, než by se v tom zvídavý čtenář začal šťourat a začal si klást otázky, jestli je opravdu dobrý nápad odvozovat děděním křivku od úsečky, jestli je to opravdu šikovné doplňovat takto vzniklou hierarchii o vlastnost barvy dalším děděním od již specializovaných tříd a k čemu je to celé dobré, když stejně na vykreslení každého z těch útvarů je objekt plátno, který to všechno umí tak nějak bokem i bez objektů. Bohužel, asi i vinou takovýchto textů v praxi spousta programů vypadá tak, jak vypadá.
V češtině existují rozhodně mnohem lepší texty o OOP, např. od V. Merunky nebo O. Čady.

P.S.: Poznámka "Chtěl jsem vybrat nějaký programovací jazyk pro popis OOP, ale neuspěl jsem. Buď se jedná o jazyk příliš složitý (smalltalk)..." hned v úvodu mě opravdu rozesmála.

Zrovna Čadova knížka o OOP je dost otřesná.

577

Vývoj / Re:Dědičnost dnes

« kdy: 01. 02. 2017, 13:54:17 »

To už je každého problém, jestli si to zjistí. V nejhorším vymyslí kolo, ale rozumný člověk bude vynakládat síly jen na něco nového.

Nové staví na starém. Alespoň v tvrdých vědách.  Nevím z kterého oboru máte to Phd., ale informatika to zcela jistě není. To co tu plácáte jsou nesmysly. Neznáte rozdíl mezi složitostí a vyčíslitelností.

Vážně?

Z pohledu vyčíslitelnosti to není (obecně) pravda.
.......
Například Dijkstrův grafový algoritmus (abych byl konkrétní) je v FP stejně efektivní jako v OOP.

A? Jistě, šlo by napsat i složitost, vyčíslitelnost je ovšem obecnější pojem, který mi zde přišel vhodnější, když už se bavíme o FP (tj. o funkcích) a jejich algoritmické charakteristice. Hádat se o slovíčka vážně nehodlám.

578

Vývoj / Re:Dědičnost dnes

« kdy: 01. 02. 2017, 13:38:16 »

To už je každého problém, jestli si to zjistí. V nejhorším vymyslí kolo, ale rozumný člověk bude vynakládat síly jen na něco nového.

Neznáte rozdíl mezi složitostí a vyčíslitelností.

Vážně?

579

Vývoj / Re:Dědičnost dnes

« kdy: 01. 02. 2017, 13:21:57 »

v té době ještě vývojáři sem tam potřebovali řešit algoritmy - dnes lze strávit úspěšnou kariéru jenom kombinací knihoven.

Řešit ve smyslu navrhovat nebo jen implementovat?

To je dobrá otázka. Myslím že i navrhovat, ale jsem moc mlád abych to pamatoval.

Nikdy neni pozde zacit vynalezat kolo.

Pod "navrhovat" se ovšem představuju vymyslet něco nového, co ještě není.

k tomu je třeba znát co už bylo vymyšleno.

To už je každého problém, jestli si to zjistí. V nejhorším vymyslí kolo, ale rozumný člověk bude vynakládat síly jen na něco nového.

580

Vývoj / Re:Dědičnost dnes

« kdy: 01. 02. 2017, 13:04:02 »

v té době ještě vývojáři sem tam potřebovali řešit algoritmy - dnes lze strávit úspěšnou kariéru jenom kombinací knihoven.

Řešit ve smyslu navrhovat nebo jen implementovat?

To je dobrá otázka. Myslím že i navrhovat, ale jsem moc mlád abych to pamatoval.

Nikdy neni pozde zacit vynalezat kolo.

Pod "navrhovat" se ovšem představuju vymyslet něco nového, co ještě není.

581

Vývoj / Re:Dědičnost dnes

« kdy: 01. 02. 2017, 11:18:00 »

v té době ještě vývojáři sem tam potřebovali řešit algoritmy - dnes lze strávit úspěšnou kariéru jenom kombinací knihoven.

Řešit ve smyslu navrhovat nebo jen implementovat?

582

/dev/null / Re:Co považujete za nejdůležitější?

« kdy: 01. 02. 2017, 10:31:43 »

Jaderna fuze nic neresi. Kdyz jsou zdroje levne, proste se s nimi zacne vic plytvat. Bez ohledu na dusledky. Neomezene levna energie by bez vyraznych spolecenskych zmen prinesla jen horsi ekologicke katastrofy.

Vzpomnel jsem si na roman Down and Out in the Magic Kingdom. Je znama tim, ze v ni Doctorow popularizoval menu zalozenou na reputaci ("whuffie") v post-scarcity ekonomice (a dodava, ze takovy popularity contest by vedl k narustu socialnich nerovnosti). Mne utkvelo hlavne to, jak si zalohovali telo/mozek/vzpominky. Kdyz se stal nejaky prusvih, proste se obnovili ze zalohy. Uvazte, jaky by v takove spolecnosti byl zajem venovat se soucasne medicine ve smyslu lecby. Nebo se na tom dobre demonstruje, jak moralni hodnoty zavisi na aktualni spolecnosti: ted je u nas znasilneni povazovano za zverstvo s dozivotnim traumatem, ale ve spolecnosti, kde by stacilo obnovit se ze zalohy (nebo jen upravit vzpominky)?

Takze, co dnes povazuji za dulezite? Udrzovat kvalitni mezilidske vztahy, zit skromne a v miru. Tak nejak jit prikladem. Protoze jinak muzeme s neomezenou energii kolonizovat Mars nebo co jak vim... a stejne byt nestastni a pristupem "po nas potopa" si k tomu i dat duvody.

Na sociální nerovnosti není nic špatného. Podstatné je, za co získáte vyšší společenský status, pokud za úspěchy na volném trhu, je to v pořádku. Kognitivní funkce kolektivu zůstanou zachovány, pokud ho získáte za následování přesvědčení elit o tom co je správně, dojde ke zhroucení kognitivních funkcí kolektivu a civilizačnímu regresu. Až tak jednoduché to je.

Dnes probíhá druhá reformace, kdy elity přestaly plnit svou funkci a získaly přesvědčení, že jsou samy schopny nelézt správný směr a že ostatní k tomu nepotřebují. A to byla přesně situace před první reformací. Ta byla technologicky tažena vynálezem knihtisku, kdy pravdu mohl hledat každý, ne jen elity. Dnes bude druhá reformace tažena rozšířením internetu, kdy pravdu lze hledat samostatně díky přístupu k informacím. Podstatou každé reformace je zbavení elit jejich patentu na pravdu.

Tedy nejdůležitější je, abyste každý hledali pravdu samostatně a podle vlastních zájmů a přitom nemysleli na lidstvo, ale na sebe a přitom nepodléhali vlivu falešných elit. O zájmy lidstva se stará trh a ne elity, těm k tomu schází potřebný nadhled.

Jo, máme přístup k informacím, hlavně k fake news

583

Vývoj / Re:Dědičnost dnes

« kdy: 31. 01. 2017, 22:47:12 »

Důkaz?

To prave nelze ani dokazat ani vyvratit.

No pana Hilberta se už asi nezeptáme...

584

Vývoj / Re:Dědičnost dnes

« kdy: 31. 01. 2017, 22:23:23 »

čímž nasrali pana Hilberta

Hilbert byl nasranej, protoze na neho v hospode zbyla zidle, stul, ale zadnej korbel piva!

Důkaz?

585

Vývoj / Re:Dědičnost dnes

« kdy: 31. 01. 2017, 22:06:12 »

A nebo prostě trvá, než si na to lidi zvyknou.

Tak me napada, podobna situace je i v matematice. Vetsina matematiku pouziva normalni predikatovou logiku, ale lambda kalkulus (treba kalkulus konstrukci) by mozna byl praktictejsi. Jde zase jen o zvyk. :-) (Ne docela, je tady cela ta otazka konstruktivismu..)

Sorry, ale predikátová logika a lambda kalkulus nejsou alternativou jeden druhému. Navíc predikátová logika je formálně silnější.

Lambda calculus je turingovo kompletny. Ino by islo opisat predikatovu logiku lambda calculom, len by to bolo ako skrabanie sa lavou rukou za pravym uchom. Sklamem vas, ale lambda calculus je silnejsi, zvladne kazdy vypocitatelny problem.

Co to je za kecy? Zjisti si, co znamená turingovsky kompletní a kam ve výpočetní hierarchii spadá formální logika. Pak se můžeme bavit, proč je logika nerozhodnutelná a co je z ní třeba odebrat, aby byla.

Poprosim dokaz. Pak se budem bavit, vole.

Na této úrovni se bavit nebudeme. Poslední, co ti řeknu, je, že nerozhodnutelnost predikátové logiky dokázali pánové Church a Turing (nezávisle na sobě) ve 30. letech minulého století, čímž nasrali pana Hilberta. Jejich důkaz(y) si můžeš najít, když na chvíli přestaneš trollit.