Какие структуры данных соответствуют структурам данных для внешней памяти

Обновлено: 25.06.2024

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

Важно изучить базовые структуры данных изнутри, иначе понимание структур более высокого уровня будет затруднено.

Начинающий

Массив: набор элементов одного типа переменных, которые последовательно хранятся в памяти. Это одна из самых популярных и простых структур данных, часто используемая для реализации других структур данных.
Связанный список. Линейная последовательность связанных узлов. Каждый узел содержит значение и указатель на следующий узел в списке.
Стек: линейная структура данных, основанная на принципе "последний пришел - первый обслужен" (LIFO).
Очередь: аналогична стеку тем, что обе они представляют собой линейные структуры данных с динамическим размером. Однако очереди представляют собой структуры данных FIFO (первым поступил, первым обслужен).
Deque (двухсторонняя очередь): расширение Queue, элементы можно добавлять или удалять из передней (головной) или задней (хвостовой) части.
Очередь с приоритетом: расширение очереди, каждый элемент связан со значением приоритета, элемент с высоким приоритетом обслуживается перед элементом с низким приоритетом.
Set: абстрактный тип данных, который может хранить уникальные значения без определенного порядка.
Хеш-таблица. Структура данных, которая может сопоставлять ключи со значениями, использует хэш-функцию для вычисления индекса в массиве сегментов, из которого можно найти нужное значение.

Средний

Куча: специализированная древовидная структура данных с наибольшим корневым узлом в максимальной куче или наименьшим корневым узлом в минимальной куче.
Дерево Хаффмана (дерево кодирования Хаффмана): полное двоичное дерево, в котором каждый лист дерева соответствует букве в заданном алфавите. Цель состоит в том, чтобы построить дерево с минимальным весом внешнего пути.
Непересекающийся набор (объединенный поиск): структура данных, в которой хранится коллекция непересекающихся наборов, поддерживающая операции объединения и поиска на подмножествах.
Trie: древовидная структура данных, используемая для поиска определенных ключей в наборе. Эти ключи чаще всего представляют собой строки, причем связи между узлами определяются не всем ключом, а отдельными символами.
Двоичное дерево поиска: корневая структура данных двоичного дерева, каждый из внутренних узлов которой хранит ключ, больший, чем все ключи в левом поддереве узла и меньший, чем ключи в его правом поддереве.

Профессионально

Дерево сегментов: структура данных, которая позволяет эффективно отвечать на запросы диапазона по массиву, но при этом достаточно гибкая, чтобы можно было изменять массив.
Дерево Фенвика (двоичное индексированное дерево): структура данных, которая может эффективно обновлять элементы и вычислять суммы префиксов в таблице чисел.
Массив суффиксов: отсортированный массив всех суффиксов строки, используемый в полнотекстовых указателях, алгоритмах сжатия данных и в области библиометрии.
Разреженная таблица. Структура данных, которая позволяет отвечать на запросы диапазона, особенно на запросы минимального диапазона в массиве.
Дерево диапазонов: упорядоченная древовидная структура данных для хранения списка точек. Он позволяет эффективно извлекать все точки в заданном диапазоне и обычно реализуется в двух или более измерениях.

Эксперт

Дерево AVL: самобалансирующееся двоичное дерево поиска, в котором каждый узел содержит дополнительную информацию, называемую коэффициентом баланса, значение которого равно -1, 0 или +1.
Суффикс-автомат. Мощная структура данных, позволяющая решать множество задач, связанных со строками, таких как поиск всех вхождений одной строки в другую или подсчет количества различных подстрок заданной строки.
Дерево суффиксов: сжатое дерево, содержащее все суффиксы данного текста в качестве их ключей и позиции в тексте в качестве их значений.
Treap (Декартово дерево): структура данных, которая сочетает в себе двоичное дерево и двоичную кучу (отсюда и название: Tree + Heap = Treap).
K-d Tree: структура данных с разделением пространства для организации точек в k-мерном пространстве.
Лес: неориентированный граф, в котором любые две вершины связаны не более чем одним путем. Эквивалентно, лес - это неориентированный ациклический граф, все компоненты связности которого являются деревьями; другими словами, граф состоит из несвязного объединения деревьев.
Splay Tree: эффективная реализация сбалансированного бинарного дерева поиска, в котором используется локальность ключей, используемых во входящих запросах на поиск.
Палиндромное дерево: древовидная структура данных, которая специально используется для решения проблем, связанных с палиндромами строки и ее подстрок.
Rope: структура данных, состоящая из меньших строк, которая используется для эффективного хранения и управления очень длинной строкой.
Основное дерево. Структура данных, представляющая оптимизированное по пространству дерево (дерево префиксов), в котором каждый единственный дочерний узел объединяется со своим родителем.
Red Black Tree: самобалансирующееся двоичное дерево поиска. В каждом узле хранится дополнительный бит, представляющий «цвет», используемый для обеспечения сбалансированности дерева при вставках и удалениях.

Место, где можно изучить веб-разработку помимо основ, с еженедельными статьями по темам.

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

В типичном анализе временной сложности алгоритма вы предполагаете, что для доступа к памяти или выполнения базовой операции ЦП, например сложения, требуется постоянное время. Это, конечно, не совсем точно: в частности, эффекты кеша означают, что время доступа к памяти сильно различается в зависимости от того, какой именно адрес вы запрашиваете. В системе, где ваш алгоритм может обращаться к внешней памяти, это становится еще более верным — ЦП, которому требуется 1 нс для выполнения сложения, может легко ожидать 5 мс (то есть 5 миллионов нс) для завершения чтения с вращающегося диска.

Альтернативная модель сложности — это машина доступа к диску (DAM). В этой модели чтение одного блока памяти (фиксированного размера B ) требует постоянных временных затрат, а все остальные операции бесплатны. Как и его обычный двоюродный брат, это явное упрощение реальности, но оно позволяет нам сжато количественно оценить использование диска различными структурами данных.

