Эффективный поиск ближайшего соседа в Scala

Я не уверен, что это полезно (или даже глупо), но я подумал об этом:

Вы используете функцию сортировки для сортировки ВСЕХ элементов в сетке, а затем выбираете первые k элементы. Если вы рассматриваете алгоритм сортировки, такой как рекурсивная сортировка слиянием, у вас будет что-то вроде этого:

1. Разделить коллекцию пополам
2. Рекурсия на обеих половинах
3. Объединить обе отсортированные половины

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

Таким образом, в худшем случае, когда k >= n (n - размер сетки), у вас все равно будет сложность только сортировки слиянием. O(n log n) Честно говоря, я не могу определить сложность этого решения относительно k. (слишком устал для этого в данный момент)

Вот пример реализации этого решения (оно определенно не оптимальное и не обобщенное):

def minK(seq: IndexedSeq[coord], x: coord, k: Int) = {

  val dist = (c: coord) => c.dist(x)

  def sort(seq: IndexedSeq[coord]): IndexedSeq[coord] = seq.size match {
    case 0 | 1 => seq
    case size => {
      val (left, right) = seq.splitAt(size / 2)
      merge(sort(left), sort(right))
    }
  }

  def merge(left: IndexedSeq[coord], right: IndexedSeq[coord]) = {

    val leftF = left.lift
    val rightF = right.lift

    val builder = IndexedSeq.newBuilder[coord]

    @tailrec
    def loop(leftIndex: Int = 0, rightIndex: Int = 0): Unit = {
      if (leftIndex + rightIndex < k) {
        (leftF(leftIndex), rightF(rightIndex)) match {
          case (Some(leftCoord), Some(rightCoord)) => {
            if (dist(leftCoord) < dist(rightCoord)) {
              builder += leftCoord
              loop(leftIndex + 1, rightIndex)
            } else {
              builder += rightCoord
              loop(leftIndex, rightIndex + 1)
            }
          }
          case (Some(leftCoord), None) => {
            builder += leftCoord
            loop(leftIndex + 1, rightIndex)
          }
          case (None, Some(rightCoord)) => {
            builder += rightCoord
            loop(leftIndex, rightIndex + 1)
          }
          case _ =>
        }
      }
    }

    loop()

    builder.result
  }

  sort(seq)
}

Профилируйте свой код, чтобы увидеть, что является дорогостоящим.

Ваш способ сортировки уже крайне неэффективен.

Не пересчитывайте расстояния все время. Это не бесплатно — скорее всего, ваша программа тратит 99% времени на вычисление расстояний (используйте профилировщик, чтобы узнать!)

Наконец, вы можете использовать структуры индексов. Для евклидова расстояния у вас, вероятно, самый большой выбор индексов для ускорения поиска ближайших соседей. Существует k-d-дерево, но я обнаружил, что R-дерево часто работает быстрее. Если вы хотите поиграть с ними, я рекомендую ELKI. Это Java-библиотека для интеллектуального анализа данных (поэтому ее должно быть легко использовать и из Scala), и она имеет огромный выбор индексных структур.

Это было довольно весело делать.

case class Coord(x: Double, y: Double) {
    def dist(c: Coord) = Math.sqrt(Math.pow(x - c.x, 2) + Math.pow(y - c.y, 2))
}
class CoordOrdering(x: Coord) extends Ordering[Coord] {
    def compare(a: Coord, b: Coord) = a.dist(x) compare b.dist(x)
}

def top[T](xs: Seq[T], n: Int)(implicit ord: Ordering[T]): Seq[T] = {
    // xs is an ordered sequence of n elements. insert returns xs with e inserted 
    // if it is less than anything currently in the sequence (and in that case, 
    // the last element is dropped) otherwise returns an unmodifed sequence

    def insert[T](xs: Seq[T], e: T)(implicit ord: Ordering[T]): Seq[T] = {
      val (l, r) = xs.span(x => ord.lt(x, e))
      (l ++ (e +: r)).take(n)
    }
    xs.drop(n).foldLeft(xs.take(n).sorted)(insert)
} 

Минимально проверено. Назовите это так:

val grid = (1 to 250000).map { _ => Coord(Math.random * 5, Math.random * 5) }
val x = Coord(Math.random * 5, Math.random * 5)
top(grid, 3)(new CoordOrdering(x)) 

РЕДАКТИРОВАТЬ: довольно легко расширить это, чтобы (предварительно) вычислить расстояния только один раз

val zippedGrid = grid map {_.dist(x)} zip grid  

object ZippedCoordOrdering extends Ordering[(Double, Coord)] {
   def compare(a:(Double, Coord), b:(Double, Coord)) = a._1 compare b._1
}

top(zippedGrid,3)(ZippedCoordOrdering).unzip._2

Вот алгоритм, использующий структуру данных R-дерева. Бесполезно для описанного небольшого набора данных, но хорошо масштабируется для большого количества объектов.

Используйте упорядоченный список, узлы которого представляют либо объекты, либо ограничивающие рамки R-дерева. Порядок является ближайшим первым, используя любую функцию расстояния, которую вы хотите. Поддерживайте порядок при вставке.

Инициализируйте список, вставив ограничивающие рамки в корневой узел R-дерева.

Чтобы получить следующий ближайший объект:

(1) Удалить первый элемент из списка.

(2) Если это объект, то ближайший.

(3) Если это ограничивающая рамка нелистового узла R-дерева, вставьте все ограничивающие рамки, представляющие дочерние элементы этого узла, в список на их надлежащих местах в соответствии с их расстоянием.

(4) Если это ограничивающая рамка листового узла R-дерева, вставьте объекты, которые являются дочерними элементами этого узла (объекты, а не их ограничивающие рамки) в соответствии с их расстоянием.

(5) Вернитесь к шагу (1).

Список останется довольно коротким. Впереди будут близлежащие объекты, которые нас интересуют, а более поздние узлы в списке будут прямоугольниками, представляющими наборы объектов, которые находятся дальше.

Это зависит от того, exact или approximation.

Несколько контрольных показателей, таких как http://www.slideshare.net/erikbern/approimate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup показывают, что аппроксимация является хорошим решением с точки зрения efficient.

Я написал ann4s, который представляет собой реализацию Annoy на Scala.

Annoy (Approximate Nearest Neighbours Oh Yeah) — это библиотека C++ с привязками Python для поиска точек в пространстве, близких к заданной точке запроса. Он также создает большие файловые структуры данных только для чтения, которые отображаются в памяти, чтобы многие процессы могли совместно использовать одни и те же данные.

Взгляните на этот репозиторий.