В теории алгоритмов хорошо известно, что оптимизация для скорости стоит памяти и наоборот.Мой алгоритм использует немного больше памяти (не так много), но взамен сканирует только большой массив один раз.
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 используется для отслеживания возможных начальных смещений smallArray в bigArray,Он никогда не будет содержать больше элементов, чем число вхождений smallArray[0] в smallArray (которое может быть рассчитано заранее для оптимизации списка и уменьшения количества перераспределений памяти).Когда в bigArray осталось недостаточно байтов, чтобы содержать smallArray, он не пробуется, а когда был найден smallArray, алгоритм останавливается.Он также останавливается, когда достигнут конец bigArray.Поэтому наихудшее время выполнения будет O (1), а использование памяти будет O (1).
Дальнейшие возможные оптимизации включают использование указателей в небезопасном коде и замену списка фиксированным массивом,Размер можно рассчитать заранее (как отмечалось ранее).Однако, поскольку в списке удалены неправильные смещения (меньший внутренний цикл), а в массиве должны быть пропущены неправильные смещения (внутренний цикл фиксированного размера, но, возможно, более быстрый доступ к элементу), вам нужно будет определить, какое из них быстрее.
Также имеет значение, ожидаете ли вы, что smallArray будет большим или нет.Когда вы это сделаете, вы можете добавить проверку в цикл while, который проверяет, является ли starts.Length != 0 || offset <= (bigArrayOffset + bigArrayCount - smallArray.Length).В противном случае цикл может прекратиться, и вхождения не были найдены.