Не нужен, если у вас терабайты ОЗУ и 2гб для вас ничто. Если возможны, скажем, адреса в диапазоне 0 - 200 000 , то в случае массива надо выделять памяти N*200'000 . Но большая часть его пустой будет, т.к использоваться адреса будут сильно не все . Если из 200'000 возможных будет использоваться где-то 200 рандомных, то их можно разместить в хеш таблице размером под 300 записей. Между размером выделенной памяти под 200'000 и 300 есть разница?
UbIvItS, > имеет смысл взять более глубокую иерархию. Если под каждую вложенную таблицу выделять ссылку, то размер ссылок будет расти, с увеличением числа таблиц. Так же и тайминг, для каждой ссылки будет выборка и синхрон. Может как то использовать AWE.. njeen, Как применить хэш к рандому вы не сказали(я ведь спрашивал функцию для примера), твердя одно и тоже Хэш-функция выбирается для известных значений!?
ну-прям супер расти-то некуда == 4 байта адрес даёт ссылку а-ля цепочка из 4 таблиц по 256 записей в каждой и экономия места получается существенной. самый большой лаг получается на создание таблиц, при большом разлёте адресов может быть печалька сильная. единственно лечить можно более жадным потреблением озу, то бишь увеличиваем размер таблиц.. но тут уЖО смотри по своей ситуации акий конфиг лучше. что это?
Нет. Функция независима от значений. Инде может придумать абсолютно любую функцию, которая генерирует индекс в диапазоне, лишь бы равномерно по таблице. Как применить - мною описано ранее. Как применить к рандому - тоже (в #16) . И функция тоже дана была как пример.
njeen, Я не понимаю о чём вы говорите: > функцию, которая генерирует индекс в диапазоне Вот из вчерашнего лога значения и их квадратичная функция: Код (Text): 007B403B 1110110101011011001000110011111000110110011001 0051BB15 0110100001011111101100000000011010111110111001 007B4048 1110110101011011010101010101000001010001000000 0051BB15 0110100001011111101100000000011010111110111001 007B4055 1110110101011011100001110110001001110000111001 0051BB15 0110100001011111101100000000011010111110111001 - что дальше с этим делать ? --- Сообщение объединено, 13 мар 2020 --- UbIvItS, Для отображения придётся вызывать ядро, что можно делать очень редко, ибо не профайл. Например переключить какие то таблицы. Только что это может дать не знаю.
UbIvItS, ~1M для младшей версии IE. Зависит от приложения, позже сниму статистику на чём либо крупном.
Indy_, вроде, размер не супер критичный == можь одну здоровую таблицу будешь пользовать? хэш главное, чтоб без коллизий был.
Допустим, у нас в данный момент хеш таблица на 100 записей. Нам нужны из полученных квадратов индексы получить, чтобы были в диапазоне 0-100. Очевидно, что для этого достаточно взять 2 цифры на определенных позициях (возьмем на 5 и 6) . Тогда в десятичном виде будут взяты цифры для индекса: value (hex) ^2 (hex) ^2 (dec) полученный индекс007B403B3B56C8CF8D9965243922271641270051BB151A17EC01AFB92869004610348110007B40483B56D554144065244132283456280051BB151A17EC01AFB92869004610348110007B40553B56E1D89C396524434229560929 --- Сообщение объединено, 13 мар 2020 --- не главное . Немного коллизий - это нормально
для борьбы с коллизиями можно так таблицу замутить.. <>------hash----adr------pointer to description-------<> то бишь хэш тут есмь индекс таблицы, потом идёт взятый адрес (дабы проверять наличие коллизий). не пойму, а зачем квадраты нужны? и второй коварный вопрос == как выделять место под таблицу, то бишь с запасом иль как ??? в куче случаев "немного" -- это уЖО МНОГО
Что-что? Какой ещё борьбы? Коллизии неизбежны, для каждого способа организации хеш таблицы есть метод работы с ними. В в случае открытого хеширования это списки элементов, у которых совпадает вычисленный номер ячейки. Возведение в квадрат - это известный метод для получения получения хеш функции, которая равномерно распределяет все значения по таблице. Если этого не делать, значения будут скаплвиваться в опред. местах и коллизий будет очень много. "второй коварный вопрос == как выделять место под таблицу, то бишь с запасом иль как ???" - вы вообще предыдущие посты читаете? Идеальный метод начального размера таблицы взятия мне неизвестен, предполагаю первое значение размера наугад.
njeen, Спасибо за наглядный пример. Но как я уже много раз повторял, выбор функции в данном случае ручной по входным(известным) значениям, уже после получения всех адресов(после трассировки, а данная оптимизация для неё и нужна). Эти адреса из лога, их идёт непрерывный поток при трассировке. UbIvItS, > в куче случаев "немного" -- это уЖО МНОГО Гипотетически в данном случае если есть коллизии, то пришлось бы каждый адрес помечать(а это затраты на память), иначе после ошибки всё упало бы. Foxit Reader, 6.1 24 минуты на трассировку до появления гуя. Память апп 73MB с маркировкой адресов данным механизмом. 4 минуты открытие доки.. 1699477 ~1.6Mips --- Сообщение объединено, 13 мар 2020 --- Плохой пример выбрал. Слишком долго оно варится". Забыл строку коментнуть и есчо ждать пол часа; два запуска ~ час.. Даже крипторы быстрее заводятся.. Но это и есть суть задачи. Что бы перейти от копирования в статик буфер на каждой итерации к бинарной трансляции. Запуск без сохранения Ip: 16MB Общее количство инструкций при запуске гуя(что бы сравнить выше) 2.729.380.014 ~ 2.542GBips --- Сообщение объединено, 14 мар 2020 --- Есчо один запуск, забыл про время Разница по времени, без использования данного механизма: 24мин/25.. погрешность, разницы нет. Получается что механизм трансляции не влияет на результат, что очень странно. При таком огромном числе инструкций. Надо подумать.
это с чего они неизбежны? вероятность коллизий падает по 2n, где энн есмь длина хэша. я уже упоминал быстрые алгосы хэша ==запруженность разрешима чрез них. нужно ориентироваться по размеру исследуемого файла == к примеру, 20% от него. --- Сообщение объединено, 14 мар 2020 --- Indy_, а не легче ли не все потоки осилить за раз, а только один поток за сессию? 1. выборка маловата. 2. тут ещё надо смотреть процент загрузки проца. к примеру, в одном случае получается получить 500 000нс доступа к процу каждую секунду, а в другом всего лишь 25 000. 3. также имеется сильная зависимость от набора используемых апи.
UbIvItS > я уже упоминал быстрые алгосы хэша ==запруженность разрешима чрез них. Что вы всё про хэши, вы предлагаете накописть некоторую часть адресов и как то составить для них хэш функцию.. такое вообще возможно ? > не легче ли не все потоки осилить за раз, а только один поток за сессию? Приложение должно транслироваться(бинарная трансляция), а не трассироваться как сейчас. Из за копирований инструкций в буфера такие тормоза. А для этого необходимо реализовать две максимально быстрые функции - получение описателя по указателю(те когда происходит ветвление нужно найти соответствие в собранном коде) и синхронное выделение памяти для сборки. --- Сообщение объединено, 14 мар 2020 --- Можно ли имея некоторое большое количество адресов составить для них хэш функцию автоматикой ? Иначе хэши в данной задаче не применимы. --- Сообщение объединено, 14 мар 2020 --- > один поток за сессию? Как это, будет ведь деадлок.
Я не знаю, что это за формула, но отображение б0льшего множества в меньшее означает вероятность коллизий > 0 . Если вероятность ненулевая, то получение на вход потенциально бесконечно большого множества входных различных входных данных означает неизбежность коллизии. Можно только оценить количество накопленных адресов и основываясь на этом выбрать размер таблицы. При открытом хешировании средняя длина списков элементов в ячейках равняется N/B, где N - количество размещаемых элементов, B - количество ячеек таблицы. И опять же, при этом типе хеширования (открытом) необходимость увеличения таблицы наступает когда возникает ситуация N > 2B ; нужно стремиться к тому, чтобы B = 2N ориентировочно при формировании таблицы. Составить функцию - да, основываясь на текущем B . (Здесь опять я с возведением в квадрат и взятием б0льшего количества чисел из середины получившегося числа =) )
njeen, Можно вопрос общего плана. Вы понимаете о чём идёт речь ? По мойму нет, раз игнорите всё сказанное выше. Какой прок мне от ваших хэшей, если функцию от последовательности невозможно рассчитать автоматически ?
Кмк, да. У вас есть некоторый код, который выдает поток адресов из опред. диапазона, и вы каждому хотите соответствие. В массиве перебор слишком долгий, поэтому вы задали вопрос, как это можно улучшить. Но упорно не хотите понять хеш таблицы. Чем вам коррекция функции хеширования в зависимости от числа встреченных адресов не автоматика?
ну-так, принцип бт в чём? по ходу дела собираешь адреса/куски кода и переделываешь их в нужную форму. из тех адресов, что за кэшировал, лабаешь хэши. даже можешь залабать хэши из уже кэшированных кусков кода, если такое по нраву Возьми исходники виртуалбокса и/ль кему, там имеется динамическая рекомпиляция. если быть точней, хэш отображает строку из энн бит в строку из эмм бит, где энн больше эмм. среднее кол-во совпадений хэша при отображение ВСЕХ строк длины энн == 2 в степени энн делить на два в степени эмм. ключевым словом тут является "ВСЕХ". обычно кол-во вхождений в таблицу гораздо меньше, чем кол-во возможных значений хэша. Тч в таблице никаких коллизий хэша не допускается от слова СОВСЕМ. N в идеале должно быть == кол-ву строк в таблице, а кол-во столбцов вариативно (не на стадии исполнения, конечно). второй момент, если мы говорим о статичных кодах, то кол-во накопленных адресов не может превышать размер бина. но даже в случае всяких тамо хитроЖО.. протекторов и морфах вполне можно задавать размер таблицы на основе размера подопытного бин файла. это довольно силовой приём.. так можно ещё и модульную арифу вспомнить но зачем так напружать проц(???), если легковесные хэши на +/-/ИЛИ/КСОР/И/СДВИГ позволяют получать тот же результат, но быстрей. например, такая таблица вполне робитЪЪЪ.. <>-----hash----id of hash func-----adr-----pointer to object-----<>
