Блог

#python #algorithm #computational-geometry #in-memory-database #computation-theory

#python #алгоритм #вычислительная геометрия #в памяти-база данных #теория вычислений

Вопрос:

 X1 = [x1_1, ..., x1_100]
X2 = [x2_1, ..., x2_100]
...
X1000000 = [x1000000_1, ..., x1000000_100]
  

 Y = [y1, ..., y100]
  

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

1. Если у вас есть только один вектор, разве вы не можете просто написать векторизованную функцию numpy для вычисления евклидова расстояния, а затем вызвать np.min() ? Не думайте, что это происходит быстрее, чем это

2. @Джефф, мне нужно извлечь каждый вектор из базы данных и выполнить np.min() 10 миллионов раз? Нет ли способа сделать это быстрее?

3. Используйте K-D дерево для поиска ближайшего соседа в k измерении, которое как временная сложность logn для поиска

4. Загрузите все ваши x векторы как 2D numpy. Создайте np.vectorize() функцию, которая находит евклидово расстояние от вашего сингла y . Вызовите свою векторизованную функцию для вашего x 2D-массива, в результате чего получится 1D results -массив. Наконец, вызовите np.min(results) . Просто нужно вызвать его один раз.

5. Не используйте стандартное kD-дерево. Из-за проблемы «проклятия размерности» это будет медленнее, чем исчерпывающий поиск! kD-деревья, как известно, неэффективны для больших размеров и, конечно же, не O (Log N). Рассмотрите возможность использования стратегии best-bin-first. en.wikipedia.org/wiki /. …

Ответ №1:

 def find_CD(X,y):
  return ​return​ spatial.distance.euclidean(X,y)
  

 listt=[]
vic=[x1,x2,.....,X1000000]
for i in range(len(vic)):
 listt.append(find_CD(vic[i],y)
  

 listt.index(min(listt))
  

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

1. Спасибо! Но я думаю, что выполнение евклидова расстояния в 10 миллионов раз не так эффективно. Мне нравится решение с K-D деревом, предложенное @Girish Dattatray Hegde.

2. @corvax: обязательно реализуйте как исчерпывающий поиск, так и поиск по kD-дереву и сравните их (см. Мое Замечание выше).

3. @corvax Как упоминалось другими, при 100 измерениях дерево KD в принципе бесполезно. KD-дерево работает лучше всего, когда N >> (much greater than) 2^D , где D — количество измерений. С 10 миллионами точек D должно быть значительно меньше 23 , чтобы оно того стоило, иначе дерево будет очень «мелким», и вы не получите от этого пользы.