如何在Scala中优化CountingSort算法的时间

Question

我想向您寻求帮助，以确定我的代码中哪一部分是无效的。我将QuickSort算法与CountingSort算法进行比较，假设Array[Byte]中的元素数小于16。

然而，在我顺序执行的所有测试中，计数排序时间远高于快速排序park中测试这段代码，以计算中值滤波器，但分布式执行时间的结果与顺序执行时间一致。我的意思是，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
}

Answer 1

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

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)}

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