Что лучше всего относится к времени и пространству: фильтр Bloom, таблица Hash или словарь?

Ответ 1

В этом вопросе у вас действительно есть только две структуры данных на С#, поскольку словари на С# реализованы с использованием хеш-таблиц. Таким образом, мы будем ссылаться на словарь и HashTable как на хэш-таблицы. Если вы используете один из них, то вам, вероятно, нужен словарь из-за типа безопасности и производительности, как описано здесь: Почему словарь предпочтительнее, чем хэш-таблица? Но поскольку словарь реализуется с использованием хэш-таблица, это не огромная разница в любом случае.

Но реальный вопрос - это хеш-таблица (Словарь) против фильтра Блума. Кто-то ранее задал соответствующий вопрос, В чем преимущество использования фильтров цветка? Они также ссылаются на страницу Википедии на фильтры Блума, что весьма информативно: https://en.wikipedia.org/wiki/Bloom_filter Коротким вариантам ответа является то, что фильтры Bloom меньше и быстрее. Однако у них есть расходы, связанные с этим: они не совсем точны. В хеш-таблице исходная строка всегда сохраняется для точного сравнения. Сначала вы хэш значение, и это говорит вам, где в таблице, чтобы посмотреть. После того, как вы посмотрели в таблицу, вы затем проверите значение, расположенное там, против значения, которое вы ищете. В фильтре Bloom вы используете несколько хешей для вычисления набора местоположений. Если во всех этих местах есть 1, то вы считаете строку найденной. Это означает, что иногда строки будут "найдены", которые изначально не были вставлены. Если таблица слишком мала, на самом деле, вы можете достичь точки насыщения, где окажется, что любая строка, которую вы пытались, будет в фильтре Bloom. Поскольку вы знаете, сколько строк вы собираетесь вставлять, вы можете правильно отсортировать таблицу, чтобы этого избежать.

Посмотрим на размеры. Чтобы цифры вышли чисто, я собираюсь притвориться, что у вас ровно 4096 строк. Чтобы иметь таблицу хэшей с относительно низким столкновением, вы хотите, чтобы ваша таблица была как минимум равной числу строк. Таким образом, реалистично (предполагая 32-разрядные (4 байта) указатели), в этом случае вы будете смотреть на размер 4096 * 4 байта = 16K для таблицы плюс 4096 * (4 + 4 + 8) = 64K для узлы списка (следующий указатель + указатель строки) и строки. Таким образом, в целом, вероятно, около 80K, что, вероятно, не очень много памяти в большинстве ситуаций, где вы будете использовать С#.

Для фильтров Bloom мы должны решить, какой процент ошибок мы хотим достичь в наших расчетах по размеру. Когда мы говорим о частоте ошибок 1%, это означает, что из каждых 100 строк, которые не были вставлены в фильтр Блума, 1 было бы ложно указано как присутствующее. Строки, которые были вставлены, всегда будут правильно указаны как вставленные. Используя уравнение m = -n * ln (p)/(ln (2) ^ 2), мы можем вычислить минимальный размер, чтобы дать нам определенную частоту ошибок. В этом уравнении m - количество слотов в таблице, p - частота ошибок, а n - количество строк, которые нужно вставить. Итак, если мы установим p на 0,01 (ошибка 1%), то получим приблизительно 9,6 * 4096 бит = 9,6 * 512 байтов = 4.8K, что, очевидно, немного меньше. Но, действительно, 1% является довольно высоким для частоты ошибок. Таким образом, более реалистично, мы должны, вероятно, пойти на что-то большее, чем 0.0001%, которое выходит до 28.8 * 4096b бит = 28.8 * 512 bytes = 14.4K. Очевидно, что любой из них существенно меньше, чем 80K, которые мы вычислили для хеш-таблицы. Однако хэш-таблица имеет коэффициент ошибок 0, который явно меньше 1% или 0,0001%.

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

Ответ 2

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

Фильтр Bloom - это вероятностная структура данных, которая хороша для проверки того, определен ли элемент определенно не в наборе, но не может точно сказать, что-то находится в наборе. Он обычно используется в распределенных системах, чтобы избежать ненужных сетевых чтений. Каждый компьютер может хранить фильтр Bloom, какие записи могут быть в базе данных, и может отфильтровывать явно ненужные сетевые вызовы, не запрашивая удаленную систему, если фильтр исключен. Это не очень хорошо для того, что вы пытаетесь сделать, поскольку ложные срабатывания, вероятно, являются нарушителем транзакций.

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

Если вам нужен отсортированный порядок, есть две другие структуры, которые вы, возможно, захотите рассмотреть. Первым будет сбалансированное двоичное дерево поиска, которое поддерживает быстрый поиск и удаление и сохраняет элементы в отсортированном порядке. Существует много хороших реализаций; практически все хорошие языки программирования поставляются с реализацией. Другой - это trie, который поддерживает очень быстрый поиск и доступ и поддерживает сортировку заказов. Это может быть бит-неэффективным в зависимости от распределения ваших строк, но может быть именно то, что вы ищете.

Надеюсь, это поможет!

Ответ 3

A System.Collections.Hashtable в .NET 1.0 на самом деле такой же, как System.Collections.Generic.Dictionary, который представлен в .NET 2.0.

Я предлагаю вам использовать словарь, поскольку он безопасен по типу, указав свой ключ и свой тип значения. Hashtable принимает только тип объекта, вам нужно будет вернуть его в строку каждый раз, когда вы извлекаете данные.