Python: 将1,000,000个整数写入文件
用Python写入1000000个整数（0, 1, 2...）到文件，最紧凑的方法是什么？我的答案是：使用struct模块，每个数字占用3个字节，总共就是1000000 * 3字节，但面试官似乎期待另一个答案...
补充一下。数字是从1到1000000，顺序是随机的（所以像5, 6, 7可以变成5-7这种情况很少见）。你可以使用任何你知道的写入方法，但最终生成的文件大小要尽量小。
7 个回答
假设你需要记住这些数字的顺序，而且这些数字的范围是从1到1,000,000，那么每个数字只需要20位二进制位，或者说2.5个字节来存储，因为1,000,000在十六进制中是0xF4240。为了节省空间，你需要把这些数字打包在一起，不过这样做的话，总共只需要2.5 * 1,000,000字节。
其实，你可以做到比2.5MB更好，因为并不是所有的排列组合都是可能的。有人可能会说，要想超过5%的压缩率，就得用到压缩技术，因为你并不是在存储序列本身。简单来说，你应该存储一个标准的序列编号。8个从0到7的数字随机排列，通常需要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。
由于鸽巢原理，我认为无论你使用压缩还是其他技术，这种策略都无法再做得更好了。
你的方案每个整数使用了三个字节（也就是24位）。理论上来说，20位就足够了，因为2的19次方小于1000000，而2的20次方大于1000000。
补充：哎呀，刚注意到Neil的评论也提到了这一点。我把这个回答标记为共同编辑，因为这其实是他的观点。