Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871952 Tue, 19 Jul 2022 16:20:36 +0000 Про хеш-таблицы и хеш-функцию для sparse array https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871952
Цитата FasterHarder @
Затем надо найти мин. в каждой строке ( как тривиальный пример ). По сути о данных ничего неизвестно, кроме их типа. Сами значения лежат каким-то образом в хеш-таблице. Только известны габариты матрицы. Ничего не остается, как запускать этот двойной цикл с колоссальным кол-вом итераций.

Цикл может и придется запустить двойной, но количество итераций внутреннего цикла может быть много меньше, чем количество элементов в строке.
Например, если ХФ будет заполнять таблицу по порядку строк (ХТ будет отсортирована по увеличению индекса в строке т.к. старшие 18 бит индекса будут равны индексу строки), тогда достаточно следовать этому правилу и прерывать внутренний цикл, когда встречается 1-ый элемент на следующей строке (с него же и будет продолжать внутренний цикл на следующей итерации внешнего).
Или ХТ будет представлять матрицу упорядоченную по строкам, а строки будут упорядочены по значениям. Тогда поиск минимальных будет сводиться к нахождению первого элемента в нужной строке из ХТ.

Цитата FasterHarder @
Короче, мы ведь не ищем конкретные данные в ХФ ( дробные числа ), а пытаемся узнать, есть ли данные с заданными координатами. Из этого я делаю вывод, что ключом выступают ТОЛЬКО координаты ячейки матрицы.

Опять же. В приведенном мной примере есть еще один интересный момент. Это откат хеш значения для получения из хеш индекса требуемого значения (это не обязательно должно быть так, но таблица может содержать в себе не только координаты, но и сами значения), тогда не придется хранить матрицу с кучей пустых значений. Что тоже ускорит перечисление и уменьшит количество памяти.

Цитата FasterHarder @
и еще, плиз, не нужен никакой код, тем более на asm-е, ни одной команды из него не знаю

На asm-е просто микширование float и int выглядит проще. Просто используй не те команды, главное, чтобы числа в длину укладывались.]]> macomics Алгоритмы https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871933 Tue, 19 Jul 2022 12:33:25 +0000 Про хеш-таблицы и хеш-функцию для sparse array https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871933 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-е, ни одной команды из него не знаю]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871928 Tue, 19 Jul 2022 11:25:51 +0000 Про хеш-таблицы и хеш-функцию для sparse array https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871928 Цитата
Вопрос: какой из подходов более правильный?

Любой, который позволит создать таблицу с уникальными индексами для всех добавленных в нее (возможных) данных.
Цитата
Или хеш-таблицы для обработки построчной 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
Можно получить из хеш число.]]> macomics Алгоритмы https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871927 Tue, 19 Jul 2022 11:11:13 +0000 Про хеш-таблицы и хеш-функцию для sparse array https://forum.sources.ru/index.php?showtopic=428695&view=findpost&p=3871927
У меня 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;

но это уже не хеш-таблица) и вся обработка сводится к линейному просмотру. Но вроде такой подход вполне здесь может быть приемлем, наверное или все-таки тоже нет]]> FasterHarder Алгоритмы