计算所有值，或者如果找到，则停止并仅返回最佳值

Question

我有一个项目列表，并为每个项目计算一个值。计算这个值有点计算密集，所以我想尽可能地将其最小化。

我需要实现的算法是：

1. 我有一个值X

2. 对于每个项目

   a。如果它是<0完全忽略它

   b。如果（值>0）&amp；（值<X）退货对（项目、价值）

3. 返回列表中的所有（项，值）对（值>0），理想情况下按值排序

为了更清楚一点，只有当没有一个项的值小于X时，步骤3才会发生。在步骤2中，当我们遇到第一个小于X的项时，我们不应该计算其余项，只返回该项（我们显然可以在Set（）中单独返回它，以匹配返回类型）。

我现在的代码如下：

  val itemValMap = items.foldLeft(Map[Item, Int)]()) {
  (map : Map[Item, Int], key : Item) =>
    val value = computeValue(item)
    if ( value >= 0 )        //we filter out negative ones
      map + (key -> value)
    else
      map
  }
 val bestItem = itemValMap.minBy(_._2)
 if (bestItem._2 < bestX)
 {
      List(bestItem)
 }
 else
 {
    itemValMap.toList.sortBy(_._2)
 }

然而，这段代码所做的是计算列表中的所有值并选择最好的值，而不是在找到"更好"的值时停止。我怀疑我必须以某种方式使用Streams才能实现这一点？

Answer 1

好吧，我不确定你的整个设置是什么样子，但我试着准备了一个反映你的情况的最小示例。

现在是：

object StreamTest {
  case class Item(value : Int)
  def createItems() = List(Item(0),Item(3),Item(30),Item(8),Item(8),Item(4),Item(54),Item(-1),Item(23),Item(131))
  def computeValue(i : Item) = { Thread.sleep(3000); i.value * 2 - 2 }
  def process(minValue : Int)(items : Seq[Item]) = {
    val stream = Stream(items: _*).map(item => item -> computeValue(item)).filter(tuple => tuple._2 >= 0)
    stream.find(tuple => tuple._2 < minValue).map(List(_)).getOrElse(stream.sortBy(_._2).toList)
  }
}

每次计算需要3秒钟。现在让我们看看它是如何工作的：

val items = StreamTest.createItems()
val result = StreamTest.process(2)(items)
result.foreach(r => println("Original: " + r._1 + " , calculated: " + r._2))

提供：

[info] Running Main 
Original: Item(3) , calculated: 4
Original: Item(4) , calculated: 6
Original: Item(8) , calculated: 14
Original: Item(8) , calculated: 14
Original: Item(23) , calculated: 44
Original: Item(30) , calculated: 58
Original: Item(54) , calculated: 106
Original: Item(131) , calculated: 260
[success] Total time: 31 s, completed 2013-11-21 15:57:54

由于没有小于2的值，我们得到了一个按计算值排序的列表。请注意，缺少两个对，因为计算的值小于0并被过滤掉。

好的，现在让我们尝试一个不同的最小截止点：

val result = StreamTest.process(5)(items)

哪个给出：

[info] Running Main 
Original: Item(3) , calculated: 4
[success] Total time: 7 s, completed 2013-11-21 15:55:20

很好，它返回了一个只有一个项目的列表，第一个值（原始列表中的第二个项目）小于"最小"值，并且不小于0。

我希望上面的例子能很容易地适应你的需要。。。

Answer 2

避免计算不需要的值的一个简单方法是使用view方法使集合变得懒惰：

val weigthedItems = items.view.map{ i => i -> computeValue(i) }.filter(_._2 >= 0 )
weigthedItems.find(_._2 < X).map(List(_)).getOrElse(weigthedItems.sortBy(_._2))

举例来说，这里是REPL:中的一个测试

scala> :paste
// Entering paste mode (ctrl-D to finish)
type Item = String
def computeValue( item: Item ): Int = {
  println("Computing " + item)
  item.toInt
}
val items = List[Item]("13", "1", "5", "-7", "12", "3", "-1", "15")
val X = 10
val weigthedItems = items.view.map{ i => i -> computeValue(i) }.filter(_._2 >= 0 )
weigthedItems.find(_._2 < X).map(List(_)).getOrElse(weigthedItems.sortBy(_._2))
// Exiting paste mode, now interpreting.
Computing 13
Computing 1
defined type alias Item
computeValue: (item: Item)Int
items: List[String] = List(13, 1, 5, -7, 12, 3, -1, 15)
X: Int = 10
weigthedItems: scala.collection.SeqView[(String, Int),Seq[_]] = SeqViewM(...)
res27: Seq[(String, Int)] = List((1,1))

正如你所看到的，computeValue只被调用到第一个值<X（即，高达1）