Практика проектирования систем в JavaScript: система кэширования и кратчайший путь для графа

Введение

Структура данных — одна из неизбежных проблем при применении роли инженера-программиста. Раньше я изучал базовые структуры данных и написал статью на JavaScript.

Однако сложно применять структуры данных для проектирования системы или решения реальной проблемы.

Целью статьи является запись общих проблем со структурами данных. Я выбираю две интересные задачи из Интервью по кодированию и переношу решения на JavaScript. Мы будем использовать хеш-таблицу, связанный список, список(массив), чтобы решить эти вопросы.

• Пожалуйста, спроектируйте кэш для одной системы?
• Как найти кратчайший путь поиска между двумя людьми?

Пожалуйста, спроектируйте кэш для одной системы?

Требования

Разработайте систему кэширования со следующими свойствами.

1. Эффективный поиск по ключу
2. Истечение срока действия старых данных, чтобы их можно было заменить новыми данными

Проектирование системы кэширования в JavaScript

Для разработки системы кэширования мы можем использовать следующие структуры данных.

1. Хеш-таблица: свойство хеш-таблицыпозволяет нам легко искать данные (O(1) ~ O(n)), но не позволяет легко очищать данные.
2. Связанный список: свойство связанного списка позволяет нам очищать старые данные. Действие очистки состоит из перемещения нового элемента на передний план (O(n)) и удаления последнего элемента, когда список превышает определенный размер (O(n))

Структуры данных для использования

• Хеш-таблица

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

Как найти кратчайший путь поиска между двумя людьми?

Требования

1. Применить BFS для неориентированного графа
2. Вернуть путь между двумя узлами

Разработка алгоритма поиска в JavaScript

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

Исходный код

Функция searchLevel предназначена для выполнения обхода по уровням. Используйте очередь для хранения источника и посещения каждого узла для перехода на следующий уровень. Отличие обхода по уровням в том, что мы должны помнить посещенные узлы.

Функция mergePaths предназначена для поиска человека, столкнувшегося с конфликтом, а затем объединения двух путей, когда мы получим человека, столкнувшегося с конфликтом.

Структуры данных для использования

Чтобы выполнить поиск по уровням, нам нужен класс для хранения посещенных путей и путей, к которым будут посещены (BFSData).

• Посещенный путь: используйте хэш-таблицу для хранения посещенного пути, чтобы легко найти путь.
• Пути, которые мы посетим: используйте очередь (список здесь) для хранения путей, которые мы посетим

Чтобы сохранить точки для пути и восстановить путь, нам нужен класс для хранения точек с функцией восстановления пути.

• Список смежности: используйте связанный список для восстановления пути

использованная литература

• График: поиск в ширину (BFS，廣度優先搜尋)
• Интервью о взломе кода

Резюме

Спасибо за вашего пациента. Я Шон. Я работаю инженером-программистом.

Эта статья — моя заметка. Пожалуйста, не стесняйтесь дать мне совет, если какие-либо ошибки. Я с нетерпением жду ваших отзывов.

• Страница Facebook для статей

• Последний побочный проект: Daily Learning

похожие темы

Как использовать двустороннюю привязку в Knout.js и ReactJS?

Узнайте, как использовать SignalR для создания приложения для чата

Мое отражение «Эффективного SQL»:

ИТ и сеть:

База данных:

Тестирование программного обеспечения:

Отладка:

DevOps: