В предыдущем посте в блоге была представлена гипотеза о слухах. В нем описывается компромисс между накладными расходами на чтение (RO), обновление (UO) и память (MO), которые следует учитывать при разработке структур данных и методов доступа.
В этом посте мы хотим поближе рассмотреть структуры данных, предназначенные для низких затрат на чтение, которые обычно используются на практике, т.е. хэш-таблицы, красно-черные деревья и списки пропусков. Этот пост в блоге является второй частью серии ромов:
- Гипотеза РОМА – Рассуждения О Доступе К Данным
- Считывать Эффективные Структуры Данных
- Обновление Эффективных Структур Данных
- Структуры Данных с Эффективной памятью
Для сравнения различных реализаций мы используем тот же пример, что и в предыдущем посте. Задача состоит в том, чтобы реализовать набор целых чисел, на этот раз сосредоточив внимание на небольшом объеме накладных расходов на чтение.
Пост структурирован следующим образом. В первом разделе мы хотим кратко изложить решение из последнего поста, которое имеет минимальные накладные расходы на чтение. В следующих разделах более подробно рассматриваются три практические альтернативы, начиная с хэш-таблиц, затем красно-черных деревьев и заканчивая списками пропусков. Заключительный раздел завершается сравнением трех различных структур данных с теоретической точки зрения, а также проведением простых экспериментов во время выполнения.
Мы видели оптимальную реализацию с точки зрения накладных расходов на чтение: учитывая возможные целые числа от 0 до 1000, мы можем использовать логический массив a размера 1001 . Элементы массива инициализируются с помощью false . Чтобы отметить целое число я как член множества, мы устанавливаем a[i] . Напомним о следующих накладных расходах:
- ро
- УО
- МО → ∞
Это непрактично для большинства реальных сценариев, поскольку объем памяти увеличивается с увеличением числа возможных значений. Хотя теоретически возможно использовать этот метод для целых чисел, это становится невозможным, например, если мы пытаемся хранить строки в наборе. Как мы можем уменьшить нагрузку на память, не теряя при этом слишком большой производительности чтения (и записи)?
На практике это достигается за счет использования подходов на основе хэша, отсортированного дерева или списка. Давайте рассмотрим три структуры данных, разработанные для эффективного чтения без ущерба для производительности записи и памяти: хэш-таблицы, красно-черные деревья и списки пропусков.
Концепция
Идея хеш-таблиц аналогична той, которая используется в оптимальном решении. Вместо того, чтобы резервировать логический слот для каждого возможного целого числа, мы ограничиваем пространство целочисленным массивом a размером m . Затем мы выбираем функцию h такой, что для каждого целого числа я: h(я) ∈ [0..m-1] . Эту функцию можно использовать для вычисления индекса массива, и мы можем хранить я в a[h(i)] .
Следующая диаграмма иллюстрирует, как целое число 3 хранится в наборе, реализованном с использованием хэш-таблицы. Мы вычисляем h(3) и сохраняем значение в соответствующем поле массива.
Как мы выбираем h ? Практическим выбором для h является повторное использование существующей криптографической хэш-функции (например, MD5 ) и получение результирующего значения по модулю m . Недостатком является то, что эти хэш-функции могут быть медленными. Вот почему Java, например, полагается на пользовательские хэш-функции для каждого типа данных (например, Строка ).
Если мы заранее знаем все возможные значения, мы можем выбрать идеальную хэш-функцию . Но в большинстве случаев это невозможно. Что нам делать, если два целых числа i и j сопоставляются с одним и тем же индексом h(i)(j) ? Существуют различные методы разрешения этих так называемых коллизий.
Одним из методов разрешения коллизий является отдельная цепочка . В отдельной цепочке мы храним не фактические значения в массиве, а другой уровень структур данных. Значение считывается из хэш-таблицы путем первого вычисления индекса массива, а затем запроса структуры данных, хранящейся там. Возможными кандидатами являются древовидные или списковые структуры, представленные в следующих разделах. Но также часто просто используют связанный список, если ожидается, что количество столкновений будет низким.
Другой часто используемый метод называется открытая адресация . Если происходит столкновение, мы вычисляем новый индекс на основе некоторой стратегии зондирования, например, линейного зондирования с h(i) + 1 .
Накладные расходы на БАРАБАН
Общие накладные расходы на реализацию хэш-таблицы в значительной степени зависят от выбранной хэш-функции, размера массива m , а также стратегии разрешения коллизий. Это позволяет настраивать накладные расходы на барабан вашей хэш-таблицы.
Если коллизии нет, то накладные расходы на чтение зависят только от накладных расходов на вычисления h(i) . Меньшие накладные расходы при оценке хэш-функции приводят к меньшим общим затратам на чтение. В случае столкновения возникают дополнительные накладные расходы, которые зависят от стратегии разрешения. Хотя полезно избегать коллизий, выбирая почти идеальную хэш-функцию, общие накладные расходы могут быть меньше, если мы сделаем хэш-функцию достаточно быстрой и будем выполнять несколько дополнительных операций при разрешении коллизий.
Поскольку для обновления сначала требуется операция чтения, накладные расходы на обновление равны накладным расходам на чтение плюс операция вставки/удаления либо в массиве, либо в связанных структурах данных в случае отдельной цепочки.
Нагрузка на память косвенно пропорциональна коэффициенту загрузки ( n/m ). Мы также должны учитывать дополнительную память, если мы используем отдельные цепочки для разрешения конфликтов.
Если мы вставляем все больше и больше данных, нагрузка на память уменьшается. Однако накладные расходы на чтение увеличиваются по мере того, как нам приходится разрешать больше коллизий. В этом случае можно изменить масштаб хэш-таблицы, для чего требуется полная копия существующих данных в больший массив и повторное вычисление всех хэш-значений.
Асимптотическая сложность
Операции чтения и обновления в среднем имеют постоянную асимптотическую сложность, поскольку вычисление хэш-значения занимает постоянное время, независимо от объема данных, хранящихся в таблице. В худшем случае (все n входные значения получают одинаковое хэш-значение) у нас есть n – 1 коллизии для разрешения. Таким образом, производительность в наихудшем случае такая же плохая, как если бы мы сохранили данные в неупорядоченном массиве и выполнили полное сканирование. Если m выбрано как можно меньше, а размер хэш-таблицы при необходимости изменен, то потребность в амортизированной памяти линейна по количеству значений, хранящихся в наборе.
| Прочитай | O(1) | O(n) |
| Обновление | O(1) | O(n) |
| Память | O(n) | O(n) |
Производительность чтения структур данных на основе хэш-таблиц в среднем постоянна. Однако по своей конструкции он эффективно поддерживает только точечные запросы. Если ваши шаблоны доступа содержат запросы диапазона, например, проверка того, являются ли целые числа [0..500] содержатся в наборе, наборы хэшей не являются правильным выбором. Для эффективной поддержки запросов диапазона мы можем хранить данные в отсортированном виде. Одним из наиболее распространенных типов структуры данных для этого варианта использования являются бинарные деревья поиска.
Концепция
В двоичном дереве поиска данные хранятся в узлах. Каждый узел имеет до двух дочерних узлов. Левое поддерево содержит только элементы, размер которых меньше текущего узла. Правое поддерево содержит только более крупные элементы. Если дерево сбалансировано, т.е. для всех узлов высота левого и правого поддеревьев отличается не более чем на 1, поиск узла занимает логарифмическое время. На следующем рисунке показано, как сохранить набор {0..6} в двоичном дереве поиска.
Вопрос в том, как мы сохраняем сбалансированность дерева при вставке и удалении элементов? Нам нужно соответствующим образом разработать наш алгоритм вставки и удаления, чтобы сделать дерево самобалансирующимся. Широко используемым вариантом таких самобалансирующихся бинарных деревьев поиска являются красно-черные деревья [1].
В красно-черном дереве каждый узел сохраняет свой цвет в дополнение к фактическому значению. Информация о цвете используется при вставке или удалении узлов, чтобы определить, как сбалансировать дерево. Перебалансировка выполняется путем изменения цвета и рекурсивного вращения поддеревьев вокруг их родителей до тех пор, пока дерево снова не будет сбалансировано.
Подробное объяснение алгоритма выходит за рамки этого поста, поэтому, пожалуйста, не стесняйтесь искать его самостоятельно. Также есть удивительная интерактивная визуализация красно-черных деревьев Дэвида Галлеса, которую стоит проверить. Теперь давайте взглянем на тот же пример набора {0..6} , хранящегося в красно-черном дереве.
Обратите внимание, что красно-черные деревья не обязательно идеально сбалансированы, а скорее с точки зрения высоты черных узлов в поддеревьях. Из-за инвариантов красно-черных деревьев сбалансированное красно-черное дерево никогда не бывает намного хуже идеально сбалансированного дерева, т.е. они имеют одинаковую асимптотическую сложность для поиска.
Накладные расходы на БАРАБАН
Накладные расходы на БАРАБАН в самобалансирующихся деревьях двоичного поиска зависят от алгоритма поддержания сбалансированности дерева. В красно-черных деревьях перебалансировка происходит рекурсивно и может повлиять на узлы вплоть до корня.
Операция чтения включает в себя обход дерева до тех пор, пока элемент не будет найден. Если элемент хранится в конечном узле, он занимает не более log(n) + c шагов обхода, при этом c является потенциальными накладными расходами, если дерево не идеально сбалансировано.
Как и в реализации на основе хэш-таблицы, операция обновления набора на основе красно-черного дерева требует сначала операции чтения. В дополнение к накладным расходам на чтение, накладные расходы на обновление зависят от обновляемого значения, следует ли его вставлять и удалять, а также от текущей структуры дерева. В самых тривиальных случаях обновление требует только одной операции на родительском узле, т.е. изменения указателя на дочерний узел. В худшем случае нам придется перебалансировать дерево до самого корня.
Асимптотическая сложность
Операции чтения имеют логарифмическую сложность, поскольку красно-черные деревья сбалансированы, поэтому поиск значения концептуально соответствует двоичному поиску . Операции обновления имеют ту же сложность, так как они требуют логарифмического поиска, плюс операции перебалансировки в худшем случае от листа к корню, что опять же логарифмично. Поскольку нам требуется по одному узлу на значение, требования к памяти линейны.
| Прочитай | O(логарифм n) | O(логарифм n) |
| Обновление | O(логарифм n) | O(логарифм n) |
| Память | O(n) | O(n) |
Мы видели, что самобалансирующиеся бинарные деревья поиска являются полезными структурами данных, если требуются запросы диапазона или данные должны быть представлены пользователю в отсортированном виде. Однако алгоритмы, необходимые для того, чтобы сделать их самобалансирующимися, довольно сложны. Кроме того, если мы хотим поддерживать параллельный доступ, мы должны заблокировать части дерева во время перебалансировки. Это может привести к непредсказуемым замедлениям, если потребуется большая перебалансировка.
Как мы можем разработать структуру данных, удобную для параллелизма, которая также поддерживает логарифмическую стоимость поиска?
Концепция
По своей конструкции связанные списки очень удобны для параллелизма, так как обновления сильно локализованы и удобны для кэширования [3]. Если бы наши данные представляли собой отсортированную последовательность, мы могли бы использовать двоичный поиск для достижения логарифмической сложности чтения. Однако проблема с отсортированным связанным списком заключается в том, что мы не можем получить доступ к случайному элементу списка. Таким образом, двоичный поиск невозможен. Или так оно и есть? Вот тут-то и появляются списки пропусков.
Списки пропусков являются вероятностной альтернативой сбалансированным деревьям [4, 5, 6]. Основная идея списка пропусков состоит в том, чтобы предоставить экспресс-маршруты для более поздних частей данных с помощью указателей пропусков.
Чтобы выполнить двоичный поиск, мы должны сравнить наш запрос с медианой. Если медиана не является тем элементом, который мы ищем, мы берем либо левый, либо правый подсписк и рекурсивно повторяем сравнение медианы. Это означает, что на самом деле нам не нужен полный произвольный доступ, а скорее доступ к медиане текущего подсписка. На следующем рисунке показано, как мы можем добиться этого с помощью указателей пропуска.
Этот список пропусков состоит из трех уровней. Самый низкий уровень содержит полный набор целых чисел {0..6} . Только следующий уровень {1, 3, 5} , в то время как верхний уровень содержит только {3} . Мы добавляем два искусственных узла -∞ и ∞ . Каждый узел содержит значение и массив указателей, по одному на каждого преемника на соответствующем уровне. Если мы сейчас захотим проверить, если 4 является членом множества, мы действуем следующим образом.
- Начните с крайнего левого элемента ( -∞ ) с самого верхнего указателя (уровень 3)
- Сравните запрос ( 4 ) со следующим элементом на текущем уровне ( 3 )
- Как 3 < 4 , мы перемещаем один элемент вправо (к 3 )
- Затем мы снова сравниваем запрос ( 4 ) со следующим элементом текущего уровня ( ∞ )
- Как ∞ , мы перемещаемся на один уровень вниз (до уровня 2)
- Затем мы снова сравниваем запрос ( 4 ) со следующим элементом на текущем уровне ( 5 )
- Как 5 , мы перемещаемся на один уровень вниз (до уровня 1)
- Затем мы снова сравниваем запрос ( 4 ) со следующим элементом на текущем уровне ( 4 )
- Как 4 , запрос успешно возвращается
Этот алгоритм отлично работает, если список статичен, и мы можем создать указатели пропуска для поддержки нашего двоичного поиска. Однако в реальном сценарии мы хотим иметь возможность вставлять или удалять элементы. Как мы можем эффективно поддерживать вставки и удаления, не теряя приятных свойств правильно размещенных указателей пропуска? Полностью перестраивать список пропусков после каждой модификации нецелесообразно. В конце концов, мы хотим иметь высоко локализованные обновления для поддержки высокого параллелизма.
Мы ввели списки пропусков в качестве вероятностной альтернативы сбалансированным деревьям. И вероятностная часть – это именно та часть, которая необходима для решения проблемы того, где и как размещать указатели пропуска.
Для каждого элемента, который мы хотим вставить в список пропусков, мы сначала ищем его позицию в существующих элементах. Затем мы вставляем его на самый низкий уровень. После этого мы подбрасываем монетку. Если на монете выпадет решка, нам конец. Если он показывает заголовки, мы “продвигаем” элемент на следующий уровень, вставляя его в список более высокого уровня, и повторяем процедуру. Чтобы удалить элемент, мы ищем его, а затем просто удаляем со всех уровней. Не стесняйтесь ознакомиться с этой удивительной интерактивной визуализацией списка пропусков .
Из-за недетерминированного характера алгоритма вставки реальные списки пропусков выглядят не так оптимально, как на рисунке выше. Скорее всего, они будут выглядеть намного более неряшливо. Тем не менее, можно показать, что ожидаемая сложность поиска по-прежнему логарифмическая [7].
Накладные расходы на БАРАБАН
Накладные расходы на БАРАБАН в списках пропусков не являются детерминированными. Именно поэтому анализ асимптотической сложности является более сложным, чем обычно, поскольку он также включает теорию вероятностей. Тем не менее, мы собираемся взглянуть на различные накладные расходы на концептуальном уровне.
Операция чтения требует прохождения последовательности горизонтальных и вертикальных указателей, сравнивая запрос с различными элементами списка по пути. Это означает, что существует потенциально большое количество вспомогательных операций чтения до тех пор, пока запрос не сможет вернуться.
Как вы могли догадаться, нам требуется операция чтения, прежде чем мы сможем выполнить обновление. Количество вспомогательных обновлений, т.е. рекламных акций, не является детерминированным. Однако они полностью локальны и не зависят от структуры оставшегося списка пропусков. Это облегчает распараллеливание обновлений.
Объем памяти зависит от количества рекламных акций, так как нам приходится хранить дополнительные указатели для каждой рекламной акции. Используя нечестную монету, т.е. используя вероятность продвижения/не продвижения [p, 1-p] с 0 < p < 1 вместо [0.5, 0.5] , мы действительно можем настроить нагрузку на память, потенциально компенсируя дополнительные затраты на чтение и обновление. Если бы мы выбрали p мы получили бы связанный список с минимальными затратами памяти, которых мы можем достичь в этой структуре данных. Если мы выберем p слишком большим, я считаю, что как объем памяти, так и накладные расходы на чтение увеличатся, так как нам потенциально придется выполнять много вертикальных перемещений по разным уровням.
Асимптотическая сложность
Существуют различные способы анализа асимптотической сложности списков пропусков. Два обычно используемых метода заключаются в рассмотрении ожидаемой асимптотической сложности или асимптотической сложности, которая выполняется с высокой вероятностью . По соображениям простоты давайте взглянем на ожидаемую сложность здесь.
При реализации списков пропусков, как описано выше, существует небольшая вероятность получить бесконечно продвигаемый элемент. В то время как ожидаемое количество уровней равно O(log(n)) , он теоретически неограничен. Чтобы решить эту проблему, можно выбрать максимальное количество уровней M что элемент может быть повышен. Если M достаточно велико, то на практике никаких негативных последствий не возникает.
Ожидаемая сложность чтения и обновления в среднем случае является логарифмической. Ожидаемая высота списка пропусков составляет O(log(n)) . Однако элементы с более высоким продвижением менее вероятны, что позволяет нам получить линейные ожидаемые требования к памяти [8].
Анализ наихудшего случая более интересен для ограниченного списка, так как неограниченный наихудший случай – это бесконечно высокий список пропусков. В худшем случае ограниченного списка мы повысили каждый элемент до максимального уровня. Если мы выберем максимальный уровень, зависящий от n , мы сможем получить линейную сложность для операций чтения и обновления.
| Прочитай | O(логарифм n) | O(n) | ∞ |
| Обновление | O(логарифм n) | O(n) | ∞ |
| Память | O(n) | O(нм) | ∞ |
Теперь мы познакомились с тремя различными типами структур данных, которые широко используются в отрасли. Мы рассмотрели их с теоретической точки зрения один за другим. Следующий раздел содержит статическое сравнение, обобщающее наши результаты, а также некоторые эксперименты во время выполнения с использованием реализаций из стандартной библиотеки Java.
Теоретическое сравнение
Из того, что мы узнали сегодня, можно с уверенностью сказать, что структуры данных, эффективные для чтения, нацелены на сублинейные накладные расходы на чтение. Хэш-таблицы отлично подходят для карт или наборов в памяти. Недостатки заключаются в необходимости масштабирования базового массива при увеличении объема данных, а также в отсутствии поддержки запросов диапазона. Древовидные структуры данных являются хорошей альтернативой, если речь идет о запросах диапазона или отсортированных выходных данных. Списки пропусков иногда предпочтительнее деревьев из-за их простоты, особенно когда дело доходит до реализаций без блокировок.
Некоторые структуры данных настраиваются с точки зрения накладных расходов на БАРАБАН. Настраивая такие параметры, как стратегия разрешения коллизий или желаемый коэффициент загрузки, мы можем снизить нагрузку на память по сравнению с затратами на чтение в хэш-таблицах. В списках пропусков мы можем добиться этого, изменив вероятность продвижения по службе.
В следующей таблице приведены средние асимптотические требования к чтению, обновлению и памяти, а также аспект общей настраиваемости трех структур данных, которые мы рассматривали в этом посте.
| O(логарифм n) | O(1) | Средний показатель. Прочитай | O(логарифм n) |
| O(логарифм n) | O(1) | Средний показатель. Обновление | O(логарифм n) |
| O(n) | O(n) | Средний показатель. Память | O(n) |
| вероятность продвижения по службе | коэффициент загрузки, хэш-функция, стратегия разрешения коллизий | Параметры настройки БАРАБАНА | – |
Эксперименты во время выполнения
И последнее, но не менее важное: мы хотим взглянуть на фактическую производительность чтения трех структур данных стандартной библиотеки Java: HashSet , Набор деревьев и Набор списков совпадений .
HashSet использует отдельную цепочку для разрешения коллизий. Если количество элементов в корзине достаточно мало, они будут сохранены в списке. Если число превышает TREEIFY_THRESHOLD , оно будет перенесено в красно-черное дерево. Набор деревьев реализован с использованием красно-черного дерева. Оба HashSet и TreeSet не являются потокобезопасными и не поддерживают одновременные модификации. Как следует из названия, ConcurrentSkipListSet поддерживает параллельный доступ. В базовых списках используется вариант алгоритма связанного упорядоченного множества Харриса-Магеда [9, 10].
В качестве эталона мы генерируем набор из n случайных целых чисел и копируем его в Хэш-набор , Набор деревьев и Набор списков совпадений соответственно. Мы также создаем оптимальный для чтения набор из этих чисел, т.Е. используем огромный логический массив. Затем мы создаем список n запросов со случайными точками и измеряем время выполнения всех запросов.
Мы используем Скаляметр для измерения производительности во время выполнения. Не стесняйтесь ознакомиться с моим сообщением в блоге microbenchmarking , в котором содержится более подробная информация об инструменте.
На следующей диаграмме показано время выполнения 100 000 точечных запросов для различных наборов, сгенерированных из 100 000 случайных целых чисел.
Как и ожидалось, реализация, оптимальная для чтения, работает значительно лучше, чем все остальные. Второе место достается хэш-набору. Как реализация, оптимальная для чтения, так и набор хэшей имеют постоянные асимптотические накладные расходы на чтение. Набор деревьев и набор списков пропусков работают намного хуже. Это также ожидается, так как они имеют логарифмическую сложность во время выполнения.
Было бы интересно также взглянуть на другие накладные расходы четырех реализаций, а также включить в них параллелизм. Но я оставляю это упражнение читателю:P В следующем посте мы подробнее рассмотрим эффективные для записи структуры данных, которые рассчитаны на низкие затраты на обновление.
- [1] Гибас Л.Дж. и Седжвик Р., 1978, октябрь. Дихроматическая структура для сбалансированных деревьев. В “Основах информатики”, 1978. , 19-й Ежегодный симпозиум по (стр. 8-21). IEEE.
- [2] Потребление памяти популярными типами данных Java – часть 2 автор Михаил Воронцов
- [3] Выбирайте Структуры Данных, Удобные для параллелизма Автор Херб Саттер
- [4] Пью, У., 1989, август. Списки пропусков: вероятностная альтернатива сбалансированным деревьям. На семинаре по алгоритмам и структурам данных (стр. 437-449). Springer, Berlin, Heidelberg.
- [5] Фрейзер К. и Харрис Т., 2007. Параллельное программирование без блокировок. Транзакции ACM в компьютерных системах (TOC), 25(2), стр.5.
- [6] Херлихи М., Лев Ю., Лучанко В. и Шавит Н., 2006. Доказуемо правильный масштабируемый список одновременных пропусков. На Конференции По принципам распределенных систем (OPODIS).
- [7] Пападакис Т., 1993. Списки пропусков и вероятностный анализ алгоритмов. Докторская диссертация: Университет Ватерлоо.
- [8] Списки пропусков – Курс структур данных Университета Бен-Гуриона в Негеве
- [9] Харрис, Т.Л., 2001, октябрь. Прагматичная реализация неблокирующих связанных списков. На Международном симпозиуме по распределенным вычислениям (pp. 300-314). Springer, Berlin, Heidelberg.
- [10] Майкл, М.М., 2002, август. Высокопроизводительные динамические хэш-таблицы без блокировок и наборы на основе списков. В материалах четырнадцатого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам (стр. 73-82). ACM.
- Изображение на обложке от Smabs Sputzer – Это ром… на flickr, CC BY 2.0, https://commons.wikimedia.org/w/index.php?curid=59888481
Оригинал: “https://dev.to/frosnerd/read-efficient-data-structures-57i5”