Python:将 1,000,000 个整数写入文件

Question

在不压缩等情况下使用 Python 将 1,000,000 个整数(0、1、2 ...)写入文件的最紧凑方法是什么？我的答案是:1,000,000 * 3 bytes using struct module，但面试官似乎期待另一个答案......

编辑。从 1 到 1,000,000 的数字以随机顺序排列(因此在极少数情况下可以应用 5、6、7 -> 5-7 等变换)。您可以使用您知道的任何写入方法，但生成的文件应具有最小大小。

Answer 1

实际上，您可以比 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。

由于鸽巢原理，我认为无论您使用压缩还是其他技术，都不可能比此策略做得更好。