如何在数组中移动项
本文关键字:移动 数组 | 更新日期: 2023-09-27 17:48:51
我有一个时间敏感的项数组。一段时间后,最后一个项目需要脱落,并在开始时放置一个新项目。
最好的方法是什么?
我建议使用队列,只是数组或列表的一个特殊实例。当您的定时事件发生时,从队列中弹出最后一个项目,然后推送您的新项目。
使用数组可能最简单的方法是使用循环索引。与其总是查看array[n],不如引用array[cIndex](其中cIndex指的是要索引的数组中的项(cIndex根据arraySize(cIndex%arraySize)递增)。
当您选择删除数组中最旧的项时,只需引用位于((cIndex+(arraySize-1))%arraySize)的元素。
或者,您可以使用linkedList方法。
请改用队列。
通过使用队列,最好是使用链表实现的队列。
看看使用队列而不是简单的数组。
如果有固定数量的项目,队列就会工作。
假设"时间量"是已知的,那么使用DateTime键的SortedDictionary并重写Add方法以删除所有键太旧的项如何。
LinkedList<T> 具有AddFirst和RemoveLast成员,它们应该可以完美工作。
编辑:查看Queue文档,它们似乎使用了一个内部数组。只要实现使用圆形数组类型的算法,性能就应该不错。
在csharp 3中,您可以执行:
original = new[] { newItem }.Concat(
original.Take(original.Count() - 1)).ToArray()
但您可能最好使用专门的数据结构
Queue
非常适合FIFO阵列。对于一般数组处理,请使用List(T)例如,Insert(0, x)
和RemoveAt(0)
方法将项目放在或删除列表前面。
从技术上讲,您需要一个deque。队列中只有一端的项目被推送和弹出。两端都有一个开口。
大多数语言都允许数组操作,只需删除第一个元素,然后在末尾放另一个元素。
或者,您可以通过循环来移动每个元素。只需将每个元素(从最旧的元素开始)替换为其相邻元素即可。然后将新项目放置在最后一个元素中。
如果你知道你的deque不会超过一定的尺寸,那么你可以把它做成圆形。你需要两个指针来告诉你两端在哪里。添加和删除项目,将相应地增加/减少指针。您必须检测缓冲区溢出情况(即指针"交叉")。你必须使用模运算,这样你的指针就可以绕着数组转一圈。
或者,您可以对数组中的每个元素加上时间戳,并在它们变得太"旧"时将其删除。您可以通过以相同的方式对一个单独的数组进行索引来实现这一点,也可以通过将时间戳存储在其中一个子元素中的两个元素数组的数组来实现。
如果你正在寻找最快的方法,它将是一个圆形数组:你可以跟踪你在数组中的当前位置(ndx)和数组的末尾(end),所以当你插入一个项时,你会隐式地删除最旧的项。
循环数组是我所知道的固定大小队列的最快实现。
例如,在C/C++中,int(当得到0时退出)的情况如下:
int queue[SIZE];
int ndx=0; // start at the beginning of the array
int end=SIZE-1;
int newitem;
while(1){
cin >> newitem;
if(!newitem) // quit if it's a 0
break;
if(ndx>end) // need to loop around the end of the array
ndx=0;
queue[ndx] = newitem;
ndx++
}
可以进行大量优化,但如果你想自己构建,这是最快的路线。
如果您不关心性能,请使用附带的Queue对象,因为它应该是通用的。
它可能经过优化,也可能没有经过优化,而且可能不支持固定大小的列表,所以在使用之前一定要查看上面的文档。