На момент написания этой статьи производительность, которую мы можем ожидать от иерархии хранилища:

< /tr> td>

Категория	Репрезентативное устройство	Пропускная способность при последовательном чтении	Пропускная способность при последовательной записи	4 КБ Чтение IOPS	4 КБ Запись IOPS
Механический диск	Western Digital Black WD4001FAEX (4 ТБ)	130 МБ /s	130 МБ/с	110	150
Твердотельный накопитель с интерфейсом SATA	Samsung 850 Pro (1 ТБ)	550 МБ/с	520 МБ/с	10 000	36 000
Твердотельный накопитель с интерфейсом PCIe	Intel 750 (1,2 ТБ)	2400 МБ/с	1200 МБ/с	440 000	290 000
Оперативная память	Skylake @ 3200 МГц	42 000 МБ/ с	48 000 МБ/с	16 100 000 (62 нс/операция)

(В приведенной выше таблице все показатели IOPS представлены для глубины очереди, равной 1, поэтому для твердотельных накопителей это, как правило, наихудшие значения.)

Обратите внимание, что предполагаемая пропускная способность произвольного чтения с механического диска составляет (110 * 4 КБ/с), т. е. 440 КБ/с, что примерно в 300 раз медленнее, чем при последовательном чтении. Напротив, полоса пропускания произвольного чтения с SSD, подключенного к PCIe, составляет (440 000 * 4 КБ/с) = 1,76 ГБ/с, то есть всего примерно в 1,4 раза медленнее, чем в случае последовательного чтения. Таким образом, вы по-прежнему платите штраф за произвольный доступ даже на твердотельных накопителях, но он намного ниже, чем эквивалентная стоимость на вращающихся дисках.

Один из способов представить приведенные выше цифры IOPS – разбить их на ту часть IOPS, которую мы можем отнести ко времени, необходимому для передачи блока 4 КБ (т. вызовите время поиска (т.е. (1/IOPS) - (4KB/пропускная способность)):

th> < tr>

Категория	Подразумеваемое время поиска с момента чтения	Подразумеваемое время поиска с момента записи	Среднее предполагаемое время поиска
Механический диск	9,06 мс	6,63 мс	7,85 мс
Твердотельный накопитель с интерфейсом SATA	92,8us	20,2us	56,5us
Твердотельный накопитель с интерфейсом PCIe	645 нс	193 нс	419 нс

Если мы используем DAM для моделирования программ, работающих поверх одного из этих механизмов хранения, какой размер блока B следует выбрать, чтобы стоимость алгоритма, полученная из DAM, была хорошим ориентиром для реальных временных затрат? Допустим, наша стоимость DAM для некоторого алгоритма составляет N чтений блока. Рассмотрим два сценария:

Если все эти чтения являются непрерывными, то реальная стоимость времени (в секундах) чтения будет равна N*(B/пропускная способность) + время поиска.
Если все они случайные, то истинная стоимость времени равна N*((B/пропускная способность) + время поиска) , т. е. (N – 1)*время поиска больше, чем в последовательном случае

Тот факт, что одна и та же стоимость DAM может соответствовать двум очень разным истинным затратам времени, предполагает, что мы должны попытаться выбрать размер блока, который минимизирует разницу между двумя возможными истинными затратами. Имея это в виду, разумным выбором будет установить B равным произведению времени поиска и пропускной способности устройства. Если мы сделаем это, то в сценарии с произвольным доступом (где DAM больше всего недооценивает стоимость):

Реализованный IOPS будет как минимум вдвое меньше пикового IOPS для устройства хранения.
Реализованная пропускная способность будет составлять не менее половины пиковой пропускной способности устройства хранения.

Если мы выберем значение B, меньшее, чем произведение пропускной способности на время поиска, количество операций ввода-вывода в секунду приблизится к максимальному для устройства, но только за счет ухудшения пропускной способности. Аналогично, блоки большего размера уменьшат количество операций ввода-вывода в секунду, но повысят пропускную способность. Предлагаемый выбор B в равной степени снижает как IOPS, так и пропускную способность. Применив эту идею к устройствам хранения выше:

th> < td>SATA-подключенный SSD

Категория	Подразумеваемый размер блока после чтения	Подразумеваемый размер блока после записи	Средний предполагаемый размер блока
Механический диск	1210 КБ	883 КБ	1040 КБ
52,3 КБ	10,8 КБ	31,6 КБ
PCIe-подключенный SSD	1,59 КБ	243 Б	933 Б

На SSD наименьшая единица хранения, доступная для записи/чтения, — это страница. На устройствах текущего поколения размер страницы обычно составляет около 8 КБ. Приятно видеть, что это находится в пределах порядка наших оценок размера блока SSD здесь.

Интересно, что предлагаемые размеры блоков для механических дисков намного больше, чем типичные размеры блоков, используемые в операционных системах и базах данных, где распространены страницы виртуальной памяти/базы данных по 4 КБ (и, конечно, намного больше, чем размер сектора 512 Б для большинства вращающихся дисков). ). Я, конечно, не первый, кто заметил, что типичные размеры страниц базы данных кажутся слишком маленькими.

Применение DAM

Теперь, когда мы решили, как мы можем применить DAM для оценки стоимости диска, которая будет транслироваться (хотя бы приблизительно) в реальную стоимость, мы можем фактически применить модель к анализу некоторых алгоритмов. Прежде чем мы начнем, несколько интересных особенностей DAM:

Двоичный поиск не оптимален. Двоичный поиск N элементов требует O(log (N/B)) чтений блока, но поиск O(log_B N) возможен с другими алгоритмами.
Сортировка путем вставки элементов по одному в B-дерево с последующим обходом дерева не оптимальна. Предлагаемый подход требует O(N log_B N), но возможна сортировка за O((N/B) * log (N/B)) .
В отличие от стандартной модели затрат, многие структуры данных карты имеют разную стоимость поиска и вставки в DAM. Это означает, что, например. добавление ограничений UNIQUE к индексам базы данных может фактически изменить сложность вставки в индекс (поскольку вам придется выполнять поиск в таком индексе, прежде чем вы узнаете, должна ли вставка быть успешной).

Теперь давайте рассмотрим несколько структур данных карты. Мы увидим, что в модели DAM хорошо себя зарекомендовали карты, способные наилучшим образом упорядочить свои шаблоны доступа для использования блочной структуры памяти.

Дерево 2-3

Дерево 2-3 – это сбалансированная древовидная структура, в которой каждый конечный узел находится на одной глубине, а все внутренние узлы имеют 1 или 2 ключа и, следовательно, имеют 2 или 3 дочерних элемента. Конечные узлы имеют 1 или 2 пары "ключ-значение".

Поиск в этом дереве совершенно прост и имеет сложность O(log N) . Вставка в дерево происходит рекурсивно, начиная с корневого узла:

При вставке в лист мы добавляем элемент данных в лист. Обратите внимание, что это может означать, что лист временно содержит 3 пары ключ/значение, что превышает обычное ограничение.
При вставке во внутренний узел мы рекурсивно добавляем элемент данных к соответствующему дочернему элементу. После этого дочерний элемент может содержать 3 ключа, и в этом случае мы подтягиваем один к этому узлу, создавая в процессе новый родственный элемент. Если этот узел уже содержит 2 ключа, это, в свою очередь, приведет к тому, что он станет слишком большим. Пример того, как это может выглядеть:
Если после завершения рекурсии корневой узел содержит 3 ключа, мы извлекаем новый корневой узел (с одним ключом) из старого корня, например:

Легко видеть, что это поддерживает баланс дерева. Этот процесс вставки также явно имеет временную сложность O(log N), как и поиск. Структура данных не пытается использовать тот факт, что память имеет блочную структуру, поэтому и вставка, и поиск имеют одинаковую сложность в DAM и стандартной модели затрат.

B-дерево

B-дерево (и очень тесно связанное с ним B+дерево), вероятно, является самой популярной структурой для хранения во внешней памяти. Его можно рассматривать как простое обобщение дерева 2-3, где каждый внутренний узел не имеет 1 или 2 ключей, а имеет от m до 2m ключей для любого m > 0. Затем мы устанавливаем m на максимальное значение, чтобы один внутренний узел точно соответствовал размеру нашего блока B , т. е. m = O(B) .

В модели затрат DAM поиск в B-дереве имеет временную сложность O(log_B N) . Это связано с тем, что мы можем получить доступ к набору не менее m ключей каждого внутреннего узла, используя чтение одного блока — то есть за O (1) — и это позволяет нам сделать выбор по крайней мере между m + 1 = O (B) дочерними узлами.< /p>

По тем же причинам, что и в случае поиска, вставка в B-дерево также требует затрат времени O(log_B N) в DAM.

Дерево буферизованного репозитория

Дерево буферизованного репозитория, или BRT, представляет собой обобщение дерева 2-3, в котором каждый внутренний узел связан с дополнительным буфером размера k = O(B) . При выборе k разумным выбором будет сделать его достаточно большим, чтобы использовать все пространство внутри блока, которое не занято ключами внутреннего узла.

При вставке в это дерево мы не сразу изменяем структуру дерева. Вместо этого запись о вставке просто добавляется в буфер корневого узла до тех пор, пока этот буфер не заполнится. Как только он заполнится, мы обязательно сможем передать как минимум k/3 вставок одному дочернему узлу. Эти вставки, в свою очередь, будут буферизоваться на более низком уровне и могут вызвать рекурсивное распространение на еще более глубокие уровни.

Какова временная сложность вставки? Некоторые вставки будут очень быстрыми, потому что они просто добавляются к буферу, в то время как другие требуют обширного сброса. Поэтому, чтобы сгладить эти различия, мы учитываем амортизированную стоимость вставки. Если мы вставим в дерево N элементов, то на каждом из O(log (N/B)) уровней дерева мы прольем не более O(N/(k/3)) = O(N/B) раз. Это дает общую стоимость вставок O((N/B) log (N/B)) , которая является амортизированной стоимостью O((log (N/B))/B) .

Поиск выполняется почти как обычно, за исключением того, что буфер на каждом уровне должен быть просмотрен до того, как будут рассмотрены какие-либо дочерние узлы. В DAM этот дополнительный поиск стоит O(1) , поэтому стоимость поиска становится O(log (N/B)) .

По сути, то, что мы сделали с этой структурой, значительно увеличили скорость вставки, используя тот факт, что DAM позволяет нам бесплатно группировать записи в группы размером O(B). Это наш первый пример структуры, стоимость вставки которой ниже, чем стоимость поиска.

Дерево B-ε

Оказывается, можно рассматривать B-дерево и BRT как два самых крайних примера целого семейства структур данных. В частности, и B-дерево, и BRT являются примерами более общего понятия, называемого B-ε-деревом, где ε – реальная переменная в диапазоне от 0 до 1.

Дерево B-ε — это обобщение дерева 2-3, в котором каждый внутренний узел имеет от m до 2m ключей, где 0 . Каждый узел также сопровождается буфером размера k = O(B) . Это буферное пространство используется для ожидающих вставки в очередь, как и в BRT.

Одна из возможных стратегий реализации — установить m так, чтобы один блок был полностью заполнен ключами, когда ε = 1 , и чтобы m = 2, когда ε = 0 . Затем можно выбрать значение k, чтобы точно занимать любое пространство внутри блока, которое не используется для ключей (так, в частности, если ε = 1, то k = 0). С этими определениями становится ясно, что случай ε = 1 соответствует B-дереву, а ε = 0 дает вам BRT.

Как и следовало ожидать, алгоритм вставки B-ε работает практически так же, как описано выше для BRT. Чтобы определить временную сложность вставки, мы еще раз смотрим на амортизированную стоимость. Обратите внимание, что структура будет иметь O(log_Bε (N/B)) = O((log_B (N/B))/ε) = O(( log_B N)/ε) уровней и что при каждом разливе мы сможем передать дочернему элементу не менее O(B1-ε) элементов. Это означает, что после вставки N элементов в дерево мы будем разливать не более O(N/(B1-ε)) = O(N*Bε-1) раз. Это дает общую стоимость вставок O(N*Bε-1*(log_B N)/ε) , которая является амортизированной стоимостью O((Bε-1/ε)*log _Б Н) .

Временная сложность поиска — это просто количество уровней в дереве, т. е. O((log_B N)/ε) .

Фрактальное дерево

Эти результаты сложности для дерева B-ε предполагают заманчивую возможность: если мы установим ε = ½, у нас будет структура данных, чье асимптотическое время вставки будет строго лучше (на коэффициент sqrt B ), чем у B -деревья, но имеющие точно такое же асимптотическое время поиска. Эта структура данных получила экзотическое название «фрактальное дерево». К сожалению, эта идея запатентована основателями Tokutek (сейчас Percona), поэтому в коммерческих целях они используются только в таких продуктах Percona, как TokuDB. Если вы хотите узнать больше о том, что вы упускаете, есть хорошая статья в блоге компании и технический документ.

Дерево слияния с логарифмической структурой

Последняя структура данных, которую мы рассмотрим, дерево слияния с логарифмической структурой (LSMT) соперничает по популярности с почтенным B-деревом и является технологией, лежащей в основе большинства хранилищ NoSQL.

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

Есть два класса LSMT, соответствующих этой общей схеме: многоуровневые и одноуровневые.

В уровневом LSMT ваша коллекция представляет собой список B-деревьев размером не более O(B), O(B*k), O(B*k2), O(B*k3) и т. д. для некоторых фактор роста к. Назовите эти уровни 0, 1, 2 и так далее. Новые элементы вставляются в дерево уровня 0. Когда это дерево превышает предельный размер, оно объединяется с деревом уровня 1, что, в свою очередь, может вызвать рекурсивное слияние.

Обратите внимание, что если мы вставим N элементов в уровневый LSMT, будет O(logk (N/B)) B-деревьев, а в последнем будет O(N/B) элементов. Следовательно, поиск имеет сложность O(log_B N * log_k (N/B)) . Чтобы получить стоимость обновления, обратите внимание, что элементы на последнем уровне были объединены на полных уровнях O(log_k (N/B)) и будут объединены в среднем на O( k) раз на каждом уровне, прежде чем перейти к следующему. Следовательно, амортизированная стоимость вставки равна O((k * log_k (N/B)) / B) .

Если мы установим k = ½, то сложность поиска и вставки упростится до O((log_B N)2) и O(log_B N / sqrt B) соответственно. .

В многоуровневом LSMT все немного по-другому. В этой схеме у нас есть промежуточный буфер размера O(B) и более одного дерева на каждом уровне: в частности, на уровне i >= 0 у нас есть до k B-деревьев размера ровно O(B*ki) . Новые элементы вставляются в промежуточный буфер. Когда место заканчивается, мы превращаем его в B-дерево и вставляем на уровень 0. Если это приводит к тому, что у нас на уровне больше k деревьев, мы объединяем k деревьев вместе в одно дерево размера O(B *k), который мы можем попытаться вставить на уровень 1, что, в свою очередь, может вызвать рекурсивное слияние.

Аргументы сложности, которые мы привели для одноуровневого LSMT, практически не изменились в этой новой настройке, показывая, что две схемы имеют одинаковые затраты. LSMT соответствуют производительности вставки фрактальных деревьев, но страдают от дополнительных логарифмических коэффициентов при поиске. Чтобы попытаться сократить время поиска, на практике большинство реализаций LSMT хранят каждое B-дерево вместе с фильтром Блума, что позволяет им избежать полного доступа к дереву, когда интересующий ключ определенно не включен в него.

В Интернете есть несколько хороших обзоров LSMT.

Эксперименты

Чтобы подтвердить свои знания об этих структурах данных, я написал программу на Python, которая пытается выполнить сравнение яблок с яблоками различных вариантов дерева B-ε. Код реализует структуру данных, а также регистрирует, сколько логических блоков ему нужно было бы коснуться, если бы дерево было фактически реализовано на устройстве с блочной структурой (на самом деле я просто представляю его как объект Python). Я предполагаю, что как можно больше деревьев ближе к вершине дерева хранится в памяти и поэтому не затрагивает блочное устройство.

Эти экспериментальные результаты соответствуют тому, что мы ожидали от теоретического анализа: BRT имеет значительное преимущество перед альтернативами, когда дело доходит до записи, B-деревья являются худшими, а фрактальные деревья занимают промежуточное положение.

Эквивалентные результаты для чтения следующие:

По сути, это зеркальное отражение результатов записи, показывающее, что здесь мы принципиально идем на компромисс.

Обзор

Мы можем свести все, что узнали выше, в следующую таблицу:

Эти результаты показывают, что вы всегда должны предпочесть использовать фрактальное дерево любому из B-деревьев, LSMT или 2-3-деревьев. В реальном мире все может быть не так однозначно: в частности, из-за патентной ситуации с фрактальным деревом может быть сложно найти бесплатную и качественную реализацию этой структуры данных.

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

