问题标签 [median]

5 的中位数有时用作算法设计中的练习，并且已知仅使用 6 次比较即可计算。

在 C#中实现这种“使用 6 次比较的 5 的中位数”的最佳方法是什么？我所有的尝试似乎都导致了笨拙的代码:(我需要漂亮且可读的代码，同时仍然只使用 6 次比较。

注意：我想我也应该在这里提供“算法”：

我发现自己无法像Azereal在他的论坛帖子中那样清楚地解释算法。所以我会在这里参考他的帖子。来自http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

好吧，我在我的一项作业中遇到了这个问题，我向这个论坛寻求帮助，但这里没有任何帮助。我最终发现了如何做到这一点。

1. 使用前 4 个元素开始合并排序，并对每一对进行排序（2 次比较）

2. 比较每对中较低的两个并从可能性中消除最低的一个（3 次比较）

3. 将留出的第 5 个数字与没有配对的数字相加并比较两者（4 次比较）

4. 比较两个新对中最低的两个并消除较低的一对（5 次比较）

5. 比较一个本身和最后一对中的较低者，较低的数字是中位数

   可能的中位数在 parentesis 内

(54321)

5:4 3:2 2 次比较

(4<5 2<3 1)

4:2 3 次比较

2(4<5 3 1)

1:3 4 次比较

2(4<5 1<3)

4:1 5 次比较

1,2(4<5 3)

4:3 6 次比较

1,2(3)4,5

三是中位数

这是我编写的 C++ 代码，用于找到 5 的中位数。不要介意它的尴尬：

它应该更紧凑，不是吗？

正如@pablito 在他的回答中指出的那样，内置List.Sort()无法满足此要求，因为它最多使用 13 次比较：]

I'm trying to calculate the median of a set of values, but I don't want to store all the values as that could blow memory requirements. Is there a way of calculating or approximating the median without storing and sorting all the individual values?

Ideally I would like to write my code a bit like the following

All I need is the actual MedianCalculator code!

Update: Some people have asked if the values I'm trying to calculate the median for have known properties. The answer is yes. One value is in 0.5 increments from about -25 to -0.5. The other is also in 0.5 increments from -120 to -60. I guess this means I can use some form of histogram for each value.

Thanks

Nick

我有一张表，其中包含一本书，然后是关于这本书的多个价格（这是一个高度简化的示例）：

我很容易计算平均值，但必须有一个很好的方法来计算中位数？

当前 SQL：

结果：

I'm trying to calculate the conditional median of a chart that looks like this:

I'm using MS Excel 2007. I am aware of the AVERAGEIF() statement, but there is no equivalent for Median. The main trick is that there are rows with no data - such as the 4th "a" above. In this case, I don't want this row considered at all in the calculations.

Googling has suggested the following, but Excel won't accept the formula format (maybe because it's 2007?)

Excel gives an error saying there is something wrong with my formula(something to do with the * in the condition) I had also tried the following, but it counts blank cells as 0's in the calculations:

I am aware that those formulas return Excel "arrays", which means one must enter "Ctrl-shift-enter" to get it to work correctly.

How can I do a conditional evaluation and not consider blank cells?

你如何找到在 Java 中存储为 LinkedList 的数字列表的中位数？我不明白维基百科所指的选择算法。如果你能解释一下，加分。

是否有一种算法可以估计一组值的中值、众数、偏度和/或峰度，但这不需要一次将所有值存储在内存中？

我想计算基本统计数据：

• 平均值：算术平均值
• 方差：与平均值的平方偏差的平均值
• 标准差：方差的平方根
• 中位数：将较大一半的数字与较小的一半分开的值
• 模式：在集合中找到的最频繁的值
• 偏度：tl；博士
• 峰度：tl；博士

计算任何这些的基本公式是小学算术，我知道它们。也有许多实现它们的统计库。

我的问题是我正在处理的集合中有大量（数十亿）值：在 Python 中工作，我不能只用数十亿个元素制作一个列表或散列。即使我用 C 语言编写了这个，十亿元素的数组也不太实用。

数据未排序。它是由其他过程随机、即时生成的。每组的大小是高度可变的，并且大小不会提前知道。

