Python:将1,000,000个int写入文件

Question

编写1,000,000个整数(0，1，2...)最紧凑的方式是什么？使用Python而不压缩文件，等等？我的答案是: 1,000,000 *3字节，使用struct模块，但似乎面试官期待着另一个答案……

编辑。从1到1,000,000之间的随机顺序的数字(所以像5，6，7 -> 5-7这样的变换可以在极少数情况下应用)。您可以使用任何已知的写入方法，但生成的文件应具有最小大小。

Answer 1

那么，您的解决方案需要每个整数三个字节(= 24位)。理论上，20位就足够了(因为2^19 < 1.000.000 < 2^20)。

编辑:哦，刚刚注意到Neil的评论也是这样。我把这个答案写成CW，因为它确实是属于他的。

Answer 2

实际上，你可以做的比2.5MB好很多，因为不是所有的排序都是可能的。有人可能会争辩说，击败5%将涉及压缩，因为一个人不是存储序列本身。基本上，您会希望存储规范的序列号。从0到7的随机顺序的8个数字通常需要24位(log(8^8)/log(2))，但是使用规范的序列号将需要16位(log(8!)/log(2))。

基本上，这涉及到提出一种算法，可以将任何整数序列转换为一个巨大的数字。8编号序列的可能编号示例是按值排序：

01234567 : 0  
01234576 : 1  
01234657 : 2  
01234675 : 3  
01234756 : 4  
01234765 : 5  
...

此策略的成本是log(1000000!)/log(2) (即log_2(1000000!))。

标准解决方案的成本通常约为log(1000000^1000000)/log(2)。

您还可以通过区别对待0000 0000 1111 1111和1111 1111来压缩更多的空间，但是这样做节省的空间量非常小。

编辑：快速而粗糙的计算表明，此优化将大小降至约2.204MiB。

由于鸽洞原理，我不相信有可能比这个策略做得更好，不管你是使用压缩还是其他一些技术。

Answer 3

假设您必须记住它们的顺序，并且这些数字的范围是1到1,000,000，由于1,000,000在十六进制中是0xF4240，因此写入每个数字只需要20位或2.5字节。您必须将它们打包在一起，这样才不会浪费任何空间，但这样做只需要2.5 * 1,000,000字节。