Scala - сворачивание значений, которые являются результатом взаимодействия объекта

Question

В Scala у меня есть список объектов, которые представляют точки и содержат значения x и y. Список описывает путь, который последовательно проходит через все эти точки. Мой вопрос: как использовать складывание в этом списке, чтобы найти общую длину пути? Или, может быть, есть даже лучший функционал или Scala способ сделать это?

Я придумал вот что:

def distance = (0 /: wps)(Waypoint.distance(_, _)) 

но, конечно, это совершенно неправильно, потому что distance возвращает Float, но принимает два Waypoint объекта.

UPDATE:

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

val distances = for(i <- 0 until wps.size) yield wps(i).distanceTo(wps(i + 1))
val distance = (0f /: distances)(_ + _)

Я чувствую, что это справедливое императивное / функциональное сочетание, которое является быстрым и также оставляет значения расстояний между каждой путевой точкой для дальнейших возможных ссылок, что также полезно в моем случае.

ОБНОВЛЕНИЕ 2: На самом деле, чтобы определить, что быстрее, мне придется выполнить тестирование всех предложенных решений для всех типов последовательностей.

Answer 1

Это должно работать.

(wps, wps drop 1).zipped.map(Waypoint.distance).sum

Answer 2

Не know, если здесь можно использовать сложение, но попробуйте следующее:

wps.sliding(2).map(segment => Waypoint.distance(segment(0), segment(1))).sum

wps.sliding(2) возвращает список всех последующих пар.Или, если вы предпочитаете сопоставление с образцом:

wps.sliding(2).collect{case start :: end :: Nil => Waypoint.distance(start, end)}.sum

Кстати, попробуйте определить:

def distanceTo(to: Waypoint)

непосредственно для класса Waypoint, а не для объекта-компаньона, поскольку он выглядит более объектно-ориентированным и позволитвам написать хороший DSL-подобный код:

point1.distanceTo(point2)

или даже:

point1 distanceTo point2

wps.sliding(2).collect{
  case start :: end :: Nil => start distanceTo end
}.sum

Answer 3

Если вы выполняете индексацию любого вида, который хотите использовать Vector, а не List:

scala> def timed(op: => Unit) = { val start = System.nanoTime; op; (System.nanoTime - start) / 1e9 }
timed: (op: => Unit)Double

scala> val l = List.fill(100000)(1)
scala> val v = Vector.fill(100000)(1)


scala> timed { var t = 0; for (i <- 0 until l.length - 1) yield t += l(i) + l(i + 1) }
res2: Double = 16.252194583

scala> timed { var t = 0; for (i <- 0 until v.length - 1) yield t += v(i) + v(i + 1) }
res3: Double = 0.047047654

ListBuffer предлагает быстрые добавления, он не предлагает быстрый произвольный доступ.

Answer 4

Ваш комментарий «слишком много функционала для вычислений в реальном времени, которые могут стать тяжелыми» делает это интересным. Сравнительный анализ и профилирование имеют решающее значение, поскольку вы не хотите писать кучу сложного в обслуживании кода для повышения производительности, а только для того, чтобы понять, что это не критично для производительности вашего приложения. Или, что еще хуже, выясните, что оптимизация производительности ухудшает вашу конкретную рабочую нагрузку.

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

Я бы очень немного изменил ответ отсутствующего фактора , чтобы позволить вам получить прирост производительности от параллельных коллекций . Тот факт, что простое добавление .par может дать вам огромный прирост производительности, демонстрирует способность придерживаться функционального программирования!

def distancePar(wps: collection.GenSeq[Waypoint]): Double = {
  val parwps = wps.par
  parwps.zip(parwps drop 1).map(Function.tupled(distance)).sum
}

Я предполагаю, что это будет работать лучше всего, если у вас есть несколько ядер для решения проблемы, а wps имеет тенденцию быть несколько длинным. Если у вас мало ядер или короткие пути, то параллелизм, вероятно, повредит больше, чем поможет.

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

def distanceImp(wps: collection.GenSeq[Waypoint]): Double = {
  if (wps.size <= 1) {
    0.0
  } else {
    var r = 0.0
    var here = wps.head
    var remaining = wps.tail

    while (!remaining.isEmpty) {
      r += distance(here, remaining.head)
      here = remaining.head
      remaining = remaining.tail
    }
    r
  }
}

Наконец, если вы ищете золотую середину между FP и императивом, вы можете попробовать рекурсию. Я не профилировал его, но я предполагаю, что это будет примерно эквивалентно императивному решению с точки зрения производительности.

def distanceRec(wps: collection.GenSeq[Waypoint]): Double = {
  @annotation.tailrec
  def helper(acc: Double, here: Waypoint, remaining: collection.GenSeq[Waypoint]): Double =
    if (remaining.isEmpty)
      acc
    else
      helper(acc + distance(here, remaining.head), remaining.head, remaining.tail)

  if (wps.size <= 1)
    0.0
  else
    helper(0.0, wps.head, wps.tail)
}