Какой самый быстрый алгоритм поиска Int32 в byte [] (C #)?

Question

Я хочу найти int в большом (50 МБ +) массиве байтов. Какой алгоритм я должен использовать? Может быть, какой-нибудь небезопасный метод?

EDIT: Это не массив int, это байтовый массив. Данные никак не сортируются.

Answer 1

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;
}

Не будет работать на архитектурах с прямым порядком байтов, но они не используются для большинства приложений .Net.

Разделение на разделы и запуск в нескольких потоках, а затем объединение результатов для повышения производительности в зависимости от размера массива и доступности ЦП.

Answer 2

Вот моя реализация. Работает в 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;
}

Answer 3

Алгоритмически, нет быстрого поиска для всего этого. С точки зрения реализации, если производительность будет иметь большое значение, лучшее, что вы можете сделать, это написать свой код, чтобы избежать чтения памяти, ответвлений и вызовов функций везде, где это возможно. Это упростит компилятору создание эффективного кода (хотя умные компиляторы могут в любом случае, и сложно гарантировать что-либо о возможном машинном коде, когда вы компилируете виртуальную машину, которая затем перекомпилирует его в машинный код для запуска). Моя реализация будет выглядеть так:

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;
    }
}

Answer 4

Это звучит как работа, в которой вы, возможно, захотите извлечь целые числа из массива и настроить простую хеш-таблицу или двоичное дерево, если вы выполняете много поисков по одним и тем же данным.Базы данных имеют индексы по той же причине.Вы можете получить производительность N / 2 или выше, в зависимости от вашего индекса.

См. Эту статью: Как работает индексирование базы данных?

И эта статья: http://en.wikipedia.org/wiki/Binary_tree

Если вы хотите пойти по этому пути, откройте новый вопрос о том, какой из них больше подходит для задачи, над которой вы работаете.

Answer 5

По сути, вы ищете подстроку в строке.Таким образом, вы захотите взглянуть на алгоритмы поиска строки .

Предложение BlackBear - наивный поиск строки.Вы также можете использовать, например, алгоритм Кнута-Морриса-Пратта

Answer 6

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);
}

Answer 7

Если я правильно понимаю ваш вопрос, вы хотите найти в байтовом массиве то, что составляет конкретный шаблон из 4 байтов. Следующие действия должны помочь, находя значение int в в любой позиции в массиве & mdash; нет никаких предположений относительно выравнивания.

Отредактировано, чтобы отметить, что

• выполняется за 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 ;
}

Answer 8

Вот один из методов. Это требует только просмотра каждого 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;
}

Answer 9

Даже в .Net 2.0 вы можете создавать новые потоки, которые позволят вам распараллелить его поиск.Вы не упоминаете, ищете ли вы все экземпляры int.Я могу придумать несколько способов повысить скорость, чем прямой поиск, включая предварительную обработку массива в словари для поиска и т. Д., Если вы всегда используете один и тот же массив для поиска данных и т. Д.