Как я могу оптимизировать время этого алгоритма CountingSort в Scala

Question

Я хотел бы попросить вас помочь определить, какая часть моего кода неэффективна. Я сравниваю алгоритм QuickSort с алгоритмом CountingSort, предполагая, что количество элементов в Array[Byte] меньше 16

Однако время CountingSort намного выше, чем время QuickSort, во всех тестах, которые я проводил последовательно. Затем я хотел протестировать этот код в Spark для вычисления Медианного фильтра, но результаты распределенного времени выполнения соответствуют времени последовательного выполнения. Я имею в виду, что 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)}

Мои тесты показывают, что он дает те же результаты, но могут быть и краевые условия, которые я пропустил.