尝试找到一种有效的方法来获取一个非常大的列表中的前 N 个项目,可能包含重复项。
我首先尝试了排序和切片,这很有效。但这似乎没有必要。如果您只想要前 20 名成员,则不需要对非常大的列表进行排序。
所以我写了一个递归例程来构建 top-n 列表。这也有效,但比非递归慢得多!
问题:我的第二个例程(精英2)比精英慢得多,我该如何让它更快?我的代码附在下面。谢谢。
import scala.collection.SeqView
import scala.math.min
object X {
def elite(s: SeqView[Int, List[Int]], k:Int):List[Int] = {
s.sorted.reverse.force.slice(0,min(k,s.size))
}
def elite2(s: SeqView[Int, List[Int]], k:Int, s2:List[Int]=Nil):List[Int] = {
if( k == 0 || s.size == 0) s2.reverse
else {
val m = s.max
val parts = s.force.partition(_==m)
val whole = if( parts._1.size > 1) parts._1.tail:::parts._2 else parts._2
elite2( whole.view, k-1, m::s2 )
}
}
def main(args:Array[String]) = {
val N = 1000000/3
val x = List(N to 1 by -1).flatten.map(x=>List(x,x,x)).flatten.view
println(elite2(x,20))
println(elite(x,20))
}
}
经典算法称为 QuickSelect。它就像快速排序,只不过你只下降到树的一半,所以它最终的平均时间为 O(n)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)