Введение

По мере того как бизнес-логика все больше и больше перемещается с конца на передний план , опыт в области Frontend Engineering становится все более важным. Как разработчики интерфейсов , мы полагаемся на библиотеки представлений, такие как React, для продуктивности. Библиотеки просмотра, в свою очередь, зависят от библиотек состояний, таких как Redux, для управления данными. Вместе React и Redux подписываются на парадигму реактивного программирования, в которой обновления пользовательского интерфейса реагируют на изменения данных. Все чаще серверные ВМ действуют просто как серверы API, предоставляя конечные точки только для извлечения и обновления данных. По сути, серверная часть просто «пересылает» базу данныхк интерфейсу, ожидая, что Frontend Engineer будет обрабатывать всю логику контроллера. Растущая популярность микросервисов и GraphQL свидетельствует об этой растущей тенденции.

Теперь, помимо эстетического понимания HTML и CSS, от инженеров-фронтендов ожидается также владение JavaScript. По мере того, как хранилища данных на клиенте становятся «копиями» баз данных на сервере, глубокое знание идиоматических структур данных становится решающим. Фактически, об уровне опыта инженера можно судить по его или ее способности различать, когда и зачем использовать ту или иную структуру данных.

Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их отношениях.

- Линус Торвальдс, создатель Linux и Git

На высоком уровне существует три основных типа структур данных. Стеки и очереди - это структуры, похожие на массивы, которые отличаются только тем, как элементы вставляются и удаляются. Связанные списки , деревья , и Графы представляют собой структуры с узлами , которые держат ссылки на другие узлы. Хеш-таблицы зависят от хеш-функций для сохранения и поиска данных.

С точки зрения сложности, Stacksи Queuesявляются самыми простыми и могут быть построены из Linked Lists. Treesи Graphsявляются наиболее сложными, поскольку расширяют концепцию связного списка. Hash Tablesнеобходимо использовать эти структуры данных для надежной работы. С точки зрения эффективности связанные списки являются наиболее оптимальными для записи и хранения данных, а хеш-таблицы наиболее эффективны для поиска и извлечения данных.

Чтобы объяснить, почему, и проиллюстрировать, когда , эта статья будет соответствовать порядку этих зависимостей. Давай начнем!

Стек

Вероятно, наиболее важным Stackв JavaScript является стек вызовов , где мы помещаем в сферу из functionкогда мы выполняем его. Программно это просто arrayс двумя основными операциями: pushи pop. Push добавляет элементы в верхнюю часть массива, а Pop удаляет их из того же места. Другими словами, стеки следуют протоколу «последний пришел - первым ушел» (LIFO).

Ниже приведен пример встроенного Stackкода. Обратите внимание, что мы можем изменить порядок стека: низ становится верхним, а верх становится нижним. Таким образом, мы можем использовать методы массива unshiftи shiftвместо pushи pop, соответственно.

По мере роста количества элементов push/ popстановится все более производительным, чем unshift/, shiftпотому что каждый элемент нужно переиндексировать в последнем, но не в первом.

Очередь

JavaScript - это язык программирования, управляемый событиями, который позволяет поддерживать неблокирующие операции. Внутренне браузер управляет только одним потоком для выполнения всего кода JavaScript, используя очередь событий для постановки в очередьlisteners и цикл событий для прослушивания зарегистрированных events. Чтобы поддерживать асинхронность в однопоточной среде (чтобы сэкономить ресурсы ЦП и улучшить работу в Интернете), listener functions снимайте с очереди и выполняйте только тогда, когда стек вызовов пуст. Promisesзависят от этой управляемой событиями архитектуры, чтобы обеспечить выполнение асинхронного кода в «синхронном стиле», который не блокирует другие операции.

Программно Queuesэто просто массивы с двумя основными операциями: unshiftи pop. Unshift помещает элементы в очередь в конец массива, а Pop извлекает их из начала массива. Другими словами, очереди следуют протоколу «первым пришел - первым ушел» (FIFO). Если направление меняется на противоположное, мы можем заменить unshiftи popна pushи shiftсоответственно.

