한 문자열과 와일드 카드 그룹을 비교하는 가장 빠른 방법

Question

나는 사전이 있고 내 키는 와일드 카드 문자열입니다. 하나의 문자열이 사전에있는 키와 일치하는지 알고 싶습니다.

예 :

String str = "Really Large String"; 
Dictionary dic = new Dictionary<String, MyClass>(); 
dic.Add("First+Match*", new MyClass()); 
dic.Add("*Large*", new MyClass()); 

편집 : 나는 그런 짓을 할 :

foreach(var s in dic.Keys){ 
    if(str.Match(s)) 
    //Do Something 
} 

Answer 1

왜,

var dic = Dictionary<Regex, MyClass>() 
dic.Add(new Regex("..."), new MyClass) 
.... 

foreach(var match in dic.Keys.Where(k => k.IsMatch(str))) 
{ 
    var myClass = dic[match]; 
    .... 
} 

이제 문제는 아마도 Match라는 Predicate로, 문자열 자체에 일치합니다. 당신은 단지 첫 경기를하려면

var matchers = new HashSet<MyClass>(); 
matchers.Add(new MyClass("some regex?"); 
.... 

foreach(var match in matchers.Where(Match(str))) 
{ 
    .... 
} 

편집

당신은 FirstOrDefault 대신 Where 사용할 수 있습니다.

var firstMatch = matchers.FirstOrDefault(Match(str)) 
if (firstMatch != null) 
{ 
    .... 
} 

그러나 목록의 순서가 중요합니다.

MyClass의 부분적인 구현이 Match 술어가 될 수 iclude하는 2

편집 ...

partial class MyClass 
{ 
    private readonly RegEx matcher; 

    public MyClass(string regEx) 
    { 
     matcher = new RegEx(regEx); 
    } 

    public bool Match(string value) 
    { 
     return matcher.IsMatch(value); 
    } 
} 

Answer 2

당신은 단순히 당신이 원하는 가정 (정규식 패턴에 와일드 카드를 문자열로 변환, 정규식을 사용할 수 있습니다 꽤 오래된 표준을 사용하려면 "*"및 "?"와일드 카드) :

public static string ToRegEx(string pattern) 
{ 
    return Regex.Escape(pattern).Replace("\\*", ".*").Replace("\\?", "."); 
} 

Answer 3

이 설명은 내가 원했던 것보다 약간 더 길어질 것입니다. 그러나 이와 같은 경우에는 두포에서 일어나는 일을 완전히 이해하는 것이 매우 유용 할 수 있습니다. 특정 접근법이 소스 코드에서 효율적으로 보이기 때문에 CPU가 같은 방식으로 인식한다는 의미는 아닙니다. byte-for-byte 실행 속도가 걱정되면 작업이 실제로 수행 될 레벨에서 어떤 일이 일어나는지 이해해야합니다. 이 레벨 이상의 모든 것은 의미 론적 의미를 지니고 있으며 실제로는 실제로 만들어내는 것에 대한 정확한 그림을 제공하지 못하는 영광스러운 매크로입니다.

Intel/AMD CPU에는 포인터를 설정하고 레지스터에 바이트를 넣고 스캔 할 바이트 수를 설정하고 내부적으로 CPU가 터지면서 스캔을 실행하는 반복 스캔 명령어 세트가 있습니다. 하나의 내부 명령. 일치 또는 불일치가 발견 될 때까지 바이트를 검색합니다 (또는 카운터가 부족합니다). 카운터가 떨어지면 지시 사항을 조정하고 "충족되지 않은 기준; 카운터를 다 써 버린 지저분한 프로세스가 될 수 있습니다!" 조건; 이 코드는 직접 코드에 영향을 미치지 않지만 루프 내에서 많은 개별 검색을 수행하는 경우 실행 시간에 영향을 줄 수 있습니다. 이런 이유로 실제 검색 횟수를 최소화하는 것은 결코 나쁜 생각이 아닙니다. 그것은 큰 요인이 아니지만 안으로 인수 수 있습니다.

내 자신의 코드에서, 큰 검색의 경우, 첫 번째 바이트에 대한 앞으로 스캔입니다. 모든 프로세스를위한 시작점으로 매치하는 것은 매 바이트를 비교하여 낭비되는 시간의 대부분을 절약합니다. CPU가 그렇게하도록하십시오. CPU가해야 할 일이 미친 듯합니다. 단지 명령을로드하고 실행할 준비가되었으므로 언제든지 프로그램을 빨리 종료 할 수 있습니다.

여기에있는 문제는 이러한 것들을 직접 제어 할 수 없다는 것입니다. 어떤 언어를 사용하든 가능한 한 가장 느린 가능한 무차별 대입 방식을 사용합니다. 바이트를 집어보고,보고 다음 바이트를 가져오고, 하품은 하품합니다. 그것이 당신의 언어가하는 방식이라면 (대부분 그렇습니다), 코딩 방법론에 대한 두 가지 선택 사항 사이에 많은 차이가 없을 것입니다. 그들은 이미 모두 성능 기반에 머물고 있습니다. 어셈블리 코드 블록을 삽입 할 수있는 상황에 있다면 엄청난 이익이 될 것입니다. 그러나 대부분의 사람들은 1985 년에 불법으로 간주되어 그 일을 금하고 있습니다. 물론 고려해야 할 32 비트 및 64 비트 문제가 있지만이를 고려할 수 있습니다. 어쨌든 결론은 특정 언어가하는 것을 정확히 찾을 수 있다면 고려해야한다는 것입니다. 문자열을 비교하는 헌트 앤 펙 (hunt-and-peck) 방법을 사용하는 경우 전투가 이미 손실되고 코드를 수정하기 위해 수행하는 작업의 대부분이 아마도 많은 영향을 미치지 않을 것입니다.전혀 MyClass를 확장하지 왜 사전을 사용하는 이유