存储频繁添加和删除元素的数组的有效方法

计算科学 matlab 内存管理 数据存储
2021-11-30 06:35:09

在任何时间点,我都有一个 N 点列表,将添加和删除点,使总点数随时间变化。如果我只使用一个数组来存储这些信息,我担心它会减慢很多速度,因为随着元素数量的变化,计算机将不得不在内存中移动东西。

什么是存储此信息的方法,可以有效地添加和删除元素,但仍然可以轻松访问存储在数组中的信息以进行简单的功能/绘图?我正在使用 matlab,希望它不会对我造成太多限制。

1个回答

让我从以下内容开始:即使是非常优秀和经验丰富的程序员也很难估计一段特定的代码是否对性能至关重要。这就产生了“过早的优化是万恶之源”的格言,可以翻译为“不必要的优化代码会导致代码晦涩难懂,难以维护、调试,并且会包含很多错误”。结果是这样的:除非你有具体的证据表明你选择的任何算法实际上都很慢,否则选择你能想到的最简单的数据结构和算法!

现在到手头的问题:有许多数据结构通常用于您的案例并针对特定案例进行了优化。

  • 如果您知道只会在 set末尾添加或删除 set 的元素,那么您通常会使用“堆栈”。如果新元素随机进入并且处理哪些元素无关紧要,就会发生这种情况——只需取堆栈中最顶层的元素即可。

  • 如果您只想将元素添加到集合的末尾,并且想要处理(并删除)集合中最长的元素,那么您将需要使用“双端队列”(“deque ”)。这模拟了一个堆栈,您只删除最底部的元素。

  • 如果删除可能发生在集合中的任何元素上,那么您可以使用“链表”,其中插入和删除很便宜,但查找元素可能很昂贵(因为您可能必须搜索所有元素才能找到它)。

  • 如果删除可能发生在集合中的任何元素上,并且您需要一种有效的方法来查找特定元素,那么您需要使用“集合”。

我不是 matlab 人,所以不知道这些数据结构在什么名称下可用。但是它们在所有编程语言中都被广泛使用,如果它们在 matlab 中以某种形式或其他形式不可用,我会感到非常惊讶。