Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.188.44.223] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
У меня 2 вопроса: теоретический и практический. По теории: Почти все источники, когда рассказывают про хеш-таблицы и хеш-функции, приводят пример такой хеш-функции ( абстрактный ): i = hash( key ); hash - хеш-функция key - ключ данных а вот i - типа номер слота в самой хеш-таблице. То есть по-большему счету, хеш-функция в качестве результата возвращает позицию "вставки" данных в хеш-таблицу. Но встретил еще одно мнение ( и интуитивно оно мне кажется очень справедливым ). Суть такая: хеш-функция ДОЛЖНА ЗАВИСЕТЬ ТОЛЬКО от свойств хешируемых данных и не иметь НИКАКОГО отношения к размеру хеш-таблицы. ИМХО, это очень справедливо В этом случае получается как бы 2х этапный процесс: 1. хеш-функция генерирует хеш-сумму, ни коим образом не зависящий от емкости слотов хеш-таблицы 2. хеш подгоняем под размер хеш-таблицы ( по классике % capacity или как-то еще ). Вопрос: какой из подходов более правильный? ------------------------------------------------------------------------ По практике: Допустим дана разреж. матрица, состоящая из 100 000 строк и 200 000 колонок ( 100К на 200К ) дробных чисел. Около 5% ячеек будут заполнены ( или даже меньше ). И нужна хеш-таблица ( с хеш-функцией ), которая отображает в себя эту матрицу. Основные операции, которые нужны над данными - построчная какая-то обработка с поиском первого минимального или последнего максимального и пр. И что-то не очень просто оказалось это сделать) каждый элемент матрицы характеризуется: - координатой по №строки - координатой по №колонки - самим числом Что из этого ключ? Кажется, что координаты - их пара уникальна в рамках всей матрицы. Но в любом случае все это не спасает от полного сканирования всей строки элементов ( от 0 до 199 999 ), когда делается попытка обработать элементы этой строки, например, в поиске последнего минимального. Здесь что-то концептуально не вяжется. По-большему счету, надо получить такой эффект, чтобы, например, при обработке элементов 3-й строки обрабатывались ТОЛЬКО реальные ячейки с данными. Но как в этом поможет хеш-таблица - не вижу помощи от нее) Или хеш-таблицы для обработки построчной sparse array крайне неудачный выбор? Подскажите, как быть-то спс. за внимание Добавлено если отказаться от хеш-таблицы, то понятно, что можно задействовать список списков для отображения разр.матрицы. создать одномерный массив ( количество слотов равно количеству строк ) указателей + построить цепочки для реальных данных. тогда структура, описывающая данные будет примерно такой: структура ЧИСЛО номер колонки само число если в какой-то i-ой строке заданной матр. нет вообще элементов, то указатель[ i ] = NULL; но это уже не хеш-таблица) и вся обработка сводится к линейному просмотру. Но вроде такой подход вполне здесь может быть приемлем, наверное или все-таки тоже нет |
Сообщ.
#2
,
|
|
|
Цитата Вопрос: какой из подходов более правильный? Любой, который позволит создать таблицу с уникальными индексами для всех добавленных в нее (возможных) данных. Цитата Или хеш-таблицы для обработки построчной sparse array крайне неудачный выбор? Хеш таблица может содержать координаты ячеек с реальными данными, а хеш и соответственно индекс будет рассчитываться по данным и координатам. Тогда перечислять можно будет только ячейки содержащие реальные данные проходя по таблице. Далее, если можно обратить хеш, то у вас есть его компонент координаты (они записаны напрямую в таблице), тогда можно получить сами данные (число). Например: ; Хеш функция (inline) mov eax, [col] xor eax, [row] add eax, [num] ; Хеш таблица lea rbx, [tbl] ; Добавление нового элемента (поиск в уже присутствующих) @@: mov rbx, [rbx] ror eax, 1 sbb rdx, rdx lea rbx, [rbx + rdx * 8 + 8] cmp qword [rbx], 0 loopnz @b jrcxz .exist ; Найден элемент с таким же хеш (наихудший исход. стоит изменить хеш функцию) ; Добавление нового элемента (дополнение недостающих индексов в таблице) @@: ; Выделение памяти из буфера под новый элемент хеш таблицы mov rdx, [buf] add rdx, 16 cmp rdx, [eob] jae .error ; Недостаточно памяти xchg rdx, [buf] ; Добавление нового элемента в хеш таблицу mov [rbx], rdx ror eax, 1 sbb rdx, rdx lea rbx, [rbx + rdx * 8 + 8] loop @b ; Выделение памяти из буфера под новый элемент хеш таблицы mov rdx, [buf] add rdx, 16 cmp rdx, [eob] jae .error ; Недостаточно памяти xchg rdx, [buf] ; Добавление последнего элемента в хеш таблицу (он содержит координаты) mov eax, [col] mov ecx, [row] mov [rdx + 0], eax mov [rdx + 4], ecx mov [rbx], rdx jmp .done ; Найден элемент с таким же хеш (наихудший исход. стоит изменить хеш функцию) .exist: ; Выделение памяти из буфера под новый элемент хеш таблицы mov rdx, [buf] add rdx, 16 cmp rdx, [eob] jae .error xchg rdx, [buf] ; Заполнение данных во вновь выделенном буфере mov eax, [col] mov ecx, [row] mov [rdx + 0], eax mov [rdx + 4], ecx and qword [rdx + 8], 0 ; Пропуск всех присутствующих элементов в динамическом списке @@: cmp qword [rbx + 8], 0 jz @f mov rbx, [rbx + 8] jmp @b ; Ошибка. В выделенном буфере недостаточно памяти для размещения хеш таблицы .error: jmp raise_error_out_of_memory ; Добавление нового элемента в динамический список элементов с одинаковым хеш @@: mov [rbx + 8], rdx ; Новый элемент добавлен в хеш таблицу (бинарное дерево) .done: mov ecx, [rdx] xor ecx, [rdx + 4] sub eax, ecx |
Сообщ.
#3
,
|
|
|
macomics, сразу еще договоримся, что хеш-таблица на цепочках ( без открытой адресации ). Открытая адресация более тонкая + возникает переполнение, когда кол-во входных данных превышает емкость ХТ и требуется реорганизация ( а этот процесс не самый тривиальный и существует множество подходов ). На цепочках память выделяется для коллизий только по мере надобности + тогда ХТ становится безразмерной ( хотя ее тоже вроде могут как-то реорганизовывать, но это ладно, пока не важно ).
Вот смотри, вот условно говоря, простейшая операция: нужно найти минимальный элемент в каждой строке матрицы. Матрица размером N x M ( N, M --> inf ). Если будет хеш-таблица, то ведь придется все равно запускать такие вещи, верно?: for ( i = 0; i < N; i++ ) { for ( j = 0; j < M; j++ ) { // здесь обращение к хеш-функции } } при этом 95% ( 5% ячеек считаем, что хранят данные ) итераций будут холостыми. Далее, однозначно коллизии будут, т к создать идеальную ХФ нереал ( ну почти ), следовательно, будут цепочки отрастать) прототип ХФ ( возьмем подход №1, который мне нравится меньше ): int hash( const int index_row, const int index_col, const double value, const int capacity ) { // здесь какая-то обработка и возвращается индекс слота для вставки в ХФ } но это ведь не годится. вот условно говоря. Заданы габариты матрицы. Введены какие-то данные. Как-то заполнена хеш-таблица. Ок. Затем надо найти мин. в каждой строке ( как тривиальный пример ). По сути о данных ничего неизвестно, кроме их типа. Сами значения лежат каким-то образом в хеш-таблице. Только известны габариты матрицы. Ничего не остается, как запускать этот двойной цикл с колоссальным кол-вом итераций. вот еще. Условно говоря, операция поиска должна мне сказать: есть ли число в матрице с данными координатами или нет. Если есть, то я беру его в обработку. Короче, мы ведь не ищем конкретные данные в ХФ ( дробные числа ), а пытаемся узнать, есть ли данные с заданными координатами. Из этого я делаю вывод, что ключом выступают ТОЛЬКО координаты ячейки матрицы. Но возникает коллизия, например, для A[ 193 ][ 385 ] и A[ 3882 ][ 99992 ] одинаковая хеш-сумма = 100. ок, отрастает цепочка. Но все равно придется отличать их друг от друга. Придется сохранять информацию для каждого элемента списка информацию о №строки и №колонки + линейный поиск по списку для поиска коллизионного значения. была еще мысль хешировать по №строки, а затем уже по №колонки, но что-то все это корявато как-то) и еще, плиз, не нужен никакой код, тем более на asm-е, ни одной команды из него не знаю |
Сообщ.
#4
,
|
|
|
В приведенной мной ХФ демонстрируется "пример" обращения с такими данными и ничего более. Она даже, скорее всего, не рабочая (набирал от балды в браузере и не проверял). Главное что позволит ХФ - это выстроить данные в удобной для линейного алгоритма форме. Я же выбрал форму бинарного дерева - она не очень удобна для поиска элементов по строкам/столбцам.
Цитата FasterHarder @ Затем надо найти мин. в каждой строке ( как тривиальный пример ). По сути о данных ничего неизвестно, кроме их типа. Сами значения лежат каким-то образом в хеш-таблице. Только известны габариты матрицы. Ничего не остается, как запускать этот двойной цикл с колоссальным кол-вом итераций. Цикл может и придется запустить двойной, но количество итераций внутреннего цикла может быть много меньше, чем количество элементов в строке. Например, если ХФ будет заполнять таблицу по порядку строк (ХТ будет отсортирована по увеличению индекса в строке т.к. старшие 18 бит индекса будут равны индексу строки), тогда достаточно следовать этому правилу и прерывать внутренний цикл, когда встречается 1-ый элемент на следующей строке (с него же и будет продолжать внутренний цикл на следующей итерации внешнего). Или ХТ будет представлять матрицу упорядоченную по строкам, а строки будут упорядочены по значениям. Тогда поиск минимальных будет сводиться к нахождению первого элемента в нужной строке из ХТ. Цитата FasterHarder @ Короче, мы ведь не ищем конкретные данные в ХФ ( дробные числа ), а пытаемся узнать, есть ли данные с заданными координатами. Из этого я делаю вывод, что ключом выступают ТОЛЬКО координаты ячейки матрицы. Опять же. В приведенном мной примере есть еще один интересный момент. Это откат хеш значения для получения из хеш индекса требуемого значения (это не обязательно должно быть так, но таблица может содержать в себе не только координаты, но и сами значения), тогда не придется хранить матрицу с кучей пустых значений. Что тоже ускорит перечисление и уменьшит количество памяти. Цитата FasterHarder @ и еще, плиз, не нужен никакой код, тем более на asm-е, ни одной команды из него не знаю На asm-е просто микширование float и int выглядит проще. Просто используй не те команды, главное, чтобы числа в длину укладывались. |