Лекция
Привет, Вы узнаете о том , что такое Примеры и компромиссы и выводы, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое Примеры и компромиссы и выводы , настоятельно рекомендую прочитать все из категории Индексирование большого набора ключей с помощью конечных автоматов.
Мысленно я всегда воспринимал компьютерные науки как исследование вычислительных компромиссов . Представление упорядоченных множеств и отображений с помощью конечных автоматов является ярким лучом этого исследования. Учитывая, что большую часть этой статьи мы посвятили обсуждению преимуществ FST, теперь мы посвятим небольшой раздел недостаткам FST.
Несмотря на множество интересных вещей, которые вы можете сделать с помощью FST, они просто не подходят в качестве структуры данных общего назначения. При написании кода, если вам нужна неупорядоченная карта или упорядоченная карта, вы должны сразу добраться до a HashMapили a BTreeMap. Структура данных на основе FST имеет ряд препятствий, которые вы должны преодолеть, прежде чем она станет полезной.
Прежде всего, сколько ключей вы ожидаете иметь? Если вы вряд ли увидите более нескольких сотен тысяч ключей, то почти наверняка лучше использовать более простую структуру данных. Для поддержки таких запросов, как нечеткий поиск или регулярные выражения, вероятно, достаточно выполнить простое линейное сканирование по ключам, поскольку их не так много.
Во-вторых, как выглядят ваши ключи? Как выглядят ваши ценности? В этой статье я представил структуру данных на основе FST, которая знает, как хранить только ключи, представляющие собой последовательности байтов, и знает только, как хранить значения, которые представляют собой 64-битные целые числа без знака. Если трудно привести ваши ключи / значения в этот формат, то использование FST может не окупиться. (Тем не менее, я отмечаю, что обычно это возможно с некоторой работой. Например, если ваши ключи представляют собой 32-битные целые числа, то кодирование их в порядке байтов с прямым порядком байтов, так что каждое число занимает 4 байта, будет отлично работать с FST. работает, потому что прямой порядок байтов сохраняет естественный порядок целых чисел посредством лексикографического упорядочения. Об этом говорит сайт https://intellect.icu . Примечательно, что кодирование с прямым порядком байтов не будет работать! Вот небольшой игрушечный пример, в котором хранится набор простых целых чисел .)
В-третьих, определен ли на ваших ключах разумный порядок? Можно ли их отсортировать? В частности, хотя обычно можно придумать порядок, вам необходимо убедиться, что он сохраняется лексикографически после преобразования в байты (иначе запросы диапазона не будут работать). Сортировка ключей также обычно не является преградой для демонстрации, поскольку вы можете группировать ключи, сортировать их и создавать промежуточные FST, которые впоследствии можно объединить. Но это дополнительные расходы; в вашем случае это может стоить или не стоить.
В-четвертых, нужна ли вам регулярная мутация? Стандартные структуры данных, такие как HashMapи BTreeMapпозволяют вызывающей стороне безрассудно добавлять, удалять или изменять ключи и их значения. Структура данных на основе FST, представленная в этой статье, не имеет такой возможности. А именно, однажды произведенный, он не может быть изменен. Как и другие препятствия, эта проблема также преодолима, но требует создания нового FST для каждой мутации. Выполнение этого зависит от того, сможете ли вы группировать свои мутации, что позволит периодически создавать новые FST вместо нового FST для каждого изменения.
Еще одно важное предостережение относительно использования fstящика, представленного в этой статье, заключается в том, что он более надежен в 64-битных системах. А именно, поскольку fstящик сильно поддерживает использование карт памяти, он должен обращаться к содержимому файла с помощью указателя. Если вы используете 32-битную систему, то тип указателя может адресовать большую 4 GBчасть данных, что означает, что ваши FST ограничены этим размером (но, вероятно, меньше, в зависимости от доступности виртуальной памяти в вашей системе). Например, это сделало бы невозможным создание и поиск Common Crawl FST. (Если вы построили его в 64-битной системе, перенесли в 32-битную систему и попытались выполнить поиск, fstящик запаникует , что обычно приводит к прерыванию программы.)
В 64-битной системе размер вашего FST фактически ограничен доступной виртуальной памятью. В 64-битной системе имеется большое количество виртуальной памяти .
Следовательно, если вы используете FST в 32-битной системе, вам необходимо позаботиться об ограничении размера создаваемых FST. Это немного сложно, так как невозможно узнать, насколько большой будет FST, пока он не будет создан. Это также означает, что любой процесс, который хочет выполнить поиск в FST, должен будет выполнять поиск по всем компонентам FST таким образом, чтобы не исчерпать доступную виртуальную память.
Формат FST в памяти и на диске сильно зависит от возможности быстрого доступа к любому конкретному байту FST. К сожалению, здесь мало ссылок. (Могут быть некоторые, но для подтверждения этого требуется дополнительный анализ и, вероятно, он сильно зависит от того, как используется избыточность в ключах.) Это означает, что если ваш FST находится на механическом диске и еще не в памяти, то запрос потенциально может быть довольно медленным. Это в основном смягчается использованием SSD с нулевой задержкой поиска, который, очевидно, хорошо поддерживает случай использования произвольного доступа.
Если ваши FST действительно большие, то SSD могут быть непомерно дорогими. Но, как мы показали в экспериментах выше, даже с более чем 1 миллиардом ключей FST вырос до всего 27 GB. В таком случае использование SSD кажется довольно рентабельным. Фактически, даже использование ОЗУ на таком уровне использования памяти может быть рентабельным. Например, машина с 61 GBОЗУ сейчас используется $0.0961/hourкак спотовый инстанс Amazon EC2 ( r3.2xlarge).
Вариант использования «держать FST в ОЗУ» хорошо поддерживается fstящиком. Несмотря на то, что я настаиваю на использовании карт памяти, также, конечно, можно хранить FST непосредственно в куче, что означает, что вы не будете восприимчивы к кешу страниц операционной системы. (Конечно, вы все еще можете быть подвержены обмену, но, насколько я понимаю, в наши дни большинство людей отключает это.)
Спасибо, что были со мной так далеко! Я надеюсь, что эта статья научила вас кое-чему об использовании конечных автоматов в качестве структуры данных, которые позволяют хранить большое количество ключей в небольшом пространстве, оставаясь при этом легко доступными для поиска.
Мы также вкратце рассмотрели эффективную реализацию идей в этой статье. Эта реализация предоставляется как часть fstящика, написанного на Rust. Он поставляется с полной документацией по API и примерами .
Наконец, вас могут заинтересовать другие работы, которые я проделал в Rust со строками:
Исследование, описанное в статье про Примеры и компромиссы и выводы, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое Примеры и компромиссы и выводы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Индексирование большого набора ключей с помощью конечных автоматов
Из статьи мы узнали кратко, но содержательно про
Комментарии
Оставить комментарий
Индексирование большого набора ключей с помощью конечных автоматов
Термины: Индексирование большого набора ключей с помощью конечных автоматов