c - 在c中以恒定时间从数组中删除3D点

Question

我这里有一个函数，它从 O(n) 的数组中删除 3D 点。但是当我运行代码时，一旦它到达数组中的大约 16000 个点，它最终会花费太长时间来删除。我想让我的删除代码更快。我将如何更改我的代码以使其在恒定时间内删除？

这是我创建的结构:

typedef struct point
{
  double x, y, z;
} point_t;

typedef struct 
{
  size_t len;
  point_t* points;
  size_t reserved; 

} point_array_t;

这是我删除数组中 3D 点的函数:

int point_array_remove( point_array_t* pa, unsigned int i )
{
    assert( pa );
    if( i >= pa->len )
        return 1;
    pa->points[i] = pa->points[pa->len-1];
    while( i < pa->len-1 )
    {
        pa->points[i] = pa->points[i+1];
        i++;
    }
    pa->len--;
    return 0;
}

Answer 1

问题是您要移动线性数量的项目以缩小差距。如果有必要，您无法避免线性时间要求。

但是，如果数组中元素的顺序不重要，您可以直接将最后一个元素移到间隙中。这意味着您只需移动一个元素 - 可以在恒定时间内完成的恒定工作量。

不过，仍然存在一个问题，因为您仍然需要搜索最后一个元素，而这将花费线性时间。但是，如果您知道数组的大小，则可以在恒定时间内直接转到最后一项 - 因此您需要跟踪该大小。将它存储在一个整数变量中，当数组大小发生变化时更新它等。

需要注意的一个小问题 - 如果您删除的项目是最后一个项目怎么办。

编辑

如果上述方法 Not Acceptable ，您所能做的就是用不同的数据结构替换数组。用于恒定时间插入和删除的经典数据结构(前提是您已经找到正确的项/位置，并保留剩余项的顺序)是链表。

与数组相比，链表具有成本，因此如果您准备好使用它，一种选择是组合链表和数组 - 有一个小型数组的链表。小数组将有一些固定的最大大小，并且知道它们包含多少元素。插入和删除是常数时间，因为每个小数组(至多)有一定数量的要移动的元素 - 该数组的最大大小(在这种情况下不是作弊)。

所以你的节点类型可能看起来像......

typedef struct
{
  chain_node_t *next;
  chain_node_t *prev;
  unsigned      num_in_this_chunk;
  point_t point [CHAIN_CHUNK_MAX];

} chain_node_t;

由于太习惯于 C++ 而不是 C，我可能在这个问题上犯了一点小错误，但它应该很容易修复。