Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 21
Для хэширования ещё возможно использовать проекцию на какое-либо случайное направление. Просто считаете скалярное произведение со случайным вектором. Если расстояние между хэшами большое, то смысла проверять расстояние между точками уже нет. В многомерных пространствах это может оказаться удобней, чем способ с ячейками.
Спасибо за статью. В чем, по вашему мнению, основное преимущество хеширования координат ячейки перед использованием банальных индексов? Из минусов обычных индексов я вижу только неудобность использования в операциях поиска, из-за необходимости указания в запросах количества сравнений == количеству размерностей. Однако, к примеру, я не вижу простого алгоритма выделения областей ячеек при использовании хэша. Может я не прав. И еще вопрос:
Вы не решали задачу поиска похожих объектов, но в случае, когда мерой похожести является не функция рассчитывающей евклидово расстояние между парой объектов, а некая функция ее замещающая?
… есть несколько объектов и вам нужно узнать нет ли между ними столкновений. Простейшим решением будет посчитать расстояние от каждого объекта до всех остальных объектов
Вы не решали задачу поиска похожих объектов, но в случае, когда мерой похожести является не функция рассчитывающей евклидово расстояние между парой объектов, а некая функция ее замещающая?
Фишка хэшей в том, что они добавляют элемент вероятности в расчёты. Это один из недавних сдвигов парадигмы в алгоритмике и криптографии. С банальными индексами мы имеем стопроцентную точность. Запрос с помощью хэша может дать немного мусора с вероятностью, например, один процент, но прирост скорости будет троекратным. Благодаря тому, что мусора немного, мы его можем легко отсеять и конечный прирост скорости будет, например, двухкратный. Конечная выгода от хэшей зависит от конкретной ситуации: плотности объектов, частоты обновления, хеш-функции и т. п. Не везде оно нужно, но реализовать и проверить схему с хэшами достаточно просто. По второму вопросу ничем помочь не могу.
Для анализа областей ячеек пространства, по-видимому, придётся перебрать все соседние ячейки, посчитать хэш для них и проанализировать объекты, попавшие в соответствующие клетки хэш-таблицы. При линейной хэш-функции можно и не считать, а сразу перейти к нужным клеткам по известным сдвигам. Возможно, будет полезно, что мы за один раз проверим соседей всех объектов с одним и тем же значением хэш-функции. Хотя, если нас интересуют соседи только одного объекта, польза превратится во вред (и нелинейная функция может оказаться лучше).
По второму вопросу — не можете привести пример? «Евклидово расстояние между парой объектов» — вообще непонятная вещь, если объекты не точки, и к «похожести» она отношения, вроде бы, не имеет. Или речь о расстоянии в пространстве параметров объектов?
По второму вопросу — не можете привести пример? «Евклидово расстояние между парой объектов» — вообще непонятная вещь, если объекты не точки, и к «похожести» она отношения, вроде бы, не имеет. Или речь о расстоянии в пространстве параметров объектов?
Признаю. Мой второй вопрос не совсем в рамках этой статьи.
Если определенные параметры двух объектов выразить через некие коэффициенты, то мы можем значения этих коэффициентов принять за координаты объекта в N-мерном пространстве. Соответственно похожие объекты будут находиться рядом в одной ячейке (с одним хэшом) или в соседних ячейках. Это верно только в случае, когда определение «похожести» линейно для всех коэффициентов.
Все меняется когда расчет похожести не линеен. К примеру: объекты у которых разница в 1 по одному коэффициенту «намного более похожи», чем объекты у которых разница по другому коэффициенту составит 0,3.
Вот про эту нелинейность, которая выражена функций я и спрашивал.
Если определенные параметры двух объектов выразить через некие коэффициенты, то мы можем значения этих коэффициентов принять за координаты объекта в N-мерном пространстве. Соответственно похожие объекты будут находиться рядом в одной ячейке (с одним хэшом) или в соседних ячейках. Это верно только в случае, когда определение «похожести» линейно для всех коэффициентов.
Все меняется когда расчет похожести не линеен. К примеру: объекты у которых разница в 1 по одному коэффициенту «намного более похожи», чем объекты у которых разница по другому коэффициенту составит 0,3.
Вот про эту нелинейность, которая выражена функций я и спрашивал.
Если значение функции (влияния параметра на метрику) не лежит в каком-нибудь отрезке [a,b] с достаточно малым b/a, то остаётся только вложить пространство параметров в какое-нибудь пространство большей размерности, где параметры уже будут более регулярными. Например, сравнивая направления векторов в пространстве, можно взять в качестве параметров «широту и долготу», но они будут нерегулярными — вблизи полюса или «линии смены дат» влияние долготы на метрику будет намного меньше, чем в других местах. Лучше слегка увеличить размерность и считать расстояния между точками на сфере (разность единичных векторов). А там и хэш-таблица поможет.
А почему бы результат «расчета похожести» не использовать как координату в одномерном пространстве?
Все, понял :)
Если «метрика похожести» действительно будет метрикой, т.е. удовлетворяет неравенству треугольника, то можно и так. Взять несколько объектов где-нибудь на разных краях конфигурационного пространства, в количестве, большем, чем число параметров, и для хеширования использовать расстояния от анализируемого объекта до них. Единственная сложность — как выбрать эти объекты.
Если я правильно понял задачу, то можно в данном случае использовать r-дерево
ru.wikipedia.org/wiki/R-дерево
ru.wikipedia.org/wiki/R-дерево
В качестве дополнения, приведу ещё ссылку на K-d дерево, которое, также, можно использовать для поиска ближайших соседей.
Но при использовании деревьев, возникает несколько проблем:
Таким образом, использование техники хэширования (и удачно подобранной хэш функции) позволяет обойти вышеперечисленные ограничения деревьев.
Но при использовании деревьев, возникает несколько проблем:
- как построить оптимальное дерево для данного расположения объектов в пространстве? (как вариант, в случае ray-tracing рендеринга, можно использовать Surface area heuristic)
- и, соответственно — ресурсоёмкость процедуры построения и модификации (в случае очень динамичных сцен — речь идёт о полной перестройке дерева)
Таким образом, использование техники хэширования (и удачно подобранной хэш функции) позволяет обойти вышеперечисленные ограничения деревьев.
Спасибо за интересную статью.
Хочу уточнить несколько нюансов.
Если разбивать пространство на ячейки одинакового размера, это значит, что в случае, если большинство объектов сцены попадут в одну ячейку — то, соответственно, будут иметь одинаковый хэш, что опять возвращает нас к квадратической сложности поиска ближайших соседей.
Если же выбрать ячейки очень маленького размера (для того чтобы уменьшить количество попаданий объектов в одну ячейку) — то столкнёмся с тем, что объекты большого размера, будут занимают много ячеек — в данном случае вычислительные ресурсы будут тратится на вычисление большого количества хэшей для одного объекта (а если больших объектов будет много?).
Таким образом, можно сделать вывод, что данная техника наиболее эффективна в тех случаях, когда все объекты сцены примерно одинакового размера, и распределены равномерно в пространстве.
Хочу уточнить несколько нюансов.
Если разбивать пространство на ячейки одинакового размера, это значит, что в случае, если большинство объектов сцены попадут в одну ячейку — то, соответственно, будут иметь одинаковый хэш, что опять возвращает нас к квадратической сложности поиска ближайших соседей.
Если же выбрать ячейки очень маленького размера (для того чтобы уменьшить количество попаданий объектов в одну ячейку) — то столкнёмся с тем, что объекты большого размера, будут занимают много ячеек — в данном случае вычислительные ресурсы будут тратится на вычисление большого количества хэшей для одного объекта (а если больших объектов будет много?).
Таким образом, можно сделать вывод, что данная техника наиболее эффективна в тех случаях, когда все объекты сцены примерно одинакового размера, и распределены равномерно в пространстве.
Да, всё верно, если в разных местах нужна разная детализация, то лучше выбрать что-нибудь вроде Octree.
Эх, промазал
Эх, промазал
Огромное спасибо, особенно за ссылку на такую замечательную хэш-функцию до которой я сам не додумался.
Что быстрее посчитать 2 * 3,14 или 2 * 3,1415926535897932384626433832795028841971…? Разумеется первое.
Почему? Какое значение здесь имеет длина десятичной записи числа?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Spatial hashing для самых маленьких