时空权衡的逆压缩

计算科学 效率
2021-12-01 21:25:07

有点奇怪的问题 - 但我正在开发一个速度至关重要的应用程序,而不是内存 - 我有能力在这个应用程序将使用的数据存储上炸毁 3 TB,我想使用时空交易关闭以提高处理速度。

我的推理是这样的——压缩算法利用特定的函数来减小文件的大小,以解压缩特定文件的算法运行时间为代价——我应该能够做相反的事情,不是吗?增加文件大小以减少处理文件所需的时间。

你能建议任何简单的方法来做到这一点吗?(逆概率碎片化是我的想法,但这个问题目前给我带来了一些主要问题,因为我不知道文件压缩的​​基本基础)

任何帮助/伪代码/建议/答案都会很棒......

在此先感谢,马丁

3个回答

没有什么神奇的方法可以通过使用更多内存来加速任意操作。同样,没有办法压缩任意数据。碰巧很多数据具有可利用的冗余,但即便如此,改变算法(例如改变空间离散化、应用形式模型缩减方法或使用伴随模型)往往会提供比通用压缩更大的收益。此外,许多操作受到内存速度而不是 CPU 速度的限制。ZFS 和 Btrfs 等现代文件系统提供透明压缩以提高速度和节省磁盘空间。使用快速压缩算法,通过写入磁盘进行压缩的速度更快。

从您提供的有关应用程序的少量细节来看,以磁盘空间为代价提高性能的最可能方法是构建更多/更好的索引。仔细分析并在算法必须进行大量读取的每个点,评估计算索引的好处,以便更快地回答查询。请注意,索引不是免费计算的,并且它使某些更改更加昂贵(因为必须更新索引)。

你问的是不可能的。

首先,如果你有一个这样大小的数据集并且正在迭代整个事情,那么几乎可以肯定是你的数据集的大小让你放慢了速度。让你的数据集更大只会让事情变得更糟,因为你必须花更多的时间等待你的磁盘和 RAM 用一些请求的内存回到 CPU。

其次,通常没有“时空权衡”。确实,某些算法通过存储中间结果来节省时间,从而使用更多空间(FFT 就是一个例子),但这仅在问题的不同部分具有相似子问题时才有效。这不是算法的一般属性。对于非常具体的问题,偶尔会有非常具体的方法来解决这个问题,但你的情况可能不是其中之一。

如果您可以仅使用 8 位数据来检索所需的所有信息,那么为什么要使用 256 位来存储它呢?扩大文件大小意味着处理器必须从硬盘读取更多位以获得相同数量的信息,这肯定会降低性能。

扩展内存导致性能更快的主要原因是 RAM 内存访问通常比硬盘访问快。在绝对需要使用 10TB 数据来执行单个指令的情况下(不是在循环中,而是在单个原子操作中)。有道理的是,更多的内存总比更少的好。

另一方面,如果您有一个动态规划问题,其中存在重叠的子问题和最优子结构,那么使用更多内存会导致更快的最优解。但同样,加速来自使用 RAM 内存,而不是主内存访问。