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

    Есть текстовый файл, в котором хранятся номера моб.телефонов(на 1 строке файла лежит 1 номер).
    Маска телефонов: 8(9XX) XXX-XX-XX, X - цифра, т е принимает целое значение от 0 до 9.
    Примеры правильных ном. телефонов:
    1. 8(919) 100-08-73
    2. 8(903) 981-02-22
    ...
    В файле может хранится до 50 млн. РАЗЛИЧНЫХ ном.телефонов.
    Нужно в общем их захешировать по оптимальнее (не прям чтоб идеально) методом цепочек.
    ===================================================
    Вот, если требовалось бы только искать ном.телефонов, тогда я бы преобразовал ном.телефонов в целые числа (без учета первой 8-ки и 9-ки), отсортировал бы Хоаром и дихотомией бы искал. Оптимальнее способа ИМХО не существовало бы. Но тогда бы вставка была бы недопустимой из-за сдвига на 1 позицию влево-вправо лютого кол-ва элементов. Прогга умерла бы при вставке, удалении (с послед.сжатием).

    Нужна какая-то хэш-функция! Желательно получше...
    1. Нужно понять, в каком типе данных обрабатывать ном.тел.: строка или перевод в целое число?
    2. Хотелось бы эти 50млн. записей в файле ОТРАЗИТЬ в хеш-таблицу, в которой не более 5000 записей. Т е в отношении 1 к 10 000. Или мало 5000 для хеш-таблицы?? Очевидно, что коллизий НЕ ИЗБЕЖАТЬ ни при каких раскладах...

    Примеры ХФ:
    1. вернуть последнюю цифру №тел. - тогда в ХТ будет 10 записей, а в каждой цепочке примерно 5млн.записей и коллизия при обработке каждого 10-го №тел.
    2. вернуть (сумму цифр тел.) mod (длина номера) - некий аналоги способа 1.
    3. вернуть самую часто встречаемую цифру в №тел. - опять-таки, будет всего 10 записей в ХТ и коллизия на каждом 10-ом
    ...

    т е все, что приходит на ум из простого отображает все номера телефонов в 10 записей ХТ. Это ведь плохо, так?

    Если привязывать к АСКИ-кодам цифр (№тел. рассматривается как строка), тут, что можно придумать?

    Я хотел бы узнать у общества, вот, если подается 50млн.записей, то в какой размер ХТ это желательно отразить? №тел.задаются ХАОТИЧНО и там нет никакой частотности или закономерности.
    Какую ХФ лучше взять?
      А зачем вам метод цепочек?
      Использовать двойное хэширование и всё.
      Не могу до конца понять двойное хеширование (перемешанные таблицы)
        нашел такой пример в инете хеширования строк!
        №тел.такой: 8(9ХХ) ХХХ-ХХ-ХХ, преобразуем в строку вида "ХХХХХХХХХ", т е в строку, состоящую ТОЛЬКО из 10-ных цифр в кол-ве РОВНО 9 штук.
        Мощность алфавита М = 10 (т к всего 10 различных цифр). Берем максимальное простое число, попадающее по значению в мощность множества Р = 7 (Р <= M) + Р-простое.
        И после этого вычисляем ХЭШ по правилу:
        <АСКИ-код 1-й цифры строки> * P^0 + <АСКИ-код 2-й цифры> * P^1 + ... + <АСКИ-код предпоследней цифры> * P^7 + <АСКИ-код последней> * P^8

        Номера телефонов лежат на отрезке ["000000000" .. "999999999"]. Значит, хеш-код будет лежать на отрезке от 0 до
        57 + 57*7 + 57*7^2 + ... + 57*7^7 + 57*7^8 = infinity

        вот тут не знаю, может имеет смысл брать не АСКИ-коды цифр-символов ('0' --> 48, '1'---> 49, ..., '9'--> 57), а цифру-цифру равную символе-цифре('0' --> 0, .., '9' --> 9), тогда правая граница значительно сократится!

        Но в любом случае, хэш-таблица будет представлять собой динамический массив, у которого кол-во элементов равно этому "инифинити". Но ведь таблица будет очень РАЗРЯЖЕННОЙ, т к не все хеш-коды можно сгенерить. Это нормально, да??

        Кстати, этот алгоритм очень мне напоминает алгоритм сравнения двух дат, когда ДД, ММ и ГГГГ умножаются на возрастающие коэффы, а потом складываются...

        Наверное, так тупо и буду делать или есть ГОРАЗДО лучше что-то??
          Есть. БД. Индексы.
            Цитата Gonarh @
            БД. Индексы.

            насколько смутно помню, в основе индексов лежат какие-то древовидные структуры данных!
            меня интересует почти оптимальная хэш-функция...
              Номер телефона, преобразованный в число mod 5000 (или сколько тебе там значений хеша нужно) и всё, если уж хочешь изобретать велосипед.
                Цитата OpenGL @
                или сколько тебе там значений хеша нужно

                а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)? в 1-ом посте и спрашиваю в том числе про это кол-во.

                '0' --> 0 или '0' --> 48??
                ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет??
                  Нужно, нужно... хрень голимая. Всё, что делается - делается зачем-то, а не для умственного онанизма. А потому - формулируй задачу. Наху зачем тебе это хэширование нужно? Искать номер? считать статистику? что-то ещё? от задачи и будет плясать оптимальное решение.

                  Цитата Gonarh @
                  Есть. БД. Индексы.

                  +146% Правильно спроектированная и проиндексированная БД - выиграет у любого рукописного приложения, за исключением узкоспецифичных однозадачников.

                  Цитата FasterHarder @
                  смутно помню, в основе индексов лежат какие-то древовидные структуры данных

                  После получения хэша тебе ещё надо оптимизировать таблицу этих хэшей для быстрого поиска. И эта оптимизированная таблица поиска у тебя будет сортированной, а оптимизацию самого поиска ты будешь производить, интерпретируя сортированный массив хэшей как дерево - явно или неявно (если не хочешь проиграть по дисковым операциям и операциям поиска в загруженном в память массиве). Заодно придёшь к мысли о кластеризации хэш-таблицы, и... поздравляю, ты придумал свою СУБД.

                  Цитата FasterHarder @
                  1. вернуть последнюю цифру №тел. - тогда в ХТ будет 10 записей, а в каждой цепочке примерно 5млн.записей и коллизия при обработке каждого 10-го №тел.

                  Во-первых, коллизия для любого телефона с вероятностью 1-0,94999999. Т.е. вероятностью отсутствия коллизии можно смело пренебречь. А не прогнозируемые тобой 90%.
                  Во-вторых, почему одну, а не, скажем, 4 или 5?
                  Сообщение отредактировано: Akina -
                    Цитата FasterHarder @
                    а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)?

                    Нисколько. Я бы битовым массивом тупо всё сделал. Его размер получился бы 128 мегабайт всего. Всяко меньше, чем вся хеш-таблица, содержащая 50 миллионов номеров.

                    Цитата FasterHarder @
                    ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет??

                    С чего бы? Во втором варианте у тебя он не от 0 же будет. Т.е. такой заменой ты просто сдвинул множество значений твоего хеша. И всё это один фиг хуже, чем просто тупой mod (то, что ты обозвал infinity) будет.
                      Akina, ну есть файл с телефонами и нужно создать на ее основе хеш-таблицу методом цепочек ДЛЯ ПОИСКА. вот и все условие. Детали формата написаны в 1-ом посте (там все тривиально).
                      Вот я и думаю), какую бы ХФ пооптимальнее соорудить...

                      Цитата OpenGL @
                      С чего бы? Во втором варианте у тебя он не от 0 же будет. Т.е. такой заменой ты просто сдвинул множество значений твоего хеша. И всё это один фиг хуже, чем просто тупой mod (то, что ты обозвал infinity) будет.

                      ну, в принципе да! сдвинуть в 0 даже удобнее с позиции языка СИ, т к нумерация элементов идет от 0...

                      Добавлено
                      Цитата Akina @
                      Во-вторых, почему одну, а не, скажем, 4 или 5?

                      а вот именно по этой причине и был создан вопрос в разделе "Алгоритмы", что понять, 1цифру или 4 или 5, а может даже 6! Или вообще совсем др.подход использовать...

                      Добавлено
                      Цитата OpenGL @
                      Я бы битовым массивом тупо всё сделал.

                      я чисто для себя полюбопытствовать (хотя битовую сетка в задании не нужна). Битовая сетка - это ведь набор элементов/бит, принимающих значения из множества {0, 1}.
                      Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому??
                        Цитата FasterHarder @
                        Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому??

                        У тебя номера телефонов, судя по маске, 9 циферные. Т.е. всего номеров 1 миллиард. Заводим битовый массив длиной миллиард, в котором 0 - телефона нет. 1 - есть. Всё же очевидно. Твоему номеру телефона соответствует число 11193890 - элемент с таким номером и задавай в 1. И кстати, а чем это не хеш-функция? Причём она идеальная без коллизий :D
                          Цитата OpenGL @
                          Заводим битовый массив длиной миллиард

                          прогга у меня на "чистом" С89. Насколько помню, самый дешевый тип данных там char (8 бит). Логич.типа нету, есть он в стандарте C99 (<stdbool.h>), но и там логич.тип наверняка 1байтовый.
                          А, эти еще есть, БИТОВЫЕ ПОЛЯ в структурах, но ведь там нельзя вроде получить массив бит. В общем нету типа данных bit, для которого sizeof(bit) = 0.125 байт.

                          Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту!

                          Итак, решено делать так, тем более, что в сети декларируют, что мол это один из лучших варианов хеширования. окэй!
                          Дан телефон в виде строки: "8(928) 183-18-35". Строим из него число x = 281 831 835 (тип данных х --> unsigned, до 4.2 лярдов держит, мне хватит!).
                          Берем минимальное простое число, которое перекрывает множество алфавита, это число 11.
                          Можно считать, что имеем число 281831835 по основанию (11). Далее переводим из СС(11) в СС(10) по правилам.
                          Вообще, по идее, можно числовое представление и не получать,а сразу обрабатывать строковое представление №телефона.

                          b0 * 11^0 + b1 * 11^1 + ... + b7 * 11^7 + b8 * 11^8, по идее для этой суммы хватит того же unsigned. В алгоритме, который видел бегут по строке СЛЕВА НАПРАВО, я же пойду наоборот. А какая разница-то? Да, никакой!
                          Т е ХФ вернет значение вот этой суммы. Хэш-таблица - одномерный динамический массив, у которой тип данных элементов самый дешевый, ну, например, ну, не знаю unsigned char (нету типа данных = 1биту).

                          Допустим, ХФ вернуло значение 99 832 104, лезем по этому индексу в ХТ и ставим, ну, не знаю, какой-то признак, ну, например, символ 'y' (типа 'y' - YES, т е есть такой №тел.). По умолчанию все элементы пустой ХТ равны чему-то, ну, не знаю чему. Да хоть чему, главное не 'y')

                          Как я понимаю, в этом случае коллизий не будет вообще, т к любое уникальное число в СС(11) преобразуется в уникальное значение в СС(10).
                          Я не знаю, вроде хотелось цепочки получать, а их тут НЕ БУДЕТ физически ни одной (кроме 1-го элемента).
                          На самом деле их можно получить, если, допустим для суммы взять не тип данных unsigned, а, например, unsigned short. В этом случае будет возникать переполнение. НУ И ЧТО! пусть идет вычет по модулю, да и все. В этом случае будет гораздо меньше элементов в ХТ.

                          В общем вот так буду делать, и там все должно быть норм. и красиво и быстро и эффективно и не заморочено! УРА! 8-)

                          P.S. но вообще, создание хороших ХФ (не как в моем трив.случае), требует не дюжей подготовки в Computer Science, ага...Ну это мое мнение, разумеется)
                          Сообщение отредактировано: FasterHarder -
                            Что вопрос решен - это хорошо, но было бы любопытно узнать: а в чем, собственно, вопрос заключался? Задача "захэшировать пятьдесят миллионов значений в таблицу на пять тыщ позиций" изначально звучит бредово. Какова же настоящая задача?

                            P. S.
                            Цитата
                            В общем нету типа данных bit, для которого sizeof(bit) = 0.125 байт.

                            Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту!

                            Гм. Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет.
                              Цитата AVA12 @
                              Какова же настоящая задача?

                              быстрый поиск №тел. с применением ХТ на цепочках! все!

                              Цитата AVA12 @
                              Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет.

                              не путай Программистов и дилетантов)
                                Цитата FasterHarder @
                                прогга у меня на "чистом" С89.
                                ...
                                А, эти еще есть, БИТОВЫЕ ПОЛЯ в структурах, но ведь там нельзя вроде получить массив бит.
                                В Плюсах есть std::bitset<> и std::vector<bool>. Тебе какой?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0398 ]   [ 16 queries used ]   [ Generated: 29.03.24, 04:39 GMT ]