Как сдвинуть элементы в массиве?

Question

У меня есть массив элементов, которые чувствительны ко времени. Через некоторое время последний элемент должен упасть, и новый элемент помещается в начало.

Каков наилучший способ сделать это?

Answer 1

Я бы предложил использовать очередь, просто специальный экземпляр массива или списка. Когда происходит ваше временное событие, извлеките последний элемент из очереди, а затем вставьте новый элемент.

Answer 2

Вероятно, самый простой способ сделать это с массивом - это использовать циклический индекс. Вместо того, чтобы всегда смотреть на массив [n], вы бы ссылались на массив [cIndex] (где cIndex ссылается на элемент в индексируемом массиве (cIndex увеличивается на основе arraySize (cIndex% arraySize)).

Когда вы решите удалить самый старый элемент в массиве, вы просто будете ссылаться на элемент, расположенный в ((cIndex + (arraySize - 1))% arraySize).

В качестве альтернативы вы могли бы использовать подход связанный список.

Answer 3

Вместо этого используйте Очередь .

Answer 4

LinkedList имеет члены AddFirst и RemoveLast, которые должны отлично работать.

РЕДАКТИРОВАТЬ: Глядя на документы очереди, кажется, они используют внутренний массив. Пока реализация использует алгоритм с типом кругового массива, производительность должна быть в порядке.

Answer 5

Очередь будет работать, если существует фиксированное количество элементов.

Учитывая, что «количество времени» известно, как насчет SortedDictionary с ключом DateTime и переопределить метод Add, чтобы удалить все элементы с ключами, которые являются слишком старыми.

Answer 6

Посмотрите на , используя Очередь вместо простого массива.

Answer 7

Используя Очередь, предпочтительно одну, реализованную с использованием связанного списка.

Answer 8

Если вы ищете способ самый быстрый , это будет круговой массив: вы отслеживаете свою текущую позицию в массиве (ndx) и конец массива (конец), поэтому, когда вы вставляете элемент, вы неявно удаляете самый старый элемент.

Круговой массив - самая быстрая реализация очереди фиксированного размера, о которой я знаю.

Например, в C / C ++ это будет выглядеть так для целых чисел (выход, когда вы получите 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, потому что он должен быть обобщенным.

Он может быть или не быть оптимизирован, и он может не поддерживать список фиксированного размера, поэтому обязательно проверьте документацию на него перед использованием.

Answer 9

Технически вам нужна дека. В очереди есть элементы, которые перемещаются и удаляются только с одного конца. Deque открыт на обоих концах.

Большинство языков позволяют манипулировать массивами, просто удалите первый элемент и поместите еще один в конец.

В качестве альтернативы вы можете перемещать каждый элемент, циклически. Просто замените каждый элемент (начиная с самого старого) своим соседом. Затем поместите новый элемент в последний элемент.

Если вы знаете, что ваша дека не превысит определенного размера, вы можете сделать ее круглой. Вам понадобятся два указателя, чтобы сказать вам, где находятся два конца. Добавление и удаление предметов увеличит / уменьшит ваши указатели соответственно. Вы должны будете обнаружить условие переполнения буфера (т. Е. Ваши указатели «пересекаются»). И вам придется использовать модульную арифметику, чтобы ваши указатели шли по кругу вокруг массива.

Или вы можете поставить отметку времени для каждого элемента в массиве и удалить их, когда они станут слишком «старыми». Вы можете сделать это, сохраняя отдельный массив индексированным таким же образом, или располагая массивом из двух массивов элементов с отметкой времени, сохраненной в одном из подэлементов.

Answer 10

Queue отлично подходит для массивов FIFO. Для обработки общего массива используйте List (T) Insert(0, x) и RemoveAt(0) методы для размещения или удаления элементов перед списком, например.