strstr() C#

Question

의 strstr()에 두 개의 byte[]이 있는데 첫 번째 byte[] (또는 그 범위)에 두 번째 byte[]의 첫 번째 항목을 찾고 싶습니다.

효율성을 위해 문자열을 사용하고 싶지 않습니다. 첫 번째 byte[]을 string로 변환하는 것이 비효율적입니다.

는 기본적으로 그게 strstr()이

그 (그래서 효율적이고 사용하기 쉽게) 할 수있는 가장 좋은 방법은 무엇입니까 C.

에 무엇을 믿을?

이는 같이하는 방법입니다 :

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, int bigArrayCount, byte[] smallArray); 

감사합니다!

UPDATE :

나는 간단한 검색보다 더 효율적으로 할 수있는 솔루션을 원한다. 즉, 버퍼를 더 효율적으로 비교할 수 있다는 사실을 사용하면 - memcmp()가 바이트을 반복하는 것보다 효율적입니다.

• 큰 배열 : 또한

  , 나는이 같은 시나리오를 최적화 알고리즘이 알고 "12312351231234"

• 작은 배열 : "1231234"
이
• 순진한 알고리즘 : 7 비교 "1231235"가 "1231234"와 다르다는 것을 알아 내고, 2는 다음 "1"을 찾기 위해 비교하고, 4는 "1235"가 "1231"과 다르다는 것을 알아 내고, 3은 다음 "1"을 찾는 것을 비교하고, 7은 일치하는 것을 찾는다. 총 7 + 2 + 4 + 3 + 7 = 23이 비교됩니다.
• 스마트 알고리즘 : 7 "1231234"가 "1231234"와 다른 경우 "비교하지 않고"다음 "1"로 바로 이동하고, 4는 "1235"가 "1231" , "5"를 넘어 직접 점프, 7 경기를 비교합니다. 총 7 + 4 + 7 = 18이 비교됩니다.

Answer 1

는 Boyer-Moore 알고리즘이다. 그것은 O (n)보다 더 잘할 수 있습니다.

Here은 CodeProject의 문자열에 대한 구현입니다. byte[]으로의 전환이 너무 어려워서는 안됩니다.

Answer 2

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, 
           int bigArrayCount, byte[] smallArray) 
{ 
    byte first = smallArray[0]; 
    bool cont= true; 
    while (cont && 
      bigArrayOffset=Array.IndexOf(bigArray, first, bigArrayOffset) != -1) 
    { 
     if (bigArrayOffset + smallArray.Length > bigArray.Length) 
     { 
       bigArrayOffset = -1; 
       break; 
     } 
     cont= false; 
     for(int i=1; i< smallArray.Length; ++i) 
     { 
       if (bigArray[bigArrayOffset+i] != smallArray[i]) 
       { 
       ++bigArrayOffset; 
       cont = true; 
       break; 
       } 
     } 
    } 
    return bigArrayOffset; 
} 

업데이트; (잘하면) 고정 문제 Henk이 나를 경고했다.

업데이트 2 : 원래의 질문에 업데이 트를 주소 : 나는 당신을 위해 모든 코드하지만 당신은 발견 할 것이다 가장 빠른 솔루션의 이름이없는

int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, 
           int bigArrayCount, byte[] smallArray) 
{ 
    int bigArrayEnd = Math.Min(bigArrayCount + bigArrayOffset, bigArray.Length) 
    byte first = smallArray[0]; 
    bool cont= true; 
    while (cont && 
      bigArrayOffset=Array.IndexOf(bigArray, first, bigArrayOffset) != -1) 
    { 
     int bookmark = bigArrauOffset + 1; 
     bool bookmarkset = false; 
     if (bigArrayOffset + smallArray.Length > bigArrayEnd) 
     { 
       bigArrayOffset = -1; 
       break; 
     } 
     cont= false; 
     for(int i=1; i< smallArray.Length; ++i) 
     { 
       if (!bookmarkset && bigArray[bigArrayOffset+i] == first) 
       { 
        bookmark = bigArrayOffset+i; 
        bookmarkset = true; 
       } 
       if (bigArray[bigArrayOffset+i] != smallArray[i]) 
       { 
       bigArrayOffset = bookmark; 
       cont = true; 
       break; 
       } 
     } 
    } 
    return bigArrayOffset; 
} 

Answer 3

