Самая эффективная коллекция для такого рода LILO?

Question

Я программирую список последних сетевых сообщений, передаваемых/от клиента. В основном я просто хочу список, который хранит до X числа моих объектов сообщения. После того, как список достигнет желаемого размера, самый старый (первый) элемент в списке должен быть удален. Коллекция должна поддерживать свой заказ, и все, что нужно будет сделать, это

1. итерацию через него,
2. добавить элемент в конец, и
3. удалить элемент с самого начала, если # 2 делает его слишком длинным.

Что представляет собой наиболее эффективная структура/массив/коллекция/метод для этого? Благодаря!

Answer 1

Вы хотите использовать Queue.

Answer 2

Я не думаю, что LILO это реальный срок ... но вы ищете FIFO очереди

Answer 3

LinkedList должен быть то, что вы ищете

Answer 4

вы можете получить с простым старым ArrayList. При добавлении, просто сделать (предположим, что ArrayList называется ал)

if (al.size() >= YOUR_MAX_ARRAY_SIZE) 
{ 
    al.remove(0); 
} 

Answer 5

Вы можете использовать ArrayList для этого. Сегодняшние компьютеры копируют данные с такой скоростью, что это не имеет значения, если ваш список не может содержать миллиарды элементов.

Информация об исполнении: Копирование 10 миллионов элементов принимает 13ms (thirteen milliseconds) на моем двойном ядре. Поэтому, думая даже секунду об оптимальной структуре данных, это отходы , если только ваш случай использования сильно отличается. В этом случае: у вас более 10 миллионов элементов, и ваше приложение ничего не делает, кроме как вставки и удаления элементов. Если вы каким-либо образом работаете с вставленными/удаленными элементами, есть вероятность, что время, затраченное на эту операцию, превышает стоимость вставки/удаления.

Связанный список кажется лучше на первый взгляд, но ему требуется больше времени, когда выделение памяти плюс код более сложный (со всем обновлением указателя). Таким образом, время работы хуже. Единственное преимущество использования LinkedList в Java - это то, что класс уже реализует интерфейс Queue, поэтому его естественнее использовать в вашем коде (используя peek() и pop()).

[EDIT] Итак, давайте посмотрим на эффективность. Что такое эффективность? Самый быстрый алгоритм? Тот, который занимает наименьшее количество строк (и, следовательно, имеет наименьшее количество ошибок)? Алгоритм, который проще всего использовать (= наименьшее количество кода на стороне разработчика + меньше ошибок)? Алгоритм, который работает лучше всего (что не всегда является самым быстрым алгоритмом)?

Давайте рассмотрим некоторые детали: LinkedList реализует Queue, поэтому код, который использует этот список, является более простым (list.pop() вместо list.remove (0)). Но LinkedList будет выделять память для каждого add(), в то время как ArrayList выделяет память только один раз за N элементов. И чтобы уменьшить это еще дальше, ArrayList будет выделять элементы N * 3/2, так как ваш список будет расти, количество распределений сократится. Если вы знаете размер своего списка заранее, ArrayList будет выделять память только один раз. Это также означает, что GC имеет меньше помех для очистки. Таким образом, с точки зрения производительности, ArrayList выигрывает на порядок в среднем случае.

Синхронизированные версии необходимы только тогда, когда несколько потоков обращаются к структуре данных.С Java 5 многие из них значительно улучшили скорость. Если у вас есть несколько потоков для ввода и ввода потоков, используйте ArrayBlockingQueue, но в этом случае LinkedBlockingQueue может быть вариантом, несмотря на плохую производительность распределения, так как реализация может разрешить push и pop из двух разных потоков одновременно, пока размер очереди> = 2 (в этом специальном случае потокам не нужно будет обращаться к тем же указателям). Чтобы решить это, единственный вариант - запустить профилировщик и определить, какая версия выполняется быстрее.

Это говорит о том, что любой совет о производительности неправильный в 90% случаев, если он не подкреплен измерением. Сегодняшние системы стали настолько сложными, и на заднем плане так много происходит, что человеку просто невозможно понять или даже перечислить все факторы, которые играют определенную роль.

Answer 6

Я думаю, что вы хотите реализовать Queue<E>, где у вас есть методы поиска, вытягивания и удаления, как будто ничего нет на голове, пока счет не превысит пороговое значение, которое вы хотите. Вероятно, вы захотите обернуть одну из существующих реализаций.

Answer 7

I second @ rich-adams re: Queue. В частности, поскольку вы упомянули об ответах на сетевые сообщения, я думаю, вы можете захотеть что-то, что хорошо справляется с параллелизмом. Выезд ArrayBlockingQueue.

Answer 8

Основываясь на вашем третьем требовании, я думаю, вам придется расширить или обернуть существующую реализацию, и я рекомендую вам начать с ConcurrentLinkedQueue.

Другие рекомендации по использованию любой блокирующей очереди приводят вас к неправильному пути. Блокирующая очередь не позволит вам добавить элемент в полную очередь до удаления другого элемента. Кроме того, они блокируются, ожидая выполнения этой операции. По вашим собственным требованиям это не то поведение, которое вы хотите. Вы хотите автоматически удалить первый элемент, когда новый будет добавлен в полную очередь.

Должно быть достаточно просто создать обертку вокруг ConcurrentLinkedQueue, переопределяя метод offer для проверки size и емкости (ваш класс-оболочка будет поддерживать емкость). Если они равны, ваш метод предложения должен будет опросить очередь, чтобы удалить первый элемент перед добавлением нового.