使用1 MB空间对1000万个整数进行排序解决方案说明-编程Pearls [英] Sorting 10 million integers with 1 MB space Solution explanation - Programming Pearls

问题描述

我正在阅读"Programming Pearls"，而我对解决方案的解释感到非常困惑.

I was reading "Programming Pearls" and I am really confused in one of the solution explanations.

问题是: 一个文件最多包含n个正整数，每个小于n，其中n = 10 ^ 7.每个正整数最多可以出现10次.如何对文件排序?"

The question was: "A file containing at most n positive integers, each less than n, where n = 10^7. Each positive integer could appear at most ten times. How would you sort the file?"

提供书中的解决方案: 如果每个整数最多出现十次，那么我们可以在一个四位半字节中计数它的出现.使用问题5的解决方案(如下)，我们可以一次通过10,000,000/2个字节对​​整个文件进行排序，或者以k为单位传递10,000,000/2k字节"

Given solution in the book: " If each integer appears at most ten times, then we can count its occurence in a four-bit half byte. Using the solution to Problem 5 (below) we can sort the complete file in a single pass with 10,000,000/2 bytes, or in k passes with 10,000,000/2k bytes"

问题5的解决方案是:两次通过算法首先使用5,000,000/8 = 625,000个存储字对整数0到4,999,999进行排序，然后在第二遍对5,000,000到9,999,999进行排序. k遍算法在时间kn和空间n/k中最多对n个小于n的非重复正整数进行排序.)

Solution to problem 5 is: A two-pass algorithm first sorts the integers 0 through 4,999,999 using 5,000,000/8 = 625,000 words of storage, then sorts 5,000,000 through 9,999,999 in a second pass. A k-pass algorithm sorts at most n non-repeated positive integers less than n in time kn and space n/k.)

我不知道作者是如何进入10,000,000/2k空间进行排序的.我的意思是，根据问题5的解决方案，首先我们需要625K字节的空间来进行首遍排序，并且每个整数需要额外的1/2字节来存储计数吗?

I am not getting how author is coming to 10,000,000/2k space to sort. I mean, based on the solution to problem 5, first we need 625K bytes of space to sort in first pass and additional 1/2 byte per integer to store the count right?

有人可以帮助我理解这一点吗?

Could someone please help me understand this?

非常感谢.

推荐答案

Each positive integer could appear at most ten times.

为此，每个计数器可以使用4位，而不是2个字节.如果将计数器分组，甚至可以降低此值，例如，如果将3个计数器分组，则为10 * 10 * 10 = 1000个组合，并且您需要10位(= 1024个值).

You can use 4 bits per counter for this, not 2 bytes. If you group counters you can even lower this value, for example if you group 3 counters, that's 10*10*10=1000 combinations and you need 10 bits (=1024 values) for that.

这篇关于使用1 MB空间对1000万个整数进行排序解决方案说明-编程Pearls的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！