여기에 해결책이 있습니다. 그것은 2로 나뉩니다. 첫 번째 부분은 주로 잠재적 시작을 찾습니다.이 하나를 발견하면 그것, 그것은 잘 알려진 알고리즘 이론에

int GetOffsetOfArrayInArray(byte[] bigArray, 
         int bigArrayOffset, 
         int bigArrayCount, 
         byte[] smallArray) 
    { 
     var length = smallArray.Length; 
     var lastPossibleStart = bigArray.Length - length; 
     var startByte = smallArray[0]; 

     for (var first = bigArrayOffset; first < lastPossibleStart; first++) 
     { 
      if (bigArray[first] == startByte && 
       check(bigArray, smallArray, first, length)) 
      { 
       return first; 
      } 
     } 
     return -1; 
    } 

    bool check(byte[] bigArray, byte[] smallArray, int first, int length) 
    { 
     var smallIndex = 0; 
     var smallLast = length - 1; 
     var last = first + length - 1; 
     for (var i = first; smallIndex <= smallLast; i++) 
     { 
      if (bigArray[i] != smallArray[smallIndex] || 
       bigArray[last] != smallArray[smallLast]) 
      { 
       return false; 
      } 
      smallIndex = i - first + 1; 
      last--; 
      smallLast--; 
     } 
     return true; 
    } 
} 

Answer 4

(기본적으로 마이크로 프로파일 러 밖으로 최적화 그러나 보통 가 빠릅니다입니다 루프 카운트를 낮출) 양쪽 끝에서 목록을 비교 속도 최적화를 위해서는 메모리 비용이, 그 반대의 경우도 마찬가지입니다. 내 알고리즘은 조금 더 많은 메모리를 사용하지만 반환 값으로 한 번만 큰 배열을 스캔합니다.

public static int GetOffsetOfArrayInArray(byte[] bigArray, int bigArrayOffset, int bigArrayCount, byte[] smallArray) 
{ 
    // TODO: Check whether none of the variables are null or out of range. 
    if (smallArray.Length == 0) 
     return 0; 

    List<int> starts = new List<int>(); // Limited number of elements. 

    int offset = bigArrayOffset; 
    // A single pass through the big array. 
    while (offset < bigArrayOffset + bigArrayCount) 
    { 
     for (int i = 0; i < starts.Count; i++) 
     { 
      if (bigArray[offset] != smallArray[offset - starts[i]]) 
      { 
       // Remove starts[i] from the list. 
       starts.RemoveAt(i); 
       i--; 
      } 
      else if (offset - starts[i] == smallArray.Length - 1) 
      { 
       // Found a match. 
       return starts[i]; 
      } 
     } 
     if (bigArray[offset] == smallArray[0] && 
      offset <= (bigArrayOffset + bigArrayCount - smallArray.Length)) 
     { 
      if (smallArray.Length > 1) 
       // Add the start to the list. 
       starts.Add(offset); 
      else 
       // Found a match. 
       return offset; 
     } 
     offset++; 
    } 
    return -1; 
} 

목록 starts는 bigArray에 smallArray의 잠재적 시작 오프셋을 추적하는 데 사용됩니다. smallArray (목록을 최적화하고 메모리 재 할당 횟수를 줄이기 위해 사전에 계산 될 수 있음)에 smallArray[0]의 발생 횟수보다 많은 요소를 포함하지 않습니다. bigArray에 smallArray이 포함되도록 충분한 바이트가 남아 있지 않으면 시도하지 않고 smallArray을 찾으면 알고리즘이 중지됩니다. bigArray의 끝에 도달하면 중지됩니다. 그러므로 최악의 경우 실행 시간은 O (1)이고 메모리 사용량은 O (1)이됩니다.

안전하지 않은 코드의 포인터를 사용하고 사전에 계산할 수있는 크기의 고정 배열로 목록을 교체하는 등의 최적화가 가능합니다. 그러나 목록에서 잘못된 오프셋이 제거되고 (작은 내부 루프) 배열에서 잘못된 오프셋을 건너 뛰고 (고정 크기 내부 루프이지만 더 빠른 요소 액세스) 가능한 경우 어느 것이 더 빠른 지 벤치 마크해야합니다.

smallArray의 크기가 큰지 여부에 관계없이 중요합니다. 그렇게하면 while 루프에 starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length)을 검사하는 검사를 추가 할 수 있습니다. 그렇지 않으면 루프가 중지되고 어커런스가 발견되지 않습니다.