gpt4 book ai didi

algorithm - 为什么我在 Scala 中的二进制搜索实现如此缓慢?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:56:27 25 4
gpt4 key购买 nike

最近,我实现了这个二进制搜索,它应该在 Scala 中运行不到 6 秒,但它在检查分配的机器上运行了 12-13 秒。

在阅读代码之前请注意:输入由两行组成:第一行 - 要搜索的数字列表,第二行 - 要在数字列表中搜索的“搜索词”列表。预期输出仅列出数字列表中每个术语的索引。每个输入的最大长度为 10^5,每个数字的最大长度为 10^9。

例如:

Input:
5 1 5 8 12 13 //note, that the first number 5 indicates the length of the
following sequence

5 8 1 23 1 11 //note, that the first number 5 indicates the length of the
following sequence

Output:
2 0 -1 0 -1 // index of each term in the input array

我的解决方案:

object BinarySearch extends App {
val n_items = readLine().split(" ").map(BigInt(_))
val n = n_items(0)
val items = n_items.drop(1)

val k :: terms = readLine().split(" ").map(BigInt(_)).toList

println(search(terms, items).mkString(" "))

def search(terms: List[BigInt], items:Array[BigInt]): Array[BigInt] = {
@tailrec
def go(terms: List[BigInt], results: Array[BigInt]): Array[BigInt] = terms match {
case List() => results
case head :: tail => go(tail, results :+ find(head))
}

def find(term: BigInt): BigInt = {
@tailrec
def go(left: BigInt, right: BigInt): BigInt = {
if (left > right) { -1 }
else {
val middle = left + (right - left) / 2
val middle_val = items(middle.toInt)

middle_val match {
case m if m == term => middle
case m if m <= term => go(middle + 1, right)
case m if m > term => go(left, middle - 1)
}
}
}

go(0, n - 1)
}

go(terms, Array())
}
}

是什么让这段代码这么慢?谢谢

最佳答案

我担心的是

的复杂性
results :+ find(head)

将一个项目附加到长度为 L 的列表是 O(L)(参见 here ),因此如果您有 n 个结果要计算,复杂度将为 O(n*n)。

尝试使用可变的 ArrayBuffer 而不是 Array 来累积结果,或者简单地通过查找函数映射输入项。

换句话说替换

go(terms, Array())

terms.map( x => find(x) ).toArray

顺便说一下,这个问题的限制很小,以至于使用 BigInt 有点矫枉过正,可能会使代码显着变慢。对于这个问题,普通整数应该足够大。

关于algorithm - 为什么我在 Scala 中的二进制搜索实现如此缓慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48469809/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com