Adobe面试：用什么数据结构来存储数千个点(x,y)以便执行某些操作更快？

Question

我们需要存储成千上万的点（x，y，c），这里的c是该点的颜色。主要与屏幕上的像素相关。我们需要执行以下操作： 给定x = i，我们必须更改所有x = i的点的颜色。 同样，给定y = i，我们必须更改所有y = i的点的颜色。

我提出了一个2D矩阵的解决方案。然后是分别针对x和y坐标的哈希表。 然后他要求我提供更好的解决方案。我们可以使用哪些更好的数据结构组合？

- user2328404

Answer 1

如果没有关于某个坐标的检索：您可以提出对坐标x，y进行哈希处理。请提交一些具有低碰撞率的哈希，例如 hash = ( y << 16 ) ^ x;。

但是，如果您想根据x或y的值访问数据，则需要使用存储点并有效执行操作的结构，即点QTree或四叉树。在这里查看。

点四叉树是二叉树的一种改进形式，用于表示二维点数据。它具有所有四叉树的特征，但是作为一个真正的树，其子分区的中心始终在一个点上。

点四叉树的节点类似于二叉树的节点，主要区别在于它有四个指针（每个象限一个），而不是普通二叉树中的两个（“左”和“右”）。此外，关键字通常被分解为两部分，分别指x和y坐标。因此，一个节点包含以下信息：4个指针：quad['NW']，quad['NE']，quad['SW']和quad['SE'] point；这反过来包含：key；通常表示为x，y坐标 value；例如名称

然后，您可以编写一个递归函数来查询AABB范围内的所有点。您可以调整QueryRange()的实现。

class QuadTree
{
  function queryRange(AABB range)
  {
    Array of XY pointsInRange;  // Prepare an array of results

    // Check objects at this quad level
    for (int p := 0; p < points.size; p++)
    {
      if (range.containsPoint(points[p]))
        pointsInRange.append(points[p]);
    }

    pointsInRange.appendArray(northWest->queryRange(range));
    pointsInRange.appendArray(northEast->queryRange(range));
    pointsInRange.appendArray(southWest->queryRange(range));
    pointsInRange.appendArray(southEast->queryRange(range));

    return pointsInRange;
  }
}

- kiriloff

---

四叉树在对矩形区域进行空间和查询效率方面非常高效，但对于像这里所描述的整个索引的操作则不太高效。 - Corey G

为什么对于范围仅限于一个元素的情况不够高效？ - kiriloff

它的最坏情况下是O(log(n))查找，如果您以这种方式扩展整个索引，将会达到最坏情况的性能。相反，哈希表和矩阵方法都是O(1)查找。 - Corey G

也许查询范围算法很昂贵，但结构仍然适合点存储检索。 - kiriloff

适合什么样的方式？除非您指定了预期的访问模式，否则没有数据结构适用于特定类型的数据。例如，如果数据是密集的，并且访问模式是整个行和列，每个索引的可能性都是均匀的，则四叉树比二维数组更慢，需要更多的存储空间。 - Corey G

Answer 2

你不需要同时使用二维数组和单独的哈希表。如果你的数据是密集的，表示所有（或大多数）矩形区域，则仅使用二维数组就足够了。你可以询问哪个坐标最可能用于查找，然后构造数组使外部坐标是该坐标，以便在内存中本地化该坐标的查找，但除此之外，你无法做得更好。相反，对于稀疏数据，哈希表是你能做到的最好的选择。（我假设你将坐标哈希到点对象的数组中）。是否提供了有关数据性质或最可能如何使用它的更多信息？

- Corey G

---

当我说我将使用哈希表来存储x坐标时，由于对应的y坐标会发生冲突，因此我将使用链表。然后面试官说，如果我已经在这些链表中使用指针，那么我是否可以更好地利用这些指针。 - user2328404

我不知道，也许他建议将x和y哈希表某种方式合并在一起以节省空间。 - user2328404