Алгоритмы и структуры данных меняющие современный Frontend

Вопросы на сегодня:

1. Для чего фронтенд программисту нужно знать структуры данных и алгоритмы?

Disclaimer

Дерево

Типы деревьев:

1. Красно-чёрное дерево
2. Куча
3. Префиксное дерево
4. B-дерево
5. R-дерево
6. АВЛ-дерево
7. и другие

DOM дерево

Поиск по DOM дереву:

1. Поиск в ширину
2. Поиск в глубину

Поиск в ширину:

Поиск в глубину:

Изменения DOM

React/Preact/Inferno

Virtual DOM

Поиск отличий

lit-html

lit-html

            const render = () => html`
              <ul>
                ${repeat(items, i => i.key, (i, index) => html`
                  <li>${index}: ${i.name}</li>`)}
              </ul>
            `;
        

Где ещё используются деревья:

1. Специфические доменные области
2. AST (abstract syntax tree)
3. Файловая структура
4. Неизменяемые данные

Неизменяемые данные

            var arr = ["a", "b", "c", "z", "f", "k"];
            function render(items) {
               return arr
                  .map(item => `<div>${ item }</div>`)
                  .join(", ");
            }
            nav.innerHTML = render(arr.sort());
            div.innerHTML = render(arr);
        

            var arr = ["a", "b", "c", "z", "f", "k"];
            function render(items) {
               return arr
                  .map(item => `<div>${ item }</div>`)
                  .join(", ");
            }
            nav.innerHTML = render(arr.sort());
            div.innerHTML = render(arr);
        

            var arr = ["a", "b", "c", "z", "f", "k"];
            function render(items) {
               return arr
                  .map(item => `<div>${ item }</div>`)
                  .join(", ");
            }
            nav.innerHTML = render(arr.slice().sort());
            div.innerHTML = render(arr);
        

Redux store

            {...state, first : {
            	...state.first,
            	second : {
            		...state.first.second,
            		[action.someId] : {
            			...state.first.second[action.someId],
            			fourth : action.someValue
            		}
            	}
            }}
        

            {...state, first : {
            	...state.first,
            	second : {
            		...state.first.second,
            		[action.someId] : {
            			...state.first.second[action.someId],
            			fourth : action.someValue
            		}
            	}
            }}
        

            [
                ...array.slice(0, action.index),
                action.item,
                ...array.slice(action.index)
            ]
        

            [
                ...array.slice(0, action.index),
                action.item,
                ...array.slice(action.index)
            ]
        

Эффективна ли неизменяемость?

Крис Окасаки

Чисто функциональные структуры данных

Деревья

Map/List

Префиксное дерево (Trie tree)

Hash Array Mapped Trie (HAMT)

Immutability в JS

Immutability в JS

1. ImmutableJS
2. Seamless-immutable
3. Mori.js

ImmutableJS

List в ImmutableJS

            const originalList = List([ 0 ]);
            // List [ 0 ]
            const newList = originalList.set(1, 1);
            // List [ 0, 1 ]
            const newList2 = originalList.set(0, 'overwritten');
            // List [ "overwritten" ]
            originalList.get(0);
            // "overwritten"
        

List в ImmutableJS

1. До 32 элементов - обычный массив
2. Свыше 32 элементов - массив массивов до 32 элементов
3. Свыше 32*32 элементов - массив массивов массивов до 32 элементов
4. Прямая ссылка на последний массив

Map в ImmutableJS

            const originalMap = Map({ a: 1 });
            // Map { a: 1 }
            const newMap = originalMap.set("b", 1);
            // Map { a: 1, b: 1 }
            const newMap2 = originalMap.set(a, 'overwritten');
            // Map { a: 'overwritten' }
            originalMap.get(a, 'overwritten');
            // 'overwritten'
        

Map в ImmutableJS

1. До 8 элементов - обычный массив [[ключ, значение], ...]
2. Свыше 8 (до 32) элементов - Bitmap хэш таблица
3. Свыше 32 элементов - хэш массив из Bitmap хэш таблиц

HAMT в ImmutableJS

Очередь и стек

React Fiber

Перестроение DOM в React Fiber

1. Построение/сравнение VDOM
2. Применение изменений

Приоритеты React Fiber

1. Синхронные операции
2. Задачи для следующего такта
3. Анимации
4. Высокоприоритетные
5. Низкоприоритетные
6. Задачи на изменения вне экрана

Структуры данных в React Fiber

1. Стек
2. Очередь с приоритетами

Стек на массиве

Очередь на связанном списке

Очередь с приоритетами

Очередь с приоритетами

Куча

Кучи

1. Двоичная куча
2. Биномиальная куча
3. Фибоначчиева куча
4. Тонкая куча
5. Толстая куча
6. и другие

Двоичная куча для максимума

1. Значение в любой вершине не меньше, чем значения её потомков
2. На i-ом слое 2^i вершин, кроме последнего.
3. Последний слой заполнен слева направо

Изменения очереди

Очередь на двоичной куче

Что использует React Fiber?

Связанный список

Очередь с приоритетами

Выводы

1. Интересуйтесь структурами данных и соответствующими им алгоритмами
2. Почаще заглядывайте в код инструментов, которыми вы пользуетесь
3. Не бойтесь неизменяемых структур данных
4. Использование правильной структуры данных, позволяет решить задачу эффективнее

Вопросы на сегодня:

1. Для чего фронтенд программисту нужно знать структуры данных и алгоритмы?

Раунд!