Самый быстрый способ найти элемент в отсортированном ArrayList

Question

В Java у меня есть ArrayList со списком объектов. У каждого объекта есть поле даты, которое является просто длинным типом данных. ArrayList сортируется по полю даты. Я хочу вставить новый объект в ArrayList, чтобы он отображался в правильной позиции относительно его даты. Единственное решение, которое я вижу, это перебрать все элементы и сравнить поле даты объекта, вставляемого в объекты, которые повторяются, а затем вставить его, как только я доберусь до правильной позиции. Это будет проблемой производительности, если мне придется вставить много записей.

Каковы возможные способы улучшения этой производительности? Может быть, ArrayList не лучшее решение?

Answer 1

Я бы сказал, что вы правильно сделать заявление:

Может быть, ArrayList не является лучшим решением

Лично я считаю, что структура дерева будет лучше подходит для этого , В частности, Дерево двоичного поиска, которое сортируется по времени времени объекта. Когда вы создадите дерево, вы можете использовать бинарный поиск, который принимает O (log n) раз.

Answer 2

Я бы подумал использовать TreeSet и сделать свой предмет: Comparable. Затем вы получаете все из коробки.

Если это невозможно, я бы искал индекс через Collections.binarySearch(...).

EDIT: Убедитесь, что производительность является проблемой, прежде чем приступить к оптимизации

Answer 3

ли не бинарный поиск + O (п) вставки плохо для вас, зависит, по крайней мере, эти вещи:

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

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