我有一个具有以下属性的正(随机)整数列表:
元素数量:78495
元素最大值:999982
转换为字符串时列表的长度:517115(字符串看起来像“6,79384,238956,...”)
磁盘上文本文件中的列表大小:520 kb
我尝试使用此列表作为在线判断问题的预计算列表,因为实际生成此列表需要很长时间。不过直接粘贴到源代码里的话太大了,无法接受,源代码上限是50kb。
我研究了 zlib 作为压缩字符串的一种方法,但它似乎只是将大小减少了一半。
有没有办法真正缩小它,以便我可以解压它/在源代码中使用它?
根据您的定义...
它是最小 k 值的列表,其中 10^k = 1 mod p 对于素数 p > 5
...我是否错误地相信您的值的形式为
(p - 1) / x
,其中 x 是明显小于 p 的整数?
例如,对于 p < 50, we have:
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 值列表计算出的素数列表。
您可能应该从一开始就解释一下您到底想压缩什么以获得更准确的答案。
简而言之,不。
log(2, 999982) ~= 20
因此最大的数字需要 20 位来存储。假设平均而言,每个数字需要 10 位来存储(均匀分布在 0 和最大值之间)。
~80,000 numbers * 10 bits per number = 800,000 bits = 100,000 bytes
因此,尽可能高效地存储这些数字将占用约 100KB 的空间。
只有当数字存在一定的非随机性时,压缩才会起作用。如果它们确实是随机的,正如您所说,那么一般的压缩算法将无法使其变得更小,因此 100KB 大约是您可以希望做到的最佳值。
编辑
请注意,情况更糟,因为您想将它们粘贴到源代码中,因此您不能只使用任意二进制数据。您将需要一些文本友好的内容,例如 base64 编码,这将额外增加约 33% 的开销。此外,您无法真正根据所需的“平均”位数来存储数字,因为您需要某种方法来了解每个数字使用了多少位。有可能的编码方案,但所有方案都会带来一些额外的开销。
第二次编辑根据上面的评论,数据
不是实际上是随机的,正如最初所说的那样。因此,通用压缩算法可能有效,如果不行,可能还有其他解决方案(例如,仅发送最初生成数字的代码,该代码可能小于 50KB)。
# check the compression ratio
import lzma
import zlib
import gzip
import bz2
import zipfile
import tarfile
compressors = ['lzma','zlib','gzip','bz2']
a = np.exp(np.random.rand(1024))
b = np.arange(1024)
b[32] = -10
b[96] = 20000
a = bytes(a)
b = bytes(b)
for i in range(len(compressors)):
print("{} compression ratio: ".format(compressors[i]))
a_lzma = eval(compressors[i]).compress(a)
b_lzma = eval(compressors[i]).compress(b)
print(float(len(a_lzma))/len(a),float(len(b_lzma))/len(b))
print("\n")
输出:
lzma压缩比: 0.93115234375 0.08984375
zlib压缩比: 0.95068359375 0.1944580078125
gzip压缩比: 0.9521484375 0.196533203125
bz2压缩比: 0.9925537109375 0.1268310546875