Быстрая структура данных для небольших наборов

Question

Мне нужна структура данных, которая может очень быстро обрабатывать небольшие наборы (10-20 строк, максимум 50, различной длины). Ложные срабатывания - это нормально, а ложные срабатывания - нет.

Последнее требование заставляет фильтры Блума казаться подходящими, но я не уверен в их скорости, какие-либо другие рекомендации?

Редактировать: набор должен поддерживать только тест вставки + членство.

Answer 1

Как насчет массива строк, которые вы используете для цикла проверки членства с String.Equals?

Для наборов эта небольшая, причудливая структура данных может потребовать слишком много накладных расходов, а big-oh не применяется. Вы пытались сделать простейшую вещь и измерить это?

(Если ложные срабатывания в порядке, вы можете также сохранить, например, массив из 1024 булев, где вы вычисляете плохой «хеш» строк, просматривая только первые два символа, самые младшие 5 бит, чтобы получить 10-бит индекс в логический массив. Похоже, это будет всего несколько инструкций.)

Answer 2

Если набор строк для проверки членства намного больше, чем набор допустимых строк, тогда Trie может дать вам лучшую производительность, чем HashSet. Скорость поиска в хэш-наборе зависит от времени выполнения алгоритма хеширования, которое обычно составляет O (k), где k - длина строки. Это верно независимо от того, находится строка в хэш-наборе или нет.

При использовании Trie поиск по-прежнему равен O (k), но если строка отсутствует в Trie, поиск будет прекращен, как только один символ не совпадет. Поэтому в лучшем случае поиск недопустимой строки будет O (1).

Answer 3

В зависимости от того, какие операции вы хотите выполнить с устройством, наиболее быстрым будет, вероятно, HashSet<string>. Подробнее см. HashSet .

Сложение Спрашивая г-на Google, вот статья, написанная джентльменами, которые написали функцию Bloom Filter в C # . Тем не менее, он по-прежнему использует (несколько) хеш-коды для заполнения фильтра. Я ожидаю, что на небольших наборах данных это будет медленнее, чем HashSet.

Answer 4

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

HashSets теоретически лучшая структура данных для вашего требования, но поскольку база данных очень мала, структура O (log (n)), такая как SortedDictionary, часто предпочтительна, или, возможно, даже просто линейный поиск (как уже упоминалось). Я вспоминаю истории, в которых переход от коллекций на основе хеша к коллекциям на основе дерева резко повысил производительность для небольших наборов.

Лучший способ - переключаться между ними и сравнивать производительность каждого из них.

Answer 5

Если HashSet слишком медленный для вас, вы можете использовать классическую технику компрессора LZ: массив хеш-кодов фиксированного размера, где каждая запись указывает на связанный список строк.

Если вы знаете область ваших данных, просто создайте идеальную хеш-функцию и используйте ее. Если это не ваш случай, вы можете использовать string.GetHashCode () что-то вроде Murmur hash и использовать хеш (str)% array.Length в качестве индекса массива.

Я полагаю, размер массива 256-512 записей достаточно хорош для вашей структуры данных с 50 строками.

Answer 6

Почему бы не использовать Radix Tree ? Это специализированная структура данных набора, основанная на дереве, который используется для хранения набора строк.

Answer 7

Проверьте System.Collections.Specialized Namespace на MSDN.

Особенно HybridDictionary и StringDictionary.

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