返回给定间隔内插入的项目

Question

如何设计一个内存高效的系统，它接受添加到其中的项目，并允许在给定的时间间隔内检索项目（即返回在时间 T1 和时间 T2 之间插入的项目）。不涉及数据库。存储在内存中的项目。涉及到的数据结构和相关算法是什么。

更新： 假设与数据查询相比插入率极高。

Answer 1

您可以使用排序的数据结构，其中键是按到达时间排序的。请注意以下事项：

1. 项目未删除
2. 项目按顺序插入 [如果项目 i 在项目 j 之后插入，则 key(i)>key(j)]。

因此，不鼓励使用树，因为它是“压倒性的”，并且在其中插入的时间复杂度为 O(logn)，您可以获得 O(1) 插入。我建议使用以下之一：

(1)数组：数组将始终在其末尾被填充。当分配的数组已满时，重新分配一个更大的[双倍大小]数组，并将现有数组复制到其中。

优点：在数组中通常需要良好的缓存，< code>O(1) 机动化插入，使用空间最多2*elementSize*#elemetns

缺点：高延迟：当数组已满，添加一个元素需要O(n)，所以你需要预料到偶尔会出现代价高昂的操作。

(2)跳过列表 跳过列表还允许您O(logn) 查找并在末尾插入 O(1) ，但它不存在延迟问题。然而，它比数组更容易遭受缓存未命中的影响。跳跃列表的平均使用空间为 elementSize*#elements + pointSize*#elements*2。

优点：O(1)插入，无需昂贵的操作。

缺点：预计缓存会很差。

建议：

如果延迟不是问题，我建议使用数组。如果是，您最好使用跳过列表。

在两者中，找到所需的间隔是：

findInterval(T1,T2):
  start <- data.find(T1)
  end <- data.find(T2)
  for each element in data from T1 to T2:
     yield element

Answer 2

BTree 或二叉搜索树都可以是完成上述任务的良好内存数据结构。只需在每个节点中保存时间戳即可进行范围查询。

Answer 3

您可以将它们全部添加到一个简单的数组中并对它们进行排序。

执行二分搜索以找到 T1 和 T2。它们之间的所有数组元素都是您要查找的内容。

如果仅在添加所有元素后才进行搜索，这会很有帮助。如果没有，您可以使用 AVL 或 红黑树

Answer 4

关系区间树怎么样（将您的项目编码为包含只有一个元素，例如 [a,a])？尽管如此，已经有人说过，预期运营的比率很重要（实际上很重要）。但我的两点意见是：

我想在时间 t(X) 插入的项目 X 与该时间戳相关联，对吧？这意味着您现在不插入具有一周前或其他时间戳的项目。如果是这种情况，请使用简单数组并进行插值搜索或类似的操作（您的项目将已经根据查询引用的属性（即时间 t(X)）进行排序）。

Answer 5

我们已经有了一个建议树的答案，但我认为我们需要更具体：这确实是一个好的解决方案的唯一情况是，如果您非常具体地了解如何构建树（然后我会说它是与另一个答案中建议的跳过列表相同）。目标是使树尽可能充满左侧 - 我将在下面更清楚地说明这意味着什么。确保每个节点都有一个指向其（最多）两个子节点的指针和指向其父节点并且知道以该节点为根的子树的深度。

保留一个指向根节点的指针，以便能够在 O(log(n)) 中进行查找，并保留一个指向最后插入的节点 N 的指针（这必然是具有最高键的节点 - 它的时间戳将是最高）。插入节点时，检查 N 有多少个子节点：

• 如果为 0，则将 N 替换为要插入的新节点，并使 N 成为其左子节点。 （此时，您需要更新最多 O(log(n)) 个节点的树深度字段。）
• 如果为 1，则将新节点添加为其右子节点。
• 如果是 2，那么事情就会变得有趣。从 N 开始沿着树向上查找，直到找到只有 1 个子节点的节点或根。如果您发现一个节点只有 1 个子节点（这必然是左子节点），则将新节点添加为其新的右子节点。如果直到根节点的所有节点都有两个子节点，则当前树已满。将新节点添加为新根节点，将旧根节点添加为其左子节点。否则不要更改旧的树结构。

---

附录：为了使缓存行为和内存开销更好，最好的解决方案可能是创建一个数组树或跳过列表。让每个节点都具有一个包含 1024 个时间戳和值的数组，而不是让每个节点都具有单个时间戳和单个值。当数组填满时，您可以在顶级数据结构中添加一个新数组，但在大多数步骤中，您只需将单个元素添加到“当前数组”的末尾即可。这不会影响 big-O 在内存或时间方面的行为，但它会将开销减少 1024 倍，而延迟仍然非常小。