[seeman_tm]

Предлагаю для обсуждения две функции по поиску массива в массиве.
Функции производят поиск в динамических или фиксированных массивах, с одной оговоркой. При поиске фиксированного или динамического подмассива в фиксированном (статическом) массиве, результат функций надо увеличить на начальный индекс фиксированного массива.

Первая функция производит поиск подмассива в массиве с лева направо.

Код:

Function lArrayPos(Const Arr, fArr: Array Of Byte; Offset: Integer = 0): Integer;
Var Index, DIndex: Integer;
Label f1;
  Begin
    Result := -1;
    if (LenGth(Arr) = 0) or (LenGth(fArr) = 0) then Exit;
    if Offset < 0 then Offset := 0;
    for Index := Low(Arr)+Offset to High(Arr) - (LenGth(fArr) - 1)  do
      Begin
        for DIndex := Low(fArr) to High(fArr) do
          Begin
             if Arr[Index+(dIndex - Low(fArr))] <> fArr[dIndex] then Goto f1;
          End;
        Result := Index;
        Exit;
      f1:
      End;
  End;

Вторая функция производит поиск подмассива в массиве с права налево.

Код:

Function rArrayPos(Const Arr, fArr: Array Of Byte; Offset: Integer = 0): Integer;
Var Index, DIndex: Integer;
Label f1;
  Begin
    Result := -1;
    if (LenGth(Arr) = 0) or (LenGth(fArr) = 0) then Exit;
    if Offset < 0 then Offset := 0;
    for Index := High(Arr) - Offset Downto Low(Arr) + (LenGth(fArr)-1) do
      Begin
        for DIndex := High(fArr) Downto Low(fArr) do
          Begin
            if Arr[Index+(dIndex - High(fArr))] <> fArr[dIndex] then Goto f1;
          End;
        Result := (Index - LenGth(fArr)) + 1;
        Exit;
      f1:
      End;
  End;

Погонял, по тестировал, ошибок не обнаружено. Интересует ваше мнение.

[seeman_tm]

Сообщение от M.A.D.M.A.N.

ШТА за Goto f1;? Здесь должен стоять Continue; и вообще, надо пересмотреть алгоритм.
Как минимум так:

Ваш "как минимум", как минимум неверен. Данная функция будет возвращать не верный результат.
Вот почему.

Массив в котором производится поиск
00, 08, DB, 33, 45, AB, 51, 29, 5E, 6C,
14, 79, 11, D6, 0F, 4A, E9, 5D, C5, 53,
B1, D7, B7, 4E, 29, 54, 76, 3E, D2, 47,
7A, 26, DE, 49, C5, F8, 7D, E2, D2, 05,
23, 24, 7F, 05, 97, 02, C5, A5, C4, B4,
8E, 34, AD, 97, F3, A4, FE, 3E, AC, 4B,
15, C4, 7E, E0, 82, 92, F3, AE, 56, 01,
B3, FC, C5, BF, 32, 24, E8, C7, 96, DC,
A5, 49, 17, A0, 47, DF, 29, 45, 8A, F5,
2C, 28, 44, 2D, 93, 7F, 48, 27, 9B, BC

Искомый массив
05, 97, 02, C5, A5,

Результат моей функции = 43
Не забываем про то что индексы динамических массивов начинаются с 0. Следовательно моя функция вернула верный результат.
Результат изменённой вами функции = 76
И это было сразу видно.

[Bargest]

Думаю, у MAD-а имелся в виду флаг.
Конечно, формально решение с goto немножко быстрее, чем с флагом, но выглядит оно откровенно ужасно. Если нужна понятность - то лучше юзать стандартное с флагом. Если нужна скорость - читаем матчасть (привел только один из примеров) и чуток расширяем для обработки блоков памяти, чем строка вообще-то всегда и является. А так - и скорости нет, и вид ужасен.
Если искомые блоки памяти короткие, вероятно будет выгоднее без крутых алгоритмов - но в этом случае тот же C++-компилятор пишет запутанный код memcmp для сравнения конкретного блока (вместо внутреннего цикла), который сравнивает по DWORD-ам, а не по байтам, что действительно даст прирост к скорости (как работает CompareMem для делфи не смотрел, скорее всего так же). Хотя табличка для того же БМХ строится очень быстро и даст прирост скорости в т.ч. на коротких блоках. Собственно как-то так строится:

Код:

FillMemory(table, length(needle) - 1, 1024)
for i := 0 to length(needle) - 1 do
  table[needle[i]] := length(needle) - i -1;

Ни одного сравнения, а сравнение, как считается, самая долгая операция.

[seeman_tm]

Да, Goto портит картину. Но что не сделаешь ради скорости.
У меня в массиве состоящий из 100000 элементов, подмассив из 50-ти элементов ищется не дольше чем 0.3 милисекунды.
Как ещё ускорить, пока не приходит в голову.

А с вашим примером пока не разобрался. А по подробней пример можно, желательно как полноценную функцию, оформить ?

[Bargest]

Как-то так, думаю:

Код:

function arrFind(Const Arr, fArr: Array Of Byte): integer;
var i, m, n:integer;
   ch, lastch: byte;
   table: array[0..255] of WORD; // можно и Integer, если fArr длиннее 64кб
begin
  m := Length(fArr);
  n := Length(Arr);

  for i := 0 to 255 do
    table[i] := m;

  for i := 0 to m - 2 do
    table[fArr[i]] := m - i -1;

  lastch := fArr[m-1];
  i := 0;
  while ( i <= n - m ) do
  begin
    ch := Arr[ i + m - 1 ];
    if ( ch = lastch ) then
        if ( CompareMem(@(Arr[i]), @(fArr[0]), m-1 ) ) then
        begin
            Result := i;
            exit;
        end;
    i := i + table[ ch ];
  end;
