Эффективная вставка и поиск строк

Question

В приложении у меня будет от 3000 до 30000 строк. После создания (чтение из файлов неупорядоченных) не будет много строк, которые будут добавляться часто (но иногда это будет!). Удаление строк также произойдет нечасто. Сравнение строки с сохраненными будет происходить часто.

Какую структуру я могу использовать лучше всего, хэш-таблицу, дерево (Red-Black, Splay, ....) или только по упорядоченному списку (возможно, StringArray?)?

(Дополнительное замечание: ссылка на хорошую реализацию C# будет оценено, а)

Answer 1

Похоже, вам просто нужна хэш-таблица. Таким образом, HashSet<T> будет идеальным выбором. (Вы, кажется, не требуют ключей, но Dictionary<T> будет правильным выбором, если вы сделали, конечно.)

Вот краткое изложение временной сложности различных операций на HashSet<T> размера n. Они частично основаны на том факте, что тип использует массив в качестве структуры данных резервного копирования.

• Вставка: Обычно O(1), но потенциально O(n) если массив должен быть изменен.
• Удаление:O(1)
• Exists (Содержит):O(1) (данные идеальное Hashtable ведра)

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

Answer 2

HashSet очень хорош для быстрой вставки и поиска скорости. Добавить, Удалить и Содержит O (1).

Редактировать-Добавить предполагает, что размер массива не требуется изменять. Если это так, как заявил Нолдорин, это O (n).

Я использовал HashSet на недавнем VB 6 (я его не писал) в .NET 3.5, где я выполнял итерацию вокруг коллекции, в которой были дочерние элементы, и каждый дочерний элемент мог отображаться в нескольких родительских элементах. Приложение обработало список предметов, которые я хотел отправить в API, который взимает много денег за звонок.

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

Answer 3

Ответы, рекомендующие HashSet<T>, являются точками, если ваши сравнения просто «эта строка присутствует в наборе или нет». Вы могли бы даже использовать разные версии IEqualityComparer<string> (возможно, выбрав их в StringComparer) для чувствительности к регистру и т. Д.

Это единственный тип сравнения, в котором вы нуждаетесь, или вам нужны такие вещи, как «где бы эта строка появилась в если это действительно упорядоченный список?«Если вам нужна такая проверка, то вы, вероятно, захотите сделать двоичный поиск. (List<T> предоставляет метод BinarySearch, я не знаю, почему и SortedDictionary этого не делают, так как оба смогут легко найти . по общему признанию SortedDictionary поиск не будет совсем же, как и обычный бинарный поиск, но он все равно обычно имеют схожие характеристики, я считаю.)

как я говорю, если вы только хотят «в наборе или не «проверка», HashSet<T> - твой друг. Я просто подумал, что я приведу остальных на случай :)

Answer 4

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

Это может быть чрезмерно спроектировано для набора только N = 30 000 вещей, которые в основном предварительно вычисляются. Возможно, вам даже лучше выделить массив k * N Optional и заполнить его пропуском k пробелов между каждой фактической вещью (таким образом уменьшая вероятность того, что ваши редкие вставки потребуют перераспределения, все еще оставляя вам вариант бинарного поиска и сохраняя ваши товары в отсортированном порядке. Если вам нужно точное «где бы эта строка появлялась в наборе», это не сработало бы, потому что вам понадобится время O (n) для проверки каждого пространства перед проверкой элемента, если бы это было пустое или O (n) время для вставки, чтобы обновить счетчик «сколько элементов на самом деле передо мной» в каждом слоте.Он мог бы предоставить вам очень быстрые индексы, хотя эти индексы были бы стабильными между вставками/удалениями .

Answer 5

Если вы ищете производительность в реальном времени или opti Я бы рекомендовал дерево оснований или явный суффикс или дерево префикса. В противном случае я, вероятно, использовал бы хэш.

Деревья имеют то преимущество, что имеют фиксированные границы для наихудшего поиска, времени вставки и удаления (в зависимости от длины шаблона, который вы ищете). У хэш-решений есть преимущество в том, что их намного проще кодировать (вы получаете их из коробки на C#), дешевле строить изначально и, если они правильно настроены, имеют аналогичную среднюю производительность. Тем не менее, они, как правило, используют больше памяти и имеют недетерминированный поиск времени, вставки (и в зависимости от реализации, возможно, удаления).