Быстрое сравнение строк со списком

Question

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

Список строк не известен до времени выполнения, но после этого он не изменится.

Я мог бы просто List<String> назвать strings и затем сделать:

if (strings.Contains(item))

Однако это будет работать плохо, если в списке много строк.

Я также мог бы использовать HashSet<String>, но это потребовало бы вызова GetHashCode для каждой входящей строки, а также Equals, что было бы пустой тратой, если, например, есть. только 3 строки в списке. Я упоминал, что это должно быть быстро ?

Я мог бы при настройке решить использовать List или HashSet в зависимости от количества строк (например, использовать List для менее чем 10 строк, HashSet в противном случае), скорее как логика в HybridDictionary.

Поскольку строки в формате Unicode, стандартная структура Trie не будет работать, хотя дерево Radix / Patricia trie могло бы работать. Есть ли хорошие реализации C # с тестами?

Некоторые упоминали, что обходили String GetHashCode и использовали более быструю хэш-функцию. Есть ли какие-то ориентиры?

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

Что еще будет работать? Стоимость установки не важна, просто скорость поиска.

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

Answer 1

Вы можете использовать trie для хранения списка строк; Попытки были разработаны для быстрого повторного Trie Val. Вот один пример реализации дерева в C #.

Обновление : Представление Powerpoint при сложенных попытках для Unicode и Ifo при реализации свернутого дерева для Unicode (не C #)

Answer 2

Проверьте это:

Jomo Fisher - Быстрое переключение с LINQ

Густаво Герра - StaticStringDictionary - Быстрое переключение с использованием LINQ, вновь

Answer 3

Я закончил этим:

private static bool Contains(List<string> list, string value)
{
    bool contains = null != list.Find(str => str.ToLower().Equals(value.ToLower()));

    return contains;
}

Полагаю, вы могли бы создать метод расширения для List<string>, но этого было достаточно для моих нужд.

Answer 4

Возможно, HybridDictionary является лучшим вариантом здесь. Его внутреннее использование зависит от количества предметов в коллекции.

Answer 5

Re ваш "когда список мал" озабоченность; если вы не возражаете против использования неуниверсальных коллекций, System.Collections.Specialized.HybridDictionary делает что-то подобное; он инкапсулирует System.Collections.Specialized.ListDictionary, когда он маленький, или System.Collections.Hashtable, когда он становится больше (>10). Стоит посмотреть?

---

В противном случае; Вы могли бы возможно использовать HashSet<T> с пользовательским компаратором? Тогда вы можете выбрать, сколько стоит GetHashCode() ...

using System;
using System.Collections.Generic;

class CustomStringComparer : IEqualityComparer<string> {
    public bool Equals(string x, string y) {
        return string.Equals(x, y);
    }
    public int GetHashCode(string s) {
        return string.IsNullOrEmpty(s) ? 0 :
            s.Length + 273133 * (int)s[0];
    }
    private CustomStringComparer() { }
    public static readonly CustomStringComparer Default
        = new CustomStringComparer();
}
static class Program {
    static void Main() {
        HashSet<string> set = new HashSet<string>(
            new string[] { "abc", "def", "ghi" }, CustomStringComparer.Default);
        Console.WriteLine(set.Contains("abc"));
        Console.WriteLine(set.Contains("abcde"));
    }
}

Answer 6

Рассматривали ли вы вместо этого класс HashSet (в .NET 3)?

Answer 7

Вы можете использовать интернирование строк, чтобы сделать это очень быстро. При построении списка вы должны сохранить интернированный формат требуемой строки (результат string.Intern()). Затем необходимо сравнить с интернированной строкой с object.ReferenceEquals - поскольку интернированные строки имеют одинаковую ссылку.

List<string> BuildList() {
    List<string> result;
    foreach (string str from StringSource())
         result.Add(str.Intern());
    return result;
}

bool CheckList(List<string> list, string stringToFind) { // list must be interned for this to work!
    return list.Find(str => object.ReferenceEquals(str, stringToFind)) != null;
}

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

Answer 8

Кроме того, если память служит, когда строится строка, ее значение HashValue предварительно вычисляется и сохраняется со строкой в ​​качестве оптимизации для этого варианта использования. Если вы используете массив символов или StringBuilder, это, очевидно, неприменимо, но для неизменяемой строки это должно быть.

РЕДАКТИРОВАТЬ: я не прав ... Java кэширует HashCode строки, C # не делает.