Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / "Плотный" хэш. (Задачка.) / 19 сообщений из 19, страница 1 из 1
24.02.2006, 14:01
    #33563758
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Задан (статический) словарь. Будем считать для простоты, что он представляет собой N различных чисел. (Соответственно, мы знаем Min() и Max() .)

Нужно "построить" как можно более компактную хэш функцию (алгоритм), отображающую этот "словарь" в множество целых чисел 1..N.

Видно, что отображение должно быть взаимно однозначное, но процедурно реализовать ОБРАТНОЕ преобразование я (пока) не прошу.

Видно также, что речь идет не просто о хэше, а - о "плотном" хэше!
_________________________

Если как построить такой хэш - не понятно, тогда просьба высказать соображения хотя бы о том, какова - теоретически - может быть минимальная длина "программы", реализующей такой алгоритм?

Предполагается, что эта минимальная длина окажется существенно меньше такой, которая позволяет "уместить" внутри алгоритма целиком весь исходный словарь!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.02.2006, 01:30
    #33564395
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXSЗадан (статический) словарь. Будем считать для простоты, что он представляет собой N различных чисел. (Соответственно, мы знаем Min() и Max() .)

Нужно "построить" как можно более компактную хэш функцию (алгоритм), отображающую этот "словарь" в множество целых чисел 1..N.
Отсортировать по возрастанию и обращаться по номеру элемента.
Э?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.02.2006, 13:12
    #33564557
maXmo
maXmo
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXSПредполагается, что эта минимальная длина окажется существенно меньше такой, которая позволяет "уместить" внутри алгоритма целиком весь исходный словарь!бугога, вынести словарь во внешний файл. Можно ещё исследовать словарь на предмет неких закономерностей его структуры. Если словарь плотный, можно запомнить промежутки между словами вместо самих слов.
------------------
- А как в Интеpнете pаботать? - Сначала нужно узнать, что вам нужно rtfm
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.02.2006, 13:19
    #33565588
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Видно, что отображение должно быть взаимно однозначное, но процедурно реализовать ОБРАТНОЕ преобразование я (пока) не прошу.


Хэш-функция по определению не может быть взаимно однозначным отображением.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.02.2006, 20:06
    #33566382
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
MasterZiv , рассмотрите любую хэш-функцию, заданную на множестве из ОДНОГО элемента. Как оно может быть там НЕ взаимно однозначной?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.02.2006, 21:42
    #33566463
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
На множестве из одного элемента бессмысленно иметь хэш-функцию.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.02.2006, 10:26
    #33566997
aleks2
aleks2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
((n-Min)*N) div (Max-Min)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.03.2006, 15:58
    #33581912
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
MasterZivНа множестве из одного элемента бессмысленно иметь хэш-функцию.
- а на множестве из двух элементов? А на множестве из трех элементов?А на множестве из N+1 элементов?

("Парадокс кучи" - знакома такая тема?)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2006, 19:17
    #33585235
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
А я отвечу. Мощность отображаемого множества должна быть как минимум на несколько порядков больше мощности целевого.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2006, 21:20
    #33585402
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Кажется, я где-то что-то недоучил:знаю, что у функции есть область определения и есть множество значений ... а что такое "целевое" множество - не знаю.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2006, 08:06
    #33585776
aleks2
aleks2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXSКажется, я где-то что-то недоучил:знаю, что у функции есть область определения и есть множество значений ... а что такое "целевое" множество - не знаю.

Хэш функции отображают (обычно) множество БОЛЬШЕЙ мощности на множество меньшей мощности, т.е. являются по-определению НЕОБРАТИМЫМИ функциями.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2006, 15:54
    #33587206
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Вы понимате разницу между "обычно" и КОНКРЕТНОЙ задачей?

Перые три слова этой ветки: "Задан ( статический ) словарь" !
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2006, 19:50
    #33587675
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXSВы понимате разницу между "обычно" и КОНКРЕТНОЙ задачей?
Перые три слова этой ветки: "Задан ( статический ) словарь" !

Иван FXSMasterZiv, рассмотрите любую хэш-функцию, заданную на множестве из ОДНОГО элемента. Как оно может быть там НЕ взаимно однозначной? MasterZivНа множестве из одного элемента бессмысленно иметь хэш-функцию.
- а на множестве из двух элементов? А на множестве из трех элементов?А на множестве из N+1 элементов?
("Парадокс кучи" - знакома такая тема?)

А сколько слов с словаре? Одно? Две? Три?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2006, 20:36
    #33587705
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Два, три, двести двадцать три ... тысячи - какая разница - с точки зрения "мощности множества"? Оно все равно остается (является) КОНЕЧНЫМ!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.03.2006, 12:34
    #33588049
aleks2
aleks2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXSВы понимате разницу между "обычно" и КОНКРЕТНОЙ задачей?

Перые три слова этой ветки: "Задан ( статический ) словарь" !

Ну чего ты пускаешь пену? Ежели вам надоть однозначное соответствие, то вам уже советовали:
1) Сортируем словарь по возрастанию (убыванию) - QuickSort тебе в руки.
2) Хеш есть номер элемента в сортированном массиве - поиск методом деления отрезка пополам тебе в руки.
-------------
ужо плотнее и однозначнее не выйдет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.03.2006, 15:14
    #33588194
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
aleks2ужо плотнее и однозначнее не выйдет.
- пожалуй ... а как насчет "как можно более компактную"?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.03.2006, 10:08
    #33595640
aleks2
aleks2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXS aleks2ужо плотнее и однозначнее не выйдет.
- пожалуй ... а как насчет "как можно более компактную"?

Огласите критерии компактности, ибо QuikSort это ~20 строк кода и ПоискДелениемОтрезкаПополам - ~10 строк кода.
---------------------------------------
Чего вам еще?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.03.2006, 12:07
    #33596089
Иван FXS
Иван FXS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Компактность не кода, а "инструмента". С точки зрения оперативно памяти, например.

Вы предлагаете решения, требующие хранения "явного" словаря. То есть размер "инструмента" - не менее размера словаря!

Я-то пытаюсь обсуждать "хэши", то есть решения без "явно хранимого" словаря. Хотя - явно ЗАВИСИМЫЕ от конкретного словаря, поскольку напираю на то, что он "задан" ("фиксированый")!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.03.2006, 13:13
    #33596384
aleks2
aleks2
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
"Плотный" хэш. (Задачка.)
Иван FXSКомпактность не кода, а "инструмента". С точки зрения оперативно памяти, например.

Вы предлагаете решения, требующие хранения "явного" словаря. То есть размер "инструмента" - не менее размера словаря!

Я-то пытаюсь обсуждать "хэши", то есть решения без "явно хранимого" словаря. Хотя - явно ЗАВИСИМЫЕ от конкретного словаря, поскольку напираю на то, что он "задан" ("фиксированый")!

Ты не обсуждаешь - а толчешь воду в ступе (это конечно мое частное мнение).
------------------------
Компактность по вашим критериям не снизить ниже массива из N чисел.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / "Плотный" хэш. (Задачка.) / 19 сообщений из 19, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]