时间戳

首页 > 解决方案 > 如何使我的快速选择算法更快

algorithm - 如何使我的快速选择算法更快

问题描述

我参加了一个检查算法的课程，我们有一个任务是使用快速选择来完成经典的 k:th 最小元素（0 是最小的并且sequence.length-1是最大的）。

该算法应该比排序方法平均快 2*

Arrays.sort

我的算法有效，但速度不够快。它比上述排序数组的方法平均慢 5 倍。到目前为止，这是我的实现：

  def find(sequence: Seq[Int], k: Int): Int = {
    require(0 <= k && k < sequence.length)
    val a: Array[Int] = sequence.toArray[Int]
    select(a,k)
  }

  def select(a: Array[Int], k: Int): Int = {
    val pivot = rand.nextInt(a.length)     
    val (low, middle, high) = partition(a,a(pivot))
    if (low.length == k) a(pivot)
    else if(low.length > k) select(low, k) 
    else if (low.length + middle.length >= k+1) middle(0)
    else if (low.length == 0) select(high, k - low.length-middle.length)
    else  findFast(high, k - low.length-middle.length)
  }

  def partition(array: Array[Int],pivot: Int): (Array[Int],Array[Int],Array[Int])={
    (array.filter(_<pivot),array.filter(_==pivot),array.filter(_>pivot))
  }

你能给我一些技巧来改进我的实现的运行时间吗？

标签： algorithmscala

解决方案

尽管总体上有很多关于 quickSelect 的帖子，并且伪代码的标准模板已经足够好，但我总是很难在 Scala 中找到好的实现，而且 Rosetta 博客中的代码很好，但可能会陷入无限循环，尤其是当左侧之一时或对右分区数组进行排序。

下面是使用 Scala 稍作修改且有效的解决方案（涵盖重复元素和排序数组等情况）。

如果输入数组已排序，则基本上返回第 k 个元素

def isSorted[T](arr: List[T])(implicit ord: Ordering[T]): Boolean = arr match {
        case Nil => true
        case x :: Nil => true
        case x :: xs => ord.lteq(x, xs.head) && isSorted(xs)
}
def quickSelect(nums: List[Int], k: Int): Int = {
        // if the input array is sorted then no point partitioning further
        // and go into a potential infinite loop even with random pivot
        // logical to pick the kth element from sorted array
        if (isSorted(nums)) return nums(k)
        // else start the partition logic
        val pvt = (new scala.util.Random).nextInt(nums.length)
        val (lower, higher) = nums.partition( _ < nums(pvt))
        if (lower.length > k) quickSelect(lower, k)
        else if (lower.length < k) quickSelect(higher, k - lower.length)
        else nums(pvt)
}

希望这会有所帮助。

推荐阅读