函数式编程的效率

Question

给定一个整数数组和一个值，我试图找出如果它在数组中存在的话，它离两端的值有多近。从而创建一张地图。我试着用不可变的数据映射和函数式的方式来解决这个问题，但是从计算的角度看，它与我用命令式方式(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

注意:这是一个问题的一部分，我提交了一个竞赛和命令式代码被接受，而下一个给出的时间超过错误。

Answer 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)

我还不确定视图是否被折叠所迫，所以使用索引的循环可能更好。以前不是用水平滚动长线而不是包装吗？这样代码是不可读的。

Answer 2

首先，让我说，您使用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。

让我们从第一个开始，它更接近你所做的。我在这里努力不做任何改变，这只是一项练习。实际上，我可能会使用不可变的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是偶数还是奇数。contains测试也可以通过在更新中使用getOrElse来删除。

它还返回一个标准映射，而不是一个默认的映射。您可以在之后添加默认值。

另一种方法可能是索姆·斯奈特的解决方案，但我宁愿让它简单一点，因为在这个解决方案中，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
}

还请注意，在这两个示例中，我更喜欢防止不必要的键进入映射，而不是在之后删除它。这可能是一个错误的决定，但是在结束时更改代码以删除它是很简单的，所以我决定给您提供一个替代方案。

Answer 3

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