问题标签 [median-of-medians]

I have implemented the select/median of medians algorithm using the following as a reference http://www.ics.uci.edu/~eppstein/161/960130.html (this has previously been linked here Median of Medians in Java).

My code seems to work for small arrays (~100) and even works for arrays of size 100001 http://pastebin.com/mwRc4Hig (answer 5008), but then fails on an input array of size 10001 http://pastebin.com/YwVBmgDk (answer 4960, my code outputs 4958).

Note that the correct answers for the texts above are equivalent to sorting the array and returning the element at array[array.length / 2], regardless of whether the array size is even or odd.

I'm not sure how to debug this issue. The functionality seems arbitrary and I'm just lost. Here below is my code:

首先，我要声明这是一个家庭作业问题，我已经进行了大量的尝试。

我被要求修改 Java 中的快速排序，以使用公式将枢轴设置为数组中 9 个值的伪中位数i * (n-1) /8

我写了一个computeMedian方法，它接受 3 个整数，确定最大值，然后返回那个值。

编码：

然后我在我的findPivot方法中使用它，该方法采用当前array, from, to值并使用它们来构造一个枢轴

这是该代码：

此方法适用于对任何小于或等于 40 的数组进行排序，但一旦它大于 40，我就会收到堆栈溢出错误，导致返回computeMedian该else {}部分中的方法。如果我把它放在那里，我会注意到它return computeMedian(a[from], a[(to)/2] , a[to]);在 > 40 部分有效，但这只是 3 个值的中值，而不是 3 组中值的中值。

目前，这就是我findPivot插入快速排序分区方法的方式：

computeMedian我对为什么我的方法无法在更大的数据集上工作感到非常困惑。我尝试i * (n-1) / 8通过 for 循环将值放入数组中，对它们进行排序并在中间返回值，以及将值放入数组中p并调用computeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etc，我得到了相同的堆栈溢出问题，但它往往会移动到我的代码的不同部分并引导我转圈。

如果有人需要，我可以发布更多片段，但我认为我的问题可能就在这里。

谢谢您的帮助。我仍在学习，我认为掌握这一点完全可以帮助我自己解决未来的问题。

以下是堆栈跟踪中的问题行： 第 16 行：int p = modPartition(a, from, to); 第 18modSort(a, p+1, to); 行 第 23 行int pivot = findPivot(a, from, to);

这也是我的整个 modSort 方法：

给定一个由 N 个 8 位数字组成的数组（值 0-255）？

如何找到中位数？

我尝试了基数排序和中位数算法的中位数。

鉴于数字的值在 0 到 255 之间，有没有更好的方法？

我正在为 Median of Medians 算法编写 C 代码，以在最坏的线性时间中找到第 k 个最小的元素。我已经检查了快速排序、交换等的代码。一切看起来都很好，但每次都不能正常工作。

输入给定 -

输出 -

但输出需要是

函数调用 -

代码 -

维基百科将中位数算法列为需要O(1)辅助空间。

然而，在算法的中间，我们对一个大小的子数组进行递归调用n/5以找到中位数的中位数。当这个递归调用返回时，我们使用返回的中位数作为基准来划分数组。

这个算法不是将O(lg n)激活记录作为递归的一部分推送到运行时堆栈吗？从我所见，这些寻找中位数的连续中位数的递归调用不能进行尾调用优化，因为我们在递归调用返回后做了额外的工作。因此，该算法似乎需要辅助空间（就像快速排序一样，由于运行时堆栈使用的空间O(lg n)，维基百科将其列为需要辅助空间）。O(lg n)

我错过了什么，还是维基百科的文章错了？

（注意：我所指的递归调用return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)在维基百科页面上。）

我使用Wikipedia 文章实现了基于algs4 quickselect的中位数选择算法的中位数，但我的代码效果不佳：

1）据说中位数的中位数找到第k大元素。但是，我的代码找到了第 k 个最小的元素。

2）我的实现比快速选择慢 1-20 倍，但中位数算法的中位数应该渐近更快。

我已经检查了好几次，但我找不到问题。

JUnit测试：

我理解为什么在最坏的情况下，其中 T 是算法的运行时间，使用中位数算法的中位数和大小为 3 的块会给出递归关系

T(n) = T(2n / 3) + T(n / 3) + O(n)

中位数算法的维基百科文章说，对于大小为 3 的块，运行时间不是 O(n)，因为它仍然需要检查所有 n 个元素。我不太明白这个解释，在我的作业中说我需要通过归纳来展示它。

在这种情况下，我如何证明中位数的中位数需要时间 Ω(n log n)？

我已经明白的

我知道中位数算法的中位数（我将表示为 MoM）是一种高常数因子 O(N) 算法。它找到 k 组（通常为 5）的中位数，并将它们用作下一次迭代的集合以找到中位数。找到这个后的支点将在原始集合的 3/10n 和 7/10n 之间，其中 n 是找到一个中值基本情况所需的迭代次数。

当我为 MoM 运行此代码时，我不断收到分段错误，但我不知道为什么。我已经对其进行了调试，并认为问题在于我正在调用medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);. 但是，我认为这在逻辑上是合理的，因为我们应该通过调用自身来递归地找到中位数。也许我的基本情况不正确？在 YouTube 上 YogiBearian 的教程（斯坦福教授，链接：https ://www.youtube.com/watch?v=YU1HfMiJzwg ）中，他没有说明任何额外的基本情况来处理 O(N/5) MoM中的递归操作。

完整代码

注意：根据建议，我添加了一个基本案例并通过向量使用 .at() 函数。

一些帮助单元测试的额外功能

这是我为这两个函数编写的一些单元测试。希望他们有所帮助。

关于我得到的输出的额外部分

在分段错误之前，这似乎还不错。我相信我的分区函数也能正常工作（是 leetcode 问题的实现之一）。

免责声明：这不是作业问题，而是我在 Leetcode 问题集中使用 quickSelect 后对算法的好奇。

如果我提出的问题需要对 MVCE 进行更多详细说明，请告诉我，谢谢！

编辑：我发现我的代码中的递归分区方案是错误的。正如 Pradhan 指出的那样 - 我不知何故有空向量，导致开始和结束分别为 0 和 -1，导致我在调用它的无限循环中出现分段错误。仍在试图弄清楚这部分。

I am trying to perform several operations in one program at same time. I have a data-frame that has Dates of which I have no clue of start and end and I want to find:

1. Total number of days the data-set has
2. Total number of hours
3. Median of the Count
4. Write a separate output for median per day/date.
5. If possible Median-of-Median in most possible simple way.

Input: Few rows from the a large file of GB size

The start and end date are NOT known.

Edit: Expected Output:1 will have only one row of results

Median-of-Median is the median value of median column from output 2

Expected Output:2, will have medians of every date which are to used to find median-of-median

Code:

Obviously the code does not give the result as it is supposed to.

The error is shown below.

Error:

研究一种方法，该方法使用中位数算法的中位数选择一个枢轴来查找数组中的第 k 个最小元素；但是它似乎没有在返回后退出pickCleverPivot：

如果有帮助，假设最初左边是 0，右边是 9，A 是 {1,2,3,4,5,6,7,8,9,10}。

这是方法：