목록과의 빠른 문자열 비교

Question

주어진 문자열이 문자열 목록에 있는지를 확인하는 빠른 방법이 필요합니다.

문자열 목록이 없습니다 런타임까지 알려져 있지만, 그 이후는 변경되지 않습니다.

나는 단순히 List<String>가 strings라고 다음을 수행 할 수 : 목록에있는 많은 문자열이있는 경우

if (strings.Contains(item)) 

그러나이 제대로 수행합니다.

HashSet<String>도 사용할 수 있지만이 경우 모든 수신 문자열에 GetHashCode과 Equals을 호출해야합니다. 예를 들어. 목록에있는 문자열은 3 개. 이 내용이 일 때 빠른 일 필요가 있음을 언급 했습니까? 내가 설정 할 수

오히려 HybridDictionary의 논리처럼, 문자열의 수 (10 개 미만 문자열에 대한 예를 들어, 사용 목록, HashSet의 기타)에 따라 List 또는 HashSet 사용하기로 결정.

문자열이 유니 코드이기 때문에 표준 트리 구조는 작동하지 않지만 기수 나무/패트리샤 토리가 작동 할 수 있습니다. 벤치 마크가있는 좋은 C# 구현이 있습니까?

일부 사용자는 String의 GetHashCode을 우회하고 더 빠른 성능의 해시 기능을 사용하는 것에 대해 언급했습니다. 밖에 벤치 마크가 있습니까?

기본적으로 LINQ 표현식을 사용하여 최적화 된 switch 문을 작성하는 것은 매우 흥미로운 새로운 접근 방식입니다.

그 밖의 다른 방법은 무엇입니까? 설치 비용은 검색 속도 만 중요하지 않습니다. 이 중요한 경우

, 들어오는 문자열 값은 거의 목록에 표시되지 않습니다.

Answer 1

체크 아웃이 : 당신의 "목록입니다 작은"문제를 다시

Jomo Fisher - Fast Switching with LINQ

Gustavo Guerra - StaticStringDictionary - Fast Switching with LINQ revisited

Answer 2

trie을 사용하여 문자열 목록을 보관할 수 있습니다. 빠른 시도를 위해 설계되었습니다. trie val. C#에서 트라이를 구현하는 방법은 one example입니다.

업데이트 : Powerpoint presentation on folded tries for Unicode 및

Answer 3

Ifo on implementation of a folded trie for Unicode (not C#) 당신이 (.NET 3)을 HashSet 클래스를 사용하여 고려 가지고 대신?

Answer 4

; 비 제너릭 컬렉션을 사용하지 않으려면 System.Collections.Specialized.HybridDictionary이 이와 같은 작업을 수행합니다. 작은 경우 System.Collections.Specialized.ListDictionary을 캡슐화하거나 더 커질 경우 System.Collections.Hashtable을 캡슐화합니다 (>10). 보람이 있니?

---

그렇지 않으면; 사용자 정의 비교 자와 함께 HashSet<T>을 사용할 수 있습니까?그럼 당신은

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

는 아마도 HybridDictionary 여기에 더 나은 옵션입니다 ... GetHashCode()가 얼마나 비싼 선택할 수 있습니다. 내부 사용은 컬렉션에있는 항목 수에 따라 다릅니다.

Answer 6

메모리가 작동하면 String이 생성 될 때 HashValue가 사전 계산되어이 유스 케이스 유형의 최적화를 위해 String으로 저장됩니다. 문자 배열 또는 StringBuilder를 사용하는 경우에는 분명히 적용되지 않지만 변경 불가능한 String의 경우에는 적용해야합니다.

EDIT : 잘못되었습니다 ... Java는 문자열의 HashCode를 캐시합니다. C#은 않습니다.

Answer 7

내가이 일을 결국 : 나는 당신이 List<string>에 대한 확장 메서드를 만들 수 같은데요,하지만 내 요구에 충분했다

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

    return contains; 
} 

.

Answer 8

문자열 인터 네킹을 사용하면이 작업을 매우 빠르게 처리 할 수 ​​있습니다. 목록을 작성할 때 필요한 문자열의 내부 형식 (결과 : 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; 
} 

이렇게하면 각 목록에 대해 4 바이트 비교가되고 원래 문자열에 대해 하나의 패스가됩니다. 문자열의 인턴 풀은 빠른 문자열 비교와 이미 존재하는 문자열을 찾아 낼 수 있도록 특별히 제작되었으므로 인턴 운영은 매우 빨라야합니다.