计算大数据集的中位数的内存高效方法？

Question

如果一台计算机只能容纳100万个数字，如何从1亿个数字中找出中位数？

- Stephen Hsu

---

https://dev59.com/7XM_5IYBdhLWcg3wmkQK - Ron

最好的情况下，这可能应该是社区维基。 - Brad Gilbert

这是一个有效的与编程有关的问题，如何以内存高效的方式计算中位数。它只是像一个难题一样出现。 - starblue

使用“中位数的中位数”方法。 - starblue

Answer 1

先进行外部排序，然后扫描一次找到中位数。

希望真正的问题是“如何进行外部排序”？（如果这是作业...我想以正确的方式帮助。 :-)

- DigitalRoss

---

这是我认为的。:) 但我不确定它是否是正确答案，所以我在这里问了一下。 - Stephen Hsu

一定有一种方法可以在设备只能存储100万个数字的字面限制下完成这个任务。使用外部排序似乎有些作弊了。现在我得整晚都想着这个问题了。 - JohnFx

嘿，我也曾想过这个问题。这是一个非常好的问题。 - DigitalRoss

Answer 2

将问题简化为一个更困难的问题：使用归并排序对1亿个数字进行排序，然后取第5000万个元素。

- Pascal Cuoq

---

但是计算机只能存储100万个数字，那我怎么找到第5000万个数字呢？ - Stephen Hsu

在磁盘上（哦，对了，现在已经不是80年代了。我是指“在磁盘上”），在第五千万个位置。你有存储100M元素的空间，对吧？因为如果没有（从流中读取元素），这个练习就可以通过计数论证明是不可能的。 - Pascal Cuoq

100 million个数字取第5000万个元素是不正确的，因为100 million是偶数，所以必须取第5000万个和第5000万个+1个元素的平均值。 - Timofey

Answer 3

使用101台计算机和类似数据库的排序合并。

- tster

---

哈哈。这个答案应该成为最好的程序员笑话！ - Ashwin

我会把它作为我的答案之一。 :) - Stephen Hsu

Answer 4

找到中间的一百万个数字，然后报告它们的中位数。(嗯，现在要如何找到那些中间的一百万个数字呢...)

- PaulMcG