Ну вот....... Нашел я таки время, чтобы детально во всем содеянном разобраться... Сделать для себя некие умозаключения. 1) Сказать нечего: летает из под IC оно гораздо круче, чем чисто в схемной реализации. Тем не менее, схемная реализация мне кажется вещью очень нужной. В алгоритме индексации (там делов-то на 4 элемента) смогут разобраться, прочувствовать его - многие наши пользователи... Таки у нас форум по HiAsm, а не по дельфячему кодингу.... Как бы не всякий, сначала найдет ошибки в коде, а уже потом его запустит. BTW Леонид писал(а): В теле цикла заменить m на j, а n на k Угу... И в аргументах _hi_OnEvent -- тоже. Не хватало мне для этого " человеческих" массивов. Ну так я их сделал. Под названием SimpleArray (там сделано так же, как я делал в матрице - есть опция выбора типа данных ArrayType). И главное, что есть методы doCount (особаченное св-во) и doFillData. Отсюда предложение к коллегам: протестировать его, на предмет добавления в штатный инструментарий (В плане иконок - никаких претензий на художника/дизайнера у меня не имеется, хотя чего-то я и должен был нарисовать). 2) Чтобы сравнивать хронометражи, мне пришлось немного причесать код Леонид-а, и "пересадить" свой алгоритм в его схему (правда добавил некоторые отладочные выводы). Тестирование проводил на файлах с " белым шумом", которые я получал по такой схеме: Ну будем тестировать, например, на файлах RND_22 (4 метра) и RND_21 (2 метра)... Что же мы видим: a) Алгоритм Леонид-а работает гораздо быстрее моего (у него ~7сек, против моих ~17сек) b) Индексация у меня проскакивает почти моментально (~20мсек), а у Леонид-а две индексации ~3.5сек. c) Косвенным подтверждением идентичности алгоритмов - количество макроопераций сравнения последовательностей (полное совпадение). Ну и фактически найденные последовательности (специально сделал сортировку по столбцу, чтобы сравнивать). Кстати говоря, с моими файлами - это ~134 МегаОпа, что отличается от 8 ТераОпов на те самые 4.8 порядка, прогнозируемые ранее. Между прочим, сами операции поиска (все 134 МегаОпа) занимают около 3-х секунд. Что в моем коде, что у Леонид-а (я их комментировал, и сравнивал времена). Вот я долго думал, почему мой код " тормозит", в сравнении с Леонид-ом. Всю башку себе сломал: как же так... ну все же правильно... ну не может этого быть... и дизасм смотрел - да там 4 элементарные команды проца! Остановился пока на таком заключении: перебор позиций вхождения в словарь у меня осуществляется лазанием (вообще-то элементарным - j:=Tail[j]) по всему массиву. Который, для RND_21, весит таки 8 метров. А у Леонид-а - эти позиции лежат все подряд в одном массиве. В общем, думаю я себе - процессор с совершенно разной скоростью обращается к памяти при таких раскладах. Опять же: 134 МегаОпа - это вам не кот чихнул. Других идей пока не возникло... Если кто в теме - поделитесь. НО, не будем пока петь осанну алгоритму индексации Леонид-а Постоянная реаллокация массива на предмет добавления одного нового элемента - очень трудозатратная вещь (что видно из его времян индексации). Да и опасная - может и AV закончиться. Собственно, я с этого и начинал: сделал себе StringArray (сначала в IC, а теперь это и SimpleArray позволяет), ну и давай себе добавлять позиции в хвостик через ';'. Ну, быстродействие этого дела - мне сразу не понравилось (схема - это вам не IC). Но, ручки то шаловливые - вот и давай я ему совать все, что под руку попадется. И попался мне под руки libmySQL.dll (кажется, намедни его поминали незлым тихим словом) - закончилось все это AV, после долгих трудов. А попробуйте подсунуть его в схему Леонид-а - у меня, по крайней мере, это закончилось тоже AV. На самом деле, это реальная проблема, при больших объемах информации. После этого я напрягся, и вспомнил идею того алгоритма индексации, что у меня сейчас. Не, это не я его придумал, читал где-то... Может и в учебнике каком ни то... А вот помните мою первую схему в этом посте? Она называется " Тест индексирования словаря" Так там есть IC с названием " String Accumulator". Думаете мне просто захотелось продемонстрировать свое искусство написания IC? Вовсе нет. Казалось бы делов: добавить в хвостик строки еще одно число через запятую. Конечно, я начинал с обыкновенного Memory. Но опять же, подсунул ему libmySQL.dll - индексация с сегодняшним алгоритмом прошла махом. А вот уж как начал он для него делать текст.... Он первую строку 20 минут делал (а дальше уже - бегом, секундное дело). Дело в том, что в этом файле двойных ноликов - как у дурака фантиков. В текстовом представлении нашего хеша, его первая строка -- треть файла занимала. Вот такая вот проблема... Ищет быстро (и именно из-за способа индексирования), а сама индексация - тормозить может, в плоть до падения при неблагоприятных обстоятельствах. 3) Проанализируем, чего у нас получается. Когда файл словаря меньше, чем хеш-таблица, то поиск в ней не зависит от размера файла. Типа, какая разница, насколько эта таблица заполнена - на треть, на четверть, или на половину. Получается, что время поиска пропорционально сумме длины словаря (время на его индексацию), и длины файла поиска. Со своим коэффициентом каждая длина, естественно. А если больше, чем хеш таблица - тогда время поиска пропорционально произведению этих длин, деленному на размер хеш таблицы. Что мы и имеем в настоящее время. Мораль такая: надо так устраивать хеш-таблицу, чтобы словарь не переполнял ее ни в коем случае. И это будет как бы самое чики-пуки. Отсюда возникает мысль: а не замахнуться ли нам на Вильяма на нашего на Шекспира Индексировать не двумя, а тремя первыми байтами. Что меняется: массив, который у меня обзывается " Entry to HashList", станет размером 16777216. Это 64 метра в памяти. Это многовато, конечно же... А с другой стороны, кому-то разве жалко ??? В общем, это может выглядеть примерно так: --- Добавлено в 2020-03-22 16:29:29Вот он, не побоюсь этого слова - SimpleArray Редактировалось 10 раз(а), последний 2020-03-26 17:32:59
|