我已经想出了如何很好地处理均值和方差，以任何顺序遍历集合中的每个值。（实际上，在我的例子中，我按照它们生成的顺序来使用它们。）这是我正在使用的算法，由http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm提供：

• 初始化三个变量：count、sum、sum_of_squares
• 对于每个值：
  • 递增计数。
  • 将值添加到总和。
  • 将值的平方添加到 sum_of_squares。
• 将总和除以计数，存储为变量均值。
• 将 sum_of_squares 除以计数，存储为变量 mean_of_squares。
• 平方均值，存储为 square_of_mean。
• 从 mean_of_squares 中减去 square_of_mean，存储为方差。
• 输出均值和方差。

这种“在线”算法有弱点（例如，准确性问题，因为 sum_of_squares 迅速增长到大于整数范围或浮点精度），但它基本上可以满足我的需求，而不必存储每个集合中的每个值。

但我不知道是否存在用于估计附加统计数据（中位数、众数、偏度、峰度）的类似技术。只要处理 N 个值所需的内存大大小于 O(N)，我就可以使用有偏差的估计器，甚至可以使用在一定程度上损害准确性的方法。

如果该库具有“在线”计算这些操作中的一个或多个的功能，那么将我指向现有的统计库也会有所帮助。

首先，我在 DB2 for i5/OS V5R4 上运行。我有 ROW_NUMBER()、RANK() 和公用表表达式。我没有TOP n PERCENT 或 LIMIT OFFSET。

我正在使用的实际数据集很难解释，所以假设我有一个天气历史表，其中的列是(city, temperature, timestamp). 我想比较每组的中位数和平均值(city)。

这是我发现获得整个表聚合的中位数的最干净的方法。我在这里从 IBM 红皮书改编了它：

这对于恢复单行很有效，但对于分组来说似乎分崩离析。从概念上讲，这就是我想要的：

可能会有一个让我看起来很愚蠢的答案，但我有一个心理障碍，这不是我现在要做的第一件事。似乎有可能，但我不能使用非常复杂的东西，因为它是一个大表，我希望能够自定义正在聚合的列。

在这里，我创建一个新列来指示 myData 是高于还是低于其中位数

工作正常。现在我想做同样的事情，但计算 myFactor 的每个级别内的中位数拆分。

我想出了这个：

byOutput 包含我想要的。它正确地对因子 A、B 和 C 的每个元素进行分类。但是我想创建一个新列 myDataFrame$FactorLevelMedianSplit，它显示新计算的中位数分割。

如何将“by”命令的输出转换为有用的数据框列？

我认为也许“by”命令不是类似 R 的方式来做到这一点......

更新：

通过 Thierry 关于如何巧妙使用 factor() 的示例，以及在 Spector 的书中发现“ave”函数后，我找到了这个解决方案，它不需要额外的包。

用 MySQL 计算中位数最简单（希望不会太慢）的方法是什么？我已经习惯于AVG(x)找到平均值，但我很难找到一种计算中位数的简单方法。现在，我将所有行返回给 PHP，进行排序，然后选择中间行，但肯定有一些简单的方法可以在单个 MySQL 查询中完成。

示例数据：

排序val给出2 2 3 4 7 8 9，所以中位数应该是4，而SELECT AVG(val)== 5。

我目前正在研究一种在 C 中实现滚动中值滤波器（类似于滚动均值滤波器）的算法。根据我对文献的搜索，似乎有两种相当有效的方法可以做到这一点。第一个是对初始值窗口进行排序，然后执行二进制搜索以插入新值并在每次迭代时删除现有值。

第二个（来自 Hardle 和 Steiger，1995，JRSS-C，算法 296）构建了一个双端堆结构，一端是 maxheap，另一端是 minheap，中间是中间值。这产生了一种线性时间算法，而不是 O(n log n)。

这是我的问题：实现前者是可行的，但我需要在数百万个时间序列上运行它，所以效率很重要。事实证明，后者非常难以实施。我在 R 的 stats 包的代码的 Trunmed.c 文件中找到了代码，但它相当难以理解。

有谁知道线性时间滚动中值算法的编写良好的 C 实现？

编辑：链接到 Trunmed.c 代码http://google.com/codesearch/p?hl=en&sa=N&cd=1&ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c