给定一个整数和值的数组，如果数组中存在该值，我试图从两端找出该值的接近程度。从而创建地图。我尝试使用不可变的数据映射和函数方式来解决它，但从计算的角度来看，与用命令式方式(java方式)编写相比，它的效率非常低。我认为这是由于我对编码的功能风格的不完全理解，而不是风格之间固有的差异。
val typeSum = 8
val data = List(2,3,4,5,2,3)
val dogTimes:scala.collection.mutable.Map[Int,Int] = scala.collection.mutable.Map() withDefaultValue(-1);
for ( x <- 1 to (data.length)/2 ){
if (dogTimes(data(x-1)) > x || dogTimes(data(x-1)) < 0) dogTimes(data(x-1)) = x;
}
for( x <- (data.length/2 + 1) to data.length ){
if (dogTimes(data(x-1)) > (data.length - x)|| dogTimes(data(x-1)) < 0)
dogTimes(data(x-1)) = data.length - x+1;
}
if (typeSum%2 ==0) dogTimes(typeSum/2) = -1
这是我可以用函数风格编写的代码，比上面的代码慢。如何改进以下代码以提高效率？
val tempDogTimes = data.zipWithIndex groupBy(_._1) mapValues(w =>
List(w.head._2+1,data.length - w.last._2).min) withDefaultValue(-1)
val dogTimes = collection.mutable.Map[Int,Double]() ++= tempDogTimes
if (typeSum%2 ==0) dogTimes(typeSum/2) = -1
注意：这是我为比赛提交的一个问题的一部分，命令式代码被接受了，而下一个给出的时间超过了错误。
让我擦去眼睛里的睡眠。你想从列表的两端遍历，记录你第一次看到每个元素的时间，对吧？
scala> val data = List(2,3,4,5,2,3)
data: List[Int] = List(2, 3, 4, 5, 2, 3)
scala> val is = ((data take (data.size / 2)), (data drop (data.size / 2)).reverse).zipped
is: scala.runtime.Tuple2Zipped[Int,List[Int],Int,List[Int]] = scala.runtime.Tuple2Zipped@72cf531c
scala> .toList
res0: List[(Int, Int)] = List((2,3), (3,2), (4,5))
scala> ((Map.empty[Int,Int], data.to[Set], 0) /: is) { case ((m, n, i), (x, y)) =>
| if (n.isEmpty) (m, n, i+1)
| else (
| m ++ List(if (m contains x) None else Some(x -> i), if (m contains y) None else Some(y -> i)).flatten,
| n -- Set(x,y),
| i + 1
| )}
res1: (scala.collection.immutable.Map[Int,Int], Set[Int], Int) = (Map(2 -> 0, 3 -> 0, 4 -> 2, 5 -> 2),Set(),3)
scala> ._1
res2: scala.collection.immutable.Map[Int,Int] = Map(2 -> 0, 3 -> 0, 4 -> 2, 5 -> 2)
使用Vector和视图来索引两半会更好。构建一组元素是无关的，但如果您已经了解该域，则会很方便。
另一个摆动：
scala> val data = List(2,3,4,5,2,3).to[Seq]
data: Seq[Int] = Vector(2, 3, 4, 5, 2, 3)
scala> val half = data.size / 2
half: Int = 3
scala> val vs = (data.view take half, (data.view drop half).reverse).zipped
vs: scala.runtime.Tuple2Zipped[Int,scala.collection.SeqView[Int,Seq[Int]],Int,scala.collection.SeqView[Int,Seq[Int]]] = scala.runtime.Tuple2Zipped@72cf531c
scala> import collection.mutable
import collection.mutable
scala> val x = 4 // some key to exclude
x: Int = 4
scala> ((mutable.Map.empty[Int,Int].withDefaultValue(Int.MaxValue), 0) /: vs) {
| case ((m, i), (x, y)) => m(x) = m(x) min i; m(y) = m(y) min i; (m, i+1) }
res4: (scala.collection.mutable.Map[Int,Int], Int) = (Map(2 -> 0, 5 -> 2, 4 -> 2, 3 -> 0),3)
scala> ._1.filter { case (k, v) => k != x }.toMap
res5: scala.collection.immutable.Map[Int,Int] = Map(2 -> 0, 5 -> 2, 3 -> 0)
我还不确定视图是否是折叠所迫，所以带索引的循环可能会更好。SO不是习惯于水平滚动长行而不是换行吗？这样代码就不可读了。
首先，让我说，在可变版本中使用List的方式非常糟糕。List在索引访问方面的性能很差，您经常使用索引访问。对于索引访问，请改用Vector。或者Array，因为它无论如何都是可变的。
在不可变版本上，您还可以在每次迭代中使用length，即List的O(n)。只需在循环外调用length一次并保存即可帮助提高性能。你也可以这样做：
List(w.head._2+1,data.length - w.last._2).min
与简单的相比有点慢
(w.head._2+1) min (data.length - w.last._2)
当然，您应该将数据结构更改为Vector，或者将data.length替换为只分配一次的内容。
现在，我可以看到两种方法。一种是像你一样在地图上走两条路并获得最小值，另一种是只像som snytt那样走一次。首先，您确实需要将类型更改为Vector。第二个将适用于List。
让我们从第一个开始，它更接近你所做的。我在这里努力做到一点都不可变，只是作为一种练习。在实践中，我可能会使用不可变Map的var，而不是递归。
def dogTimes(data: IndexedSeq[Int], typeSum: Int): Map[Int, Int] = {
import scala.annotation.tailrec
val unwantedKey = typeSum / 2
val end = data.length
val halfway = end / 2
@tailrec
def forward(result: Map[Int, Int], i: Int): Map[Int, Int] = {
if (i > halfway) result
else if (data(i) == unwantedKey) forward(result, i + 1)
else if (result contains data(i)) forward(result, i + 1)
else forward(result updated (data(i), i + 1), i + 1)
}
@tailrec
def backward(result: Map[Int, Int], i: Int): Map[Int, Int] = {
println(s"$i ${data(i)} $result")
if (i < halfway) result
else if (data(i) == unwantedKey) backward(result, i - 1)
else if (result contains data(i)) backward(result updated (data(i), result(data(i)) min (end - i)), i - 1)
else backward(result updated (data(i), end - i), i - 1)
}
// forward has to be computed first
val fwd = forward(Map.empty[Int, Int], 0)
val bwd = backward(fwd, end - 1)
bwd
}
这几乎是可变代码的一个功能版本——它很冗长，并且没有真正使用任何收集方法来帮助工作。它也可以简化一点——例如，data.length % 2是不必要的，因为无论data.length是偶数还是奇数，它内部的代码都会一直工作。在更新中使用getOrElse也可以删除contains测试。
它还返回一个标准贴图，而不是带有默认贴图的贴图。之后可以添加默认值。
另一种方法或多或少是somsnytt的解决方案，但我宁愿让它简单一点，因为min在该解决方案中不是必需的。在这里，我接受Seq，它将适用于List。
def dogTimes(data: Seq[Int], typeSum: Int): Map[Int, Int] = {
import scala.annotation.tailrec
val unwantedKey = typeSum / 2
val half = data.length / 2 + 1
val vs = (data.view take half zip data.view.reverse).zipWithIndex
val result = vs.foldLeft(Map.empty[Int, Int]) {
case (map, ((x, y), i)) =>
val m1 = if (map.contains(x) || x == unwantedKey) map else map.updated(x, i + 1)
if (m1.contains(y) || y == unwantedKey) m1 else m1.updated(y, i + 1)
}
result
}
我保留了一些snytt的view，但我怀疑它在反向上的性能对于List来说会非常糟糕。Vector应该可以，但我认为删除第二个view调用应该会使List更快。
请注意，我在这段代码中没有使用min，原因很简单：由于我同时从最低索引到最高索引进行正向和反向移动，所以无论何时键在映射中，我都知道它的索引必须低于或等于当前索引。
还要注意，我选择了half + 1——这确保了我将处理奇数大小列表中的中间元素。我不会在反转之前丢弃元素，因为zip总是选择最小的尺寸。
如果我们决定需要索引seqs，以下可能会更快：
def dogTimes(data: IndexedSeq[Int], typeSum: Int): Map[Int, Int] = {
import scala.annotation.tailrec
val unwantedKey = typeSum / 2
val end = data.length
val halfway = end / 2
val result = (0 to halfway).foldLeft(Map.empty[Int, Int]) {
case (map, i) =>
val x = data(i)
val y = data(end - i - 1)
val m1 = if (map.contains(x) || x == unwantedKey) map else map.updated(x, i + 1)
if (m1.contains(y) || y == unwantedKey) m1 else m1.updated(y, i + 1)
}
result
}
还要注意，在这两个例子中，我更喜欢防止不需要的密钥进入映射，而不是在之后将其删除。这可能是一个糟糕的决定，但更改代码以在最后删除它是微不足道的，所以我决定向您提供另一种选择。
Scala有一种将列表项与其索引配对的优雅方法：zipWithIndex。当你把列表分成两半时，你可以做出两个匹配的情况，第一个条件是：
val typeSum = 8
val data = List(2, 3, 4, 5, 2, 3)
val dogTimes: scala.collection.mutable.Map[Int, Int] = scala.collection.mutable.Map() withDefaultValue (-1)
data.zipWithIndex foreach {
case (value, index) if (index < data.length / 2) => {
if (dogTimes(value) > index + 1 || dogTimes(value) < 0) {
dogTimes(value) = index + 1
}
}
case (value, index) => {
if (dogTimes(value) > (data.length - index) || dogTimes(value) < 0) {
dogTimes(value) = data.length - index
}
}
}
if (typeSum % 2 == 0) dogTimes(typeSum / 2) = -1