Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni
🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!24.08.2024
Функціональні структури даних
Теоретична частина: поставив собі питання — яким чином функціональні мови здатні… функціонувати, коли вони ніби повинні без кінця копіювати значення для збереження незмінності? Це ж повинно бути надзвичайно неефективно, особливо коли структури даних більшають.
Коротка відповідь: функціональні мови використовують особливі структури даних, які зокрема дозволяють зберігати незмінену частину без копіювання. Як виявилося, існує величезна академічна та практична база за цим питанням.Направляю у вікіпедію за подробицями.
Та другий аспект — як я зрозумів, ліниві обчислення насамперед корисні тим, що дозволяють групувати низку перетворень, а значить — уникати зберігання проміжних результатів.
Виходить, що чисто функціональна мова (або чисто функціональна бібліотека) здатна хоча б наблизитись за швидкістю до імперативної. Що досить суттєвий аргумент за використання функціональної мови “від природи” замість ФП імперативною мовою, що я відразу вирішив перевірити на JavaScript.
Та тут практична частина: зробив невеличкий тестовий скрипт; задача — підрахувати кількістю ключів у SteamDB, довших за 5 символів. Така досить класична функціональна задача на поважному обсязі в 163 Мб даних. Що маємо:
- Функціональне рішення лише у 2 рази повільніше за імперативне (яке не приводжу заради стислості):
json.reduce((a, r) => a + Object.keys(r).filter((k) => k.length > 5).length, 0);
-
Таке саме рішення, але з використанням відомої бібліотеки Immutable, в 10 разів повільніше за попереднє! Висновок: на практиці ціна функціональних структур даних перевищує витрати на копіювання традиційних.
-
Та саме цікаве: думаю, ну добре, але ось ClojureScript точно повинен робити все правильно та ефективно. Але ні: код на ClojureScript був ще в 4 рази повільніше за Immutable, тобто у 80 разів повільніший за імперативне рішення!
(reduce + 0 (map
(fn [r]
(count (filter #(> (count %) 5) (keys r))))
json))
Висновок: я вірю, що якщо взяти низькорівневу мову та реалізувати функціональні структури близько до заліза, можливо, з власним керуванням памʼяттю, то це може бути швидко (Тобто, наприклад, варіант Haskell, а можливо й Clojure без -script.) Але в імперативній мові вони навряд чи зроблять функціональний код швидше.