Текущее время: Вс, июл 27 2025, 23:38

Часовой пояс: UTC + 3 часа


Правила форума


ВНИМАНИЕ!

Вопросы по SAP Query и Quick View - сюда



Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Пт, мар 20 2015, 20:34 
Старший специалист
Старший специалист

Зарегистрирован:
Чт, окт 22 2009, 12:41
Сообщения: 473
Тут вдруг стало интересно: а какие хеш функции используются САПом при работе с хеш таблицами? И по каким параметрам они выбираются?
Вообще доступ по хешу считается довольно спорным из-за того, что все зависит от удачности выбора хеш функции для конкретного случая. И вроде как бинарный поиск - разумная альтернатива в общем случае.
Но в САПе я как-то все сталкивался с тем, что хеш таблицы быстрее сортированных. Это они так удачно функции выбирают или мне так просто везло?


Принять этот ответ
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Сб, мар 21 2015, 09:28 
Почетный гуру
Почетный гуру
Аватара пользователя

Зарегистрирован:
Пн, мар 28 2005, 15:38
Сообщения: 1257
weise написал(а):
Но в САПе я как-то все сталкивался с тем, что хеш таблицы быстрее сортированных. Это они так удачно функции выбирают или мне так просто везло?


Может быть вам стоит лучше изучить вопрос о самих алгоритмах, ассимптотических выражениях и оценки времени выполнения для различных алгоритмов? Вот, например, фундаментальный труд на эту тему, который обычно способствует просветлению: "Алгоритмы: построение и анализ " , авторы Томас Кормен, Чарльз Лейзерсон, Рональд Ривест и Клиффорд Штайн. Ну или всеми любимый Дональд Кнут и его "Искусство программирования".
Что значит "быстрее\медленнее"? На какой именно операции(вставка-удаление-изменение)? При каком размере?
Например: поиск в отсортированной таблице по binary serach оценивается как O( log2( n ) , а поиск в хэш-таблице O (1)

_________________
Там, где я рос, единственным развлечением было запоминать число «π».(С) Н. Стивенсон


Принять этот ответ
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Ср, мар 25 2015, 23:36 
Старший специалист
Старший специалист

Зарегистрирован:
Чт, окт 22 2009, 12:41
Сообщения: 473
Да, вроде бы изучал, правда, возможно не очень детально. Спасибо за книжку, постараюсь почитать.
Но не очень понимаю как это мне поможет в данном вопросе?
Разумеется на чтение - всё таки в подавляющем большинстве случаев таблица заполняется один раз, а потом много раз считываются данные. Как пример - лоакальный кеш. Быстрее/медленнее - время, которое требуется на считывание одной записи по ключу таблицы (а какие еще есть варианты?). Размеры разные =) В общем случае как я понимаю на объемах до 100 записей разница не существенна.

Да, я разумеется знаю про O-нотацию. Но на практике интересны не теоретические ассимптоты, а абсолютные значения. Нами любимый хеш-индекс по сути - двухмерный массив. Индекс первого измерения - результат применения хеш функции к ключу. Второй - список адресов совпавших записей. Если наша хеш функция - остаток от деления на 5 (т.е. все записи будут распределяться по 5 массивам), а всего записей 1000000, то понятно, что O(1) вроде как и не совсем от 1, скорее от n. Всё зависит от хеш функции. А вот как ее САП выбирает и есть вопрос :D Количество записей все-таки заранее не известно.


Принять этот ответ
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Чт, мар 26 2015, 01:30 
Почетный гуру
Почетный гуру
Аватара пользователя

Зарегистрирован:
Чт, окт 06 2005, 16:44
Сообщения: 3080
Откуда: Москва
weise написал(а):
Но в САПе я как-то все сталкивался с тем, что хеш таблицы быстрее сортированных. Это они так удачно функции выбирают или мне так просто везло?

На практике разницей во времени поиска в сортированных и хеш-таблицах для реальных задач можно пренебречь. Главное - не использовать поиск по несортированным таблицам.

_________________
С уважением,
Удав.


Принять этот ответ
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Чт, мар 26 2015, 08:42 
Почетный гуру
Почетный гуру
Аватара пользователя

Зарегистрирован:
Пн, мар 28 2005, 15:38
Сообщения: 1257
Удав написал(а):
На практике разницей во времени поиска в сортированных и хеш-таблицах для реальных задач можно пренебречь. Главное - не использовать поиск по несортированным таблицам.


Позвольте не согласиться. Пример из se30(Single Read: Sorted vs. hashed tables ) в моей системе показывает разницу в 20%(т.е. чтение из хэш-таблицы на 20% быстрее). При том, что там речь идет о чтении 250 раз из таблицы длинной 1000. В продуктивной задаче данных может быть и побольше, выигрыш будет аналогично - больше.
Другое дело, что всегда стоит подумать в зависимости от задачи в целом. Правильно построенный механизм перебора записей между собой (да ну хотя бы на примере из того же se30 в части Joining internal tables - использование параллельных курсоров - не смотря на всю свою банальность) может давать лучшую производительность даже на обычных таблицах, чем "наивный" алгоритм с использованием sorted\hashed таблиц

weise написал(а):
Да, я разумеется знаю про O-нотацию. Но на практике интересны не теоретические ассимптоты, а абсолютные значения... что O(1) вроде как и не совсем от 1, скорее от n


O(f(n)) - это не значит, что прям вот скорость\сложность алгоритма f(n) и все. а то, что скорость не превышает некоторой f(n) да еще и умноженной на некоторую константу. Т.е. есть некий порог, он точно не превышается, но до него может быть достаточно произвольное поведение.

_________________
Там, где я рос, единственным развлечением было запоминать число «π».(С) Н. Стивенсон


Принять этот ответ
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Чт, мар 26 2015, 12:12 
Почетный гуру
Почетный гуру
Аватара пользователя

Зарегистрирован:
Чт, окт 06 2005, 16:44
Сообщения: 3080
Откуда: Москва
Кодер написал(а):
Пример из se30(Single Read: Sorted vs. hashed tables ) в моей системе показывает разницу в 20%(т.е. чтение из хэш-таблицы на 20% быстрее). При том, что там речь идет о чтении 250 раз из таблицы длинной 1000. В продуктивной задаче данных может быть и побольше, выигрыш будет аналогично - больше.

Я имел в виду, что даже если разница будет 20%, то в абсолютном времени выполнения программы это будут секунды и единицы процентов в лучшем случае.
Как пример - в отчете MM по остаткам (с определением времени последнего прихода для остатка) идет куча чтений внутренних таблиц (45 секунд) - 2,4% от общего времени выполнения программы :wink:

_________________
С уважением,
Удав.


Принять этот ответ
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Какие хеш функции используются в хеш таблицах
СообщениеДобавлено: Чт, мар 26 2015, 15:42 
Почетный гуру
Почетный гуру
Аватара пользователя

Зарегистрирован:
Чт, сен 09 2004, 07:32
Сообщения: 777
Откуда: Москва
Пол: Мужской
Вот здесь народ много и долго спорил о "сферическом коне в вакууме"... :D
http://sapland.ru/blogs/obermann/?post=13135

_________________
"Прежде чем сделать что-то, подумай, к чему это может привести..."


Принять этот ответ
Вернуться к началу
 Профиль Отправить email  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: Google [Bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB