На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Про хеш-таблицы и хеш-функцию для sparse array
    Всем хай! Сходу к делу!

    У меня 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;

    но это уже не хеш-таблица) и вся обработка сводится к линейному просмотру. Но вроде такой подход вполне здесь может быть приемлем, наверное или все-таки тоже нет
      Цитата
      Вопрос: какой из подходов более правильный?

      Любой, который позволит создать таблицу с уникальными индексами для всех добавленных в нее (возможных) данных.
      Цитата
      Или хеш-таблицы для обработки построчной sparse array крайне неудачный выбор?

      Хеш таблица может содержать координаты ячеек с реальными данными, а хеш и соответственно индекс будет рассчитываться по данным и координатам. Тогда перечислять можно будет только ячейки содержащие реальные данные проходя по таблице.
      Далее, если можно обратить хеш, то у вас есть его компонент координаты (они записаны напрямую в таблице), тогда можно получить сами данные (число).
      Например:
      ExpandedWrap disabled
        ; Хеш функция (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:
      В конечном итоге при поиске будут найдены координаты в этой таблице и известен хеш. Тогда выполнив
      ExpandedWrap disabled
        mov ecx, [rdx]
        xor ecx, [rdx + 4]
        sub eax, ecx
      Можно получить из хеш число.
      Сообщение отредактировано: macomics -
        macomics, сразу еще договоримся, что хеш-таблица на цепочках ( без открытой адресации ). Открытая адресация более тонкая + возникает переполнение, когда кол-во входных данных превышает емкость ХТ и требуется реорганизация ( а этот процесс не самый тривиальный и существует множество подходов ). На цепочках память выделяется для коллизий только по мере надобности + тогда ХТ становится безразмерной ( хотя ее тоже вроде могут как-то реорганизовывать, но это ладно, пока не важно ).

        Вот смотри, вот условно говоря, простейшая операция: нужно найти минимальный элемент в каждой строке матрицы. Матрица размером N x M ( N, M --> inf ).
        Если будет хеш-таблица, то ведь придется все равно запускать такие вещи, верно?:
        ExpandedWrap disabled
          for ( i = 0; i < N; i++ )
          {
               for ( j = 0; j < M; j++ )
               {
                     // здесь обращение к хеш-функции
               }
          }


        при этом 95% ( 5% ячеек считаем, что хранят данные ) итераций будут холостыми.

        Далее, однозначно коллизии будут, т к создать идеальную ХФ нереал ( ну почти ), следовательно, будут цепочки отрастать)
        прототип ХФ ( возьмем подход №1, который мне нравится меньше ):

        ExpandedWrap disabled
          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 -
          В приведенной мной ХФ демонстрируется "пример" обращения с такими данными и ничего более. Она даже, скорее всего, не рабочая (набирал от балды в браузере и не проверял). Главное что позволит ХФ - это выстроить данные в удобной для линейного алгоритма форме. Я же выбрал форму бинарного дерева - она не очень удобна для поиска элементов по строкам/столбцам.

          Цитата FasterHarder @
          Затем надо найти мин. в каждой строке ( как тривиальный пример ). По сути о данных ничего неизвестно, кроме их типа. Сами значения лежат каким-то образом в хеш-таблице. Только известны габариты матрицы. Ничего не остается, как запускать этот двойной цикл с колоссальным кол-вом итераций.

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

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

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

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

          На asm-е просто микширование float и int выглядит проще. Просто используй не те команды, главное, чтобы числа в длину укладывались.
          Сообщение отредактировано: macomics -
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0372 ]   [ 15 queries used ]   [ Generated: 19.03.24, 02:28 GMT ]