|
|
Регистрация | << Правила форума >> | 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)
|