时间戳

首页 > 解决方案 > 如何在 Scala 中优化此 CountingSort 算法的时序

scala - 如何在 Scala 中优化此 CountingSort 算法的时序

问题描述

我想请您帮忙确定我的代码的哪一部分效率不高。我将QuickSort算法与CountingSort算法进行比较，假设 an 中的元素数Array[Byte]小于 16。

但是，在我按顺序执行的所有测试中， CountingSort时间远高于QuickSort时间。然后，我想在Spark中测试这段代码来计算Median Filter，但是分布式执行时间的结果与顺序执行时间一致。我的意思是QuickSort总是比CountingSort快，即使对于较小的数组也是如此。

显然，我的代码中的某些内容正在挂起最终处理。

这是代码：

def Histogram(Input: Array[Byte]) : Array[Int] = {
  val result = Array.ofDim[Int](256)
  val range = Input.distinct.map(x => x & 0xFF)
  val mx = Input.map(x => x & 0xFF).max
  for (h <- range)
    result(h) = Input.count(x => (x & 0xFF) == h)
  result.slice(0, mx + 1)
}

def CummulativeSum(Input: Array[Int]): Array[Long] = Input.map(x => x.toLong).scanLeft(0.toLong)(_ + _).drop(1)

def CountingSort(Input: Array[Byte]): Array[Byte] = {
  val hist = Histogram(Input)
  val cum = CummulativeSum(hist)
  val Output = Array.fill[Byte](Input.length)(0)
  for (i <- Input.indices) {
    Output(cum(Input(i) & 0xFF).toInt - 1) = Input(i)
    cum(Input(i) & 0xFF) -= 1
  }
  Output
}

标签： scalamediancounting-sort

解决方案

您可以构建直方图，而无需多次遍历输入。

def histogram(input :Array[Byte]) :Array[Int] = {
  val inputMap :Map[Int,Array[Byte]] = input.groupBy(_ & 0xFF)
                                            .withDefaultValue(Array())
  Array.tabulate(inputMap.keys.max+1)(inputMap(_).length)
}

我不确定这是否更快，但它肯定更简洁。

def countingSort(input :Array[Byte]) :Array[Byte] =
  histogram(input).zipWithIndex.flatMap{case (v,x) => Seq.fill(v)(x.toByte)}

我的测试表明它产生了相同的结果，但我可能错过了一些边缘条件。

推荐阅读