blocks|key|3052518|text|拆分10%5E9个数字，10%5E7分配给每台计算机，每台计算机大约80MB。每台计算机都会对其数字进行排序。然后计算机1合并-将自己的数字与计算机2、计算机3和计算机4等的数字进行排序。然后计算机1将数字的一半写回2、3到4，依此类推。然后1合并对来自计算机1、2、3、4的数字进行排序，将它们写回。诸若此类。根据计算机上RAM的大小，您可能不会在每个步骤中将所有数字写回各个计算机，但您可以将计算机1上的数字累加几个步骤，但您需要进行数学运算。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052519|哦，最终得到500000000th和50000000first值的平均值(但请检查其中是否有足够的00，我没有)。|3052520|编辑：@Roman+--如果你不相信它，即使它是真的，那么我揭示这个命题的真假就没有意义了。我想说的是，在一场比赛中，蛮力有时会击败聪明。我花了大约15秒设计了一个算法，我相信我可以实现这个算法，它将工作，并将适应各种大小的输入和计算机的数量，并可根据计算机和网络安排的特点进行调整。如果你或者其他任何人花了15分钟来设计一个更复杂的算法，我有14m45s的优势来编写我的解决方案并开始运行。|3052521|但我坦率地承认这一切都是断言，我没有测量过任何东西。|3052522|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

Split the 10^9 numbers, 10^7 to each computer ~ 80MB on each. Each computer sorts its numbers. Then computer 1 merge-sorts its own numbers with those from computer 2, computer 3 and 4, etc ... Then computer 1 writes half of the numbers back to 2, 3 to 4, etc. Then 1 merge sorts the numbers from computers 1,2,3,4, writes them back. And so on. Depending on the size of RAM on the computers you may get away with not writing all the numbers back to the individual computers at each step, you might be able to accumulate the numbers on computer 1 for several steps, but you do the maths.

Oh, finally get the mean of the 500000000th and 500000001st values (but check there are enough 00s in there, I haven't).

EDIT: @Roman -- well if you can't believe it even it it's true then there's no point in my revealing the truth or falsehood of the proposition. What I meant to state was that brute force sometimes beats smart in a race. It took me about 15 seconds to devise an algorithm which I am confident that I can implement, which will work, and which will be adaptable to a wide range of sizes of inputs and numbers of computers, and tunable to the characteristics of the computers and networking arrangements. If it takes you, or anyone else, say 15 minutes to devise a more sophisticated algorithm I have a 14m45s advantage to code up my solution and start it running.

But I freely admit this is all assertion, I haven't measured anything.

blocks|key|314725|text|一台计算机足以解决这个问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|314726|但让我们假设有100台计算机。您应该做的唯一复杂的事情就是对列表进行排序。将它分成100个部分，将一个部分发送到每台计算机，让它们在那里排序，然后合并部分。|314727|然后从排序列表的中间取数字(即索引为5+000+000+000)。|314728|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

One computer is more than enough to solve the problem.

But let's assume that there are 100 computers. The only complex thing you should do is to sort the list. Split it to 100 parts, send one part to each computer, let them be sorted there, and merge parts after that.

Then take number from the middle of the sorted list (i.e. with index 5 000 000 000).

blocks|key|309704|text|sort+-g+numbers+%7C+head+-n+500000001+%7C+tail+-n+2+%7C+dc+-e+"1+k+?+?+%2B+2+/+p"|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|309705|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
</code></pre>

blocks|key|312685|text|啊，我的大脑刚刚开始运转，我现在有一个明智的建议。如果这是一次面试，可能已经太晚了，但没关系：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312686|机器1应称为“控制机器”，为了便于论证，它要么从所有数据开始，然后将其以相等的包发送给其他99台机器，要么开始在机器之间均匀分配数据，并将其数据的1/99发送给其他每台机器。分区不必相等，只需接近即可。|312687|每台机器对其数据进行排序，并以一种倾向于首先找到较低值的方式进行排序。例如，快速排序，总是先对分区的较低部分进行排序*。它尽快将其数据以递增的顺序写回控制机器(使用异步IO以便继续排序，并可能使用Nagle+on:实验一下)。|312688|控制机器在数据到达时对其执行99路合并，但丢弃合并后的数据，仅对它看到的值的数量进行计数。它将中位数计算为1/2亿分之一和1/2亿加1的平均值。|312689|这是一个“群体中最慢”的问题。直到分选机发送了小于中位数的每个值，该算法才能完成。有一个合理的机会，其中一个这样的值将在其数据包中相当高。因此，一旦完成数据的初始分区，估计的运行时间是排序1/99的数据并将其发送回控制计算机的时间和控件读取1/2数据的时间的组合。“组合”是介于这些时间的最大值和总和之间的某个地方，可能接近最大值。|312690|我的直觉是，为了通过网络发送数据比排序更快(更不用说只选择中位数了)，它需要一个非常快的网络。如果可以假定网络是即时的，则可能是一个更好的前景，例如，如果您有100个内核，可以平等地访问包含数据的RAM。|312691|由于网络I/O很可能是受限制的，因此可能会有一些技巧可以使用，至少对于返回到控制计算机的数据是这样。例如，不发送"1,2,3，..+100"，也许分类机可以发送一条消息，意思是"100个值小于101“。然后，控制机器可以执行修改的合并，在该合并中，它找到所有那些范围顶端的值中的最小值，然后告诉所有排序机器它是什么，这样它们就可以(a)告诉控制机器有多少值比该值“计数”，以及(b)从这一点开始发送它们的排序数据。|312692|更广泛地说，可能有一个巧妙的挑战-响应猜测游戏，控制机器可以与99台分拣机一起玩。|312693|然而，这涉及到机器之间的往返，而我的更简单的第一个版本避免了这一点。我真的不知道如何盲目估计它们的相对性能，而且由于权衡是复杂的，我认为有比我自己认为的任何解决方案更好的解决方案，假设这是一个真正的问题。|312694|*可用堆栈允许-如果您没有O(N)额外空间，那么您对先做哪一部分的选择会受到限制。但是如果你确实有足够的额外空间，你可以随意选择，如果你没有足够的空间，你至少可以使用你必须做的一些角落，通过首先为前几个分区做小部分。|312695|entityMap^0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Y|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|Z|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|10|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|11|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|12|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|13|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|14|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|U|$]]

Ah, my brain has just kicked into gear, I have a sensible suggestion now. Probably too late if this had been an interview, but never mind:

Machine 1 shall be called the "control machine", and for the sake of argument either it starts with all the data, and sends it in equal parcels to the other 99 machines, or else the data starts evenly distributed between the machines, and it sends 1/99 of its data to each of the others. The partitions do not have to be equal, just close.

Each other machine sorts its data, and does so in a way which favours finding the lower values first. So for example a quicksort, always sorting the lower part of the partition first[*]. It writes its data back to the control machine in increasing order as soon as it can (using asynchronous IO so as to continue sorting, and probably with Nagle on: experiment a bit).

The control machine performs a 99-way merge on the data as it arrives, but discards the merged data, just keeping count of the number of values it has seen. It calculates the median as the mean of the 1/2 billionth and 1/2 billion plus oneth values.

This suffers from the "slowest in the herd" problem. The algorithm cannot complete until every value less than the median has been sent by a sorting machine. There's a reasonable chance that one such value will be quite high within its parcel of data. So once the initial partitioning of the data is complete, estimated running time is the combination of the time to sort 1/99th of the data and send it back to the control computer, and the time for the control to read 1/2 the data. The "combination" is somewhere between the maximum and the sum of those times, probably close to the max.

My instinct is that for sending data over a network to be faster than sorting it (let alone just selecting the median) it needs to be a pretty damn fast network. Might be a better prospect if the network can be presumed to be instantaneous, for example if you have 100 cores with equal access to RAM containing the data.

Since network I/O is likely to be the bound, there might be some tricks you can play, at least for the data coming back to the control machine. For example, instead of sending "1,2,3,.. 100", perhaps a sorting machine could send a message meaning "100 values less than 101". The control machine could then perform a modified merge, in which it finds the least of all those top-of-a-range values, then tells all the sorting machines what it was, so that they can (a) tell the control machine how many values to "count" below that value, and (b) resume sending their sorted data from that point.

More generally, there's probably a clever challenge-response guessing game that the control machine can play with the 99 sorting machines.

This involves round-trips between the machines, though, which my simpler first version avoids. I don't really know how to blind-estimate their relative performance, and since the trade-offs are complex, I imagine there are much better solutions out there than anything I'll think of myself, assuming this is ever a real problem.

[*] available stack permitting - your choice of which part to do first is constrained if you don't have O(N) extra space. But if you do have enough extra space, you can take your pick, and if you don't have enough space you can at least use what you do have to cut some corners, by doing the small part first for the first few partitions.

blocks|key|311896|text|这个怎么样：-每个节点可以接受10亿/100个数字。在每个节点上，可以对元素进行排序，并且可以找到中值。找出中位数的中位数。我们可以通过聚合所有节点上小于中位数中位数的计数，找出中位数所造成的x%25:y%25分裂。现在要求所有节点删除小于中位数中位数的元素(以30%25:70%25拆分为例)删除.30%25编号。10亿的70%25是7亿。现在，所有删除了少于300万个节点的节点都可以将这些额外的节点发送回主计算机。主计算机以这样的方式重新分布，现在所有节点将具有几乎相等的节点数量(700万)。现在问题已经减少到7亿个数字...继续下去，直到我们有一个更小的集合，可以在一个comp上计算。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|311897|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

How about this:- each node can take 1Billion/100 numbers. At each node the elements can be sorted and median can be found. Find the median of medians. we can, by aggregating the counts of numbers less than median-of-median on all nodes find out x%:y% split which the median-of-medians makes. Now ask all nodes to delete elements less than the median of medians( taking example of 30%:70% split).30% numbers are deleted. 70% of 1Billion is 700million. Now all nodes which deleted less than 3million nodes can send those extra nodes back to a main computer. The main computer redistributes in such a way that now all nodes will have almost equal number of nodes(7million). Now that the problem is reduced to 700million numbers.... goes on until we have a smaller set which can be computed on one comp.

blocks|key|309763|text|奇怪的是，我认为如果你有足够的计算机，你最好进行排序，而不是使用O(n)中值查找算法。(不过，除非您的内核非常、非常慢，否则我只会使用一个，仅对1e9数字使用O(n)中值查找算法；但是，如果您有1e12，这可能就不太实用了。)|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|309764|无论如何，让我们假设我们有超过log个内核来处理这个问题，并且我们不关心功耗，只是快速地得到答案。让我们进一步假设这是一台SMP机器，所有数据都已加载到内存中。(例如，Sun的32核计算机就属于这种类型。)|309765|一个线程盲目地将列表分割成大小相等的部分，并告诉其他M个线程对它们进行排序。这些线程在(n/M)+log+(n/M)时间内勤奋地这样做。然后，它们不仅返回中位数，还返回第25和75个百分位数(如果您选择稍微不同的数字，反常的最坏情况会更好)。现在您有了4M范围的数据。然后对这些范围进行排序，并向上遍历列表，直到找到一个数字，如果您丢弃了小于或包含该数字的每个区域，您将丢弃一半的数据。这是中位数的下限。对上限执行相同的操作。这需要像M+log+M这样的时间，而且所有内核都必须等待，所以这真的是在浪费M%5E2+log+M潜在的时间。现在，您让您的单个线程告诉其他线程丢弃范围外的所有数据(每次都应该抛出大约一半)，然后重复--这是一个非常快的操作，因为数据已经排序好了。在获取剩余数据并使用标准O(n)中值查找器之前，您不应该重复此操作超过log(n/M)次。|309766|因此，总的复杂性类似于O((n/M)+log+(n/M)+%2B+M%5E2+log+M+log+(n/M))。因此，在M+>>+log(n/M)和M%5E3+log+M+<+n的情况下，这比在一个核上进行O(n)中值排序更快，对于您描述的场景是正确的。|309767|我认为这是一个非常糟糕的想法，因为它的效率很低，但它更快。|309768|entityMap^0|W|4|27|4|0|0|17|F|61|7|6Z|9|9N|4|AA|8|0|B|14|1K|D|1Y|D|2P|4|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]|$9|S|A|T|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|U|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|V|8|@$9|W|A|X|B|C]|$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]]|D|@]|E|$]]|$1|J|3|K|5|6|7|16|8|@$9|17|A|18|B|C]|$9|19|A|1A|B|C]|$9|1B|A|1C|B|C]|$9|1D|A|1E|B|C]]|D|@]|E|$]]|$1|L|3|M|5|6|7|1F|8|@]|D|@]|E|$]]|$1|N|3|-4|5|6|7|1G|8|@]|D|@]|E|$]]]|O|$]]

