在 Python 中压缩整数列表

Question

我有一个具有以下属性的正（随机）整数列表：

元素数量：78495

元素最大值：999982

转换为字符串时列表的长度：517115（字符串看起来像“6,79384,238956,...”）

磁盘上文本文件中的列表大小：520 kb

我尝试使用此列表作为在线判断问题的预计算列表，因为实际生成此列表需要很长时间。但是直接粘贴到源代码中的话，太大了，无法接受，源代码的上限是50kb。

我研究了 zlib 作为压缩字符串的一种方法，但它似乎只是将大小减少了一半。

有没有办法真正缩小它，以便我可以解压它/在源代码中使用它？

Answer 1

鉴于你的定义...

它是最小 k 值的列表，其中 10^k = 1 mod p 对于素数 p > 5

...我是否错误地认为您的值的形式(p - 1) / x为 x 是明显小于 p 的整数？

例如，对于 p < 50，我们有：

p = 7  : 10^6  = 1 (mod 7)  => k = 6  = (p - 1) / 1  => x = 1
p = 11 : 10^2  = 1 (mod 11) => k = 2  = (p - 1) / 5  => x = 5
p = 13 : 10^6  = 1 (mod 13) => k = 6  = (p - 1) / 2  => x = 2
p = 17 : 10^16 = 1 (mod 17) => k = 16 = (p - 1) / 1  => x = 1
p = 19 : 10^18 = 1 (mod 19) => k = 18 = (p - 1) / 1  => x = 1
p = 23 : 10^22 = 1 (mod 23) => k = 22 = (p - 1) / 1  => x = 1
p = 29 : 10^28 = 1 (mod 29) => k = 28 = (p - 1) / 1  => x = 1
p = 31 : 10^15 = 1 (mod 31) => k = 15 = (p - 1) / 2  => x = 2
p = 37 : 10^3  = 1 (mod 37) => k = 3  = (p - 1) / 12 => x = 12
p = 41 : 10^5  = 1 (mod 41) => k = 5  = (p - 1) / 8  => x = 8
p = 43 : 10^21 = 1 (mod 43) => k = 21 = (p - 1) / 2  => x = 2
p = 47 : 10^46 = 1 (mod 47) => k = 46 = (p - 1) / 1  => x = 1

x 值列表应该比 k 值列表压缩得更好。（例如，我愿意打赌 x 最常见的值将是“1”。）

而且因为计算最多 100 万个素数（我认为这是您的上限）相当容易和快速，您也许能够根据 x 值的压缩列表和实时计算的值快速重建 k 值列表素数列表。

您可能应该从一开始就解释一下您到底试图压缩什么以获得更准确的答案。