问题标签 [space-efficiency]

如何最小化代码中重复的异常抛出代码：

所以快速排序的空间效率是O(log(n))。这是维护调用堆栈所需的空间。

现在，根据Quicksort 上的维基百科页面，这符合就地算法，因为该算法只是交换输入数据结构中的元素。

然而，根据此页面，O(log n) 的空间效率使快速排序无法到位，因为它的空间效率大于 O(1)。根据这个定义，任何空间效率大于 O(1) 的算法都不是就地的。所以我假设这意味着所有递归算法都没有按定义到位？

所以很明显这里有两种不同的就地定义。维基百科并不总是一个完全可靠的来源，所以我咨询了我的一位教授。

我的教授同意第二个定义。他说 Quicksort 没有到位。即使数据保留在输入数组中，堆栈所需的额外空间也会使其不合格。我的教授写了一本关于算法的流行书，所以我非常尊重他的意见，但这个答案对我来说似乎并不正确。

我认为就地的属性是相当字面的。数据保持不变。它不会脱离其原始数据结构。对我来说，这个定义更有用，因为它意味着您可以使用指针执行算法，而不是要求您复制数据。这似乎是算法的一个有价值的属性，并且配得上“就地”的名称。

所以我正在写我的俄罗斯方块版本。这是我想做的：

screen[0][1].setColor(Color.RED); screen[0][1].setStatus(1);

有没有办法只用一行来做到这一点？

我想实现一个算法来获得一个介于 1 和一个非常大的数之间的素数列表。我打算用 Erasthosthenes 筛子。但是要实现筛子，我们不应该首先创建一个包含这么多数字的布尔数组。这不是很消耗内存吗？有没有其他方法可以做到这一点？

我有许多大的 1GB+ doubles（浮点数）矩阵，其中许多0.0需要有效存储。我打算保留该double类型，因为某些元素确实需要是 a double（但如果它可以节省大量空间，我可以考虑更改它）。字符串标头是可选的。矩阵没有缺失元素、NaN、NA、空值等：它们都是doubles.

有些列会稀疏，有些则不会。稀疏列的比例因文件而异。

什么是 CSV 的节省空间的替代方案？对于我的使用，我需要将此矩阵快速解析为R,python 和 Java，因此特定于单一语言的文件格式是不合适的。访问可能需要按行或按列。

我也不是在寻找商业解决方案。

我的主要目标是节省硬盘空间而不会耗尽io时间。导入后的 RAM 使用情况不是主要考虑因素。

我一直在研究最佳做法是对尝试在网站上注册的用户进行电子邮件验证。（我正在运行 laravel 安装，这发生在 php 中，尽管这更像是一个理论问题）。我有几个问题想听听大家的意见！

1. 将激活密钥存储得比需要的时间长有什么用吗？到目前为止，我已将其设置为在用户激活他/她的帐户后删除密钥。
2. 当我在激活后清除表中的数据时，空间是否会被取消分配？还是只是清空了？
3. 有没有更好的方法来完成这个过程？（我有一个模糊的想法，即使用一个临时的“令牌”表，其中键和电子邮件 ID 作为列，每次注册时都会添加一个新行，然后在用户确认后将其删除（或者，在特定超时后时期）
4. 理想情况下，生成的密钥的大小应该是多少？一个简单的 5 位字母数字代码可以容纳 6000 万多个组合，那么真的需要散列吗？

我已经对此进行了一段时间的研究，我的目标是使我的系统完全可扩展并尽可能高效。欢迎任何信息/讨论。

我正在寻找一个好的算法（或代码，如果你说得比英语好）来执行以下操作：

对于给定的 IP 范围（例如 1.1.1.1 - 1.1.2.247），找到包含指定范围内所有 IP 的子网/地址的最小组合。忽略广播、子网 0 限制和网络类。

例子：