Oddly enough, I think if you have enough computers, you're better off sorting than using <code>O(n)</code> median-finding algorithms. (Unless your cores are very, very slow, though, I'd just use one and use an <code>O(n)</code> median-finding algorithm for merely 1e9 numbers; if you had 1e12, though, that might be less practical.)

Anyway, let's suppose we have more than log n cores to deal with this problem, and we don't care about power consumption, just getting the answer fast. Let's further assume that this is a SMP machine with all the data already loaded in memory. (Sun's 32-core machines are of this type, for instance.)

One thread chops the list up blindly into equal sized pieces and tells the other M threads to sort them. Those threads diligently do so, in <code>(n/M) log (n/M)</code> time. They then return not only their medians, but, say, their 25th and 75th percentiles as well (perverse worst cases are better if you choose slightly different numbers). Now you have 4M ranges of data. You then sort these ranges and work upwards through the list until you find a number such that, if you throw out every range that is smaller than or contains the number, you will have thrown out half your data. That's your lower bound for the median. Do the same for the upper bound. This takes something like <code>M log M</code> time, and all cores have to wait for it, so it's really wasting <code>M^2 log M</code> potential time. Now you have your single thread tell the others to toss all data outside the range (you should throw out about half on each pass) and repeat--this is a trivially fast operation since the data is already sorted. You shouldn't have to repeat this more than <code>log(n/M)</code> times before it's faster to just grab the remaining data and use a standard <code>O(n)</code> median finder on it.

So, total complexity is something like <code>O((n/M) log (n/M) + M^2 log M log (n/M))</code>. Thus, this is faster than <code>O(n)</code> median sort on one core if <code>M &gt;&gt; log(n/M)</code> and <code>M^3 log M &lt; n</code>, which is true for the scenario you've described.

I think this is a really bad idea given how inefficient it is, but it is faster.

blocks|key|309843|text|我讨厌在这里做逆向投资者，但我不认为排序是必需的，而且我认为任何涉及对十亿/100个数字进行排序的算法都将是缓慢的。让我们考虑一台计算机上的一个算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309844|1)从十亿中随机选择1000个值，并使用它们来了解数字的分布情况，特别是范围。|309845|2)不是对值进行排序，而是根据您刚才计算的分布将其分配到存储桶中。选择存储桶的数量是为了使计算机能够有效地处理它们，但在其他情况下应该尽可能大。存储桶范围应该使每个存储桶中的值数量大致相等(这对算法并不关键，但有助于提高效率。100,000个存储桶可能是合适的)。注意每个存储桶中的值的数量。这是一个O(n)过程。|309846|3)找出中位数所在的存储桶范围。这可以通过简单地检查每个存储桶中的总数来完成。|309847|4)通过检查该桶中的值来找到实际的中位数。如果您愿意，您可以在这里使用排序，因为您只能对大约10,000个数字进行排序。如果该存储桶中的值的数量很大，则可以再次使用此算法，直到有足够小的值进行排序。|309848|这种方法通过在计算机之间划分值来实现微不足道的并行。每台计算机将每个存储桶中的总和报告给执行步骤3的“控制”计算机。对于步骤4，每台计算机将相关存储桶中的(排序的)值发送到控制计算机(您也可以并行执行这两个算法，但可能不值得这样做)。|309849|整个过程是O(n)，因为只要存储桶的数量足够大，步骤3和4都是微不足道的。|309850|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|S|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

I hate to be the contrarian here, but I don't believe sorting is required, and I think any algorithm involving sorting a billion/100 numbers is going to be slow. Let's consider an algorithm on one computer.

1) Select 1000 values at random from the billion, and use them to get an idea of the distribution of the numbers, especially a range. 

2) Instead of sorting the values, allocate them to buckets based on the distribution you just calculated. The number of buckets is chosen so that the computer can handle them efficiently, but should otherwise be as large as convenient. The bucket ranges should be so that approximately equal numbers of values go in each bucket (this isn't critical to the algorithm, but it helps efficiency. 100,000 buckets might be appropriate). Note the number of values in each bucket. This is an O(n) process.

3) Find out which bucket range the median lies. This can be done by simply examining the total numbers in each bucket. 

4) Find the actual median by examining the values in that bucket. You can use a sort here if you like, since you are only sorting maybe 10,000 numbers. If the number of values in that bucket is large then you can use this algorithm again until you have a small enough number to sort.

This approach parallelizes trivially by dividing the values between the computers. Each computer reports the totals in each bucket to a 'control' computer which does step 3. For step 4 each computer sends the (sorted) values in the relevant bucket to the control computer (you can do both of those algorithms in parallel too, but it probably isn't worth it).

The total process is O(n), since both steps 3 and 4 are trivial, provided the number of buckets is large enough.

blocks|key|314911|text|让我们首先找出如何在一台机器上找到n个数字的中位数:我基本上是使用分区策略。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|314912|问题:选择(n，n/2)+:从最小数中找出第n/2个数。|offset|length|style|BOLD|314913|您选择中间元素k，并将数据划分为两个子数组。第一个包含所有元素<+k，第二个包含所有元素>=+k。|314914|如果sizeof(第一个子数组)为n/2，则您知道此子数组包含中位数。然后，您可以抛出第二个子数组。解决这个问题的选择(第一个子数组的大小，n/2)。|314915|在其他情况下，丢弃第一个子数组并求解大小选择(第二个子数组，n/2+-(第一个子数组))|314916|递归地做。|314917|时间复杂度是+O(n)期望时间。|314918|现在，如果我们有许多机器，在每次迭代中，我们必须处理一个要拆分的数组，我们将该数组分配到不同的机器中。每台机器处理自己的数组块，向集线器控制机返回摘要，即第一子阵列的大小和第二子阵列的大小。集线器将摘要相加，并决定进一步处理哪个子阵列(第一或第二子阵列)和第二个选择参数，并将其发送回每台机器。诸若此类。|314919|使用map+reduce可以非常灵活地实现此算法。|314920|看起来怎么样？|314921|entityMap^0|0|0|E|0|0|0|Z|9|0|0|0|6|0|1S|V|0|0|0^^$0|@$1|2|3|4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|10|8|@$D|11|E|12|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|13|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|14|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|15|8|@$D|16|E|17|F|G]]|9|@]|A|$]]|$1|N|3|O|5|6|7|18|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|19|8|@$D|1A|E|1B|F|G]]|9|@]|A|$]]|$1|R|3|S|5|6|7|1C|8|@$D|1D|E|1E|F|G]]|9|@]|A|$]]|$1|T|3|U|5|6|7|1F|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1G|8|@]|9|@]|A|$]]|$1|X|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|Y|$]]

Let's first work out how to find a median of n numbers on a single machine:
I am basically using partitioning strategy.

Problem :selection(n,n/2) : Find n/2 th number from least number.

You pick say middle element k and partition data into 2 sub arrays. the 1st contains all elements &lt; k and 2nd contains all elements >= k.

if sizeof(1st sub-array) >= n/2, you know that this sub-array contains the median. You can then throw-off the 2nd sub-array. Solve this problem selection(sizeof 1st sub-array,n/2). 

In else case, throw off this 1st subarray and solve selection(2nd subarray , n/2 - sizeof(1st subarray))

Do it recursively.

time complexity is O(n) expected time.

Now if we have many machines, in each iteration, we have to process an array to split, we distribute the array into diff machines. Each machine processes their chunk of array and sends back the summary to hub controlling machine i.e. size of 1st subarray and size of 2nd subarray. The hub machines adds up summaries and decide which subarray (1st or 2nd) to process further and 2nd parameter of selection and sends it back to each machine.
and so on.

This algorithm can be implemented very neatly using map reduce?

How does it look?

blocks|key|3052885|text|这组数字的中位数|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052886|2、3、5、7、11、13、67、71、73、79、83、89、97|3052887|是67岁。|3052888|3052889|3、5、7、11、13、67、71、73、79、83、89|3052890|是40。|3052891|假设问题是大约1,000,000,000个整数(X)，其中0+>=+x+<=+2,147,483,647，并且OP正在查找(element(499,999,999,999)%2B+element(500,000,000))+/2(如果对数字进行了排序)。还假设所有100台计算机都相等。|offset|length|style|BOLD|3052892|用我的笔记本和GigE..。|3052893|我发现我的笔记本电脑可以在1.3秒内对1000万个Int32进行排序。因此，粗略估计一个十亿次数字排序将需要100+x+1.3秒(2分10秒)+;)。|3052894|千兆位以太网上40MB文件的单向文件传输估计为.32秒。这意味着来自所有计算机的排序结果将在大约32秒内返回(计算机99直到启动后30秒才得到他的文件)。从那时起，丢弃最低的499,999,998个数字，添加下一个2并除以2应该不会花很长时间。|3052895|entityMap^0|0|0|0|0|0|0|3H|G|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Z|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|10|8|@]|9|@]|A|$]]|$1|F|3|4|5|6|7|11|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|12|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|13|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|14|8|@$M|15|N|16|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|17|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|18|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|19|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|1A|8|@]|9|@]|A|$]]]|X|$]]

The median for this set of numbers

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97

is 67.

The median for this set of numbers

2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89

is 40.

Assuming the question was about 1,000,000,000 integers(x) where 0 >= x &lt;= 2,147,483,647 and that the OP was looking for (element(499,999,999) + element(500,000,000)) / 2 (if the numbers were sorted). Also assuming that all 100 computers were all equal.

using my laptop and GigE...

What I found was that my laptop can sort 10,000,000 Int32's in 1.3 seconds. So a rough estimate would be that a billion number sort would take 100 x 1.3 seconds(2 minutes 10 seconds) ;).

An estimate of a one-way file transfer of a 40MB file on a gigabit Ethernet is .32 seconds. This means that the sorted results from all computers will be returned in approximately 32 seconds(computer 99 didn't get his file until 30 seconds after the start). From there it shouldn't take long to discard the lowest 499,999,998 numbers, add the next 2 and divide by 2.

blocks|key|3052989|text|我认为Steve+Jessop的回答会是最快的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052990|如果网络数据传输的大小是瓶颈，这里有另一种方法。|offset|length|style|BOLD|3052991|Divide+the+numbers+into+100+computers+(10+MB+each).+
Loop+until+we+have+one+element+in+each+list+++++
++++Find+the+meadian+in+each+of+them+with+quickselect+which+is+O(N)+and+we+are+processing+in+parallel.+The+lists+will+be+partitioned+at+the+end+wrt+median.
++++Send+the+medians+to+a+central+computer+and+find+the+median+of+medians.+Then+send+the+median+back+to+each+computer.+
++++For+each+computer,+if+the+overall+median+that+we+just+computed+is+smaller+than+its+median,+continue+in+the+lower+part+of+the+list+(it+is+already+partitioned),+and+if+larger+in+the+upper+part.
When+we+have+one+number+in+each+list,+send+them+to+the+central+computer+and+find+and+return+the+median.|code-block|syntax|javascript|3052992|entityMap^0|0|9|2|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@$D|Q|E|R|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|S|8|@]|9|@]|A|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

I think Steve Jessop's answer will be the fastest.

If the network data transfer size is the bottleneck, here is another approach.

<pre><code>Divide the numbers into 100 computers (10 MB each). 
Loop until we have one element in each list 
 Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
 Send the medians to a central computer and find the median of medians. Then send the median back to each computer. 
 For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.
