Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.15.2.78] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Есть текстовый файл, в котором хранятся номера моб.телефонов(на 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млн.записей, то в какой размер ХТ это желательно отразить? №тел.задаются ХАОТИЧНО и там нет никакой частотности или закономерности. Какую ХФ лучше взять? |
Сообщ.
#2
,
|
|
|
А зачем вам метод цепочек?
Использовать двойное хэширование и всё. Не могу до конца понять двойное хеширование (перемешанные таблицы) |
Сообщ.
#3
,
|
|
|
нашел такой пример в инете хеширования строк!
№тел.такой: 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), тогда правая граница значительно сократится! Но в любом случае, хэш-таблица будет представлять собой динамический массив, у которого кол-во элементов равно этому "инифинити". Но ведь таблица будет очень РАЗРЯЖЕННОЙ, т к не все хеш-коды можно сгенерить. Это нормально, да?? Кстати, этот алгоритм очень мне напоминает алгоритм сравнения двух дат, когда ДД, ММ и ГГГГ умножаются на возрастающие коэффы, а потом складываются... Наверное, так тупо и буду делать или есть ГОРАЗДО лучше что-то?? |
Сообщ.
#4
,
|
|
|
Есть. БД. Индексы.
|
Сообщ.
#5
,
|
|
|
Цитата Gonarh @ БД. Индексы. насколько смутно помню, в основе индексов лежат какие-то древовидные структуры данных! меня интересует почти оптимальная хэш-функция... |
Сообщ.
#6
,
|
|
|
Номер телефона, преобразованный в число mod 5000 (или сколько тебе там значений хеша нужно) и всё, если уж хочешь изобретать велосипед.
|
Сообщ.
#7
,
|
|
|
Цитата OpenGL @ или сколько тебе там значений хеша нужно а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)? в 1-ом посте и спрашиваю в том числе про это кол-во. '0' --> 0 или '0' --> 48?? ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет?? |
Сообщ.
#8
,
|
|
|
Нужно, нужно... хрень голимая. Всё, что делается - делается зачем-то, а не для умственного онанизма. А потому - формулируй задачу. На
Цитата Gonarh @ Есть. БД. Индексы. +146% Правильно спроектированная и проиндексированная БД - выиграет у любого рукописного приложения, за исключением узкоспецифичных однозадачников. Цитата FasterHarder @ смутно помню, в основе индексов лежат какие-то древовидные структуры данных После получения хэша тебе ещё надо оптимизировать таблицу этих хэшей для быстрого поиска. И эта оптимизированная таблица поиска у тебя будет сортированной, а оптимизацию самого поиска ты будешь производить, интерпретируя сортированный массив хэшей как дерево - явно или неявно (если не хочешь проиграть по дисковым операциям и операциям поиска в загруженном в память массиве). Заодно придёшь к мысли о кластеризации хэш-таблицы, и... поздравляю, ты придумал свою СУБД. Цитата FasterHarder @ 1. вернуть последнюю цифру №тел. - тогда в ХТ будет 10 записей, а в каждой цепочке примерно 5млн.записей и коллизия при обработке каждого 10-го №тел. Во-первых, коллизия для любого телефона с вероятностью 1-0,94999999. Т.е. вероятностью отсутствия коллизии можно смело пренебречь. А не прогнозируемые тобой 90%. Во-вторых, почему одну, а не, скажем, 4 или 5? |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ а сколько бы ты сделал (т е подается N номеров и отражается во сколько записей ХТ)? Нисколько. Я бы битовым массивом тупо всё сделал. Его размер получился бы 128 мегабайт всего. Всяко меньше, чем вся хеш-таблица, содержащая 50 миллионов номеров. Цитата FasterHarder @ ИМХО, 2-й вариант уменьшает вероятность появления коллизий. Нет?? С чего бы? Во втором варианте у тебя он не от 0 же будет. Т.е. такой заменой ты просто сдвинул множество значений твоего хеша. И всё это один фиг хуже, чем просто тупой mod (то, что ты обозвал infinity) будет. |
Сообщ.
#10
,
|
|
|
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-ную СС? или вообще все совсем по-другому?? |
Сообщ.
#11
,
|
|
|
Цитата FasterHarder @ Т е есть вот есть произвольный номер: 8(901) 119-38-90. Что бы ты сделал? Получил число "011198390" (кстати, если брать как число, то ведущий 0 отваливается из анализа) и перевел в 2-ную СС? или вообще все совсем по-другому?? У тебя номера телефонов, судя по маске, 9 циферные. Т.е. всего номеров 1 миллиард. Заводим битовый массив длиной миллиард, в котором 0 - телефона нет. 1 - есть. Всё же очевидно. Твоему номеру телефона соответствует число 11193890 - элемент с таким номером и задавай в 1. И кстати, а чем это не хеш-функция? Причём она идеальная без коллизий |
Сообщ.
#12
,
|
|
|
Цитата 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. В этом случае будет возникать переполнение. НУ И ЧТО! пусть идет вычет по модулю, да и все. В этом случае будет гораздо меньше элементов в ХТ. В общем вот так буду делать, и там все должно быть норм. и красиво и быстро и эффективно и не заморочено! УРА! P.S. но вообще, создание хороших ХФ (не как в моем трив.случае), требует не дюжей подготовки в Computer Science, ага...Ну это мое мнение, разумеется) |
Сообщ.
#13
,
|
|
|
Что вопрос решен - это хорошо, но было бы любопытно узнать: а в чем, собственно, вопрос заключался? Задача "захэшировать пятьдесят миллионов значений в таблицу на пять тыщ позиций" изначально звучит бредово. Какова же настоящая задача?
P. S. Цитата В общем нету типа данных bit, для которого sizeof(bit) = 0.125 байт. Поэтому я не выкупаю, как можно создать массив, в котором лярд элементов и на который отводится строго по 1 малому биту! Гм. Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет. |
Сообщ.
#14
,
|
|
|
Цитата AVA12 @ Какова же настоящая задача? быстрый поиск №тел. с применением ХТ на цепочках! все! Цитата AVA12 @ Программисты умудряются делать битовые массивы на ассемблере - хотя в ассемблере вообще никаких массивов нет. не путай Программистов и дилетантов) |
Сообщ.
#15
,
|
|
|
Цитата FasterHarder @ В Плюсах есть std::bitset<> и std::vector<bool>. Тебе какой? прогга у меня на "чистом" С89. ... А, эти еще есть, БИТОВЫЕ ПОЛЯ в структурах, но ведь там нельзя вроде получить массив бит. |