我正在阅读"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万个整数进行排序解决方案说明
发布评论