问题标签 [quickselect]

I am struggling with my homework and need a little push- the question is to design an algorithm that will in O(nlogm) time find multiple smallest elements 1<k1<k2<...<kn and you have m *k. I know that a simple selection algorithm takes o(n) time to find the kth element, but how do you reduce the m in your recurrence? I though to do both k1 and kn in each run, but that will only take out 2, not m/2.

Would appreciate some directions. Thanks

问题：我经常需要查看在特定日志的最后一天内重复频率最高的“模式”是什么。就像这里的一小部分 tomcat 日志一样：

如果我想找出最常用的 URL（以及方法和 retcode） - 我会这样做：

如果我想从同一个文件中找出最常用的用户名 - 我会这样做：

上面在小数据集上工作得很好，但是对于更大的输入集 - 性能（复杂性）sort|uniq -c|sort -rn|head -$N是难以忍受的（大约 100 台服务器，每台服务器约 250 个日志文件，每个日志文件约 100 万行）

尝试解决： |sort|uniq -c零件可以很容易地用 awk 1-liner 替换，变成：

但我未能找到“快速选择算法”（在此处讨论）的标准/简单和高效内存实现来优化该|sort -rn|head -$N部分。正在寻找 GNU 二进制文件、rpms、awk 1-liners 或一些我可以在数据中心携带/传播的易于编译的 Ansi C 代码，以转向：

进入（给定 N = 3）：

我可能可以获取示例 Java 代码并将其移植为上述标准输入格式（顺便说一下 - 对.quickselect(...)核心 java 的缺乏感到惊讶） - 但是到处部署 java-runtime 的需要并不吸引人。我也许也可以抓取它的示例（基于数组的）C 片段，然后将其调整为上述标准输入格式，然后测试和修复泄漏等一段时间。或者甚至在 awk 中从头开始实现它。但是（！） - 超过 1% 的人可能经常面临这种简单的需求 - 应该有一个标准的（预先测试的）实现吗？希望...也许我使用了错误的关键字来查找它...

其他障碍：在处理大型数据集时还面临一些问题：

• 日志文件位于约 100 台服务器的 NFS 安装卷上 - 因此将工作并行化并将其拆分为更小的块是有意义的
• 以上awk '{S[$0]+=1}...需要内存 - 我看到它在耗尽 16GB 时会死掉（尽管有 48GB 的​​可用 RAM 和大量交换......也许我忽略了一些 linux 限制）

我目前的解决方案仍然不可靠且不是最佳的（正在进行中）看起来像：

我已经在这几天了，我无法破解这个错误：

背景

我正在尝试使用或多或少严格的CLRS实现来实现有保证的线性时间 SELECT 函数。随机选择，中值枢轴选择，一切都顺利进行，直到我点击了这个。这是代码partition：

这几乎是 CLRS 伪代码的逐字转录（因此基本上没有错误检查），当我编写的其他风格的 SELECT 调用它时它可以工作，所以我认为问题出在线性时间 SELECT ：

我在解释器中手动跟踪它并没有收到任何错误。（我还没有学会如何使用调试器，虽然我花了一个小时左右查看不同的包，比如hammertime。）事实上，由于在错误出现之前进行了改组，如果我再次运行它就可以了：

我认为错误是因为上索引（ 中的第三个参数partition()）超出范围，但我不清楚这是如何发生的。

任何帮助解释此错误，或朝着正确的方向推动找出原因将不胜感激。我觉得我很接近了。

编辑：作为参考，这是我实现该Array#median方法的方式（下中位数）：

我在 github 中找到了此代码，用于quickselect算法，也称为order-statistics. 这段代码工作正常。

我不明白medianOf3方法，它应该按排序顺序排列第一个、中间和最后一个索引。medianof3但实际上在调用方法后输出数组时并没有。除了最后一次调用swap(list, centerIndex, rightIndex - 1);. 有人可以解释为什么会这样吗？

提取 51 个元素的中值，包括将 51 拆分为 25 的 H(ead) 组，然后是中值，然后是 25 的 T(ail)。我知道的所有算法都以H 和 T 的附加属性使得 [min(H), max(H)[ 和 ]min(T), max(T)] 不重叠。

这个附加属性是否被证明是强制性的（我想是的）？我在哪里可以找到证据（我想它已经完成了很长时间）？

（这只是为了热爱算法）

我想知道为什么 QuickSelect 应该是一种性能如此出色的算法，可以从 n 大小的未排序集合中找到任意元素。我的意思是，当你一个一个地遍历所有元素时，直到你找到所需的元素，它需要 O(n) 比较——这就是快速选择的最佳情况，而且容易得多。

我错过了一些重要的东西吗？QiuckSelect 是否存在比线性搜索更好的情况？

我想在未排序列表中找到近似中位数，我知道两种算法

算法1-快速选择

算法 2- 中位数的中位数

我不能在我的项目中使用快速选择，因为在最坏的情况下它需要 O(n^2)。我听说过中位数的中位数，但我的同事建议它需要 O(n) 和一些常数因子。因此它的时间复杂度是 Cn 并且常数因子与快速选择相比很大。我想知道与中位数的中位数相关的常数因子是什么？为什么中位数的中位数不使用 9 元素的伪中位数？
或者他们是否有任何其他算法可以在线性时间 O(n) 中找到近似中位数？

我正在寻找k从输入数组返回顶级元素的有效方法。
一种方法是对数组进行排序并k从数组末尾返回元素。

这里建议了其他方法，其中一种使用quickselect 算法，但据我了解， quickselect 仅返回k未排序数组中的第 - 个元素。在它返回后，左侧和右侧的元素k仍然是未排序的。

所以它应该是这样的：

快速选择是O(n)，我们k多次这样做，所以总体时间复杂度是O(n*k).
但帖子中的数据表明，这比O(n log n).
从一百万个样本中选择前 200 名意味着200 million在前一种情况下，但20 million在后一种情况下。显然这要好得多。

我对如何使用快速选择来选择前 200 个元素的理解是否正确？

该程序应该使用快速选择并返回一组整数值的中位数。

问题：当我运行程序时，它告诉我 k 没有定义。我应该如何定义 k 以获得中位数？

我在理解快速选择算法时遇到问题。我知道它基于快速排序算法（我很熟悉），它可以为您提供所需的结果，可能会使数组的一部分未排序。现在这是我遇到困难的地方。问题是从数组中找到第二个最小的元素：

现在假设我们随机选择枢轴然后根据这篇文章我们有以下条件：

• k == pivot. 那么你已经找到了第 k 个最小的了。这是因为分区的工作方式。恰好有 k - 1 个元素小于第 k 个元素。

• k < pivot. 然后第 k 个最小的在枢轴的左侧。

• k > pivot. 然后第 k 个最小的在枢轴的右侧。要找到它，您实际上必须在右侧找到 k-pivot 最小数字。

如果有人能解释k==pivot 我们如何找到第 k 个（在我的情况下是第二个最小元素），我将不胜感激。此外，如果k < pivot我们是否重复枢轴左侧的过程？