Овладев характеристиками различных структур данных, вы сможете использовать соответствующие структуры данных для решения различных задач и добиться мультипликативного эффекта вдвое меньшими усилиями.
Итак, на этот раз мы подробно познакомим вас с характеристиками различных структур данных, надеюсь, вы справитесь.
интенсивное чтение
множество
Массив используется очень часто, это непрерывное пространство памяти, поэтому к нему можно получить доступ напрямую в соответствии с индексом, а его эффективность поиска составляет O (1).
Однако эффективность вставки и удаления массива невысока, всего O(n), поскольку для сохранения непрерывности массива после вставки или удаления над массивом необходимо выполнить некоторые операции: например, вставить K-й элемент, необходимо сдвинуть следующие элементы назад. ; Чтобы удалить K-й элемент, необходимо сдвинуть следующие элементы вперед.
связанный список
Связный список был придуман для решения проблемы с массивами: он повышает эффективность вставки и удаления за счет эффективности поиска.
Эффективность вставки и удаления связанного списка равна O(1), потому что пока соответствующий элемент позиции отключается и снова подключается, вставка и удаление могут выполняться, не заботясь о других узлах.
Соответствующая эффективность поиска низка, потому что пространство для хранения не является непрерывным, поэтому в нем нельзя напрямую искать по индексам, как в массиве, а нужно искать непрерывно по указателям, поэтому эффективность поиска составляет O (n).
Кстати, связанный список можно добавить, добавив.prevАтрибут преобразуется в двусвязный список или путем определения двух.nextсформировать бинарное дерево (.left .right) или полидерево (N.next).
куча
Стек — это структура «первым пришел — последним вышел», которую можно смоделировать с помощью массива.
const stack: number[] = []
// 入栈
stack.push(1)
// 出栈
stack.pop()
куча
Куча — это особый вид полного бинарного дерева, разделенного на кучу с большой вершиной и кучу с маленькой вершиной.
Куча с большой вершиной означает, что корневой узел двоичного дерева представляет собой наибольшее число, а куча с малой вершиной означает, что корневой узел двоичного дерева представляет собой наименьшее число. Для удобства описания ниже в качестве примера используется большая верхняя куча, а логика маленькой верхней кучи прямо противоположна.
В большой верхней куче любой узел больше, чем его узел листьев, поэтому корневой узел является самым большим узлом. Преимущество этой структуры данных состоит в том, что максимальное значение можно найти в O (1) эффективности (минимальное значение найден в небольшом верхнем куче), потому что непосредственно получаетstack[0]является корневым узлом.
Вот небольшое упоминание о сопоставлении между двоичным деревом и структурой массива, потому что двоичное число обрабатывается массивом, независимо от операции или пространства. Первый элемент хранит общее количество узлов. Даfloor(K / 2), а индексы его дочерних узлов равныK * 2,K * 2 + 1, так что вы можете быстро найти родительские и дочерние позиции.
Используя эту функцию, можно добиться эффективности вставки и удаления.O(logn), потому что порядок других узлов можно регулировать, двигаясь вверх и вниз, а для полного бинарного дерева с n узлами глубина дерева равнаlogn.
хеш-таблица
Хеш-таблица — это так называемая карта.Различные карты реализуются по-разному.Обычными являются HashMap, TreeMap, HashSet и TreeSet.
Среди них Map и Set похожи по реализации, поэтому для объяснения возьмем Map в качестве примера.
Сначала найдите кодовое значение ASCII символа, который нужно сохранить, а затем найдите нижний индекс массива в соответствии с такими методами, как остаток.Один и тот же нижний индекс может соответствовать нескольким значениям, поэтому этот нижний индекс может соответствовать связанному списку, и далее поиск по связанному списку, этот метод называется методом застежки-молнии.
Если хранимое значение превышает определенное число, эффективность запроса связанного списка будет снижена, и он может быть повышен до хранилища красно-черного дерева.Короче говоря, эффективность такого добавления, удаления и запросаO(1), но недостатком является то, что его содержимое неупорядочено.
Чтобы обеспечить упорядоченность контента, для хранения можно использовать древовидную структуру, эта структура данных называется HashTree, поэтому временная сложность снижается доO(logn), но преимущество в том, что контент можно заказать.
Дерево и бинарное дерево поиска
Бинарное дерево поиска — это особый вид бинарного дерева, а более сложное — красно-черное дерево, но я не буду здесь углубляться, будет представлено только бинарное дерево поиска.
Бинарное дерево поиска удовлетворяет тому, что для любого узлаleft 的所有节点 < 根节点 < right 的所有节点, обратите внимание, что здесь все узлы, поэтому все случаи нужно рассматривать рекурсивно при оценке.
Преимущество бинарного дерева поиска состоит в том, что временная сложность доступа, поиска, вставки и удаления составляет O(logn), потому что любая операция может быть выполнена в двоичном виде. Но в худшем случае оно будет деградировано до O(n), причина в том, что после нескольких операций бинарное дерево поиска может больше не быть сбалансированным и, наконец, выродиться в связанный список, который становится временной сложностью связанного список.
Лучшие решения включают деревья AVL, красно-черные деревья и т. д. Двоичные деревья поиска, реализованные стандартными библиотеками JAVA и C++, — это красно-черные деревья.
словарное дерево
Дерево словаря в основном используется в сценариях поиска слов.Пока дается одно начало, вы можете быстро найти несколько рекомендуемых слов в конце.
Например, в приведенном выше примере, если вы введете «o», вы сможете быстро найти два слова, за которыми следуют «ok» и «ol». Следует отметить, что каждый узел должен иметь атрибутisEndOfWordУказывает, является ли это полным словом на данный момент: напримерgoа такжеgoodОба являются полными словами, ноgooнет, так второйoс четвертымdимеютisEndOfWordМетка означает, что после прочтения найдено полное слово, а метка конечного узла также может быть опущена.
и проверить
Поиск объединения используется для решения проблемы банды или проблемы острова, то есть для определения того, принадлежат ли несколько элементов определенному множеству. Union and Find по-английски — это Union и Find, то есть слияние и поиск, поэтому структуру данных Union Search можно записать в виде класса, обеспечивающего два самых основных метода.unionа такжеfind.
вunionВы можете поместить любые два элемента в набор, иfindВы можете найти, к какой корневой коллекции принадлежит любой элемент.
Структура данных массива используется для поиска по объединению, но она имеет следующие специальные значения, а нижний индекс устанавливается равным k:
-
nums[k]представляет набор, которому он принадлежит, еслиnums[k] === kУказывает, что это корневой узел этой коллекции.
Если вы хотите подсчитать в общей сложности несколько наборов, если число удовлетворяетnums[k] === kКоличество условий достаточное, как и сколько банд, лишь бы боссов было несколько.
Реализация набора поиска объединения отличается, и данные также будут немного отличаться.Когда вставляется эффективный набор поиска объединения, он будет рекурсивно указывать значение элемента на корневую бобышку, насколько это возможно, так что вычисление быстрее при поиске и оценке, но даже если точка не корень.босс, можно найти корневой босс и рекурсией.
Фильтр Блума
Фильтр Блума — это всего лишь фильтр, который может исключать пропущенные данные со скоростью, намного превышающей другие алгоритмы, но данные, которые не исключены, могут на самом деле не существовать, поэтому требуется дополнительный запрос.
Как это делает фильтр Блума? Это через бинарное суждение.
Как показано на рисунке выше, мы сначала сохраняем данные a и b, преобразуем их в двоичные данные и меняем соответствующие на 1, а затем, когда мы снова запрашиваем a или b, поскольку отношение отображения такое же, найденный результат определенно существует. .
Однако при запросе c обнаруживается, что один элемент равен 0, что указывает на то, что c не должно существовать; но при запросе d оба они равны 1, но фактическое d не существует, что является причиной ошибка.
Фильтры Блума широко используются в биткойнах и распределенных системах. Например, когда биткойн запрашивает, находится ли транзакция на определенном узле, используйте фильтр Блума, чтобы быстро пропустить ненужные поиски. Распределенные системы Расчеты, такие как Map Reduce, также быстро отфильтровывают вычисления, которые не в определенном узле через фильтр Блума.
Суммировать
Наконец, даны диаграммы средней и наихудшей временной сложности каждой структуры данных «доступ, запрос, вставка, удаление»:
Эта картинка изbigocheatsheet, вы также можете щелкнуть ссылку, чтобы получить к ней прямой доступ.
Изучив эти базовые структуры данных, я надеюсь, вы сможете их освоить, научиться комбинировать эти структуры данных для решения практических задач и в то же время понимать, что никакая структура данных не является всемогущей, иначе придется изучать так много структур данных. Просто используйте универсальную структуру данных.
Для комбинации структур данных я привожу два примера:
Первый пример — как запросить максимальное или минимальное значение стека со средней временной сложностью O(1). В настоящее время одного стека недостаточно, и для помощи необходим другой стек B. Когда встречается большее или меньшее значение, стек B помещается в стек, так что первое число стека B является наибольшим или наименьшим значением в текущий стек, а эффективность запроса составляет O (1), и его необходимо обновлять только при извлечении из стека, поэтому общая средняя временная сложность составляет O (1).
Второй пример — как повысить эффективность поиска в связанном списке.Вы можете использовать хеш-таблицу, чтобы быстро найти положение любого значения в связанном списке, объединив хэш-таблицу со связанным списком, изменив пробел на время и вы можете удвоить пространство, используя хеш-таблицу.В обмен на жертву временная сложность вставки, удаления и запроса составляет O (1). Хотя хеш-таблица может достичь этой временной сложности, хэш-таблица неупорядочена; хотя HashTree упорядочена, временная сложность составляет O (logn), поэтому только путем объединения HashMap и связанного списка можно получить упорядоченную и временную сложность. , но в жертву приносится космическая сложность.
В том числе фильтр Блума, упомянутый в конце, используется не сам по себе, это просто брандмауэр, который блокирует некоторые незаконные данные с чрезвычайно высокой эффективностью, но то, что не блокируется, не обязательно является законным, и требуется дополнительное расследование.
Поэтому я надеюсь, что вы сможете понять характеристики, ограничения и комбинированное использование каждой структуры данных.Я считаю, что вы можете гибко использовать различные структуры данных в реальных сценариях для достижения оптимального решения для текущего бизнес-сценария.
Адрес обсуждения:Интенсивное чтение «Компонент React Server», выпуск № 312 dt-fe/еженедельно
Если вы хотите принять участие в обсуждении, пожалуйста,кликните сюда, с новыми темами каждую неделю, выходящими по выходным или понедельникам. Интерфейс интенсивного чтения — поможет вам отфильтровать надежный контент.
Сфокусируйся наАккаунт WeChat для интенсивного чтения в интерфейсе
Заявление об авторских правах: Бесплатная перепечатка - некоммерческая - не производная - сохранить авторство (Лицензия Creative Commons 3.0)