Мотивация: графы перекрытия с точным совпадением широко используются в контексте сборки ДНК и в задаче о самой короткой суперстроке, где количество строк n колеблется от тысяч до миллиарды. Длина ℓ строк составляет от 25 до 1000, в зависимости от технологий секвенирования ДНК. Однако многие сборщики ДНК, использующие графы перекрытия, страдают от необходимости тратить слишком много времени и места на построение графов. Эти сборщики ДНК практически не в состоянии обрабатывать огромные объемы данных, создаваемых технологиями секвенирования следующего поколения, где количество строк n может достигать нескольких миллиардов.Если граф перекрытий хранится явно, для него потребуется Ω(n 2 ) памяти, что на практике может оказаться недопустимым, если n превышает сто миллионов. В этой статье мы предлагаем новую структуру данных, с помощью которой можно компактно хранить граф перекрытий. Эта структура данных требует только линейного времени для построения и линейной памяти для хранения.

Результаты. Для заданного набора входных строк (также называемых прочтениями) мы можем неофициально определить граф точного совпадения следующим образом. Каждое чтение представлено в виде узла на графе, и между двумя узлами есть ребро, если соответствующие чтения достаточно перекрываются. Далее следует формальное описание. Максимальное точное совпадение двух строк x и y, обозначаемое как ov_max(x , y) — самая длинная строка, состоящая из суффикса x и префикса y. Граф точного совпадения n с заданными строками длины ℓ — это взвешенный по ребрам граф, в котором каждая вершина связана со строкой и существует ребро (x, y) веса ω=ℓ−|ov_max(x, y )| тогда и только тогда, когда ω≤λ, где |ov_max(x, y)| — длина ov_max(x, y), а λ — заданный порог. В этой статье мы показываем, что графы перекрытия с точным совпадением могут быть представлены компактной структурой данных, которая может храниться с использованием не более чем (2λ−1)(2⌈logn⌉+⌈logλ⌉ )n бит с гарантией того, что базовая операция доступа к ребру занимает O(log λ) времени. Мы также предлагаем два алгоритма построения структуры данных для графа точного совпадения. Первый алгоритм выполняется за O(λℓnlogn) в худшем случае и требует O(λ) дополнительная память. Второй выполняется за O(λℓn) времени и требует O(n) дополнительной памяти. Наши экспериментальные результаты на огромном количестве смоделированных данных из сборки последовательности показывают, что структура данных может быть построена эффективно с точки зрения времени и памяти.

1 ВВЕДЕНИЕ

График точного совпадения n заданных строк длины ℓ каждая представляет собой взвешенный по ребрам граф, определяемый следующим образом. Каждая вершина связана со строкой, и существует ребро (x, y) веса ω=ℓ−|ov_max(x, y)| тогда и только тогда, когда ω≤λ, где λ — заданный порог и |ov_max(x, y )| длина максимального точного совпадения двух строк x и y. τ=ℓ−λ≤|ov_max(x, y)| называется порогом перекрытия. Формальное определение графа точного совпадения дано в разделе 2.

Эффективное хранение графиков перекрытий с точным совпадением с точки зрения памяти становится важным, когда количество строк очень велико. В литературе есть две общие структуры данных для хранения общего графа: G=(V, E). Первая структура данных использует двумерный массив размером |V|×|V|. Мы называем это структурой данных на основе массива. Одним из его преимуществ является то, что время доступа к заданному ребру составляет O(1). Однако для этого требуется Ω(|V| 2 ) памяти. Вторая структура данных хранит набор ребер E. Мы называем это пограничной структурой данных. Для этого требуется Ω(|V|+|E|) памяти, а время доступа к данному ребру составляет O(logΔ), где Δ является степенью графа. Обе эти структуры данных требуют Ω(|E|) памяти. Если графики точного совпадения хранятся с использованием этих двух структур данных, нам потребуется Ω(|E|) памяти. Даже такой большой объем памяти может оказаться невыполнимым в случаях, когда количество строк превышает сто миллионов. В этой статье мы сосредоточимся на структурах данных для графов перекрытия с точным совпадением, которые требуют гораздо меньше памяти, чем |E|.

1.1 Наш вклад

Мы показываем, что существует компактная структура данных, представляющая граф перекрытия с точным совпадением, для которой требуется гораздо меньше памяти, чем для |E| с гарантией того, что базовая операция доступа к ребру занимает O(logλ) времени, что является почти константой в контексте сборки ДНК. Структура данных может быть построена эффективно во времени и в памяти. В частности, мы показываем, что

Структура данных занимает не более (2λ−1)(2⌈logn⌉+⌈logλ⌉)n бит.

Структура данных может быть построена за O(λℓn) времени.

В результате любой алгоритм, использующий перекрывающиеся графы и работающий за время T, можно смоделировать с помощью нашей компактной структуры данных. В этом случае необходимая память составляет не более (2λ−1)(2⌈logn⌉+⌈logλ⌉)n бит (для хранения графа перекрытий) и необходимое время составляет O(Tlogλ).Если λ является константой или намного меньше, чем n, наша структура данных будет идеальным решением для любого приложения, у которого недостаточно памяти для хранения графа перекрытий традиционным способом.

Наше утверждение может показаться противоречивым, потому что в некоторых графах с точным совпадением количество ребер может быть Ω(n 2 ), и кажется, что для этого потребуется Ω(n 2 ) время и память для их создания. К счастью, благодаря некоторым особым свойствам графов точного совпадения мы можем эффективно строить и хранить их. В Разделе 3.1 мы подробно опишем эти специальные свойства.

