斯卡拉 - 摺疊對象交互產生的值

在斯卡拉我有一個對象的列表，代表點，幷包含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

斯卡拉 - 摺疊對象交互產生的值

回答

相關問題