</code></pre>

blocks|key|3053025|text|这可以比投票的算法更快(n+log+n)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3053026|3053027|顺序统计量分布式选择算法-+O(n)|unordered-list-item|3053028|3053029|将问题简化为在未排序的array.|3053030|Counting排序直方图O(n)中寻找第k个数的原始问题|3053031|3053032|你必须假设一些关于数字范围的属性--范围能放在内存中吗？-外部合并排序-+O(n+log+n)+-如上所述|3053033|你基本上是对第一遍的数字进行排序，然后找出第二遍的中位数。，|3053034|，如果知道任何关于数字分布的信息，就可以产生其他算法。|3053035|3053036|有关更多详细信息和实现，请参阅：|3053037|http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html|offset|length|3053038|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|0|0|0|0|0|0|0|0|0|0|1Z|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|16|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|17|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|18|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|19|8|@]|9|@]|A|$]]|$1|I|3|J|5|E|7|1A|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1C|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1D|8|@]|9|@]|A|$]]|$1|P|3|Q|5|E|7|1E|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|1F|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|1G|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1H|8|@]|9|@$W|1I|X|1J|1|1K]]|A|$]]|$1|Y|3|-4|5|6|7|1L|8|@]|9|@]|A|$]]]|Z|$10|$5|11|12|13|A|$14|V]]]]

This can be done faster than the algorithm voted (n log n) 
 
 - Order statistics distributed selection algorithm - O(n) 
Simplify the problem to the original problem of finding the kth number in an unsorted array. 
 - Counting sort histogram O(n) 
You have to assume some properties about the range of the numbers - can the range fit in the memory?
 - External merge sort - O(n log n) - described above 
You basically sort the numbers on the first pass, then find the median on the second. 
 - If anything is known about the distribution of the numbers other
 algorithms can be produced.
 
For more details and implementation see: 
<a href="http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html" rel="nofollow">http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html</a>

blocks|key|312970|text|Steve+Jessop的答案是错误的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312971|考虑以下四组：|312972|{2，4，6，8，10}|312973|{21，21，24，26，28}|312974|{12，14，30，32，34}|312975|{16，18，36，38，40}|312976|中位数是21，包含在第二组中。|312977|四组的中位数分别为6、24、30、36，总中位数为27。|312978|因此，在第一个循环之后，这四个组将变成：|312979|{6，8，10}|312980|{24，26，28}|312981|{12，14，30}|312982|{16，18，36}|312983|21已经被错误地丢弃了。|312984|该算法仅支持有两个组的情况。|312985|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|15|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|16|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|17|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|18|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|19|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1A|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|1B|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|1C|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|1D|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|1E|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|1F|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1G|8|@]|9|@]|A|$]]|$1|X|3|Y|5|6|7|1H|8|@]|9|@]|A|$]]|$1|Z|3|10|5|6|7|1I|8|@]|9|@]|A|$]]|$1|11|3|12|5|6|7|1J|8|@]|9|@]|A|$]]|$1|13|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]]|14|$]]

Steve Jessop's answer is wrong:

consider the following four groups:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

The median is 21, which is contained in the second group.

The median of the four groups are 6, 24, 30, 36, The total median is 27.

So after the first loop, the four groups will become:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

The 21 is already wrongly discarded.

This algorithm only support the case when there are two groups.

blocks|key|3053214|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3053215|将10亿个数字分成100台机器。每台计算机将有10%5E7个数字。|ordered-list-item|3053216|对于计算机中的每个传入号码，将该数字存储在频率图number+->+count中。|3053217|查找每台机器的中位数:从每台机器的最小数开始，将计数相加，直到达到中位数索引。每台机器的中位数将约为。小于和大于5*10%5E6的数字。|3053218|查找所有中位数的中位数，这将小于和大于近似。50*10%5E7个数字，这是10亿个数字的中位数。|3053219|3053220|现在对第二步进行一些优化:将计数存储在可变位数组中，而不是存储在频率映射中。例如:假设从机器中的最小数字开始，这些是频率计数：|3053221|[min+number]+-+8+count
[min%2B1+number]+-+7+count
[min%2B2+number]+-+5+count|code-block|syntax|javascript|3053222|以上内容可以存储在位数组中，如下所示：|3053223|[min+number]+-+10000000
[min%2B1+number]+-+1000000
[min%2B2+number]+-+10000|3053224|请注意，每台机器总共需要花费大约10%5E7位，因为每台机器只能处理10%5E7个数字。10%5E7bits+=+1.25*10%5E6字节，即1.25MB|3053225|因此，使用上面的方法，每台机器将需要1.25MB的空间来计算局部中值。中位数可以从这100个本地中位数计算出来，结果是10亿个数字的中位数。|3053226|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|-4|4|5|6|11|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|12|7|@]|8|@]|9|$]]|$1|D|3|E|4|C|6|13|7|@]|8|@]|9|$]]|$1|F|3|G|4|C|6|14|7|@]|8|@]|9|$]]|$1|H|3|I|4|C|6|15|7|@]|8|@]|9|$]]|$1|J|3|-4|4|5|6|16|7|@]|8|@]|9|$]]|$1|K|3|L|4|5|6|17|7|@]|8|@]|9|$]]|$1|M|3|N|4|O|6|18|7|@]|8|@]|9|$P|Q]]|$1|R|3|S|4|5|6|19|7|@]|8|@]|9|$]]|$1|T|3|U|4|O|6|1A|7|@]|8|@]|9|$P|Q]]|$1|V|3|W|4|5|6|1B|7|@]|8|@]|9|$]]|$1|X|3|Y|4|5|6|1C|7|@]|8|@]|9|$]]|$1|Z|3|-4|4|5|6|1D|7|@]|8|@]|9|$]]]|10|$]]

<ol>
<li>Divide the 1 billion numbers into 100 machines. Each machine will have 10^7 numbers.</li>
<li>For each incoming number to a machine, store the number in a frequency map, 
number -> count. Also store the min number in each machine.</li>
<li>Find median in each machine: starting from min number in each machine, sum the counts until median index is reached. The median in each machine, will be the approx. lesser and greater than 5*10^6 numbers.</li>
<li>Find median of all medians, which will be lesser and greater than approx. 50*10^7 numbers, which is the median of 1 billion numbers.</li>
</ol>

Now some optimization of 2nd step: Instead of storing in a frequency map, store the counts in a variable bit array. For example: Lets say starting from min number in a machine, these are frequency counts:

