为什么这个scala函数使用map比使用list要快得多？
为什么这个scala函数使用map比使用list要快得多？
提问于 2021-03-10 04:08:20
我已经在Scala中实现了Papadimitriou的算法来解决two-satisfiability问题。为了提高我的算法的速度，我首先做了一个缩减步骤，它消除了所有子句中只有一个值在整个子句集中出现(xor)被否定或未被否定的子句。
该算法是一种局部搜索算法，需要在每个循环中设置随机的初始状态。我不是完全随机的，而是从归约步骤中知道某些比特的状态。因此，我的代码生成一个初始状态的数组缓冲区，它的输入是位集合的总长度，以及从缩减步骤计算出的约束列表。
最初，我的实现只是使用列表来检查是否存在特定位的约束，或者是否需要随机生成该位：
// Is bit number x false (negX = true)?
case class Constraint(negX: Boolean, x: Int) extends Ordered[Constraint] {
def compare(that: Constraint) = this.x - that.x
}
private def getInitial(len: Int, allConstraints: List[Constraint]): ArrayBuffer[Boolean] = {
var constraints = allConstraints.sorted
val buff = ArrayBuffer.fill(len)(false)
for (i <- 0 to (len - 1)) {
if (constraints.length > 0 && constraints.head.x == i) {
buff(i) = !constraints.head.negX
constraints = constraints.tail
} else {
buff(i) = math.random < 0.5
}
}
buff
}上面的代码运行得很好，但在分析了我的代码后，我发现它相当慢。我知道列表的查找通常很慢，因为每次你想要搜索值的时候都要遍历整个列表，但我认为当我对列表进行排序时，只是检查了头部，它不会太慢。
无论如何，我尝试了使用map的第二个实现：
private def getInitial(len: Int, allConstraints: List[Constraint]): ArrayBuffer[Boolean] = {
var constraintMap = allConstraints.map{ case Constraint(negX,x) => (x,negX)}.toMap
val buff = ArrayBuffer.fill(len)(false)
for (i <- 0 to (len - 1)) {
buff(i) = !constraintMap.get(i).getOrElse(math.random < 0.5)
}
buff
}令我惊讶的是，这明显更快。所以我的问题是为什么？
我有6个不同的数据集，所以我尝试对最小的数据集(100,000个变量/子句)和最大的数据集(1,000,000个变量/子句)进行一些时间分析。通过多次运行，我得到了以下最佳时间(由于算法的随机性，时间会有所不同，最好的时间会有较少的重复，因此产生初始条件的时间将控制时间)
/* Small dataset */
// Using List
( scala target/scala-2.13/papadimitriou-s-algorithmn_2.13-1.0.jar main1; ) 9.71s user 0.16s system 116% cpu 8.451 total
// Using Map
( scala target/scala-2.13/papadimitriou-s-algorithmn_2.13-1.0.jar main1; ) 3.94s user 0.14s system 301% cpu 1.351 total
/* Large dataset */
// Using List
// ...never finished within 15 minutes
// Using Map
( scala target/scala-2.13/papadimitriou-s-algorithmn_2.13-1.0.jar main6; ) 72.85s user 1.70s system 428% cpu 17.384 total回答 1
Stack Overflow用户
回答已采纳
发布于 2021-03-10 04:50:01
正确的答案在评论中，但我的审美者无法不注意到，这在一个实际的习惯用法scala中看起来会好得多:)
def getInitial(len: Int, allConstraints: List[Constraint]) = {
@tailrec
def loop(i: Int, constraints: List[Constraint], result: List[Boolean]): List[Boolean] =
(i, constraints) match {
case (0, _) => result.reversed
case (_, head :: tail) if head.x == i => loop(i - 1, tail, !head.negX :: result)
case _ => loop(i-1, constraints, Random.nextBoolean :: result)
}
loop(len-1, allConstraints.sorted.reversed)
} 我认为，如果你使用一个预填充数组作为结果，你也可以不用排序就做到这一点(改变数组元素是很糟糕的，但如果性能很重要，约束的大小很大，这将减少几个周期：
def getInitial(len: Int, allConstraints: List[Constraint]) = {
val result = Array.fill(len)(Random.nextBoolean)
allConstraints.foreach { c => result(c.x) = !c.negX }
result
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66554040
复制相关文章
相似问题
腾讯云开发者
