python - 在 Python 中压缩整数列表

Question

我有一个具有以下属性的正(随机)整数列表:

元素个数:78495

元素的最大值:999982

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

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

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

我将 zlib 视为一种压缩字符串的方法，但它似乎只能将大小减半。

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

Answer 1

根据您的定义...

它是最小 k 值的列表，其中 10^k = 1 mod p for primes 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 值列表-时间计算的素数列表。

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