Как стать автором
Обновить

Комментарии 21

НЛО прилетело и опубликовало эту надпись здесь
Для хэширования ещё возможно использовать проекцию на какое-либо случайное направление. Просто считаете скалярное произведение со случайным вектором. Если расстояние между хэшами большое, то смысла проверять расстояние между точками уже нет. В многомерных пространствах это может оказаться удобней, чем способ с ячейками.
Позвольте, автор именно это и делает в первом хэше от nVidia, криво находя скалярное произведение с вектором (cellsize-1* 2xshift; cellsize-1* 2yshift; cellsize-1* 2zshift) с помощью битовых операций :)
Спасибо за статью. В чем, по вашему мнению, основное преимущество хеширования координат ячейки перед использованием банальных индексов? Из минусов обычных индексов я вижу только неудобность использования в операциях поиска, из-за необходимости указания в запросах количества сравнений == количеству размерностей. Однако, к примеру, я не вижу простого алгоритма выделения областей ячеек при использовании хэша. Может я не прав. И еще вопрос:

… есть несколько объектов и вам нужно узнать нет ли между ними столкновений. Простейшим решением будет посчитать расстояние от каждого объекта до всех остальных объектов

Вы не решали задачу поиска похожих объектов, но в случае, когда мерой похожести является не функция рассчитывающей евклидово расстояние между парой объектов, а некая функция ее замещающая?
Фишка хэшей в том, что они добавляют элемент вероятности в расчёты. Это один из недавних сдвигов парадигмы в алгоритмике и криптографии. С банальными индексами мы имеем стопроцентную точность. Запрос с помощью хэша может дать немного мусора с вероятностью, например, один процент, но прирост скорости будет троекратным. Благодаря тому, что мусора немного, мы его можем легко отсеять и конечный прирост скорости будет, например, двухкратный. Конечная выгода от хэшей зависит от конкретной ситуации: плотности объектов, частоты обновления, хеш-функции и т. п. Не везде оно нужно, но реализовать и проверить схему с хэшами достаточно просто. По второму вопросу ничем помочь не могу.
Добавил ещё один абзац в пост
Для анализа областей ячеек пространства, по-видимому, придётся перебрать все соседние ячейки, посчитать хэш для них и проанализировать объекты, попавшие в соответствующие клетки хэш-таблицы. При линейной хэш-функции можно и не считать, а сразу перейти к нужным клеткам по известным сдвигам. Возможно, будет полезно, что мы за один раз проверим соседей всех объектов с одним и тем же значением хэш-функции. Хотя, если нас интересуют соседи только одного объекта, польза превратится во вред (и нелинейная функция может оказаться лучше).

По второму вопросу — не можете привести пример? «Евклидово расстояние между парой объектов» — вообще непонятная вещь, если объекты не точки, и к «похожести» она отношения, вроде бы, не имеет. Или речь о расстоянии в пространстве параметров объектов?
Признаю. Мой второй вопрос не совсем в рамках этой статьи.
Если определенные параметры двух объектов выразить через некие коэффициенты, то мы можем значения этих коэффициентов принять за координаты объекта в N-мерном пространстве. Соответственно похожие объекты будут находиться рядом в одной ячейке (с одним хэшом) или в соседних ячейках. Это верно только в случае, когда определение «похожести» линейно для всех коэффициентов.
Все меняется когда расчет похожести не линеен. К примеру: объекты у которых разница в 1 по одному коэффициенту «намного более похожи», чем объекты у которых разница по другому коэффициенту составит 0,3.
Вот про эту нелинейность, которая выражена функций я и спрашивал.
Если значение функции (влияния параметра на метрику) не лежит в каком-нибудь отрезке [a,b] с достаточно малым b/a, то остаётся только вложить пространство параметров в какое-нибудь пространство большей размерности, где параметры уже будут более регулярными. Например, сравнивая направления векторов в пространстве, можно взять в качестве параметров «широту и долготу», но они будут нерегулярными — вблизи полюса или «линии смены дат» влияние долготы на метрику будет намного меньше, чем в других местах. Лучше слегка увеличить размерность и считать расстояния между точками на сфере (разность единичных векторов). А там и хэш-таблица поможет.
А почему бы результат «расчета похожести» не использовать как координату в одномерном пространстве?
Все, понял :)
Если «метрика похожести» действительно будет метрикой, т.е. удовлетворяет неравенству треугольника, то можно и так. Взять несколько объектов где-нибудь на разных краях конфигурационного пространства, в количестве, большем, чем число параметров, и для хеширования использовать расстояния от анализируемого объекта до них. Единственная сложность — как выбрать эти объекты.
В качестве дополнения, приведу ещё ссылку на K-d дерево, которое, также, можно использовать для поиска ближайших соседей.

Но при использовании деревьев, возникает несколько проблем:
  • как построить оптимальное дерево для данного расположения объектов в пространстве? (как вариант, в случае ray-tracing рендеринга, можно использовать Surface area heuristic)
  • и, соответственно — ресурсоёмкость процедуры построения и модификации (в случае очень динамичных сцен — речь идёт о полной перестройке дерева)

Таким образом, использование техники хэширования (и удачно подобранной хэш функции) позволяет обойти вышеперечисленные ограничения деревьев.
Да, тут вы правы, я у себя использовал деревья для объектов, большинство из которых не меняют своего положения.
Спасибо за интересную статью.

Хочу уточнить несколько нюансов.

Если разбивать пространство на ячейки одинакового размера, это значит, что в случае, если большинство объектов сцены попадут в одну ячейку — то, соответственно, будут иметь одинаковый хэш, что опять возвращает нас к квадратической сложности поиска ближайших соседей.

Если же выбрать ячейки очень маленького размера (для того чтобы уменьшить количество попаданий объектов в одну ячейку) — то столкнёмся с тем, что объекты большого размера, будут занимают много ячеек — в данном случае вычислительные ресурсы будут тратится на вычисление большого количества хэшей для одного объекта (а если больших объектов будет много?).

Таким образом, можно сделать вывод, что данная техника наиболее эффективна в тех случаях, когда все объекты сцены примерно одинакового размера, и распределены равномерно в пространстве.
Огромное спасибо, особенно за ссылку на такую замечательную хэш-функцию до которой я сам не додумался.
Что быстрее посчитать 2 * 3,14 или 2 * 3,1415926535897932384626433832795028841971…? Разумеется первое.

Почему? Какое значение здесь имеет длина десятичной записи числа?
Вы попробуйте в уме посчитать сначала первое, потом второе. Я привёл общечеловеческий пример, чтобы было понятнее о чём речь. Разумеется, на другой платформе вычислений может и не быть разницы в скорости.
Спасибо. Я почему-то решил, что вы говорили о машинных вычислениях.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории