问是否值得尝试编写万无一失的数据结构？
EN

Software Engineering用户

提问于 2013-03-02 19:10:44

回答 3查看 616关注 0票数 3

问题

我们需要以类似于表的方式存储数据，但是我们有非常严格的空间限制(每个10k+行表的~1MB)。我们存储这样的数据：

ID | reviews | factor | score | interval | etc.
---+---------+--------+-------+----------+-----
 1 |     244 |    2.4 |    10 |     4268 | ...

在一个简单的二进制格式(一个一维字节数组，其中每一行的索引可以简单地通过了解每一行的长度，这是固定的)。

只有一个函数读取此数据(按其索引获取一行)，只有一个函数追加一个新行(到末尾)。从表中移除项是永远不需要的(该表仅附加)。这两个功能都包含了相当数量的单元测试。

问题是:我们需要能够快速地遍历按不同列排序的行。换句话说，我们需要至少按两列对数据进行排序。

--一个简单的解决方案

为了解决这个问题，我们将实现同样是二进制数据块的索引。现在，我将通过创建只列出原始表中行的索引的有序数据结构来直观地做到这一点：

factor_index        score_index
------------        -----------
          6                  2
          2                  1
          3                  6
          1                  4
          .                  .

将新行附加到表中的函数必须更新，才能使索引也被更新。

示例:要获得按得分排序的第一项，我们只需在索引表中查找score (2)的第一个值，并从原始表中获得相应的行(如果我们同意该表是零索引的，则为第三行)。

然而，有人建议我采取不同的办法。

--一个更复杂但更安全的

版本

我们不只是存储索引，而是在每个索引表中复制ID字段：

factor_index | ID        score_index | ID
-------------+---        ------------+---
          6  | 46                  2 |  8
          2  |  8                  1 | 14
          3  | 91                  6 | 46
          1  | 14                  4 | 60
          .  |  .                  . |  .

然后保持原始表按ID排序，并仅将索引用作原始表中二进制搜索的起始位置。

添加新记录的函数现在必须按ID执行二进制搜索，以查找插入新行的位置，并使索引更新。

为了获得按分数排序的第一项，我们在索引表中查找分数(2，8)的第一行，并使用索引(2)作为表中二进制搜索的起始位置。如果数据是有效的，我们甚至不需要进行二进制搜索，因为在位置2，我们将找到ID为8的行。但是，如果我们发现位置2的记录有不同的索引，我们继续进行二进制搜索以找到正确的数据，并记录错误。

这种方法的论点是，即使索引指向表中的错误行，它也会工作。

不过，我很难相信这种方法确实更好，原因如下：

它需要一个二进制搜索，这可能是一个新的bug来源。
它要求保持表的有序性，这意味着更复杂的插入(相对于简单的附加)。
它并不能防止主表出现故障:如果出现这种情况，索引甚至可能无法通过二进制搜索找到记录。
它需要编写(和测试)从未打算运行的代码。
它使用的数据比所需的要多。

问题

对于我们的应用程序来说，非常高的优先级是，上面的数据始终是有效的。但是，这是否有理由编写更复杂的数据结构和查找机制，以防止可能发生或不可能发生的边缘情况？难道不应该把时间和精力花在为更简单的版本编写更健壮的测试用例上吗？

data-structures

defensive-programming

回答 3

Software Engineering用户

回答已采纳

发布于 2013-03-02 22:09:02

如果我正确地理解了您的索引，它们不是存储它们的最有效的方法。

无论如何，你不能同时在两把钥匙上整理你的桌子，所以我认为你根本不应该试着把它分类。相反，对索引进行排序。

10k行--一个两个字节的值可以指表中的任何条目。因此，构建最初以1..10k为种子的两个数组(或表中有多少个条目)。虽然这些不是CPU意义上的指针，但无论如何都要使用它们作为指针。根据表中的值对两个数组进行排序。

Insert是通过简单地追加记录，然后重建数组来处理的。是的，这是一项相当昂贵的操作，但是由于您已经指定了数组，所以数组并不大，不能增长太多，因此不应该经常这样做。你做的任何事都是天生的至少O(n)，一个完整的度假村只有O(n log n)，我会走后一条路。(你甚至可能会发现它更快，因为与移动记录相比，对主内存的写入要少得多。)

请注意，这些数组只是两个字节的值，而不是像您所指示的那样的键值对。

还有一些其他的事情也浮现在脑海中--你似乎异常关注数据的大小。这告诉我，要么您正在传输这些块(此时可以省略这些索引，因为它们可以在另一端重新创建)，要么您立即在内存中存储了大量这些数据。在后一种情况下，如果您使用的是支持弱引用的语言，则可以使用它们--让块的索引没有被积极地用于垃圾收集，然后在需要时重新创建。

票数 3