end;

Собственно, код взят по ссылке с вики и портирован на делфи с минимальными изменениями.
И если уж устраивать скоростную фаллометрию, то гонять надо автоматом на разных комбинациях (степень похожести и кол-во частичных вхождений, размеры разные пробовать и т.д) и собирать статистику. Попробуй на таких массивах:
Arr1: 1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,...[и так 100 000 раз]...5,6,7
fArr: 1,2,3,4,5,6,7
Пример, ессно, искусственный, но все же. На нем стандартный код с флагом или goto будет работать очень медленно. В реальности конечно не все так плохо, но БМХ должен быть быстрее, т.к. запускает сравнение памяти (цикл в цикле) не на каждом символе, а скачет с большими пропусками. Но на выборке блоков памяти с высокой энтропией (максимально случайных - см. данные в архиве, шифрованная информация и т.п.), думаю, разницы заметно почти не будет. Хотя зачем нужно искать что-то в высокоэнтропийном блоке, когда он по определению содержит бред...

И кстати. 100 000 - это мало. Надо хотя бы 1000000, а лучше больше. И разумеется, тест проводится множество раз подряд и замеряется общее время. Иначе разницу не увидеть, а вылезет она только тогда, когда мощный сервер будет обрабатывать тысячи таких запросов и не справится.

[seeman_tm]

Время поиска в 15 раз меньше моих функций при поиске подмассива размером в 50 элеиентов в массиве из 10000001. Беру на вооружение.
Вот только надо бы сделать поиск не с начала а с указанным пользователем пропуском. То есть после какой позиции производить поиск подмассива в массиве.

[Bargest]

Вот только надо бы сделать поиск не с начала а с указанным пользователем пропуском. То есть после какой позиции производить поиск подмассива в массиве.

Ну так вместо i := 0 сделать i := offset перед while и все дела. Ну и для приличия можно перед последним END-ом функции поставить result := -1. На случай, если блок не найден.

[seeman_tm]

to Bargest.

(Массивы представлены как HEX)
Массив байт в котором производится поиск.
47, 45, 54, 20, 2F, 74, 61, 6B, 65, 6C,
6F, 67, 69, 6E, 2E, 70, 68, 70, 20, 48,
54, 54, 50, 2F, 31, 2E, 31, 0D, 0A, 48,
6F, 73, 74, 3A, 20, 31, 39, 32, 2E, 31,
36, 38, 2E, 30, 2E, 31, 30, 30, 3A, 39,
30, 39, 30, 0D, 0A, 0D, 0A

Искомый массив байт
0D, 0A, 0D, 0A

Ваша функция не отрабатывает и вешает ядро поцессора. Стало быть зацикливается.

В чём заморочка ?

[madMonia]

Сообщение от seeman_tm

В чём заморочка ?

У вас есть код и пример, на котором, как вы говорите, он не работает. В чем проблема самому разобраться и понять?

[Bargest]

Опечатался немного. Надо конечно

Код:

for i := 0 to m - 2 do
    table[fArr[i]] := m - i -1;

Т.е. m-2 вместо m-1. Потому что последний символ выдает сдвиг в ноль байт, и все виснет. А вообще, думаю, для поиска подстроки в строке (в данном случае в HTTP запросе) лучше использовать стандартный Pos; думаю, он написан неплохо и оптимизирован.

[madMonia]

Pos фигня, зацените мой вариант

Код:

function SubArrayPos(const SubArr, Arr: array of byte; Offset: Integer): Integer;
var
  I, LIterCnt, L, J: Integer;
  PSubStr, PS: PByte;
begin
  L := Length(SubArr);
  { Calculate the number of possible iterations. Not valid if Offset < 1. }
  LIterCnt := Length(Arr) - Offset - L + 1;

  { Only continue if the number of iterations is positive or zero (there is space to check) }
  if (LIterCnt >= 0) and (L > 0) then
  begin
    PSubStr := @SubArr[0];
    PS := @Arr[0];
    Inc(PS, Offset - 1 );

    for I := 0 to LIterCnt do
    begin
      J := 0;
      while (J >= 0) and (J < L) do
      begin
        if PS[I + J] = PSubStr[J] then
          Inc(J)
        else
          J := -1;
      end;
      if J >= L then
        Exit(I + Offset - 1);
    end;
  end;

  Result := -1;
end;

[seeman_tm]

Да у меня идёт погоня за быстродействием.
Стандартная функция Pos не подходит из-за её не удовлетворительной скорости. Тем более в ней нет очень важного параметра. Поиск с позиции.

[seeman_tm]

Сообщение от madMonia

Pos фигня, зацените мой вариант

Ваша функция всегда возвращает 0. А должна, в случае отсутствия подмассива в массиве возвращать индекс -1.

[madMonia]

Сообщение от seeman_tm

Ваша функция всегда возвращает 0;

У меня все работает, вы что-то не так делаете

И в каком это эльфийском королевстве символ не является числом?

[seeman_tm]

Сообщение от madMonia

У меня все работает, вы что-то не так делаете

И в каком это эльфийском королевстве символ не является числом?

Приношу свои извинения. Дело было в том, что в вашей функции первым параметром указывается подмассив, а вторым сам массив в котором ведётся поиск. Не посмотрел туда внимательней сразу. Но на первых замерах ваша функция уступает по скорости моей lArrayPos на 0.0023 ms.
Сейчас погоняю вашу функцию в спарке со своей функцией lArrayPos и выложу результаты по скоростям. А там, если у вас желание будет, продолжим разговор про эльфийские королевства.