Какая структура данных? LinkedList или любой другой на Java?

Question

У меня есть особые требования к структуре данных, которые будут использоваться в моей программе на Java. Он (Структура данных) должен иметь возможность хранить большие объемы данных (не фиксировано), мои основные операции - добавлять в конце, а также удалять/читать с самого начала (LinkedLists выглядят хорошо soo далеко). Но иногда мне также нужно удалить из середины, и именно здесь LinkedLists боятся боли. Может ли кто-нибудь предложить мне способ обойти это? Или любые оптимизации, благодаря которым я могу сделать удаление менее болезненным в LinkedLists?

Спасибо за помощь!

Answer 1

вы можете попробовать использовать связанный список с указателями после элемента evey 10000th, чтобы сократить время поиска середины, которую вы хотите удалить. здесь некоторые различные вариации связанного списка: http://experimentgarden.blogspot.com/2009/08/performance-analysis-of-thirty-eight.html

Answer 2

LinkedList падает на случайном порядке. Удаление, без поиска по произвольному доступу, является постоянным временем и поэтому действительно не слишком плохо для длинных списков.

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

ArrayDeque как ArrayList только он использует круговой буфер и имеет странный интерфейс.

Обычный совет: попробуйте.

Answer 3

LinkedHashMap может удовлетворить ваши цели Вы бы использовать итератор, чтобы вытащить вещи из передней и выполните поиск записи по ключу, когда вам необходимо получить доступ к середине списка

Answer 4

LinkedHashMap, вероятно, способ идти. Отлично подходит для итераций, операций deque и поиска в середине. Затраты дополнительно в памяти, тем не менее, поскольку вам нужно управлять набором ключей поверх вашей основной коллекции. Плюс, я думаю, что он оставит пробелы в тех пространствах, которые вы удалили, что привело к непоследовательному набору ключей (хотя это не должно влиять на итерацию).

Редактировать: Aha! Я знаю, что вам нужно: LinkedMultiSet! Все преимущества LinkedHashMap, но без лишнего набора ключей. Тем не менее, это немного сложнее.

Answer 5

Прежде всего вам нужно рассмотреть, будет ли вы удалять из центра списка часто по сравнению с длиной списка. Если ваш список содержит N элементов, но вы удаляете гораздо реже, чем 1/N, не беспокойтесь об этом. Используйте LinkedList или ArrayDeque, как пожелаете. (Если ваши списки иногда огромны, а затем уменьшаются, но в основном небольшие, то LinkedList лучше, так как восстановить память невозможно, в противном случае ArrayDeque не нуждается в дополнительных объектах, поэтому он немного быстрее и компактнее - кроме базовых массив никогда не уменьшится)

Если, с другой стороны, вы удаляете совсем немного чаще, чем 1/N, то вам следует рассмотреть LinkedHashSet, который поддерживает связанные очереди списка на вершине хэша-набор. - но набор, поэтому имейте в виду, что вы не можете хранить повторяющиеся элементы. У этого есть накладные расходы LinkedList и ArrayDeque, но если вы делаете центральные удаления часто, это, вероятно, будет стоить того.

Оптимальная структура, однако, если вам действительно нужна каждая минута скорости и вы готовы потратить время кодирования, чтобы получить ее, это будет «изменяемый размер» массива (т.е. перераспределяется, когда он слишком мал) с круговой буфер, где вы можете пропустить элементы из середины, установив их в null. (Вы также можете перераспределить буфер, когда слишком много было пустым, если у вас был случай с неправильным использованием.) Я не рекомендую кодировать это, если вы не действительно наслаждаетесь кодированием высокопроизводительных структур данных или не имеете убедительных доказательств того, что это один из ключевые узкие места в вашем коде и, следовательно, вам это действительно нужно.