Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

24.12.2023

Дев-адвент 24: звʼязаний список

🎄 Всіх з Різдвом, хто святкує! Дізнався, що в App Store вже кілька років немає різдвяних канікул, та публікувати програми можна протягом всіх зимових свят. Що приємно, бо до Нового року я як раз дотягну решту функціонала.

Сьогодні нарешті закінчив роботу над збереженням стану системи та інкрементальним оновленням.

Як один з останніх нюансів, знайшов ефективнішу схему зберігання розвʼязку свого алгоритму. Як я писав, алгоритм будує розвʼязки для більших послідовностей через розвʼязки для коротших; але раніше я зберігав кожний розвʼязок наново. Виходила купа даних з квадратичним характером зростання.

Так от, зрозумів, що можна буквально зберігати кожну нову послідовність через номер коротшої послідовності, з якої вона побудована; виходить такий звʼязаний список. Тепер розмір даних зростає лінійно — та ще й без зайвого копіювання. Ба більше, я майже впевнений, що коли ми вчили динамічне програмування, то так воно й зберігалося.

Наступний етап — нарешті, доповнення історії різними цікавими статистичними фактами.