|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
||||
|
||||
Функции поиска чего то в чём то
Предлагаю для обсуждения две функции по поиску массива в массиве.
Функции производят поиск в динамических или фиксированных массивах, с одной оговоркой. При поиске фиксированного или динамического подмассива в фиксированном (статическом) массиве, результат функций надо увеличить на начальный индекс фиксированного массива. Первая функция производит поиск подмассива в массиве с лева направо. Код:
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; Погонял, по тестировал, ошибок не обнаружено. Интересует ваше мнение. |
#2
|
||||
|
||||
Цитата:
Ваш "как минимум", как минимум неверен. Данная функция будет возвращать не верный результат. Вот почему. Массив в котором производится поиск 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 И это было сразу видно. Последний раз редактировалось seeman_tm, 17.03.2014 в 21:18. |
#3
|
||||
|
||||
Думаю, у 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; jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 17.03.2014 в 22:41. |
#4
|
||||
|
||||
Bargest
Да, Goto портит картину. Но что не сделаешь ради скорости.
У меня в массиве состоящий из 100000 элементов, подмассив из 50-ти элементов ищется не дольше чем 0.3 милисекунды. Как ещё ускорить, пока не приходит в голову. А с вашим примером пока не разобрался. А по подробней пример можно, желательно как полноценную функцию, оформить ? |
#5
|
||||
|
||||
Как-то так, думаю:
Код:
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, а лучше больше. И разумеется, тест проводится множество раз подряд и замеряется общее время. Иначе разницу не увидеть, а вылезет она только тогда, когда мощный сервер будет обрабатывать тысячи таких запросов и не справится. jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 28.03.2014 в 18:10. |
Этот пользователь сказал Спасибо Bargest за это полезное сообщение: | ||
seeman_tm (18.03.2014)
|
#6
|
||||
|
||||
Время поиска в 15 раз меньше моих функций при поиске подмассива размером в 50 элеиентов в массиве из 10000001. Беру на вооружение.
Вот только надо бы сделать поиск не с начала а с указанным пользователем пропуском. То есть после какой позиции производить поиск подмассива в массиве. |
#7
|
||||
|
||||
Цитата:
jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 18.03.2014 в 13:09. |
#8
|
||||
|
||||
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 Ваша функция не отрабатывает и вешает ядро поцессора. Стало быть зацикливается. В чём заморочка ? |
#9
|
||||
|
||||
Цитата:
Невозможно заточить карандаш тупым топором. Столь же тщетно пытаться сделать это десятком тупых топоров |
#10
|
||||
|
||||
Опечатался немного. Надо конечно
Код:
for i := 0 to m - 2 do table[fArr[i]] := m - i -1; jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 27.03.2014 в 17:12. |
Этот пользователь сказал Спасибо Bargest за это полезное сообщение: | ||
seeman_tm (27.03.2014)
|
#11
|
||||
|
||||
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; Невозможно заточить карандаш тупым топором. Столь же тщетно пытаться сделать это десятком тупых топоров Последний раз редактировалось madMonia, 27.03.2014 в 19:02. |
#12
|
||||
|
||||
Да у меня идёт погоня за быстродействием.
Стандартная функция Pos не подходит из-за её не удовлетворительной скорости. Тем более в ней нет очень важного параметра. Поиск с позиции. |
#13
|
||||
|
||||
Цитата:
Ваша функция всегда возвращает 0. А должна, в случае отсутствия подмассива в массиве возвращать индекс -1. Последний раз редактировалось seeman_tm, 27.03.2014 в 17:44. |
#14
|
||||
|
||||
Цитата:
И в каком это эльфийском королевстве символ не является числом? Невозможно заточить карандаш тупым топором. Столь же тщетно пытаться сделать это десятком тупых топоров |
#15
|
||||
|
||||
Цитата:
Приношу свои извинения. Дело было в том, что в вашей функции первым параметром указывается подмассив, а вторым сам массив в котором ведётся поиск. Не посмотрел туда внимательней сразу. Но на первых замерах ваша функция уступает по скорости моей lArrayPos на 0.0023 ms. Сейчас погоняю вашу функцию в спарке со своей функцией lArrayPos и выложу результаты по скоростям. А там, если у вас желание будет, продолжим разговор про эльфийские королевства. Последний раз редактировалось seeman_tm, 27.03.2014 в 17:59. |