1

有没有更快的方法来做到这一点:

    Vector3* points = malloc(maxBufferCount*sizeof(Vector3));
    //put content into the buffer and increment bufferCount        
    ...

    // remove one point at index `removeIndex`
    bufferCount--;
    for (int j=removeIndex; j<bufferCount; j++) {
        points[j] = points[j+1];
    }

我问是因为我有一个巨大的缓冲区,我经常从中删除元素。

4

3 回答 3

5

不,抱歉 - 从数组中间删除元素需要O(n)时间。如果您真的想经常修改元素(即删除某些项目和/或添加其他项目),请改用链表 - 它具有恒定时间的删除和添加。相比之下,数组具有恒定的查找时间,而链表可以在线性时间内访问(读取)。因此,决定您将更频繁地做什么(阅读或写作)并根据该决定选择适当的数据结构。

但是请注意,我(好心地)假设您并没有试图犯下过早优化的罪行。如果您还没有基准测试这是瓶颈,那么可能就不用担心它了。

于 2013-02-26T20:56:49.670 回答
3
于 2013-02-26T21:01:10.353 回答
2

有几件事要说。memmove 函数可能会比您复制得更快,通常它由您的特定编译器的编写者优化以使用在没有内联汇编程序的 C 语言中不可用的特殊指令。我相信这些指令被称为 SIMD 指令(单指令多数据)?如果我错了,有人纠正我。

如果您可以保存要删除的项目,那么您可以通过对要删除的项目列表进行排序来优化,然后执行一次。这并不难,但只需要一些有趣的算术。

您也可以将每个项目存储在一个链表中,删除一个项目是微不足道的,但您会失去对数组的随机访问。

最后,您可以拥有一个额外的指针数组,与数组大小相同,每个指针指向一个元素。然后你可以通过双重间接访问数组,你可以通过交换指针对数组进行排序,你可以通过使它们的指针为空来删除项目。

希望这能给你一些想法。通常有一种方法可以优化事物,但随后它变得更加特定于应用程序。

于 2013-02-26T21:20:51.783 回答