什么'；s是在byte[](C#)中搜索Int32的最快算法

本文关键字：搜索 Int32 算法 是在 byte 什么 | 更新日期: 2023-09-27 18:06:41

我想在一个大(50mb+(字节数组中搜索一个int。我应该使用什么算法？也许是一些不安全的方法？

编辑：它不是int数组，而是字节数组。数据没有以任何方式排序。

什么'；s是在byte[](C#)中搜索Int32的最快算法

public IList<int> FindIntInBytes(byte[] bytes, int target)
{
    IList<int> found = new List<int>();
    unsafe
    {
        fixed (byte* pBytes = bytes)
        {
            byte* pCurrent = pBytes;
            for (int i = 0; i <= bytes.Length - 4; i++, pCurrent++)
            {
                if (target == *(int*)pCurrent)
                {
                    found.Add(i);
                }
            }
        }
    }
    return found;
}

不会在big-endian体系结构上工作，但它们不用于大多数.Net应用程序。

根据阵列的大小和CPU的可用性，拆分为多个部分并在多个线程中运行，然后合并结果以获得更快的性能。

这是我的实现。在O(n(中工作；

int findInArray(byte[] array, int what)
{
    byte[] toMatch = /* convert your dword to a 4 elements byte array */;
    int matched = 0;
    for(int i = 0; i < array.length; i++) {
        if(array[i] == toMatch[matched]) {
            matched += 1;
            if(matched == 4) {
                return i - 4;
            }
        }
        else {
            i -= matched;
            matched = 0;
        }
    }
    return -1;
}

从算法上讲，没有捷径可以搜索整个内容。在实现方面，如果性能很重要，那么最好的方法就是编写代码，尽可能避免内存读取、分支和函数调用。这将使编译器更容易生成高效的代码(尽管聪明的编译器无论如何都可能，而且当你编译到VM时，很难保证最终的机器代码，然后VM将其重新编译为机器代码来运行(。我的实现是这样的：

System.Collections.Generic.IEnumerable<int> FindIntInByteArray(int match, byte[] array) {
    if (array.Length < 4) yield break;
    byte b0 = 0;
    byte b1 = array[0];
    byte b2 = array[1];
    byte b3 = array[2];
    int len = array.Length;
    for (int i=3;i<len;i++) {
        b0 = b1;
        b1 = b2;
        b2 = b3;
        b3 = array[i];
        /* The following line should be changed depending on endian-ness or which
           bytes are to be considered most significant. */
        int comp = (b0 << 24) | (b1 << 16) | (b2 << 8) | b3;
        if (comp == match) yield return i-3;
    }
}

您实际要做的是在字符串中查找子字符串。因此，您需要了解字符串搜索算法。

BlackBear的建议是一个天真的字符串搜索。例如，您也可以使用，Knuth–Morris–Pratt算法

如果对同一数据进行大量搜索，这听起来像是一项工作，您可能希望从数组中提取整数，并建立一个简单的哈希表或二进制树。数据库有索引也是出于同样的原因。根据您的指数，您可以获得N/2或更好的性能。

请参阅本文：数据库索引是如何工作的？

这篇文章：http://en.wikipedia.org/wiki/Binary_tree

如果你想走这条路，打开一个新的问题，关于哪一个更适合你正在处理的任务。

即使在.Net 2.0中，你也可以创建新的线程，使你能够并行搜索它。你没有提到你是否在寻找int的所有实例。我可以想出几种比直接搜索提高速度的方法，包括将数组预处理到字典中进行查找，等等。如果你总是使用同一个数组来查找数据，等等。

这里有一个方法。它只需要每隔4个字节查看一次，所以应该会稍微快一点。(如果您正在查找0x11223344，并且找到了0x55，则您知道目标整数根本不包含此字节。(应该是O(n/4(。

我没有运行这个，可能有语法错误或一个错误。

bool Compare4(byte[] searchIn, int offset, byte[] searchFor)
{
    return searchIn[offset]   == searchFor[0] &&
           searchIn[offset+1] == searchFor[1] &&
           searchIn[offset+2] == searchFor[2] &&
           searchIn[offset+3] == searchFor[3];
}
/// Returns index if found, -1 if not found.
int FindIntInArray(int target, byte[] array)
{
    byte[] targetArray = new byte[4];
    targetArray[0] = target & 0xFF;
    targetArray[1] = (target>>8) & 0xFF;
    targetArray[2] = (target>>16) & 0xFF;
    targetArray[3] = (target>>24) & 0xFF;
    bool[] bytesUsed = new bool[256];
    foreach(byte b in targetArray) bytesUsed[b] = true;
    for(int i = 3; i < array.Length - 3; i += 4)
    {
        if(bytesUsed[array[i]])
        {
            if(Compare4(array, i-3, targetArray)) return i-3;
            if(Compare4(array, i-2, targetArray)) return i-2;
            if(Compare4(array, i-1, targetArray)) return i-1;
            if(Compare4(array, i, targetArray)) return i;
        }
    }
    return -1;
}

如果我能正确理解你的问题，你想在一个字节数组中搜索一个4字节的特定模式。下面的操作应该可以做到，在数组中的任何位置找到int值—没有关于对准的假设。

编辑以注意

  • 它在O(n(时间内运行，并且
  • 任何字节顺序问题都是您的问题

这是代码：

private static int FindIntValueInByteArray( int value , byte[] octets )
{
  int matchPosition = -1 ; // assume no match
  for ( int i = 0 ; i < octets.Length-3 ; ++i )
  {
    int t = BitConverter.ToInt32( octets , i ) ;
    if ( t == value )
    {
      matchPosition = i ;
      break ;
    }
  }
  return matchPosition ;
}

public static class ByteListExtensions
{
    public static IEnumerable<int> AllIndexesOf(this IList<byte> source, int match, bool isLittleEndian = true)
    {
        if (source.Count < 4)
        {
            return Enumerable.Empty<int>();
        }
        var b0 = (byte)(match & (isLittleEndian ? 0xff000000 : 0x000000ff));
        var b1 = (byte)(match & (isLittleEndian ? 0x00ff0000 : 0x0000ff00));
        var b2 = (byte)(match & (isLittleEndian ? 0x0000ff00 : 0x00ff0000));
        var b3 = (byte)(match & (isLittleEndian ? 0x000000ff : 0xff000000));
        var indexes = Enumerable.Range(0, source.Count / 4)
            .AsParallel()
            .Select(x => x * 4)
            .Where(x => source[x] == b0)
            .Where(x => source[x + 1] == b1)
            .Where(x => source[x + 2] == b2)
            .Where(x => source[x + 3] == b3);
        return indexes;
    }
}

示例用法：

var callingAssembly = Assembly.GetCallingAssembly();
var bytes = File.ReadAllBytes(callingAssembly.Location);
const int intToFind = 42;
var indexes = bytes.AllIndexesOf(intToFind);
foreach (var index in indexes)
{
    Console.WriteLine(index);
}
相关文章：