3

我有两个byte[]，我想byte[]在第一个byte[]（或其中的一个范围）中找到第二个的第一次出现。

我不想使用字符串来提高效率（将第一个转换byte[]为 astring效率低下）。

基本上我相信这就是strstr()C 中的作用。

最好的方法是什么（因此它既高效又易于使用）？

它应该是这样的：

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

谢谢！

更新：

我想要一个比简单搜索更有效的解决方案。这意味着应该使用比较缓冲区可以更有效的事实 - memcmp() 比迭代字节更有效。

另外，我知道有一些算法可以优化这样的场景：

  • 大数组：“12312351231234”
  • 小数组：“1231234”
  • 朴素算法： 7比较发现“1231235”与“1231234”不同，2比较发现下一个“1”，4比较发现“1235”与“1231”不同，3比较发现下一个“ 1", 7 比较以找到匹配项。总共 7+2+4+3+7=23 次比较。
  • 智能算法： 7比较发现“1231235”和“1231234”不同，直接跳到下一个“1”（不比较），4比较发现“1235”和“1231”不同，直接跳到下一个“1” "5", 7 比较以找到匹配项。总共 7+4+7=18 次比较。
4

4 回答 4

3

我没有任何代码给你，但你会发现最快的解决方案的名称是Boyer-Moore算法。它可以比 O(n) 做得更好。

这是 CodeProject 上字符串的实现。看起来转换到byte[]应该不会太难。

于 2010-08-21T09:41:46.890 回答
1 
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;
}
于 2010-08-21T08:50:24.880 回答
0

这是我对解决方案的看法。它一分为二。第一部分主要寻找潜在的起点。如果找到一个，它会比较两端的列表（以降低循环计数，这基本上是一种没有分析器的微优化，但通常速度更快）

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;
    }
}
于 2010-08-21T10:55:29.693 回答
0

在算法理论中，众所周知，优化速度会消耗内存，反之亦然。我的算法使用更多的内存（不多），但作为回报只扫描一次大数组。

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用于跟踪 in 的潜在起始偏移smallArray量bigArray。smallArray[0]它永远不会包含比in出现次数更多的元素smallArray（可以提前计算以优化列表并减少内存重新分配的次数）。当没有足够的字节bigArray包含smallArray时，不会尝试，当smallArray找到时，算法停止。当到达结束时它也会停止bigArray。因此，最坏情况下的运行时间为 O(1)，内存使用量为 O(1)。

进一步可能的优化包括在不安全的代码中使用指针，并用可以预先计算大小的固定数组替换列表（如前所述）。但是，因为在列表中删除了错误的偏移量（较小的内循环）并且在数组中必须跳过错误的偏移量（固定大小的内循环但可能更快的元素访问），您必须对哪个更快进行基准测试。

您是否期望smallArray变大也很重要。当你这样做时，你可以在 while 循环中添加一个检查来检查starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length). 否则循环可能会停止并且没有发现任何事件。

于 2010-08-21T12:59:01.693 回答