Сейчас на форуме: jinoweb (+6 невидимых) |
eXeL@B —› Программирование —› ByteToHex |
. 1 . 2 . 3 . 4 . 5 . >> |
Посл.ответ | Сообщение |
|
Создано: 07 июля 2018 22:06 · Поправил: Isaev · Личное сообщение · #1 Не подскажите максимально быстрый способ перевода? Помню во времена доса на асме буквально из десятка байт был финт для этого дела, может помнит кто? А то дельфовый IntToHex(n, 2) сожрал всю скорость, посмотрев сырки стало сразу понятно куда) А вообще нужно из md5 массива байт строку собрать если делать влоб Code:
то 10млн раз выполняются около 6 сек, хотелось бы поделить это время на 2 или 3... к слову, если вместо IntToHex просто добавлять '00', то будет 2 сек. Пробовал вместо простой конкатенации заюзать TStringBuilder, но нынче, похоже менеджер памяти уже сам вполне справляется с этим хламом и с ним только на 1 сек дольше получается. Так же пробовал выделить память сразу под всю строку и мувами загонять на места, но получается тоже дольше... в общем проблема только в переводе в hex, остальное, похоже достаточно оптимально работает ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 07 июля 2018 22:14 · Личное сообщение · #2 |
|
Создано: 07 июля 2018 22:18 · Личное сообщение · #3 |
|
Создано: 07 июля 2018 22:24 · Личное сообщение · #4 shellstorm говорю же потестил, особо без разницы IntToHex то на асм, но он не заточен под байт и прыгает по куче подпрограмм, а в основе вот такой код Code:
т.ч. бред его для байта юзать... пойду копаться в старых асмовских сырках своих, может где-то, осталось) ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 07 июля 2018 22:24 · Поправил: kunix · Личное сообщение · #5 |
|
Создано: 07 июля 2018 22:25 · Поправил: difexacaw · Личное сообщение · #6 Проиндексировать, если всего по одному символу выводить [0%F], то можно без использования памяти под массив обойтись, загрузить его в регистры и там индексировать. Быстрее врядле как получится. Добавлено спустя 6 минут Isaev Так ведь в 7 у вас плавающая точка. Для int32 в васме можно подсмотреть, там макрос есть: Code:
А есчо я по суркам 2к поиск прогнал, есть такое: Code:
----- vx | Сообщение посчитали полезным: Isaev |
|
Создано: 07 июля 2018 22:33 · Личное сообщение · #7 Archer пишет: А зачем генерить 10 млн МД5 строк? ищу более-менее стойкую хеш-функцию для хеш-листа... подумал md5 может на деле не очень ущербна по скорости будет для этой цели... вообще цель следующая: надо сделать самопальное хранилище для деревьев с большим количеством узлов, соответственно с поиском узлов по хешу O(1) А хеш будет браться от массива на 255 байт со словарём в 6 символов... вот думаю как получить меньше коллизий ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 07 июля 2018 22:36 · Личное сообщение · #8 |
|
Создано: 07 июля 2018 22:45 · Поправил: Isaev · Личное сообщение · #9 kunix ну давай, свежую идею... может я слишком заморачиваюсь на самом деле и нужен свежий взгляд со стороны... Эти массивы (от которых я хотел хеш хранить) храниться сами не будут, т.к. это слишком много памяти, а при составлении дерева нужно быстро определить была ли уже в нём эта вершина (т.е. если была соединяемся с ней, если не было, то добавляем) Как можно к решению подойти иначе? вместо md5 может и правильнее использовать полиномиальный хеш, но его генерация думаю будет заметно дороже... хотя надо тестить всё ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 07 июля 2018 22:47 · Поправил: shellstorm · Личное сообщение · #10 любой приличный компилятор оптимизирует это решение лучше того высера из рантайма делфи. в делфи x64 clang компилирует, должен нормально оптимизировать. Code:
hash_map давно изобрели, md5 здесь точно не нужен. |
|
Создано: 07 июля 2018 22:50 · Личное сообщение · #11 Чем-то типа этого пользуюсь, размазываешь байт по 16битам с учетом little endian, складываешь с символами нулей, если надо докручиваешь оба до abcdef. При желании можно эффективней набивать регистр, особенно 64битный, но это уже наверное слишком. Code:
----- 2 оттенка серого | Сообщение посчитали полезным: Isaev |
|
Создано: 07 июля 2018 22:57 · Личное сообщение · #12 shellstorm пишет: hash_map давно изобрели, md5 здесь точно не нужен. его изобрели везде, кроме дельфи) там можно заюзать Generics.Collections.TDictionary<TKey,TValue> где TKey должен быть уникальным... у меня это массив, массив мы ему загнать не можем, потому надо взять от него хеш... так ведь?) ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 07 июля 2018 22:58 · Поправил: kunix · Личное сообщение · #13 |
|
Создано: 07 июля 2018 23:05 · Личное сообщение · #14 Isaev пишет: где TKey должен быть уникальным... не настолько уникальным, достаточно операций с константой. первый попавший исходный код, скорее всего сомнительный, но для понимания сути достаточно https://github.com/ffTsuzuku/Hash_Map/blob/master/hash.c коллизии конечно возможны, но они и в md5 есть, приходится выбирать соотношения надежности, потребления памяти, и скорости, иначе так до sha512 можно добраться. |
|
Создано: 07 июля 2018 23:17 · Поправил: Isaev · Личное сообщение · #15 kunix пишет: Блин, если исходные ключи не сохраняются, то при коллизии все сломается, так?. именно, потому md5, наверное, тоже бредовая затея, но я погоняю, мне интересно на сколько часто на таком объёме там могут коллизии проскакивать shellstorm пишет: не настолько уникальным, достаточно операций с константой. это я не понял shellstorm пишет: первый попавший исходный код, скорее всего сомнительный ну он под маленький словарь просто, на 5к элементов... может на нём он и не даёт коллизий ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 07 июля 2018 23:22 · Поправил: shellstorm · Личное сообщение · #16 Isaev пишет: это я не понял подобранной константой добавляют соль. Code:
Isaev пишет: может на нём он и не даёт коллизий зависит от входных данных, допустим для построения cfg графа PE файла не нужны никакие md5. важны как сами данные, так и их количественное разнообразие, в описаниях алгоритма указывается вероятность коллизии, подбирайте под свой случай, поскольку даже md5 не всегда достаточно, смотря какие требования к отказоустойчивости. |
|
Создано: 07 июля 2018 23:45 · Личное сообщение · #17 |
|
Создано: 08 июля 2018 00:24 · Поправил: shellstorm · Личное сообщение · #18 |
|
Создано: 08 июля 2018 00:44 · Личное сообщение · #19 shellstorm пишет: для этого случая давно изобрели суффиксные\префиксные деревья, и работать с ними с адекватной скоростью. но их в делфи скорее всего тоже не завезли. Это всё мелочи, главное знать как это называется. Логика гуглится, а дальше дело техники... всё имплементируемо! Спасибо за наводку! ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 08 июля 2018 00:53 · Личное сообщение · #20 Всё там завезли Isaev пишет: там можно заюзать Generics.Collections.TDictionary<TKey,TValue> где TKey должен быть уникальным... у меня это массив, массив мы ему загнать не можем, потому надо взять от него хеш... так ведь?) что значит загнать массив не можем? там можно хранить все что угодно, хоть структуры, хоть классы, хоть чёрта лысого. Isaev пишет: соответственно с поиском узлов по хешу O(1) TDictionary это и есть хештаблица с доступом к элементу O(1) | Сообщение посчитали полезным: Isaev |
|
Создано: 08 июля 2018 01:19 · Личное сообщение · #21 |
|
Создано: 08 июля 2018 01:20 · Поправил: Isaev · Личное сообщение · #22 SReg пишет: там можно хранить все что угодно Вот именно, что хранить, а хранить я его совсем не планировал... Но при таком подходе сам массив же тоже будет храниться и жрать много памяти! Глянул в этом словаре хеш функцию, я правильно понимаю, в качестве хеша используется указатель на сам элемент? ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 08 июля 2018 01:22 · Личное сообщение · #23 |
|
Создано: 08 июля 2018 01:57 · Личное сообщение · #24 |
|
Создано: 08 июля 2018 03:19 · Поправил: dosprog · Личное сообщение · #25 Isaev пишет: Не подскажите максимально быстрый способ перевода? Помню во времена доса на асме буквально из десятка байт был финт для этого дела, может помнит кто? Вариант 1 Code:
Code:
|
|
Создано: 08 июля 2018 06:55 · Личное сообщение · #26 Хеш-таблицы - это хорошо. А зачем для этого 10 млн строк? Зачем вообще для этого строки? Когда хранение именно в байтах занимает в 2 раза меньше памяти и быстрее сравнивается? Для хеш-таблиц выбор именно криптографического хеша не всегда оправдан. И да, к коллизиям надо быть готовым в любом случае, неважно, какой хеш. Пытаться избавиться от коллизий, повышая размерность и стойкость хеша, занятие обычно неблагодарное. |
|
Создано: 08 июля 2018 08:18 · Поправил: Isaev · Личное сообщение · #27 SReg пишет: непонятно, что за массивы ты хранить собрался. Я то как раз собрался их НЕ хранить... а в TKey они будут храниться целиком в памяти! В том и проблема PS: потестил... мало того, он умножает занятое место ещё на 2 для хранения... т.е. если 1млн ключей по 255 байт занимал бы 255мб, то он хранит это в 530мб ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
Создано: 08 июля 2018 14:53 · Поправил: Crawler · Личное сообщение · #28 В С++ - это без оптимизации и в дебаг-режиме - занимает 7 секунд. В релизе с флагом /O2 занимает 1.5 секунды. Может, написать статическую библиотеку и встроить код (я хер знает, можно ли это в дельфи ? А, сука, я там \n поставил по старой привычке переводить строку. Было бы быстрее без него раза в два Значения массива для тестирования инициализировались rand()%255. 1. 2. * Чтобы оценить поточнее, поставил float и убрал перенос строки - получилось 1.066 секунды. Это учитывая, что вместо sprintf() можно встроить какой-нибудь эффективный инлайн-кусочек. ** Версия с itoa(value, buff[i], 16); выполняется за ~0.35-0.5 секунд. ----- Харе курить веники и нюхать клей, к вам едет из Америки бог Шива, и он еврей. |
|
Создано: 08 июля 2018 16:00 · Личное сообщение · #29 |
|
Создано: 08 июля 2018 16:05 · Поправил: Crawler · Личное сообщение · #30 dosprog, поэтому ниже я дописал, что протестировал с itoa(), получилось 0.35 секунд ;) Можно посмотреть исходники itoa(), убрать оттуда работу с разными основаниями (подставить сразу же 16), и выиграть ещё где-то 0.1 секунды. ----- Харе курить веники и нюхать клей, к вам едет из Америки бог Шива, и он еврей. |
. 1 . 2 . 3 . 4 . 5 . >> |
eXeL@B —› Программирование —› ByteToHex |