Ответ 1
Неизменяемый алгоритм
первый алгоритм указал Тейлор Лиз квадратичен, но имеет линейное среднее значение. Это, однако, зависит от выбора стержня. Таким образом, я предоставляю здесь версию, которая имеет возможность подключения с возможностью поворота, и как случайный стержень, так и медиану срединной оси (которая гарантирует линейное время).
import scala.annotation.tailrec
@tailrec def findKMedian(arr: Array[Double], k: Int)(implicit choosePivot: Array[Double] => Double): Double = {
val a = choosePivot(arr)
val (s, b) = arr partition (a >)
if (s.size == k) a
// The following test is used to avoid infinite repetition
else if (s.isEmpty) {
val (s, b) = arr partition (a ==)
if (s.size > k) a
else findKMedian(b, k - s.size)
} else if (s.size < k) findKMedian(b, k - s.size)
else findKMedian(s, k)
}
def findMedian(arr: Array[Double])(implicit choosePivot: Array[Double] => Double) = findKMedian(arr, (arr.size - 1) / 2)
Случайный стержень (квадратичный, линейный средний), Неизменяемый
Это случайный выбор. Анализ алгоритмов со случайными факторами более сложный, чем обычно, поскольку он в основном связан с вероятностью и статистикой.
def chooseRandomPivot(arr: Array[Double]): Double = arr(scala.util.Random.nextInt(arr.size))
Медиана медиан (линейная), неизменяемая
Медиана метода медианов, которая гарантирует линейное время при использовании с вышеприведенным алгоритмом. Во-первых, и алгоритм вычисления медианы до 5 чисел, который является основой медианы алгоритма медианов. Этот был предоставлен Rex Kerr в этом ответе - алгоритм во многом зависит от его скорости.
def medianUpTo5(five: Array[Double]): Double = {
def order2(a: Array[Double], i: Int, j: Int) = {
if (a(i)>a(j)) { val t = a(i); a(i) = a(j); a(j) = t }
}
def pairs(a: Array[Double], i: Int, j: Int, k: Int, l: Int) = {
if (a(i)<a(k)) { order2(a,j,k); a(j) }
else { order2(a,i,l); a(i) }
}
if (five.length < 2) return five(0)
order2(five,0,1)
if (five.length < 4) return (
if (five.length==2 || five(2) < five(0)) five(0)
else if (five(2) > five(1)) five(1)
else five(2)
)
order2(five,2,3)
if (five.length < 5) pairs(five,0,1,2,3)
else if (five(0) < five(2)) { order2(five,1,4); pairs(five,1,4,2,3) }
else { order2(five,3,4); pairs(five,0,1,3,4) }
}
И тогда медиана самого медиана алгоритма. В принципе, это гарантирует, что выбранный стержень будет больше, чем минимум 30% и меньше, чем другие 30% списка, что достаточно, чтобы гарантировать линейность предыдущего алгоритма. Подробнее см. Ссылку на wikipedia, указанную в другом ответе.
def medianOfMedians(arr: Array[Double]): Double = {
val medians = arr grouped 5 map medianUpTo5 toArray;
if (medians.size <= 5) medianUpTo5 (medians)
else medianOfMedians(medians)
}
Алгоритм на месте
Итак, вот версия на месте в алгоритме. Я использую класс, который реализует раздел на месте, с базовым массивом, так что изменения в алгоритмах минимальны.
case class ArrayView(arr: Array[Double], from: Int, until: Int) {
def apply(n: Int) =
if (from + n < until) arr(from + n)
else throw new ArrayIndexOutOfBoundsException(n)
def partitionInPlace(p: Double => Boolean): (ArrayView, ArrayView) = {
var upper = until - 1
var lower = from
while (lower < upper) {
while (lower < until && p(arr(lower))) lower += 1
while (upper >= from && !p(arr(upper))) upper -= 1
if (lower < upper) { val tmp = arr(lower); arr(lower) = arr(upper); arr(upper) = tmp }
}
(copy(until = lower), copy(from = lower))
}
def size = until - from
def isEmpty = size <= 0
override def toString = arr mkString ("ArraySize(", ", ", ")")
}; object ArrayView {
def apply(arr: Array[Double]) = new ArrayView(arr, 0, arr.size)
}
@tailrec def findKMedianInPlace(arr: ArrayView, k: Int)(implicit choosePivot: ArrayView => Double): Double = {
val a = choosePivot(arr)
val (s, b) = arr partitionInPlace (a >)
if (s.size == k) a
// The following test is used to avoid infinite repetition
else if (s.isEmpty) {
val (s, b) = arr partitionInPlace (a ==)
if (s.size > k) a
else findKMedianInPlace(b, k - s.size)
} else if (s.size < k) findKMedianInPlace(b, k - s.size)
else findKMedianInPlace(s, k)
}
def findMedianInPlace(arr: Array[Double])(implicit choosePivot: ArrayView => Double) = findKMedianInPlace(ArrayView(arr), (arr.size - 1) / 2)
Случайный стержень, место
Я использую только опорный радиус для локальных алгоритмов, так как медиана медианов потребует большей поддержки, чем то, что в настоящее время предоставляется классом ArrayView, определенным мной.
def chooseRandomPivotInPlace(arr: ArrayView): Double = arr(scala.util.Random.nextInt(arr.size))
Алгоритм гистограммы (память O (log (n)), Неизменяемый
Итак, о потоках. Невозможно сделать что-то меньшее, чем O(n) память для потока, который может быть пройден только один раз, если только вы не знаете, что такое длина строки (в этом случае она перестает быть потоком в моей книге).
Использование ведер также немного проблематично, но если мы можем пройти его несколько раз, то мы можем знать его размер, максимум и минимум и работать оттуда. Например:
def findMedianHistogram(s: Traversable[Double]) = {
def medianHistogram(s: Traversable[Double], discarded: Int, medianIndex: Int): Double = {
// The buckets
def numberOfBuckets = (math.log(s.size).toInt + 1) max 2
val buckets = new Array[Int](numberOfBuckets)
// The upper limit of each bucket
val max = s.max
val min = s.min
val increment = (max - min) / numberOfBuckets
val indices = (-numberOfBuckets + 1 to 0) map (max + increment * _)
// Return the bucket a number is supposed to be in
def bucketIndex(d: Double) = indices indexWhere (d <=)
// Compute how many in each bucket
s foreach { d => buckets(bucketIndex(d)) += 1 }
// Now make the buckets cumulative
val partialTotals = buckets.scanLeft(discarded)(_+_).drop(1)
// The bucket where our target is at
val medianBucket = partialTotals indexWhere (medianIndex <)
// Keep track of how many numbers there are that are less
// than the median bucket
val newDiscarded = if (medianBucket == 0) discarded else partialTotals(medianBucket - 1)
// Test whether a number is in the median bucket
def insideMedianBucket(d: Double) = bucketIndex(d) == medianBucket
// Get a view of the target bucket
val view = s.view filter insideMedianBucket
// If all numbers in the bucket are equal, return that
if (view forall (view.head ==)) view.head
// Otherwise, recurse on that bucket
else medianHistogram(view, newDiscarded, medianIndex)
}
medianHistogram(s, 0, (s.size - 1) / 2)
}
Тест и контрольная таблица
Чтобы проверить алгоритмы, я использую Scalacheck и сравнивая вывод каждого алгоритма с выходом тривиальной реализации с сортировкой. Это предполагает, что версия сортировки верна, конечно.
Я сравниваю каждый из вышеперечисленных алгоритмов со всеми предоставленными выборками, а также фиксированный выбор поворота (на полпути массива округляется вниз). Каждый алгоритм тестируется с тремя различными размерами входных массивов и три раза против каждого.
Здесь код тестирования:
import org.scalacheck.{Prop, Pretty, Test}
import Prop._
import Pretty._
def test(algorithm: Array[Double] => Double,
reference: Array[Double] => Double): String = {
def prettyPrintArray(arr: Array[Double]) = arr mkString ("Array(", ", ", ")")
val resultEqualsReference = forAll { (arr: Array[Double]) =>
arr.nonEmpty ==> (algorithm(arr) == reference(arr)) :| prettyPrintArray(arr)
}
Test.check(Test.Params(), resultEqualsReference)(Pretty.Params(verbosity = 0))
}
import java.lang.System.currentTimeMillis
def bench[A](n: Int)(body: => A): Long = {
val start = currentTimeMillis()
1 to n foreach { _ => body }
currentTimeMillis() - start
}
import scala.util.Random.nextDouble
def benchmark(algorithm: Array[Double] => Double,
arraySizes: List[Int]): List[Iterable[Long]] =
for (size <- arraySizes)
yield for (iteration <- 1 to 3)
yield bench(50000)(algorithm(Array.fill(size)(nextDouble)))
def testAndBenchmark: String = {
val immutablePivotSelection: List[(String, Array[Double] => Double)] = List(
"Random Pivot" -> chooseRandomPivot,
"Median of Medians" -> medianOfMedians,
"Midpoint" -> ((arr: Array[Double]) => arr((arr.size - 1) / 2))
)
val inPlacePivotSelection: List[(String, ArrayView => Double)] = List(
"Random Pivot (in-place)" -> chooseRandomPivotInPlace,
"Midpoint (in-place)" -> ((arr: ArrayView) => arr((arr.size - 1) / 2))
)
val immutableAlgorithms = for ((name, pivotSelection) <- immutablePivotSelection)
yield name -> (findMedian(_: Array[Double])(pivotSelection))
val inPlaceAlgorithms = for ((name, pivotSelection) <- inPlacePivotSelection)
yield name -> (findMedianInPlace(_: Array[Double])(pivotSelection))
val histogramAlgorithm = "Histogram" -> ((arr: Array[Double]) => findMedianHistogram(arr))
val sortingAlgorithm = "Sorting" -> ((arr: Array[Double]) => arr.sorted.apply((arr.size - 1) / 2))
val algorithms = sortingAlgorithm :: histogramAlgorithm :: immutableAlgorithms ::: inPlaceAlgorithms
val formattingString = "%%-%ds %%s" format (algorithms map (_._1.length) max)
// Tests
val testResults = for ((name, algorithm) <- algorithms)
yield formattingString format (name, test(algorithm, sortingAlgorithm._2))
// Benchmarks
val arraySizes = List(100, 500, 1000)
def formatResults(results: List[Long]) = results map ("%8d" format _) mkString
val benchmarkResults: List[String] = for {
(name, algorithm) <- algorithms
results <- benchmark(algorithm, arraySizes).transpose
} yield formattingString format (name, formatResults(results))
val header = formattingString format ("Algorithm", formatResults(arraySizes.map(_.toLong)))
"Tests" :: "*****" :: testResults :::
("" :: "Benchmark" :: "*********" :: header :: benchmarkResults) mkString ("", "\n", "\n")
}
Результаты
Тесты:
Tests
*****
Sorting OK, passed 100 tests.
Histogram OK, passed 100 tests.
Random Pivot OK, passed 100 tests.
Median of Medians OK, passed 100 tests.
Midpoint OK, passed 100 tests.
Random Pivot (in-place)OK, passed 100 tests.
Midpoint (in-place) OK, passed 100 tests.
Ориентиры:
Benchmark
*********
Algorithm 100 500 1000
Sorting 1038 6230 14034
Sorting 1037 6223 13777
Sorting 1039 6220 13785
Histogram 2918 11065 21590
Histogram 2596 11046 21486
Histogram 2592 11044 21606
Random Pivot 904 4330 8622
Random Pivot 902 4323 8815
Random Pivot 896 4348 8767
Median of Medians 3591 16857 33307
Median of Medians 3530 16872 33321
Median of Medians 3517 16793 33358
Midpoint 1003 4672 9236
Midpoint 1010 4755 9157
Midpoint 1017 4663 9166
Random Pivot (in-place) 392 1746 3430
Random Pivot (in-place) 386 1747 3424
Random Pivot (in-place) 386 1751 3431
Midpoint (in-place) 378 1735 3405
Midpoint (in-place) 377 1740 3408
Midpoint (in-place) 375 1736 3408
Анализ
Все алгоритмы (кроме версии сортировки) имеют результаты, совместимые со средней линейной сложностью времени.
Медиана медианов, которая гарантирует линейную временную сложность в худшем случае, намного медленнее, чем случайный стержень.
Фиксированный выбор поворота немного хуже, чем случайный стержень, но может иметь гораздо худшую производительность на неслучайных входах.
Версия на месте примерно на 230% ~ 250% быстрее, но дальнейшие тесты (не показаны), похоже, указывают на то, что это преимущество растет с размером массива.
Я был очень удивлен алгоритмом гистограммы. Он отображает линейную среднюю сложность по времени, а также на 33% быстрее, чем медиана медиан. Однако вход случайный. Худший случай - квадратичный - я видел несколько примеров этого, когда я отлаживал код.