问题标签 [space-efficiency]

我们目前每周收到数千个平面文件，我有一个系统可以运行这些文件并将它们导出为 PDF 格式供我们的人员处理和参考。

我目前将这些批量加载到数据库中，确保所有字段/格式都有效，导出它们，并在下次运行时截断表。

我想知道的是，每个人都认为存储可能 6 个月的批量加载纯文本数据最节省空间的方式是什么？

无论是以日常 SQL 备份的形式，还是压缩档案的形式，或其他形式，所以我总是能够重新加载旧数据以进行故障排除。

欢迎任何想法，我愿意接受任何建议。

你们发现所有算法在这两个方面都有惊人的（艰难的，奇怪的）复杂性分析 - 产生的 O 表示法和分析方式的唯一性？

pickle 模块在酸洗时似乎使用了字符串转义字符；这变得低效，例如在 numpy 数组上。考虑以下

长度分别为 1133 个字符和 4249 个字符。

z.dumps() 显示类似 "\x00\x00" （字符串中的实际零）的内容，但 pickle 似乎正在使用字符串的 repr() 函数，产生 "'\x00\x00'" （零是 ascii 零）。

即 ("0" in z.dumps() == False) 和 ("0" in cPickle.dumps(z.dumps()) == True)

似乎没有一本算法教科书提到过空间效率，所以当我遇到要求只需要恒定内存的算法的问题时，我真的不明白。

什么是使用常量内存的算法和不使用常量内存的算法的几个示例？

我需要一个实现 Iterable 的类，并且不需要对并发使用是安全的。在 LinkedList、HashSet、ArrayList 等各种选项中，哪个是最轻的？

为了阐明用例，我需要能够向 Iterable 添加一些对象（通常为 3 或 4 个），然后需要对其进行迭代。

如何有效地找到数组中每个元素的排名，在平局的情况下进行平均？例如：

我能想到的唯一方法需要分配3个数组：

1. 输入数组的副本，因为它必须排序并且我们不拥有它。
2. 一个数组，用于跟踪输入数组的排序顺序。
3. 要返回的秩数组。

有谁知道如何在 O(N log N) 时间和 O(1) 辅助空间中执行此操作（这意味着我们必须分配的唯一数组是我们要返回的数组），或者至少摆脱其中一个上面的三个数组？

假设您有一个List<List<Boolean>>，并且您想以最紧凑的方式将其编码为二进制形式。

我不关心读取或写入性能。我只想使用最少的空间。此外，示例是用 Java 编写的，但我们不限于 Java 系统。每个“列表”的长度是无限的。因此，任何对每个列表的长度进行编码的解决方案本身都必须对可变长度数据类型进行编码。

与这个问题相关的是可变长度整数的编码。您可以将每个List<Boolean>视为可变长度unsigned integer。

请仔细阅读问题。我们不仅限于 Java 系统。

编辑

我不明白为什么很多答案都在谈论压缩。我并不是要进行压缩本身，而只是将随机的比特序列编码下来。除了每个位序列的长度不同并且需要保留顺序。

你可以用不同的方式思考这个问题。假设您有一个随机无符号整数（无界）的任意列表。你如何在二进制文件中编码这个列表？

研究

我做了一些阅读，发现我真正想要的是通用代码

结果

我将使用论文A new recursive universal code of the positive integers 中描述的Elias Omega Coding的变体

我现在明白了较小整数的表示越小是如何与较大整数进行权衡的。通过简单地选择具有第一个整数的“大”表示的通用代码，从长远来看，当您需要对任意大整数进行编码时，您可以节省大量空间。

我有一个 500k+ 的词表，我将它加载到DAWG数据结构中。我的应用程序适用于手机。我当然不想每次都重复所有的转换步骤来将此单词表加载到 DAWG 中，因为在手机上保存单词表会占用大量存储空间，并且每次将其加载到 DAWG 中都需要很多时间. 因此，我正在寻找一种方法将我的 DAWG 中的数据以一种既可以节省空间又可以让我快速将其加载回我的 DAWG 数据结构的格式存储到文件或数据库中。

我收到一个建议，我可以将每个节点存储在 SQLite DB 中，但我不确定这将如何工作，如果我这样做了，我将如何快速检索它。我当然不想运行很多查询。其他类型的存储方法会更好吗？我还收到了有关创建序列化文件或将其存储为位图的建议。

这个问题来自给我的家庭作业。您可以使用以下三种格式之一建立您的存储系统：

DD MM SS.S

嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯

DD.DDDDD

您希望通过使用尽可能少的字节来最大化可以存储的数据量。

我的解决方案基于第一种格式。我用 3 个字节表示纬度：8 位用于 DD（-90 到 90），6 位用于 MM（0-59），10 位用于 SS.S（0-59.9）。然后我使用 25 位作为经度：9 位用于 DDD（-180 到 180），6 位用于 MM，10 位用于 SS.S。这个解决方案不太适合字节边界，但我认为下一个读数可以立即存储在前一个读数之后，8 个读数仅使用 49 个字节。

我很好奇其他人可以提出什么方法。有没有更有效的方法来存储这些数据？作为说明，我考虑了基于偏移的存储，但问题没有表明读数之间的值可能会发生多少变化，所以我假设任何变化都是可能的。

我正在开发一个开源备份实用程序，它可以备份文件并通过 FTP/SFTP/SCP 协议将它们传输到各种外部位置，例如 Amazon S3、Rackspace Cloud Files、Dropbox 和远程服务器。

现在，我收到了关于进行增量备份的功能请求（以防所做的备份很大并且传输和存储变得昂贵）。我一直在环顾四周，有人提到了该rsync实用程序。我对此进行了一些测试，但不确定这是否合适，所以想听听任何有经验的人的意见rsync。

让我简要介绍一下进行备份时会发生什么。基本上它会开始转储数据库，如 MySQL、PostgreSQL、MongoDB、Redis。它可能需要来自文件系统的一些常规文件（如图像）。一切就绪后，它将全部捆绑在一个 .tar 中（此外，它将使用gzipand对其进行压缩和加密openssl）。

完成后，我们有一个文件，如下所示：
mybackup.tar.gz.enc

现在我想将此文件传输到远程位置。目标是降低带宽和存储成本。所以让我们假设这个小备份包1GB的大小差不多。因此，我们使用rsync将其传输到远程位置并在本地删除文件备份。明天将生成一个新的备份文件，事实证明在过去 24 小时内添加了更多数据，我们构建了一个新mybackup.tar.gz.enc文件，看起来我们1.2GB的大小已经达到了。

现在，我的问题是：是否可以仅转移200MB过去 24 小时内添加的内容？我尝试了以下命令：

rsync -vhP --append mybackup.tar.gz.enc backups/mybackup.tar.gz.enc

结果：

mybackup.tar.gz.enc 1.20G 100% 36.69MB/s 0:00:46 (xfer#1, to-check=0/1)

发送 200.01M 字节
接收 849.40K 字节
8.14M 字节/秒
总大小为 1.20G
加速为 2.01

看着sent 200.01M bytes我会说数据的“附加”工作正常。我现在想知道的是，它是否传输了整个文件1.2GB以便弄清楚要附加到现有备份的数量和内容，还是真的只传输200MB? 因为如果它传输了整个文件1.2GB，那么我看不出它与scp在单个大文件上使用该实用程序有何不同。

另外，如果我想要完成的工作完全有可能，你推荐什么标志？如果无法使用rsync，是否可以推荐使用任何实用程序？

非常感谢任何反馈！