<pre><code>[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count
</code></pre>

The above can be stored in bit array as:

<pre><code>[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000
</code></pre>

Note that altogether it will cost about 10^7 bits for each machine, since each machine only handles 10^7 numbers. 10^7bits = 1.25*10^6 bytes, which is 1.25MB

So with the above approach each machine will need 1.25MB of space to compute local median. And median of medians can be computed from those 100 local medians, resulting in median of 1 billion numbers.

blocks|key|3266833|text|可以通过以下方式在节点上使用未跨节点排序的数据(例如，从日志文件中)来完成此操作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3266834|有1个父节点和99个子节点。子节点有两个api调用：|3266835|3266836|unordered-list-item|3266837|()：返回最小值、最大值和最大值，返回计数匹配值、计数小于值和计数大于值|3266838|父节点在所有子节点上调用stats()，指出所有节点的最小和最大值。|3266839|现在可以通过以下方式执行二进制搜索：|3266840|3266841|将最小和最大四舍五入一分为二-如果大于计数大于小于计数，则这是中位数‘|ordered-list-item|3266842|’|3266843|；如果大于计数小于小于计数，则将最小值设置为guess|3266844|；如果计数为奇数，则将最大值设置为guess|3266845|；如果最小值和最大值相等，则将最大值设置为finish+<|3266846|>H115如果计数为偶数完成时，最大值和最小值%2B+guess.match_count。可以使用以下方式在使用未排序数据(例如来自日志文件)的节点上完成此操作。H216<代码>G217|3266847|3266848|3266849|3266850|3266851|3266852|3266853|3266854|将最小和最大四舍五入一分为二-如果大于计数大于小于计数，则将最小值设置为|3266855|；如果大于计数小于小于计数，则将最大计数设置为猜测结束计数；如果计数为奇数，则将最大计数设置为猜测|3266856|；如果最小值和最大计数相等，则将最大值设置为|3266857|<|3266858|>H133如果计数为偶数，则在最大计数最小值和最大值相等的情况下完成|3266859|3266860|如果计数为偶数完成，则将最大值设置为|3266861|3266862|3266863|如果stats()和compare()可以使用O(N/Mlogn/M)排序进行预计算，那么对于预计算，内存复杂度为O(N)的O(N/M)预计算。然后，您可以在固定时间内执行compare()，因此整个程序(包括预计算)将在O(N/MlogN/M)%2BO(logN)中运行。|3266864|如果我弄错了，请告诉我！|3266865|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1T|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|1U|8|@]|9|@]|A|$]]|$1|E|3|-4|5|F|7|1V|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|1W|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|1X|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|1Z|8|@]|9|@]|A|$]]|$1|N|3|O|5|P|7|20|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|21|8|@]|9|@]|A|$]]|$1|S|3|T|5|P|7|22|8|@]|9|@]|A|$]]|$1|U|3|V|5|P|7|23|8|@]|9|@]|A|$]]|$1|W|3|X|5|P|7|24|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|25|8|@]|9|@]|A|$]]|$1|10|3|C|5|6|7|26|8|@]|9|@]|A|$]]|$1|11|3|-4|5|6|7|27|8|@]|9|@]|A|$]]|$1|12|3|-4|5|F|7|28|8|@]|9|@]|A|$]]|$1|13|3|H|5|6|7|29|8|@]|9|@]|A|$]]|$1|14|3|J|5|6|7|2A|8|@]|9|@]|A|$]]|$1|15|3|L|5|6|7|2B|8|@]|9|@]|A|$]]|$1|16|3|-4|5|6|7|2C|8|@]|9|@]|A|$]]|$1|17|3|18|5|P|7|2D|8|@]|9|@]|A|$]]|$1|19|3|1A|5|P|7|2E|8|@]|9|@]|A|$]]|$1|1B|3|1C|5|P|7|2F|8|@]|9|@]|A|$]]|$1|1D|3|1E|5|P|7|2G|8|@]|9|@]|A|$]]|$1|1F|3|1G|5|6|7|2H|8|@]|9|@]|A|$]]|$1|1H|3|-4|5|P|7|2I|8|@]|9|@]|A|$]]|$1|1I|3|1J|5|P|7|2J|8|@]|9|@]|A|$]]|$1|1K|3|-4|5|P|7|2K|8|@]|9|@]|A|$]]|$1|1L|3|-4|5|6|7|2L|8|@]|9|@]|A|$]]|$1|1M|3|1N|5|6|7|2M|8|@]|9|@]|A|$]]|$1|1O|3|1P|5|6|7|2N|8|@]|9|@]|A|$]]|$1|1Q|3|-4|5|6|7|2O|8|@]|9|@]|A|$]]]|1R|$]]

This could be done on nodes using data that is not sorted across nodes (say from log files) in the following manner.

There is 1 parent node and 99 child nodes. The child nodes have two api calls:

<ul>
<li>stats(): returns min, max and count</li>
<li>compare(median_guess): returns count matching value, count less than value and count greater than value</li>
</ul>

The parent node calls stats() on all child nodes, noting the minimum and maximum of all nodes.

A binary search may now be conducted in the following way:

<ol>
<li>Bisect the minimum and maximum rounding down - this is the median 'guess'</li>
<li>If the greater than count is more than the less than count, set the minimum to the guess</li>
<li>If the greater than count is less than the less than count, set the maximum to the guess</li>
<li>If count is odd finish when minimum and maximum are equal</li>
<li>If count is even finish when maximum &lt;= minimum + guess.match_count
This could be done on nodes using unsorted data (say from log files) in the following manner.</li>
</ol>

There is 1 parent node and 99 child nodes. The child nodes have two api calls:

<ul>
<li>stats(): returns min, max and count</li>
<li>compare(median_guess): returns count matching value, count less than value and count greater than value</li>
</ul>

The parent node calls stats() on all child nodes, noting the minimum and maximum of all nodes.

A binary search may now be conducted in the following way:

<ol>
<li>Bisect the minimum and maximum rounding down - this is the median 'guess'</li>
<li>If the greater than count is more than the less than count, set the minimum to the guess</li>
<li>If the greater than count is less than the less than count, set the maximum to the guess</li>
<li>If count is odd finish when minimum and maximum are equal</li>
<li>If count is even finish when maximum &lt;= minimum + guess.match_count</li>
</ol>

If the stats() and compare() could be pre-calculated with a O(N/Mlogn/M) sort, then a O(N/M) pre-calculation with a memory complexity of O(N) for the pre-calculation. Then you could do compare() in constant time, so the whole thing (including pre-calculation) would run in O(N/MlogN/M)+O(logN)

Let me know if I have made a mistake!

blocks|key|3266961|text|我会这样做：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3266962|在开始时，所有的100人都在寻找最高和最低的数字；每台计算机都有它所查询的数据库/文件的一部分；|3266963|当找到最高和最低的数字时，一台计算机读取数据，并将每个数字均匀地分配给99个数字的其余部分；这些数字按等间隔分布；(一个数字可以从-1亿到0，另一个可以从0到1亿，等等)；|3266964|在接收数字时，99台计算机中的每一台都已经对它们进行了排序；|3266965|然后，很容易找到中位数...查看每台计算机有多少个数字，将所有数字相加(有多少个数字之和，而不是数字本身)，除以2；计算哪台计算机中的数字，以及在哪个索引上；|3266966|:)+voilla|3266967|附注:这里似乎有很多混淆；中位数-是排序后的数字列表中间的数字！|3266968|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|S|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

I would do it like this:

in the beginning all 100 work to find the highest and the lowest number; each of the computer has his part of the database/file which it queries;

when the highest and lowest numbers are found, one computer reads the data, and distributes each number, evenly, to the rest of the 99; the numbers are distributed by equal intervals; (one may take from -100 million to 0, another - from 0 to 100 million, etc);

While receiving numbers, each of the 99 of the computers already sorts them;

Then, it's easy to find the median... See how many numbers has each computer, add all of them (the sum of how many numbers there are, not the numbers themselves), divide by 2; calculate in which computer is the number, and at which index;

:) voilla

P.S. Seems there's a lot of confusion here; the MEDIAN - is the NUMBER IN THE MIDDLE OF A SORTED LIST OF NUMBERS!

blocks|key|312194|text|顺序统计量的估计，如中位数和99%25，可以使用t-digest或Q-digest等算法有效地分布。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|312195|使用这两种算法，每个节点都会生成一个摘要，该摘要表示本地存储的值的分布。摘要在单个节点上收集，合并(有效地对分布求和)，然后可以查找中位数或任何其他百分位数。|312196|elasticsearch和BigQuery+(按照分位数函数的描述)都使用这种方法。|312197|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/tdunning/t-digest|1|http://www.inf.fu-berlin.de/lehre/WS11/Wireless/papers/AgrQdigest.pdf|2|https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations-metrics-percentile-aggregation.html|3|https://cloud.google.com/bigquery/query-reference#aggfunctions^0|M|8|0|V|8|1|0|0|0|D|2|E|8|3|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]|$A|Z|B|10|1|11]]|C|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|13|8|@]|9|@$A|14|B|15|1|16]|$A|17|B|18|1|19]]|C|$]]|$1|H|3|-4|5|6|7|1A|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]|R|$5|K|L|M|C|$N|S]]|T|$5|K|L|M|C|$N|U]]]]

The estimation of order statistics like median and 99th percentile can be efficiently distributed with algorithms like <a href="https://github.com/tdunning/t-digest">t-digest</a> or <a href="http://www.inf.fu-berlin.de/lehre/WS11/Wireless/papers/AgrQdigest.pdf">Q-digest</a>.

