斯卡拉 - 折叠对象交互产生的值

在斯卡拉我有一个对象的列表，代表点，并包含x和y值。该列表描述了顺序贯穿所有这些点的路径。我的问题是如何在列表上使用折叠来查找路径的总长度？或者，甚至有更好的功能或斯卡拉方式来做到这一点？斯卡拉 - 折叠对象交互产生的值

我已经想出了这样的：

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

但ofcourse这是完全错误的，因为distance回报Float，但接受两个Waypoint对象。

UPDATE：

感谢提出的解决方案！它们确实很有趣，但我认为这对实时计算功能来说太多了，可能会变得很沉重。到目前为止，我已经与这些线就出来了：

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

我觉得这是一个公平的当务之急/功能搭配，既快速，也使各航点为进一步可能的基准之间的距离值，这也是一个benifit在我的情况。实际上，要确定什么更快，我将不得不对所有类型的序列提出所有解决方案的基准。

来源

2012-02-17 noncom

回复：您的更新没有任何必要，它只是功能性的，但可能比'zipped.map'解决方案更昂贵。 – missingfaktor 2012-02-17 10:18:58

注意'wps（i）'，它可能对某些序列具有'O（n）'复杂性，最终会以'O（n^2）'最终的复杂性结束。 – 2012-02-17 10:21:59

你是对的。选择序列类型时，我应该更加小心。在讨论这个问题时，我已经切换到了可变缓冲区类型，但是我将不得不做一些可能的序列类型和各种建议解决方案的基准。那将是一次很好的体验！ – noncom 2012-02-17 10:26:20

这应该起作用。

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

来源

2012-02-17 09:53:26 missingfaktor

为什么不简单地'（wps zip wps.tail）'？此外，看起来像'Waypoint.distance'需要两个参数，而不是一个元组，所以你需要：'map（Function.tupled（Waypoint.distance））' – 2012-02-17 09:56:56

@TomaszNurkiewicz，'（wps zip wps.tail）'会抛出一个空列表异常。 – missingfaktor 2012-02-17 09:58:11

@TomaszNurkiewicz和'Tuple2 #Zipped＃map'不需要tupled函数。 – missingfaktor 2012-02-17 09:59:13

不要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

BTW考虑定义：

def distanceTo(to: Waypoint)

上Waypoint类直接，而不是同伴的对象，因为它看起来更多，可以让你写得真好DSL-面向对象类似的代码：

point1.distanceTo(point2)

甚至：

point1 distanceTo point2 

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

来源

2012-02-17 09:48:26

'sum'是'fold'的一个特殊应用。 – ziggystar 2012-02-17 09:49:45

@ziggystar：true，但我使用'sum'来计算已计算距离的总和。我不知道如何使用'sum' /'foldLeft'而没有中间的'sliding' /'map'。 – 2012-02-17 09:52:08

当然，你仍然需要滑动。你可以使用'foldLeft'并保持折叠状态的最后一个点。虽然'滑动'看起来更好，我怀疑（但可能效率较低）。 – ziggystar 2012-02-17 09:53:44

您的评论“太多的功能为实时计算可能成为重”，使这个有趣的。基准测试和分析是至关重要的，因为您不想为了性能而编写大量难以维护的代码，只是发现它并不是应用程序中性能至关重要的部分！或者，更糟的是，发现你的性能优化会让你的特定工作负载变得更糟。

性能最佳的实现将取决于您的具体情况（路径有多长？系统上有多少个内核？）但我认为混合使用命令式和功能性方法可能会给您带来最糟糕的两个世界。如果你不小心，你可能会失去可读性和性能！

我会稍微修改missingfaktor's answer以使您从parallel collections获得性能提升。简单地添加.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) 
}

来源

2012-02-17 17:07:03 leedm777

如果你正在做你想要使用矢量任何类型的索引，就不一一列举：

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提供快速的附加，它不提供快速随机访问。

来源

2012-02-19 08:56:54

斯卡拉 - 折叠对象交互产生的值

回答

相关问题