ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / "Плотный" хэш. (Задачка.)
19 сообщений из 19, страница 1 из 1
"Плотный" хэш. (Задачка.)
    #33563758
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Задан (статический) словарь. Будем считать для простоты, что он представляет собой N различных чисел. (Соответственно, мы знаем Min() и Max() .)

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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