Using either algorithm, each node produces a digest, which represents the distribution of the values stored locally. The digests are collected at a single node, merged (effectively summing the distributions), and the median or any other percentile can then be looked up.

This approach is used by <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations-metrics-percentile-aggregation.html">elasticsearch</a> and, presumably, <a href="https://cloud.google.com/bigquery/query-reference#aggfunctions">BigQuery</a> (going by the description of the QUANTILES function).

blocks|key|3053518|text|这取决于你的数据。最坏的情况是它是均匀分布的数字。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3053519|在这种情况下，您可以在O(N)时间内找到中位数，如下例所示：|3053520|假设您的数字是2，7，5，10，1，6，4，4，6，10，4，7，1，8，4，9，3，4，3(范围为1-10)。|3053521|我们创建3个存储桶:+1-3，4-7，8-10。请注意，顶部和底部的大小相同。|3053522|我们用数字填满桶，计算每个桶中有多少个落地，最大和最小|3053523|3053524|低(5)：2,+1，1,3,3，最小1，最大3|unordered-list-item|3053525|中(10)：7，5，6，4，4，4，7，4，4，4，最小4，最大7|3053526|高(5)：10，10，8，9，9，最小8，最大10|3053527|3053528|中庸之道落在中间，我们忽略了其余的。|3053529|我们创建了3个存储桶:+4，5-6，7。低将从计数5开始，最大值为3，高，最小值为8，计数为5。|3053530|对于每个数字，我们计算有多少落入低桶和高桶，最大值和最小值，并保留中间桶。|3053531|3053532|旧低(5)|3053533|低(5)：4，4，4，4，4，最大4|3053534|中(3)：5，6，6|3053535|高(2)：7，7，最低7|3053536|<代码>H117旧高(5)<代码>H218<代码>F219|3053537|现在我们可以直接计算中位数:我们有这样的情况|3053538|old+low++++low++++++++++middle++high++old+high
x+x+x+x+x++4+4+4+4+4+4+++5+6+6++7+7+++x+x+x+x+x|code-block|syntax|javascript|3053539|所以中位数是4.5。|3053540|假设您对分布略知一二，您可以微调如何定义范围以优化速度。在任何情况下，性能都应该是O(N)，因为1%2B+1/3+%2B+1/9...=+1.5|3053541|你需要最小和最大，因为边缘情况(例如，如果中位数是旧低和下一个元素的最大值之间的平均值)。|3053542|所有这些操作都可以并行化，您可以将1/100的数据提供给每台计算机，并计算每个节点中的3个bucket，然后分配您保留的bucket。这再次使您有效地使用网络，因为每个数字平均传递1.5次(因此O(N))。如果你只在节点之间传递最小的数字，你甚至可以超越它(例如，如果节点1有100个数字，节点2有150个数字，那么节点2可以给节点1+25个数字)。|3053543|除非您对分布有更多的了解，否则我怀疑您在这里能比O(N)做得更好，因为您实际上至少需要计算一次元素。|3053544|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1T|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|1U|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|1V|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|1W|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|1X|8|@]|9|@]|A|$]]|$1|K|3|L|5|M|7|1Y|8|@]|9|@]|A|$]]|$1|N|3|O|5|M|7|1Z|8|@]|9|@]|A|$]]|$1|P|3|Q|5|M|7|20|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|21|8|@]|9|@]|A|$]]|$1|S|3|T|5|6|7|22|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|23|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|24|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|25|8|@]|9|@]|A|$]]|$1|Z|3|10|5|M|7|26|8|@]|9|@]|A|$]]|$1|11|3|12|5|M|7|27|8|@]|9|@]|A|$]]|$1|13|3|14|5|M|7|28|8|@]|9|@]|A|$]]|$1|15|3|16|5|M|7|29|8|@]|9|@]|A|$]]|$1|17|3|18|5|6|7|2A|8|@]|9|@]|A|$]]|$1|19|3|1A|5|6|7|2B|8|@]|9|@]|A|$]]|$1|1B|3|1C|5|1D|7|2C|8|@]|9|@]|A|$1E|1F]]|$1|1G|3|1H|5|6|7|2D|8|@]|9|@]|A|$]]|$1|1I|3|1J|5|6|7|2E|8|@]|9|@]|A|$]]|$1|1K|3|1L|5|6|7|2F|8|@]|9|@]|A|$]]|$1|1M|3|1N|5|6|7|2G|8|@]|9|@]|A|$]]|$1|1O|3|1P|5|6|7|2H|8|@]|9|@]|A|$]]|$1|1Q|3|-4|5|6|7|2I|8|@]|9|@]|A|$]]]|1R|$]]

It depends on your data. The worst case scenario is that it's uniformly distributed numbers.

In this case you can find the median in O(N) time like in this example:

Suppose your numbers are 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (range is 1-10).

We create 3 buckets: 1-3, 4-7, 8-10. Note that top and bottom have equal size.

We fill the buckets with the numbers, count how many fall in each, the max and the min

<ul>
<li>low (5): 2,1,1,3,3, min 1, max 3</li>
<li>middle (10): 7,5,6,4,4,6,4,7,4,4, min 4, max 7</li>
<li>high (5): 10, 10, 8, 9, 9, min 8, max 10</li>
</ul>

The mean falls in the middle bucket, we disregard the rest

We create 3 buckets: 4, 5-6, 7. Low will start with a count of 5 and with a max of 3 and high with a min of 8 and a count of 5.

For each number we count how many fall in the low and high bucket, the max and the min, and keep the middle bucket.

<ul>
<li>old low (5)</li>
<li>low (5): 4, 4, 4, 4, 4, max 4</li>
<li>middle (3): 5,6,6</li>
<li>high (2): 7, 7, min 7</li>
<li>old high (5)</li>
</ul>

Now we can calculate the median directly: we have a situation like this

<pre><code>old low low middle high old high
x x x x x 4 4 4 4 4 4 5 6 6 7 7 x x x x x
</code></pre>

so the median is 4.5.

Assuming you know a little about the distribution, you can fine tune how to define the ranges to optimize speed. In any case, the performance should go with O(N), because 1 + 1/3 + 1/9... = 1.5

You need min and max because of edge cases (e.g. if the median is the average between the max of old low and the next element).

All of these operations can be parallelized, you can give 1/100 of the data to each computer and calculate the 3 buckets in each node, then distribute the bucket you keep. This again makes you use the network efficiently because each number is passed on average 1.5 times (so O(N)). You can even beat that if you only pass the minimal numbers among nodes (e.g. if node 1 has 100 numbers and node 2 has 150 numbers, then node 2 can give 25 numbers to node 1).

Unless you know more about the distribution, I doubt you can do better than O(N) here, because you actually need to count the elements at least once.

blocks|key|315227|text|您可以使用锦标赛树方法来查找中位数。我们可以创建一个包含1000个叶子节点的树，这样每个叶子节点就是一个数组。然后，我们在n/2锦标赛的结果之后，在根上进行不同的arrays.The值之间的n/2锦标赛。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|315228|http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/|offset|length|315229|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|1P|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@$D|O|E|P|1|Q]]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|C]]]]

You can use the tournament tree method for finding the median.
We can create a tree with 1000 leave nodes such that each leaf node is an array.
We then conduct n/2 tournaments between the different arrays.The value on the root after the n/2 tournaments is the result.

<a href="http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/" rel="nofollow">http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/</a>

blocks|key|3053592|text|我建议一种近似计算中位数的方法。:)如果这十亿个数字是随机排列的，我想我可以随机挑选十亿个数字的1/100或1/10，用100台机器对它们进行排序，然后取它们的中位数。或者让我们将十亿个数字分成100个部分，让每台机器随机选择每个部分的1/10，计算它们的中位数。在那之后，我们有100个数字，我们可以更容易地计算100个数字的中位数。这只是一个建议，我不确定它在数学上是否正确。但我认为你可以把结果展示给不太擅长数学的经理。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3053593|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I suggest a method to calculate approximately the Median. :) If these one billion numbers are in a randomly order, I think I can pick 1/100 or 1/10 of one billion number randomly, sort them with 100 machine, then pick the median of them. Or let's split billion numbers in 100 parts, let each machine pick 1/10 of each part randomly, calculate the median of them. After that we have 100 numbers and we can calculate the median of the 100 number easier. Just a suggestion, I'm not sure if it's mathematically correct. But I think you can show the result to a not-so-good-at-math manager.

