ΠΠΏΡΠ±Π»ΠΈΠΊΠΎΠ²Π°Π½Ρ ΠΏΠ΅ΡΠ²ΡΠ΅ Π²ΡΠΏΡΡΠΊΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠ° Bend, ΡΠ°Π·Π²ΠΈΠ²Π°ΡΡΠ΅Π³ΠΎ Π²ΡΡΠΎΠΊΠΎΡΡΠΎΠ²Π½Π΅Π²ΡΠΉ ΡΠ·ΡΠΊ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π΄Π»Ρ ΠΏΠ°ΡΠ°Π»Π»Π΅Π»ΡΠ½ΡΡ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠΉ, ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠ·ΠΈΡΠΈΠΎΠ½ΠΈΡΡΠ΅ΡΡΡ ΠΊΠ°ΠΊ Π°Π»ΡΡΠ΅ΡΠ½Π°ΡΠΈΠ²Π° Π½ΠΈΠ·ΠΊΠΎΡΡΠΎΠ²Π½Π΅Π²ΡΠΌΠΈ ΡΠ·ΡΠΊΠ°ΠΌ, ΡΠ°ΠΊΠΈΠΌ ΠΊΠ°ΠΊ CUDA ΠΈ Metal, ΠΎΠ±Π»Π°Π΄Π°ΡΡΠ°Ρ Π²ΡΡΠ°Π·ΠΈΡΠ΅Π»ΡΠ½ΡΠΌ ΡΠΈΠ½ΡΠ°ΠΊΡΠΈΡΠΎΠΌ ΠΈ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡΠΌΠΈ Π΄Π»Ρ ΠΏΠΎΠ²ΡΡΠ΅Π½ΠΈΡ ΡΠ΄ΠΎΠ±ΡΡΠ²Π° ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ, ΡΠ²ΠΎΠΉΡΡΠ²Π΅Π½Π½ΡΠΌΠΈ ΡΠ°ΠΊΠΈΠΌ ΡΠ·ΡΠΊΠ°ΠΌ, ΠΊΠ°ΠΊ Python ΠΈ Haskell. ΠΠΎΠ΄ ΠΏΡΠΎΠ΅ΠΊΡΠ° Π½Π°ΠΏΠΈΡΠ°Π½ Π½Π° ΡΠ·ΡΠΊΠ΅ Rust ΠΈ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½ΡΠ΅ΡΡΡ ΠΏΠΎΠ΄ Π»ΠΈΡΠ΅Π½Π·ΠΈΠ΅ΠΉ Apache 2.0.
ΠΠ· Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΠ΅ΠΉ ΡΠ·ΡΠΊΠ° Bend ΠΎΡΠΌΠ΅ΡΠ°Π΅ΡΡΡ Π±ΡΡΡΡΠΎΠ΅ ΡΠ°ΡΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΠΎΠ², Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΡ ΡΡΠ½ΠΊΡΠΈΠΉ Π²ΡΡΡΠ΅Π³ΠΎ ΠΏΠΎΡΡΠ΄ΠΊΠ°, Π·Π°ΠΌΡΠΊΠ°Π½ΠΈΠΉ, ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ΅Π½ΠΈΠΉ, Π½Π΅ΠΎΠ³ΡΠ°Π½ΠΈΡΠ΅Π½Π½ΠΎΠΉ ΡΠ΅ΠΊΡΡΡΠΈΠΈ, ΡΠΎΠΏΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Ρ ΠΎΠ±ΡΠ°Π·ΡΠΎΠΌ, ΡΠ΅ΠΊΡΡΡΠΈΠ²Π½ΡΡ ΡΠΎΠΏΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΠΉ (fold) ΠΈ ΡΠΈΠΊΠ»ΠΎΠ² (bend), ΡΠ΅Π»ΠΎΡΠΈΡΠ»Π΅Π½Π½ΡΡ , ΡΡΡΠΎΠΊΠΎΠ²ΡΡ ΠΈ ΡΠΏΠΈΡΠΎΡΠ½ΡΡ ΡΠΈΠΏΠΎΠ². ΠΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅ΡΡΡ Π΄Π²Π° Π²Π°ΡΠΈΠ°Π½ΡΠ° ΡΠΈΠ½ΡΠ°ΠΊΡΠΈΡΠ° — Π² ΡΡΠΈΠ»Π΅ Python ΠΈ Π² ΡΡΠΈΠ»Π΅ Haskell. Π ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°Ρ Π½Π΅ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ ΡΠΊΠ°Π·Π°Π½ΠΈΠ΅ ΡΠΏΡΠ°Π²Π»ΡΡΡΠΈΡ ΡΠ°ΡΠΏΠ°ΡΠ°Π»Π΅Π»Π»ΠΈΠ²Π°Π½ΠΈΠ΅ΠΌ Π°Π½Π½ΠΎΡΠ°ΡΠΈΠΉ, ΡΠ²Π½ΠΎΠ³ΠΎ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΠΏΠΎΡΠΎΠΊΠΎΠ² ΠΈ Π²ΡΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π±Π»ΠΎΠΊΠΈΡΠΎΠ²ΠΎΠΊ. Π Π°ΡΠΏΠ°ΡΠ°Π»Π»Π΅Π»ΠΈΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΡΡ Π°Π²ΡΠΎΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠΈ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠΈ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΠΈ Π²ΡΡΠ°ΠΆΠ΅Π½ΠΈΡ «((1 + 2) + (3 + 4))», ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ «1 + 2» ΠΈ «3 + 4» Π±ΡΠ΄ΡΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½Ρ ΠΏΠ°ΡΠ°Π»Π»Π΅Π»ΡΠ½ΠΎ.
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π½Π° ΡΠ·ΡΠΊΠ΅ Bend ΠΌΠΎΠ³ΡΡ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ Π½Π° ΠΎΠ±ΠΎΡΡΠ΄ΠΎΠ²Π°Π½ΠΈΠΈ, ΠΎΠ±Π΅ΡΠΏΠ΅ΡΠΈΠ²Π°ΡΡΠ΅ΠΌ ΠΌΠ°ΡΡΠΎΠ²ΡΠΉ ΠΏΠ°ΡΠ΅Π»Π»Π΅Π»ΠΈΠ·ΠΌ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, Π½Π° GPU, Π΄Π΅ΠΌΠΎΠ½ΡΡΡΠΈΡΡΡ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ Π»ΠΈΠ½Π΅ΠΉΠ½ΡΠΉ ΡΠΎΡΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π² Π·Π°Π²ΠΈΡΠΈΠΌΠΎΡΡΠΈ ΠΎΡ ΡΠΈΡΠ»Π° Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΡΠ΄Π΅Ρ. ΠΠΎΠ΄ Π½Π° ΡΠ·ΡΠΊΠ΅ Bend ΠΊΠΎΠΌΠΏΠΈΠ»ΠΈΡΡΠ΅ΡΡΡ Π² Π½ΠΈΠ·ΠΊΠΎΡΡΠΎΠ²Π½Π΅Π²ΠΎΠ΅ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΠΎΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ HVM2 (Higher-order Virtual Machine 2), ΠΊΠΎΡΠΎΡΠΎΠ΅ Π·Π°ΡΠ΅ΠΌ ΠΊΠΎΠΌΠΏΠΈΠ»ΠΈΡΡΠ΅ΡΡΡ Π² ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ Π½Π° C ΠΈ CUDA. Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ ΠΏΡΠΎΠ΅ΠΊΡΠΎΠΌ ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π½Π° GPU NVIDIA.
Π§ΡΠΎ ΠΊΠ°ΡΠ°Π΅ΡΡΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ, ΡΠΎ ΡΠ΅ΡΡΠΎΠ²ΠΎΠ΅ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠ΅ΠΉ Π±ΠΈΡΠΎΠ½Π½ΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ, ΠΏΡΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΏΠΎΡΠΎΠΊΠ΅ CPU Apple M3 Max Π±ΡΠ»ΠΎ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΎ Π·Π° 12.15 ΡΠ΅ΠΊ., ΠΏΡΠΈ Π·Π°Π΄Π΅ΠΉΡΡΠ²ΠΎΠ²Π°Π½ΠΈΠΈ 16 ΠΏΠΎΡΠΎΠΊΠΎΠ² — Π·Π° 0.96 ΡΠ΅ΠΊ., Π° ΠΏΡΠΈ ΠΏΡΠΈΠ²Π»Π΅ΡΠ΅Π½ΠΈΠΈ GPU NVIDIA RTX 4090 Ρ 16k ΠΏΠΎΡΠΎΠΊΠ°ΠΌΠΈ — Π·Π° 0.21 ΡΠ΅ΠΊ. def sort(d, s, tree): switch d: case 0: return tree case _: (x,y) = tree lft = sort(d-1, 0, x) rgt = sort(d-1, 1, y) return rots(d, s, lft, rgt) def rots(d, s, tree): switch d: case 0: return tree case _: (x,y) = tree return down(d, s, warp(d-1, s, x, y)) …
ΠΡΡΠΎΡΠ½ΠΈΠΊ: opennet.ru