Szybkie porównywanie ciągów z listą

Question

Potrzebuję szybkiej metody do określenia, czy dany ciąg znajduje się na liście ciągów.

Lista ciągów znaków nie jest znana do czasu wykonania, ale po tym czasie nie ulegnie zmianie.

I może po prostu mieć List<String> nazywa strings a następnie wykonaj:

if (strings.Contains(item)) 

Jednak to będzie działać źle, jeśli istnieje wiele ciągi w wykazie.

Mogę również użyć HashSet<String>, ale wymagałoby to wywołania GetHashCode na każdym przychodzącym łańcuchu, a także Equals, który byłby stratą, gdyby istniały np. tylko 3 ciągi na liście. Czy wspomniałem, że musi to być szybko?

mogę podczas konfigurowania zdecyduje się użyć List lub HashSet zależności od liczby łańcuchów (na przykład wykorzystanie listy mniej niż 10 Ciągi HashSet inaczej), a jak logika HybridDictionary.

Ponieważ łańcuchy są w formacie Unicode, standardowa struktura Trie nie zadziała, chociaż może być to drzewo Radix/Patricia. Czy są jakieś dobre implementacje C# z benchmarkami?

Niektórzy wspomnieli o obejściu StringGetHashCode i użyciu szybciej działającej funkcji skrótu. Czy są tam jakieś testy porównawcze?

Używanie wyrażeń LINQ do stworzenia zoptymalizowanego przełącznika jest nowatorskim podejściem, które wygląda bardzo interesująco.

Co jeszcze by zadziałało? Koszt instalacji nie jest ważny, tylko prędkość wyszukiwania.

Jeśli to ma znaczenie, przychodzące wartości ciągów rzadko pojawią się na liście.

Answer 1

Sprawdź te:

Jomo Fisher - Fast Switching with LINQ

Gustavo Guerra - StaticStringDictionary - Fast Switching with LINQ revisited

Answer 2

Można użyć trie do przechowywania listy ciągów; Próby zostały zaprojektowane dla szybkiej re trie val. Oto one example implementacji trie w języku C#.

Aktualizacja: Powerpoint presentation on folded tries for Unicode i Ifo on implementation of a folded trie for Unicode (not C#)

Answer 3

Czy bierzesz pod uwagę przy użyciu klasy HashSet w .NET (3) zamiast?

Answer 4

Re swoim "gdy lista jest mały" troski; jeśli nie masz nic przeciwko używaniu nietypowych kolekcji, to coś takiego zrobi: System.Collections.Specialized.HybridDictionary; hermetyzuje on System.Collections.Specialized.ListDictionary, gdy jest mały lub System.Collections.Hashtable, gdy staje się większy (>10). Warte zobaczenia?

---

W przeciwnym razie; być może użyjesz HashSet<T> z niestandardowym narzędziem porównującym?Następnie można wybrać, jak drogie jest 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 5

Może HybridDictionary jest lepszym rozwiązaniem tutaj. Jego wewnętrzne użycie zależy od tego, ile elementów jest w kolekcji.

Answer 6

Na marginesie, jeśli pamięć jest serwowana, podczas konstruowania łańcucha wartość jego HashValue jest wstępnie obliczana i zapisywana za pomocą ciągu znaków jako optymalizacja dla tego typu przypadku użycia. Jeśli używasz tablicy znaków lub StringBuilder, to oczywiście nie ma zastosowania, ale w przypadku niezmiennego String powinno.

EDYCJA: Jestem niepoprawny ... Java robi cache Stringa HashCode, C# nie.

Answer 7

skończyło się w ten sposób:

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

    return contains; 
} 

Zgaduję można utworzyć metodę rozszerzenia dla List<string>, ale to było wystarczające dla moich potrzeb.

Answer 8

Można użyć sekwencji strun do tego bardzo szybko. Podczas budowania listy, musisz przechowywać wymagany format internowanego łańcucha (wynik string.Intern()). Następnie należy porównać z internowanym ciągiem znaków z object.ReferenceEquals - ponieważ internowane łańcuchy mają takie same referencje.

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; 
} 

Spowoduje to czterobajtowe porównanie dla każdej listy i jedno przejście przez oryginalny ciąg. Wewnętrzna pula łańcuchów została zbudowana specjalnie do szybkiego porównywania ciągów i znajdowania, jeśli już istnieje, więc operacja intern powinna być dość szybka.