blocks|key|315286|text|一种更简单的方法是使用加权数字。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|315287|315288|在计算机之间拆分大集合|unordered-list-item|315289|排序每个集合|315290|迭代通过小集合，并计算重复元素的权重|315291|合并每两个集合为1(每个集合都已排序)更新权重|315292|继续合并集合，直到只得到一个集合|315293|迭代此集合累积权重，直到到达OneBillion/2|315294|315295|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|T|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|U|8|@]|9|@]|A|$]]|$1|F|3|G|5|E|7|V|8|@]|9|@]|A|$]]|$1|H|3|I|5|E|7|W|8|@]|9|@]|A|$]]|$1|J|3|K|5|E|7|X|8|@]|9|@]|A|$]]|$1|L|3|M|5|E|7|Y|8|@]|9|@]|A|$]]|$1|N|3|O|5|E|7|Z|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|R|$]]

An easier method is to have weighted numbers.

<ul>
<li>Split the large set among computers</li>
<li>Sort each set</li>
<li>iterate through the small-set, and calculate weights to repeated elements</li>
<li>merge each 2 sets into 1 (each is sorted already) updating weights</li>
<li>keep merging sets until you get only one set</li>
<li>iterate through this set accumulating weights until you reach OneBillion/2</li>
</ul>

blocks|key|310251|text|如果数字不明确，并且只属于某个范围，即它们是重复的，那么我想到的一个简单的解决方案是在99台机器上平均分配这些数字，并保留一台机器作为主机。现在，每台机器都会迭代其给定的数字，并将每个数字的计数存储在一个散列集中。每次该数字在分配给该特定计算机的一组数字中重复时，它都会更新其在散列集中的计数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|310252|然后，所有机器将它们的哈希集返回给主机器。主计算机组合哈希集，对在哈希集中找到的相同键的计数求和。例如，机器#1的哈希集的条目为("1",7)，机器#2的哈希集的条目为("1",9)，因此主机器在梳理哈希集时生成条目("1"，16)，依此类推。|310253|一旦哈希集被合并，那么只需对键进行排序，现在您就可以很容易地从排序的哈希集中找到第(n/2)项和第(n%2B2/2)项。|310254|如果十亿个数字是不同的，这种方法就不会有什么好处。|310255|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

If the numbers are not distinct, and only belong to a certain range, that is they are repeated, then a simple solution that comes to my mind is to distribute the numbers among 99 machines equally, and keep one machine as the master. Now every machine iterates over its given numbers, and stores the count of each number in a hash set. Each time the number gets repeated in the set of numbers allotted to that particular computer, it updates its count in the hash set.

All the machines then return their hash set to the master machine. The master machine combines the hash sets, summing the count of the same key found in a hash set. For example machine#1's hash set had an entry of ("1",7), and machine#2's hash set had an entry of ("1",9), so the master machine when combing the hash sets makes an entry of ("1", 16), and so on.

Once the hash sets have been merged, then just sort the keys, and now you can easily find the (n/2)th item and the (n+2/2)th item, from the sorted hash set.

This method won't be beneficial if the billion numbers are distinct.

blocks|key|315334|text|对于一台现代计算机来说，10亿实际上是一个相当无聊的任务。我们在这里讨论的是4+GB的4字节整数...+4+GB+...这是一些智能手机的内存。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|315335|public+class+Median+{
++++public+static+void+main(String[]+args)+{
++++++++long+start+=+System.currentTimeMillis();

++++++++int[]+numbers+=+new+int[1_000_000_000];

++++++++System.out.println("created+array+after+"+%2B++(System.currentTimeMillis()+-+start)+%2B+"+ms");

++++++++Random+rand+=+new+Random();
++++++++for+(int+i+=+0;+i+<+numbers.length;+i%2B%2B)+{
++++++++++++numbers[i]+=+rand.nextInt();
++++++++}

++++++++System.out.println("initialized+array+after+"+%2B+(System.currentTimeMillis()+-+start)+%2B+"+ms");

++++++++Arrays.sort(numbers);

++++++++System.out.println("sorted+array+after+"+%2B+(System.currentTimeMillis()+-+start)+%2B+"+ms");

++++++++if+(numbers.length+%25+2+==+1)+{
++++++++++++System.out.println("median+=+"+%2B+numbers[numbers.length+/+2+-+1]);
++++++++}+else+{
++++++++++++int+m1+=+numbers[numbers.length+/+2+-+1];
++++++++++++int+m2+=+numbers[numbers.length+/+2];
++++++++++++double+m+=+((long)+m1+%2B+m2)+/+2.0;
++++++++++++System.out.println("median+=+"+%2B+new+DecimalFormat("#.#").format(m));
++++++++}
}|code-block|syntax|javascript|315336|我机器上的输出：|315337|created+array+after+518+ms
initialized+array+after+10177+ms
sorted+array+after+102936+ms
median+=+19196|315338|因此，在我的机器上，这项工作在不到两分钟内完成(1:43，其中0:10生成随机数)，使用单个内核，它甚至可以进行完全排序。真的没什么特别的。|315339|对于更大的数字集来说，这肯定是一项有趣的任务。我只想在这里说明一点:十亿美元是微不足道的。因此，在你开始在令人惊讶的简单任务中使用复杂的解决方案之前，请三思;)|315340|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

One billion is actually quite a boring task for a modern computer. We're talking about 4 GB worth of 4 byte integers here ... 4 GB ... that's the RAM of some smartphones.

<pre><code>public class Median {
 public static void main(String[] args) {
 long start = System.currentTimeMillis();

 int[] numbers = new int[1_000_000_000];

 System.out.println("created array after " + (System.currentTimeMillis() - start) + " ms");

 Random rand = new Random();
 for (int i = 0; i &lt; numbers.length; i++) {
 numbers[i] = rand.nextInt();
 }

 System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");

 Arrays.sort(numbers);

 System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");

 if (numbers.length % 2 == 1) {
 System.out.println("median = " + numbers[numbers.length / 2 - 1]);
 } else {
 int m1 = numbers[numbers.length / 2 - 1];
 int m2 = numbers[numbers.length / 2];
 double m = ((long) m1 + m2) / 2.0;
 System.out.println("median = " + new DecimalFormat("#.#").format(m));
 }
}
</code></pre>

Output on my machine:

<pre><code>created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196
</code></pre>

So this completes on my machine within less than two minutes (1:43 of which 0:10 are to generate random numbers) using a single core and it's even doing a full sort. Nothing fancy really.

This surely is an interesting task for larger sets of numbers. I just want to make a point here: one billion is peanuts. So think twice before you start throwing complex solutions at surprisingly simple tasks ;)

blocks|key|312345|text|好吧，假设您知道不同整数的数量是(比方说)40亿，那么您可以将它们存储到64k存储桶中，并从集群中的每台计算机(100台计算机)获得每个存储桶的分布式计数。结合所有这些计数。现在，找到具有中位数的存储桶，这一次只请求存储目标存储桶中64k个元素的存储桶。这需要对您的“集群”执行O(1)+(具体地说是2)个查询。:D|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312346|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Well, suppose you know that the number of distinct integers is (say) 4 billion, then you can bucket them into 64k buckets and get a distributed count for each bucket from each machine in the cluster(100 computers). Combine all these counts. Now, find the bucket which has the median, and this time only ask for buckets for the 64k elements that would lie in your target bucket. This requires O(1) (specifically 2) queries over your "cluster". :D

blocks|key|3267379|text|我一分钱的价值，别人已经提出来了：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3267380|在一台机器上找到中位数是O(N)：https://en.wikipedia.org/wiki/Selection_algorithm。|offset|length|3267381|向100台机器发送N个数字也是O(N)。因此，为了让使用100台机器变得有趣，要么通信必须相对较快，要么N太大，以至于一台机器无法处理它，而N/100是可行的，或者我们只想考虑数学问题，而不考虑数据通信。|3267382|简而言之，我假设在合理的范围内，我们可以在不影响效率分析的情况下发送/分发数字。|3267383|然后考虑下面的方法，其中一台机器被分配为一些常规处理的“主”。这将是相对较快的，因此“主”也参与了每台机器执行的常见任务。|3267384|3267385|每台机器接收N/100个数字，计算它自己的中位数，并将该信息发送给主机。|ordered-list-item|3267386|主机编译所有不同介质的排序列表，并将该列表发送回每台机器，定义桶的有序序列(在每台机器上相同)，每个中间值一个桶(单值桶)，相邻介质之间的每个间隔一个桶。当然，对于低于最低中值和高于最高中值的值，也有较低端和较高端的存储桶。|3267387|每台机器计算每个存储桶中有多少个数字，并将该信息传回主存储桶。|3267388|主存储桶确定哪个存储桶包含中位数，有多少较低的值(总计)低于该存储桶，以及有多少低于该存储桶的值。|3267389|如果选择的存储桶是单值存储桶(中间值之一)，则选择的存储桶只包含1+(N奇数)或2+(N偶数)值，我们就完成了。否则，我们使用以下(明显的)+modifications:|3267390|Only重复上述步骤。从所选存储桶中的数字被(重新)从主计算机分配到100台机器，并且moreover|3267391|We're不会计算(在每台机器上)中值，而是第k个值，其中我们考虑了从总数中丢弃了多少较高的数字，以及有多少较低的数字。从概念上讲，每台机器也有其丢弃的低/高数字份额，并在计算(概念上)包括(其份额)丢弃数字的集合中的新中值时将其考虑在内。|3267392|3267393|时间复杂度：|3267394|3267395|稍微思考一下就会让你相信，在每一步中，要分析的值的总数至少减少了两倍(2倍将是一个相当糟糕的情况；你可能会期望一个明显更好的减少)。从这里我们get:|3267396|Assuming找到中位数(或第k个值)，这是O(N)，需要c*N时间，其中预因子c不会随N变化太大，所以我们可以将它作为一个常数，我们将在最多2*c*N/100次得到我们的最终结果。因此，使用100台机器可以给我们带来100/2+(至少)的加速比。|3267397|最初说过:在机器之间传递数字所涉及的时间可能会使在一台机器上简单地做所有事情变得更有吸引力。然而，如果我们采用分布式方法，那么在所有步骤中一起通信的总数量将不会超过2*N+(第一次为N，第二次<=N/2，第三次为<=一半，依此类推)。|3267398|3267399|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Selection_algorithm^0|0|H|1D|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1L|8|@]|9|@$D|1M|E|1N|1|1O]]|A|$]]|$1|F|3|G|5|6|7|1P|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1R|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|1S|8|@]|9|@]|A|$]]|$1|M|3|N|5|O|7|1T|8|@]|9|@]|A|$]]|$1|P|3|Q|5|O|7|1U|8|@]|9|@]|A|$]]|$1|R|3|S|5|O|7|1V|8|@]|9|@]|A|$]]|$1|T|3|U|5|O|7|1W|8|@]|9|@]|A|$]]|$1|V|3|W|5|O|7|1X|8|@]|9|@]|A|$]]|$1|X|3|Y|5|O|7|1Y|8|@]|9|@]|A|$]]|$1|Z|3|10|5|O|7|1Z|8|@]|9|@]|A|$]]|$1|11|3|-4|5|6|7|20|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|21|8|@]|9|@]|A|$]]|$1|14|3|-4|5|6|7|22|8|@]|9|@]|A|$]]|$1|15|3|16|5|O|7|23|8|@]|9|@]|A|$]]|$1|17|3|18|5|O|7|24|8|@]|9|@]|A|$]]|$1|19|3|1A|5|O|7|25|8|@]|9|@]|A|$]]|$1|1B|3|-4|5|6|7|26|8|@]|9|@]|A|$]]|$1|1C|3|-4|5|6|7|27|8|@]|9|@]|A|$]]]|1D|$1E|$5|1F|1G|1H|A|$1I|1J]]]]

My penny worth, after all that has already been brought up by others:

Finding the median on a single machine is O(N): <a href="https://en.wikipedia.org/wiki/Selection_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Selection_algorithm</a>.

Sending N numbers to 100 machines is also O(N). So, in order to make using 100 machines interesting, either the communication must be relatively fast, or N is so large that a single machine cannot handle it while N/100 is doable, or we just want to consider the mathematical problem without bothering about datacommunication.

To cut things short I'll assume therefore that, within reasonable limits, we can send/distribute the numbers without affecting the efficiency analysis.

Consider then the following approach, where one machine is assigned to be the "master" for some general processing. This will be comparatively fast, so the "master" also participates in the common tasks that each machine performs.

<ol>
<li>Each machine receives N/100 of the numbers, computes its own median and sends that information to the master.</li>
<li>The master compiles a sorted list of all distinct medians and sends that back to each machine, defining an ordered sequence of buckets (on each machine the same), one for each median value (a single-value bucket) and one for each interval between adjacent medians. Of course there are also the lower-end and higher-end buckets for values below the lowest median and above the hightest.</li>
<li>Each machine computes how many numbers fall in each bucket and communicates that information back to the master.</li>
<li>The master determines which bucket contains the median, how many lower values (in total) fall below that bucket, and how many above.</li>
<li>If the selected bucket is a single-value bucket (one of the medians) orelse the selected bucket contains only 1 (N odd) or 2 (N even) values we're done. Otherwise we repeat the steps above with the following (obvious) modifications:</li>
<li>Only the numbers from the selected bucket are (re)distributed from the master to the 100 machines, and moreover</li>
<li>We're not going to compute (on each machine) the median, but the k-th value, where we take into account how many higher numbers have been discarded from the total, and how many lower numbers. Conceptually each machine has also its share of the discarded low/high numbers and takes that into account when computing the new median in the set that (conceptually) includes (its share of) the discarded numbers.</li>
</ol>

Time-complexity:

<ol>
<li>A little thinking will convince you that on each step the total number of values to analyse is reduced by a factor at least two (2 would be a rather sick case; you may expect a significantly better reduction). From this we get:</li>
<li>Assuming that finding the median (or k-th value), which is O(N), takes c*N time where the prefactor c does not vary too wildly with N so that we can take it as a constant for the moment, we'll get our final result in at most 2*c*N/100 time. Using 100 machines gives us, therefore, a speedup factor of 100/2 (at least).</li>
<li>As remarked initially: the time involved in communicating the numbers between the machines may make it more attractive to simply do everything on one machine. However, IF we go for the distributed approach, the total count of numbers to be communicated in all steps together will not exceed 2*N (N for the first time, &lt;=N/2 the second time, &lt;= half of that the third, and so on).</li>
</ol>

If you have one billion numbers and one hundred computers, what is the best way to locate the median of these numbers?

One solution which I have is:

<ul>
<li>Split the set equally among the computers.</li>
<li>Sort them.</li>
<li>Find the medians for each set.</li>
<li>Sort the sets on medians.</li>
<li>Merge two sets at a time from the lowest to the highest median.</li>
</ul>

If we have <code>m1 &lt; m2 &lt; m3 ...</code> then first merge <code>Set1</code> and <code>Set2</code> and in the resulting set we can discard all the numbers lower than the median of <code>Set12</code> (merged). So at any point of time we have equal sized sets. By the way this cannot be done in a parallel manner. Any ideas?

Calculate the median of a billion numbers

日志文件

数据库

如果你有十亿个数字和100台计算机，找到这些数字的中位数的最佳方法是什么？我有一个解决方案是：在中位数之间平均分配集合。查找每个集合的中位数。按中位数对集合进行排序。从最低到最高中位数一次合并两个集合。如果我们有m1 < m2 < m3 ...，那么首先合并Set1和Set2，在结果集中，我们可以丢弃所有低于Set12...

问计算十亿个数字的中位数
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算十亿个数字的中位数EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算十亿个数字的中位数
EN