• 对于 1.1.1.1 - 1.1.2.1 你会得到 {1.1.1.1/24, 1.1.2.1} 比 {1.1.1.1, 1.1.1.2, ..., 1.1.1.255, 1.1.2.1} 更好/更小
• 对于 1.1.1.12 - 1.1.1.31，您会得到 {1.1.1.12/30, 1.1.1.16/28}，它比 {1.1.1.12, 1.1.1.13, 1.1.1.14, 1.1.1.15, 1.1 更好/更小。 1.16/28}

出于好奇，用例是使用 Openflow 协议将任意范围的源/目标 IP 上的网络流量与最少的流量匹配。这种优化的需求源于硬件交换机/路由器对这些流配置的空间有限，并且需要相对较长的时间来编程/修改。

我想构建一个节省空间的模块化算术类。这个想法是模数 M 是一个在实例化期间固定的不可变属性，因此如果我们有一个具有相同 M 值的大型数组（std::vector 或其他容器），则 M 只需要存储一次。

如果 M 可以在编译时固定，这可以使用模板来完成：

但是，在我的应用程序中，我们应该能够表达 M 运行时。我所拥有的看起来像这样：

这可行，但是 mod M 值的大向量使用它需要的空间的 2 倍。

我认为潜在的概念问题是不同模数的 Mod 在语法上属于相同类型，即使它们“应该”是不同的类型。例如，像这样的语句

应该“自然”引发运行时错误（在我的版本中，它“手动”这样做：检查内置于复制构造函数以及我实现的每个二元运算符中）。

那么，有没有办法实现某种动态类型，以便 Mod 对象的类型记住模数？我真的很感激任何想法如何解决这个问题。

这对我来说是一个反复出现的问题，涉及各种数学结构（例如，在同一集合上存储许多排列、同一组的元素等）

编辑：据我所知，

• 模板是由类或文字参数化的类型。

• 我想要什么：由 const 对象参数化的类型（const num在这种情况下，const Group&或const Group *const用于组等）。

这可能吗？

这是改进我的 Perl 的尝试 ：通过更彻底地解释我正在尝试做的事情来寻找和读取位，而不是字节。

我有 x，一个 9136 x 42 的整数数组，我想将它超高效地存储在文件中。整数具有以下约束：

• x[0..9135][0] 中的所有 9136 个整数都在 -137438953472 和 137438953471 之间，因此可以使用 38 位存储。

• x[0..9135][1] 中的所有 9136 个整数都在 -16777216 和 16777215 之间，因此可以使用 25 位存储。

• 依此类推...（整数位约束是预先知道的；Perl 不必计算它们）

问题：使用 Perl，我如何有效地将这个数组存储在一个文件中？

笔记：

• 如果一个整数可以存储为 25 位，那么它也可以存储为 4 个字节（32 位），如果您愿意浪费 7 位。然而，在我的情况下，每一点都很重要。

• 我想使用文件 seek() 快速查找数据，而不是通过文件顺序读取。

• 该数组通常以 x[i] 的形式访问。换句话说，我想要与给定 x[i] 对应的 42 个整数，因此这 42 个整数应该彼此靠近存储（理想情况下，它们应该在文件中彼此相邻存储）

• 我最初的方法是只放置一个比特流，然后找到一种方法将其读回并将其改回整数。我最初的问题集中在这个问题上，但对于我没有看到的更大问题，也许有更好的解决方案。

关于我在做什么的太多细节：

• https://github.com/barrycarter/bcapps/blob/master/ASTRO/bc-read-cheb.m
• https://github.com/barrycarter/bcapps/blob/master/ASTRO/bc-read-cheb.pl
• https://github.com/barrycarter/bcapps/blob/master/ASTRO/playground.pl

我很好奇这是否以前做过，不一定是否具有实用价值（尽管空间效率的提高是显而易见的）。是否曾经在同一机器代码中编码多个指令？例如：

（这完全是编造的）

0xAEA2 -> 添加 R3 0xA2

0xEAE6 -> 移动 R1 0xE6

0xAAAA ...

通过向左移动一个半字节来重新解释机器代码变成：

0xEA2E -> 移动 R1 0x2E

0xAE5A -> 添加 R3 0x5A