scala 中中位数的快速实现是什么？
这是我在 rosetta 代码 上发现的：
def median(s: Seq[Double]) =
{
val (lower, upper) = s.sortWith(_<_).splitAt(s.size / 2)
if (s.size % 2 == 0) (lower.last + upper.head) / 2.0 else upper.head
}
我不喜欢它，因为它做了种类。我知道有一些方法可以在线性时间内计算中位数。
编辑：
我想要一组可以在各种场景中使用的中值函数：
- 快速、就地中值计算，可以在线性时间中完成中
- 值，该中值适用于您可以遍历的流多次，但只能在内存中保留
O(log n) 值 像这样
- 在流上工作的中位数，您最多可以容纳
O(log n)内存中的值，并且您最多可以遍历流一次（这可能吗？）
请仅发布编译和正确计算中位数的代码。为简单起见，您可以假设所有输入都包含奇数个值。
What's a fast implementation of median in scala?
This is what I found on rosetta code:
def median(s: Seq[Double]) =
{
val (lower, upper) = s.sortWith(_<_).splitAt(s.size / 2)
if (s.size % 2 == 0) (lower.last + upper.head) / 2.0 else upper.head
}
I don't like it because it does a sort. I know there are ways to compute the median in linear time.
EDIT:
I would like to have a set of median functions that I can use in various scenarios:
- fast, in place median computation that can be done in linear time
- median that works on a stream that you can traverse multiple times, but you can only keep
O(log n) values in memory like this
- median that works on a stream, where you can hold at most
O(log n) values in memory, and you can traverse the stream at most once (is this even possible?)
Please only post code that compiles and correctly computes the median. For simplicity, you may assume that all inputs contain an odd number of values.
发布评论
评论（1）
不可变算法
第一个算法 由Taylor Leese 是二次函数，但具有线性平均值。然而，这取决于枢轴的选择。因此，我在这里提供一个具有可插入枢轴选择的版本，以及随机枢轴和中值枢轴的中值（保证线性时间）。
随机枢轴（二次、线性平均），不可变
这是随机枢轴选择。具有随机因素的算法的分析比平常更棘手，因为它主要涉及概率和统计。
Median of Medians（线性），不可变
中位数方法，与上述算法一起使用时保证线性时间。首先，算法计算最多 5 个数字的中位数，这是中位数算法的基础。这是由 Rex Kerr 在 这个答案——算法在很大程度上取决于它的速度。
然后是中位数算法本身的中位数。基本上，它保证所选择的主元将大于列表中的至少30%并小于列表中的其他30%，这足以保证先前算法的线性。有关详细信息，请参阅另一个答案中提供的维基百科链接。
就地算法
因此，这是该算法的就地版本。我正在使用一个类，该类通过支持数组就地实现分区，以便对算法的更改最小化。
随机枢轴，就地
我只为就地算法实现随机枢轴，因为中位数的中位数需要比我定义的 ArrayView 类目前提供的支持更多的支持。
直方图算法（O(log(n))内存），不可变
所以，关于流。对于只能遍历一次的流，不可能执行小于
O(n)内存的操作，除非您碰巧知道字符串长度是多少（在这种情况下，它不再是一个流）在我的书中）。使用桶也有点问题，但是如果我们可以多次遍历它，那么我们就可以知道它的大小、最大值和最小值，并从那里开始工作。例如：
测试和基准
为了测试算法，我使用 Scalacheck，并比较每个算法的输出到带有排序的简单实现的输出。当然，这是假设排序版本是正确的。
我使用所有提供的主元选择以及固定的主元选择（数组的一半，向下舍入）对上述每个算法进行基准测试。每种算法都使用三种不同的输入数组大小进行测试，并对每种算法进行三次。
下面是测试代码：
结果
测试：
基准：
分析
所有算法（排序版本除外）的结果都与平均线性时间复杂度兼容。
中位数的中位数，保证了最坏情况下的线性时间复杂度，比随机主元慢得多。
固定主元选择比随机主元稍差，但在非随机输入上的性能可能更差。
就地版本大约快 230% ~ 250%，但进一步的测试（未显示）似乎表明这种优势随着数组大小的增加而增加。
我对直方图算法感到非常惊讶。它显示了线性时间复杂度平均值，并且比中位数快了 33%。然而，输入是随机的。最坏的情况是二次的——我在调试代码时看到了一些例子。
Immutable Algorithm
The first algorithm indicated by Taylor Leese is quadratic, but has linear average. That, however, depends on the pivot selection. So I'm providing here a version which has a pluggable pivot selection, and both the random pivot and the median of medians pivot (which guarantees linear time).
Random Pivot (quadratic, linear average), Immutable
This is the random pivot selection. Analysis of algorithms with random factors is trickier than normal, because it deals largely with probability and statistics.
Median of Medians (linear), Immutable
The median of medians method, which guarantees linear time when used with the algorithm above. First, and algorithm to compute the median of up to 5 numbers, which is the basis of the median of medians algorithm. This one was provided by Rex Kerr in this answer -- the algorithm depends a lot on the speed of it.
And, then, the median of medians algorithm itself. Basically, it guarantees that the choosen pivot will be greater than at least 30% and smaller than other 30% of the list, which is enough to guarantee the linearity of the previous algorithm. Look up the wikipedia link provided in another answer for details.
In-place Algorithm
So, here's an in-place version of the algorithm. I'm using a class that implements a partition in-place, with a backing array, so that the changes to the algorithms are minimal.
Random Pivot, In-place
I'm only implementing the radom pivot for the in-place algorithms, as the median of medians would require more support than what is presently provided by the
ArrayViewclass I defined.Histogram Algorithm (O(log(n)) memory), Immutable
So, about streams. It is impossible to do anything less than
O(n)memory for a stream that can only be traversed once, unless you happen to know what the string length is (in which case it ceases to be a stream in my book).Using buckets is also a bit problematic, but if we can traverse it multiple times, then we can know its size, maximum and minimum, and work from there. For example:
Test and Benchmark
To test the algorithms, I'm using Scalacheck, and comparing the output of each algorithm to the output of a trivial implementation with sorting. That assumes the sorting version is correct, of course.
I'm benchmarking each of the above algorithms with all provided pivot selections, plus a fixed pivot selection (halfway the array, round down). Each algorithm is tested with three different input array sizes, and for three times against each one.
Here's the testing code:
Results
Tests:
Benchmarks:
Analysis
All algorithms (except the sorting version) have results that are compatible with average linear time complexity.
The median of medians, which guarantees linear time complexity in the worst case is much slower than the random pivot.
The fixed pivot selection is slightly worse than random pivot, but may have much worse performance on non-random inputs.
The in-place version is about 230% ~ 250% faster, but further tests (not shown) seem to indicate this advantage grows with the size of the array.
I was very surprised by the histogram algorithm. It displayed linear time complexity average, and it's also 33% faster than the median of medians. However, the input is random. The worst case is quadratic -- I saw some examples of it while I was debugging the code.