goryinyich's blog

By goryinyich, 8 years ago, In Russian,

Всегда думал, что задачи типа "дано 100....000 точек, для каждой найти ближайшую" - это олимпиадная блажь, на практике никому не нужная. Оказалось, что понадобилась, причем как раз на работе, причем в усложненном виде.


Задача такая. Дано порядка 10000 точек в N-мерном (N небольшое - не более 10) единичном кубике, для каждой нужно найти K (K < 100) ближайших. Строгих ограничений, понятно, нет, но хотелось бы, чтобы на обычном компьютере это укладывалось в несколько секунд.

Буду рад любым идеям как это можно решать хотя бы приближенно. Заранее спасибо за советы.

UPD: оптимизированное решение "в лоб" работает порядка минуты. Нужно ускорить его хотя бы в несколько десятков раз.

UPD^2: после прочтения комментариев и обдумывания, пришел к выводу, что оптимальным по "сложность написания/качество" будет следующий алгоритм: создаем N списков точек, отсортированных по различным измерениям, и перебираем для заданной только точки, входящие в 2К ближайших по какому-либо измерению.
 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it