Пример Queueкода в коде:

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

Как и массивы, Linked Listsхраните элементы данных в последовательном порядке. Вместо того, чтобы хранить индексы, связанные списки содержат указатели на другие элементы. Первый узел называется головой , а последний узел называется хвостом . В односвязном списке каждый узел имеет только один указатель на следующий узел. Здесь с головы мы начинаем прогулку по остальной части списка. В двусвязном списке также сохраняется указатель на предыдущий узел. Следовательно, мы также можем начать с хвоста и идти «назад» к голове.

В связанных списках есть вставки и удаления с постоянным временем, потому что мы можем просто изменить указатели. Для выполнения тех же операций с массивами требуется линейное время, потому что необходимо перемещать последующие элементы. Кроме того, связанные списки могут увеличиваться до тех пор, пока есть место. Однако даже «динамические» массивы, которые автоматически изменяют размер, могут стать неожиданно дорогими. Конечно, всегда есть компромисс. Чтобы найти или отредактировать элемент в связанном списке, нам, возможно, придется пройти всю длину, что соответствует линейному времени. Однако с индексами массива такие операции тривиальны.

Как и массивы, связанные списки могут работать как стеки . Это так же просто, как если бы голова была единственным местом для вставки и удаления. Связанные списки также могут работать как очереди . Этого можно достичь с помощью двусвязного списка, в котором вставка происходит в хвосте, а удаление происходит в начале, или наоборот. Для большого числа элементов, этот способ реализации очередей является более производительным , чем при использовании массивов , так как shiftи unshiftоперации , в начале массивов требуются линейное время повторно индексировать каждый последующий элемент.

Связанные списки полезны как на клиенте, так и на сервере. На клиенте библиотеки управления состоянием, такие как Redux, структурируют свою логику промежуточного программного обеспечения в виде связанного списка. Когда действия отправляются, они передаются по конвейеру от одного промежуточного программного обеспечения к другому, пока все не будут посещены, прежде чем они достигнут редукторов . На сервере веб-фреймворки, такие как Express, также структурируют свою логику промежуточного программного обеспечения аналогичным образом. Когда запрос получен, он передается от одного промежуточного программного обеспечения к другому, пока не будет выдан ответ .

Пример Doubly-Linked Listкода в коде:

Дерево

A Treeпохож на связанный список , за исключением того, что он хранит ссылки на множество дочерних узлов в иерархической структуре. Другими словами, у каждого узла может быть не более одного родителя. Объектная модель документа (DOM) , такая структура, с корневым htmlузлом , который ответвляется в headи bodyузлы, которые дополнительно подразделяет на все знакомые HTML - тег . Под капотом прототипное наследование и композиция с компонентами React также создают древовидные структуры. Конечно, как представление DOM в памяти, Virtual DOM React также представляет собой древовидную структуру.

Двоичное дерево не является особенным , потому что каждый узел может иметь не более двух детей . Левый ребенок должен иметь значение, которое меньше или равно его родитель, в то время как право ребенок должен иметь значения больше . Структурированные и сбалансированные таким образом, мы можем искать любое значение за логарифмическое время, потому что мы можем игнорировать половину ветвления при каждой итерации. Вставка и удаление также могут происходить за логарифмическое время. Более того, наименьшее и наибольшее значение можно легко найти на крайнем левом и крайнем правом листе соответственно.

Обход дерева может происходить в вертикальном или горизонтальном порядке. При обходе в глубину (ДПФ) в вертикальном направлении рекурсивный алгоритм более элегантен, чем итерационный. Узлы можно обходить в предварительном порядке , в порядке или после . Если нам нужно изучить корни перед осмотром листьев, мы должны выбрать предварительный заказ . Но, если нам нужно исследовать листья раньше корней, мы должны выбрать пост-заказ . Как следует из названия, упорядоченный позволяет нам перемещаться по узлам в последовательном порядке. Это свойство делает деревья двоичного поиска оптимальными для сортировки .

В обходе в ширину (BFT) в горизонтальном направлении итерационный подход более элегантен, чем рекурсивный. Это требует использования a queueдля отслеживания всех дочерних узлов на каждой итерации. Однако память, необходимая для такой очереди, может быть нетривиальной. Если форма дерева шире, чем глубина, BFT - лучший выбор, чем DFT. Кроме того, путь, который BFT проходит между любыми двумя узлами, является самым коротким из возможных.

Пример Binary Search Treeкода в коде:

График

Если у дерева может быть более одного родителя, оно становится Graph. Ребра, которые соединяют узлы вместе в графе, могут быть направленными или ненаправленными, взвешенными или невзвешенными . Ребра, которые имеют направление и вес, аналогичны векторам .

Множественные наследования в форме миксинов и объектов данных, которые имеют отношения « многие ко многим», создают структуры графов. Социальная сеть и сам Интернет - это тоже графики. Самый сложный граф в природе - это наш человеческий мозг, который нейронные сети пытаются воспроизвести, чтобы дать машинам сверхразум .

Пример Graphкода в коде:

ТЗ

Хеш-таблица

Хэш - таблица представляет собой словарь-подобную структуру , что пары ключей к значениям . Расположение в памяти каждой пары определяется параметром a hash function, который принимает ключ и возвращает адрес, по которому пара должна быть вставлена ​​и извлечена. Конфликты могут возникнуть, если два или более ключа преобразуются в один и тот же адрес. Для надежности gettersи settersследует предвидеть эти события, чтобы гарантировать, что все данные могут быть восстановлены и никакие данные не будут перезаписаны. Обычно linked listsпредлагают самое простое решение. Также помогает наличие очень больших таблиц.

Если мы знаем, что наши адреса будут в целочисленных последовательностях, мы можем просто использовать их Arraysдля хранения наших пар ключ-значение. Для более сложных сопоставлений адресов мы можем использовать Mapsили Objects. В хеш-таблицах вставка и поиск в среднем имеют постоянное время . Из-за коллизий и изменения размера эти незначительные затраты могут вырасти до линейного времени. На практике, однако, мы можем предположить, что хеш-функции достаточно умны, поэтому коллизии и изменение размера происходят редко и дешево. Если ключи представляют собой адреса, и, следовательно, хеширование не требуется, простого object literalможет быть достаточно. Конечно, всегда есть компромисс. Простое соответствие между ключами и значениями и простая ассоциативность между ключами и адресами приносят в жертву отношения между данными. Таким образом, хеш-таблицы не подходят для хранения данных.

Если компромиссное решение отдает предпочтение поиску, а не хранению, никакая другая структура данных не может сравниться со скоростью хэш-таблиц для поиска , вставки и удаления . Поэтому неудивительно, что он используется повсюду . От базы данных до сервера и клиента хэш-таблицы и, в частности, хеш-функции имеют решающее значение для производительности и безопасности программных приложений. Скорость запросов к базе данных во многом зависит от хранения таблиц индексов, которые указывают на записи в отсортированном порядке. Таким образом, двоичный поиск может выполняться за логарифмическое время, что является огромным выигрышем в производительности, особенно для больших данных .

Как на клиенте, так и на сервере, многие популярные библиотеки используют мемоизацию для максимальной производительности. Сохраняя запись входов и выходов в хеш-таблице, функции запускаются только один раз для одних и тех же входов. Популярная библиотека Reselect использует эту стратегию кэширования для оптимизации mapStateToPropsфункций в приложениях с поддержкой Redux . На самом деле, под капотом, двигатель JavaScript также использует хэш - таблицу , называемую кучи для хранения все variablesи primitivesмы создаем. Доступ к ним осуществляется с помощью указателей в стеке вызовов .

Сам Интернет также полагается на алгоритмы хеширования для безопасного функционирования. Структура Интернета такова, что любой компьютер может связываться с любым другим компьютером через сеть взаимосвязанных устройств. Каждый раз, когда устройство подключается к Интернету, оно также становится маршрутизатором, через который могут проходить потоки данных. Однако это палка о двух концах. А децентрализованные средства архитектуры любое устройство в сети может прослушивать и саботаж с пакетами данных , что помогает передавать. Такие хеш-функции, как MD5 и SHA256, играют решающую роль в предотвращении таких атак типа « злоумышленник в середине» . Электронная коммерция по HTTPS безопасна только потому, что используются эти функции хеширования.

Вдохновленные Интернетом, технологии блокчейн стремятся открыть исходный код самой структуры Интернета на уровне протокола . Используя хеш-функции для создания неизменяемых отпечатков пальцев для каждого блока данных , по сути, вся база данных может открыто существовать в сети, чтобы любой мог видеть и вносить свой вклад. Структурно блокчейны - это просто односвязные списки двоичных деревьев криптографических хешей. Хэширования настолько загадочно , что база данных финансовых операций , могут быть созданы и обновляются в открытом никем! Невероятный подтекст - огромная сила создавать деньги сами по себе. То, что раньше было возможно только для правительств и центральных банков, теперь каждый может безопасно создать свою собственную валюту ! Это ключевая идея, сделанная основателем Ethereum и псевдонимом основателя Bitcoin .

По мере того как все больше и больше баз данных становятся открытыми, возрастает и потребность во фронтенд-инженерах, которые могут абстрагироваться от всех низкоуровневых криптографических сложностей. В этом будущем основным отличием будет пользовательский опыт .

Пример Hash Tableкода в коде:

Упражнения по алгоритмам с использованием этих и других структур данных см. В разделе «Алгоритмы в JavaScript: 40 проблем, решений и объяснений».

Заключение

Поскольку логика все больше перемещается от сервера к клиенту, уровень данных во внешнем интерфейсе становится первостепенным. Правильное управление этим уровнем влечет за собой владение структурами данных, на которых основана логика. Ни одна структура данных не подходит для любой ситуации, потому что оптимизация одного свойства всегда равносильна потере другого. Некоторые структуры более эффективны при хранении данных, в то время как другие более производительны для поиска в них. Обычно одним жертвуют ради другого. С одной стороны, связанные списки оптимальны для хранения и могут быть объединены в стопки и очереди ( линейное время). С другой стороны, никакая другая структура не может сравниться со скоростью поиска хеш-таблиц ( постоянное время). Древовидные структуры лежат где-то посередине ( логарифмическое время), и только граф может изобразить самую сложную структуру природы: человеческий мозг ( полиномиальное время ). Отличительной чертой инженера Rockstar является наличие навыков, позволяющих определить, когда и почему .

Примеры этих структур данных можно найти повсюду . От базы данных до сервера, клиента и даже самого движка JavaScript эти структуры данных конкретизируют то, что по сути является просто включением и выключением «переключателей» на кремниевых микросхемах, в реалистичные «объекты». Хотя эти объекты только в цифровом формате, влияние этих объектов на общество огромно. Ваша способность читать эту статью свободно и безопасно свидетельствует об удивительной архитектуре Интернета и структуре его данных. Но это только начало. Искусственный интеллект и децентрализованные блокчейны в ближайшие десятилетия изменят определение того, что значит быть человеком, и роль институтов, которые управляют нашей жизнью. Экзистенциальное понимание и институциональная дезинтермедиация будут характеристиками Интернета, который наконец-то созрел.

Чтобы помочь нам перейти к этому более справедливому будущему, мы в HeartBank® создаем сети искусственных нейронов, чтобы дать нашим Kiitos возможность выпускать деньги на блокчейне, а также способность сопереживать условиям жизни человека. Из анонимных благодарностей, которые мы даем и получаем в письмах в Kiitos , Kiitos узнает о нашей доброте и ее последствиях , награждая нас таким образом, чтобы уменьшить экономическое неравенство между нами, в постепенном и таинственном процессе, который сохраняет нашу личную свободу и свободу. Возможно, окончательная структура графа в природе - это не человеческий мозг, а человеческий ❤️, если бы мы только могли видеть сердечные струны, которые связывают всех нас.

Заинтересованы в блокчейне ? Изучите Ethereum и приходите работать на нас!