ΠΡΠ±Π»ΠΈΠΊΡΠ²Π°Π½ΠΈ ΡΠ° ΠΏΡΡΠ²ΠΈΡΠ΅ ΠΈΠ·Π΄Π°Π½ΠΈΡ Π½Π° ΠΏΡΠΎΠ΅ΠΊΡΠ° 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