Вкратце, идея компактного хранения графа перекрытий основана на следующем простом наблюдении. Если строки отсортированы в лексикографическом порядке, то для любой строки x лексикографические порядки строк, содержащих x в качестве префикса, находятся в определенном целочисленном диапазоне или целочисленном интервале [а, б]. Следовательно, информация о внешней окрестности вершины может быть описана с помощью не более чем λ интервалов. Такие интервалы обладают хорошим свойством: они либо не пересекаются, либо содержат друг друга. Это свойство позволяет описать внешнюю окрестность вершины не более чем 2λ−1 непересекающимися интервалами. Каждый интервал стоит 2⌈logn⌉+⌈logλ⌉) битов, где 2⌈logn⌉ битов предназначены для хранения двух его границ, а ⌈logλ⌉ битов предназначены для хранения вес. У нас есть n вершин, поэтому объем памяти, требуемый нашей структурой данных, не превышает (2λ−1)(2⌈logn⌉+⌈logλ⌉)n бит. Обратите внимание, что это всего лишь верхняя граница. На практике объем памяти может быть намного меньше.

1.2 Применение: сборка ДНК

Основная мотивация для создания графов точного совпадения связана с их использованием в реализации алгоритмов быстрой аппроксимации для задачи о самой короткой суперстроке, которая является самой первой постановкой задачи для сборки ДНК. Графики точного совпадения можно использовать и для других формулировок задач сборки ДНК.

Графики точного совпадения широко используются в контексте сборки ДНК и в задаче о самой короткой суперцепочке, где количество строк n колеблется от тысяч до миллиардов. Длина ℓ строк составляет от 25 до 1000, в зависимости от используемой технологии секвенирования ДНК. Однако многие сборщики ДНК, использующие графы перекрытия, требуют много времени и памяти. Если граф перекрытий сохранен явно, для него потребуется Ω(n 2 ) памяти, что на практике может оказаться непомерно большим. В этой статье мы представляем структуру данных для представления графов перекрытий, которая требует только линейного времени и линейной памяти. Экспериментальные результаты показали, что наш предварительный ассемблер последовательности ДНК, использующий эту структуру данных, может обрабатывать большое количество строк. В частности, требуется около 2,4 дня и 62,4 ГБ памяти для обработки набора из 660 миллионов строк ДНК длиной 100 каждая. Набор последовательностей ДНК случайным образом выбирается из эталонного генома человека размером 3,3 миллиарда пар оснований.

1.3 Связанная работа

Гасфилд и др. (1992) и Гасфилд (1997) рассматривают проблему всех пар суффикс-префикс, которая на самом деле является частным случаем вычисления точного соответствия графики перекрытия, когда λ=ℓ. Они разработали алгоритм времени O(ℓn+n 2 ) для решения проблемы всех пар суффикс-префикс. В этом случае граф точного совпадения является полным графом. Таким образом, время выполнения алгоритма оптимально, если граф точного совпадения хранится традиционным способом.

Хотя время выполнения алгоритма Гасфилда et al. теоретически является оптимальным в этих условиях, он использует обобщенное дерево суффиксов, которое на практике имеет два недостатка. Первый недостаток заключается в том, что суффиксное дерево занимает довольно много места (Kurtz, 1999). Второй недостаток заключается в том, что суффиксное дерево обычно страдает от плохой локальности ссылок на память (Ohlebusch and Gog, 2010). К счастью, Абуэльхода et al. (2004) предложили структуру моделирования дерева суффиксов, которая позволяет моделировать любой алгоритм, использующий дерево суффиксов, с помощью расширенных массивов суффиксов. Олебуш и Гог (2010) использовали свойства расширенных массивов суффиксов для разработки алгоритма решения проблемы суффикс-префикс для всех пар напрямую, без использования среды моделирования суффиксного дерева. Время выполнения алгоритма Олебуша и Гога также составляет O(ℓn+n 2 ). Обратите внимание, что нашу структуру данных и алгоритм можно использовать для решения проблемы суффикс-префикс за O(λℓn) времени. В контексте сборки ДНК λ обычно намного меньше, чем n, поэтому наш алгоритм будет быстрее алгоритмов Гасфилда (1997) и Олебуша и Гога (2010).

График перекрытия с точным совпадением следует отличать от графа перекрытия с приблизительным совпадением, который рассматривается в Myers (2005), Medvedev et al. (2007 г.) и Поп (2009 г.). В графе перекрытий с приблизительным совпадением ребро между двумя строками x и y существует тогда и только тогда, когда существует префикс x, скажем x′, и есть суффикс y, скажем, y′, такой, что расстояние редактирования между x′ и y′ не превышает определенного порога.

2 ФОН

Пусть Σ будет алфавитом. Размер Σ является константой. В контексте сборки ДНК Σ=A, C, G, T>. Длина строки x на Σ, обозначаемая |x|, равна количеству символов в x. Пусть x[i] будет i-м символом строки x, а x[i, j] — подстрока x между i-м и j позиций. Префиксом строки x является подстрока x[1, i] для некоторого i. Суффикс строки x — это подстрока x[i, |x|] для некоторого i .

Для двух строк x и y на Σ точное совпадение между x и y, обозначаемый как ov(x, y), представляет собой строку, которая является суффиксом x< /em> и префикс y (обратите внимание, что это определение несимметрично). Максимальное точное совпадение между x и y, обозначаемое как ov_max(x, y), – самое длинное совпадение с точным соответствием между x и y.

Графы перекрытия с точным совпадением: неформально, граф перекрытия с точным соответствием — это не что иное, как граф, в котором есть узел для каждого чтения, а два узла соединены ребром, если имеется достаточное перекрытие между соответствующими операциями чтения.

Мы начнем с краткого, неполного обзора основных структур данных в пандах, чтобы вы могли начать работу. Фундаментальное поведение в отношении типов данных, индексации и маркировки/выравнивания осей применяется ко всем объектам. Для начала импортируйте NumPy и загрузите pandas в свое пространство имен:

Вот основной принцип, о котором следует помнить: выравнивание данных является неотъемлемой частью. Связь между ярлыками и данными не будет разорвана, если только вы не сделаете это явным образом.

Мы дадим краткое введение в структуры данных, а затем рассмотрим все широкие категории функций и методов в отдельных разделах.

Серии¶

Series — это одномерный массив с метками, способный хранить данные любого типа (целые числа, строки, числа с плавающей запятой, объекты Python и т. д.). Метки осей вместе называются индексом. Основной метод создания серии — вызов:

Здесь данные могут быть самыми разными:

скалярное значение (например, 5)

Переданный индекс представляет собой список меток осей. Таким образом, это разделяется на несколько случаев в зависимости от того, какие данные:

От ндаррай

Если данные представляют собой ndarray, длина индекса должна быть такой же, как у данных. Если индекс не передан, он будет создан со значениями [0, . len(данные) - 1].

pandas поддерживает неуникальные значения индекса. При попытке выполнить операцию, не поддерживающую повторяющиеся значения индекса, в это время будет возбуждено исключение. Причина лени почти всегда связана с производительностью (во многих случаях в вычислениях, таких как части GroupBy, индекс не используется).

Из словаря

Серия может быть создана из словарей:

Если данные представляют собой словарь, а индекс не передается, индекс Series будет упорядочен в соответствии с порядком вставки словаря, если вы используете версию Python >= 3.6 и версию pandas >= 0.23.

Если вы используете Python Series, индексом будет лексически упорядоченный список ключей словаря.

В приведенном выше примере, если вы использовали версию Python ниже 3.6 или версию pandas ниже 0.23, серия будет упорядочена в соответствии с лексическим порядком ключей dict (например, ['a', 'b', 'c'], а не ['b', 'a', 'c'] ).

Если передается индекс, значения в данных, соответствующие меткам в индексе, будут извлечены.

NaN (не число) — это стандартный маркер отсутствующих данных, используемый в пандах.

Из скалярного значения

Если данные представляют собой скалярное значение, необходимо указать индекс. Значение будет повторяться, чтобы соответствовать длине индекса.

Серия похожа на ndarray¶

Series действует очень похоже на ndarray и является допустимым аргументом для большинства функций NumPy. Однако такие операции, как нарезка, также будут нарезать индекс.

Мы рассмотрим индексирование на основе массива, например s[[4, 3, 1]] в разделе об индексировании .

Как и массив NumPy, серия pandas имеет тип dtype .

Часто это тип NumPy. Однако pandas и сторонние библиотеки расширяют систему типов NumPy в нескольких местах, и в этом случае dtype будет ExtensionDtype. Некоторыми примерами в pandas являются категориальные данные и целочисленный тип данных Nullable. Дополнительные сведения см. в разделе dtypes.

Если вам нужен фактический массив, поддерживающий Series , используйте Series.array .

Доступ к массиву может быть полезен, когда вам нужно выполнить какую-либо операцию без индекса (например, чтобы отключить автоматическое выравнивание).

Series.array всегда будет ExtensionArray . Вкратце, ExtensionArray — это тонкая оболочка вокруг одного или нескольких конкретных массивов, например numpy.ndarray . pandas знает, как взять ExtensionArray и сохранить его в Series или столбце DataFrame. Дополнительные сведения см. в разделе dtypes.

Хотя Series похож на ndarray, если вам нужен настоящий ndarray, используйте Series.to_numpy() .

Даже если Series поддерживается ExtensionArray , Series.to_numpy() вернет NumPy ndarray.

Серия похожа на словарь¶

Серия похожа на словарь фиксированного размера в том смысле, что вы можете получать и устанавливать значения по метке индекса:

Если метка не содержится, возникает исключение:

При использовании метода get отсутствующая метка возвращает None или указанное значение по умолчанию:

Векторные операции и выравнивание меток с помощью Series¶

При работе с необработанными массивами NumPy цикл по значению обычно не требуется. То же самое верно и при работе с сериями в pandas. Серии также можно передавать в большинство методов NumPy, ожидающих ndarray.

Ключевое различие между Series и ndarray заключается в том, что операции между Series автоматически выравнивают данные на основе метки. Таким образом, вы можете записывать вычисления, не обращая внимания на то, имеют ли задействованные ряды одинаковые метки.

Результатом операции между невыровненными сериями будет объединение задействованных индексов. Если метка не найдена в той или иной серии, результат будет помечен как отсутствующий NaN . Возможность писать код без явного выравнивания данных дает огромную свободу и гибкость в интерактивном анализе данных и исследованиях. Интегрированные функции выравнивания данных структур данных pandas отличают pandas от большинства связанных инструментов для работы с помеченными данными.

В целом мы решили, что результатом операций между объектами с разными индексами по умолчанию является объединение индексов, чтобы избежать потери информации. Наличие метки индекса, хотя данные отсутствуют, обычно является важной информацией как часть вычислений. У вас, конечно, есть возможность сбрасывать ярлыки с отсутствующими данными с помощью функции dropna.

Имя атрибута¶

Серии также могут иметь атрибут имени:

Имя серии будет присваиваться автоматически во многих случаях, в частности, при получении одномерных срезов DataFrame, как вы увидите ниже.

Вы можете переименовать серию с помощью метода pandas.Series.rename().

Обратите внимание, что s и s2 относятся к разным объектам.

Фрейм данных¶

DataFrame – это двухмерная структура данных с метками, в которой столбцы могут быть разных типов. Вы можете думать об этом как об электронной таблице или таблице SQL или наборе объектов Series. Как правило, это наиболее часто используемый объект панд. Как и Series, DataFrame принимает различные типы входных данных:

Dict одномерных массивов, списков, dicts или серий

Вместе с данными можно дополнительно передать аргументы индекса (метки строк) и столбцов (метки столбцов). Если вы передаете индекс и/или столбцы, вы гарантируете индекс и/или столбцы результирующего DataFrame. Таким образом, dict Series плюс определенный индекс отбрасывают все данные, не соответствующие переданному индексу.

Если метки осей не переданы, они будут созданы из входных данных на основе правил здравого смысла.

Если данные представляют собой словарь, а столбцы не указаны, столбцы DataFrame будут упорядочены в соответствии с порядком вставки словаря, если вы используете версию Python >= 3.6 и pandas >= 0.23.

Если вы используете столбцы Python, не указано, столбцы DataFrame будут лексически упорядоченным списком ключей dict.

Из словаря серии или словарей¶

Результирующий индекс будет объединением индексов различных серий. Если есть какие-либо вложенные словари, они сначала будут преобразованы в Series. Если столбцы не переданы, столбцы будут упорядоченным списком ключей dict.

Доступ к меткам строк и столбцов можно получить соответственно, обратившись к атрибутам индекса и столбцов:

Когда определенный набор столбцов передается вместе с словарем данных, переданные столбцы переопределяют ключи в словаре.

Из списка ndarrays/lists¶

Все ndarrays должны быть одинаковой длины. Если передается индекс, он явно должен быть той же длины, что и массивы. Если индекс не передан, результатом будет range(n) , где n — длина массива.

Из структурированного или массива записей¶

Этот случай обрабатывается так же, как и массивы.

DataFrame не предназначен для работы в точности как двумерный NumPy ndarray.

Из списка дикторов¶

Из списка кортежей¶

Вы можете автоматически создать фрейм MultiIndexed, передав словарь кортежей.

Из серии¶

Результатом будет DataFrame с тем же индексом, что и у входной серии, и с одним столбцом, имя которого является исходным именем серии (только если не указано другое имя столбца).

Из списка именованных кортежей¶

Имена полей первого namedtuple в списке определяют столбцы DataFrame . Оставшиеся namedtuples (или кортежи) просто распаковываются и их значения передаются в строки DataFrame. Если какой-либо из этих кортежей короче первого именованного кортежа, то последующие столбцы в соответствующей строке помечаются как отсутствующие значения. Если какой-либо из них длиннее первого namedtuple , возникает ошибка ValueError.

Из списка классов данных¶

Новое в версии 1.1.0.

Класс данных, представленный в PEP557, можно передавать в конструктор DataFrame. Передача списка классов данных эквивалентна передаче списка словарей.

Обратите внимание, что все значения в списке должны быть классами данных, смешивание типов в списке приведет к ошибке TypeError.

Отсутствуют данные

На эту тему будет сказано гораздо больше в разделе «Отсутствующие данные». Чтобы создать DataFrame с отсутствующими данными, мы используем np.nan для представления отсутствующих значений. Кроме того, вы можете передать numpy.MaskedArray в качестве аргумента данных конструктору DataFrame, и его замаскированные записи будут считаться отсутствующими.

Альтернативные конструкторы¶

DataFrame.from_dict

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

Если вы передадите ориент='index' , ключами будут метки строк. В этом случае вы также можете передать нужные имена столбцов:

DataFrame.from_records

DataFrame.from_records принимает список кортежей или ndarray со структурированным dtype. Он работает аналогично обычному конструктору DataFrame, за исключением того, что результирующий индекс DataFrame может быть определенным полем структурированного dtype. Например:

Выбор столбца, добавление, удаление¶

Вы можете рассматривать DataFrame семантически как список объектов Series с одинаковыми индексами. Получение, установка и удаление столбцов работают с тем же синтаксисом, что и аналогичные операции dict:

Столбцы могут быть удалены или извлечены, как в случае со словарем:

При вставке скалярного значения оно естественным образом распространяется на всю колонку:

При вставке серии, которая не имеет того же индекса, что и DataFrame, она будет соответствовать индексу DataFrame:

Вы можете вставить необработанные ndarrays, но их длина должна соответствовать длине индекса DataFrame.

По умолчанию столбцы вставляются в конце. Функция вставки доступна для вставки в определенное место в столбцах:

Назначение новых столбцов в цепочках методов¶

Вдохновленный глаголом mutate dplyr, DataFrame имеет метод assign(), который позволяет легко создавать новые столбцы, которые потенциально являются производными от существующих столбцов.

В приведенном выше примере мы вставили предварительно вычисленное значение. Мы также можем передать функцию одного аргумента для оценки назначаемого DataFrame.

assign всегда возвращает копию данных, оставляя исходный DataFrame нетронутым.

Передача вызываемого объекта, а не фактического значения для вставки, полезна, когда у вас нет под рукой ссылки на DataFrame. Это обычное дело при использовании assign в цепочке операций. Например, мы можем ограничить DataFrame только теми наблюдениями, у которых длина чашелистика больше 5, вычислить отношение и построить график:

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

Сигнатура функции для assign — это просто **kwargs . Ключи — это имена столбцов для новых полей, а значения — это либо значение, которое нужно вставить (например, массив Series или NumPy), либо функция одного аргумента, которую нужно вызвать в DataFrame. Возвращается копия исходного DataFrame со вставленными новыми значениями.

Начиная с Python 3.6 порядок **kwargs сохраняется. Это позволяет использовать зависимое присваивание, когда выражение позже в **kwargs может ссылаться на столбец, созданный ранее в том же assign() .

Во втором выражении x['C'] будет ссылаться на вновь созданный столбец, равный dfa['A'] + dfa['B'] .

Читайте также:


Чтобы продолжить работу с того места, где вы остановились, перезапустите прослушивание, как решить

Как изменить страну в Google Chrome

Что нужно ввести в указанное поле, чтобы найти все файлы doc docx в общей папке

Как изменить пароль почты Google на компьютере

Почему в России не делают компьютерные игры?