Эффективность ArrayList

Question

Я делаю программу на Java, на которой шар отскакивает на экране. Пользователь может добавлять другие шары, и все они отскакивают друг от друга. Мой вопрос заключается в хранении добавленных шаров. На данный момент я использую ArrayList для их хранения, и каждый раз при нажатии пробела создается новый класс шаров и добавляется в список массивов. Это самый эффективный способ сделать что-то? Я не указываю размер списка массивов в начале, так что неэффективно распределять новое пространство в массиве каждый раз, когда пользователь хочет новый шар, даже если счет шара встанет в сотни? Есть ли другой класс, который я мог бы использовать, чтобы справиться с этим более эффективно?

Спасибо!

EDIT:

К сожалению, я должен был быть более ясным. Я повторяю шары каждые 30 миллисекунд, используя вложенные для циклов, чтобы увидеть, пересекаются ли они друг с другом. Я получаю доступ к одному шару чаще всего (мяч, который пользователь может контролировать с помощью клавиш со стрелками, еще одна особенность игры), но пользователь может выбрать переключатель шаров управления. Шары никогда не удаляются. Итак, я выполняю довольно сложные вычисления (я использую свой собственный векторный класс, чтобы перемещать их друг от друга при каждом столкновении) на шарах очень часто.

Answer 1

Измерьте это и узнайте! Во всей серьезности, часто раз лучший способ получить ответы на эти вопросы - это настроить тест и обменять различные типы коллекций.

Я могу сказать, что он не будет выделять новое пространство каждые время, когда вы добавляете новый элемент в ArrayList. Дополнительное пространство выделяется так, что у него есть место для роста.

LinkedList - это еще один вариант списка. Очень дешево добавлять элементы, но произвольный доступ (list.get (10)) стоит дорого. Наборы также могут быть хорошими, если вам не нужен заказный доступ (хотя есть и упорядоченные наборы), и вам нужна реализация Map, если вы обращаетесь к ним с помощью своего рода ключа/id. Все зависит от того, как вы используете коллекцию.

Обновление, основанная на дополнительных данных Похоже, что вы в основном выполняете последовательные чтения по всему списку. В этом случае LinkedList, вероятно, является вашим лучшим выбором. Хотя опять же, если вы только раскрываете интерфейс List для остальной части вашего кода (или даже более общей коллекции), вы можете легко поменять местами различные реализации и фактически измерить разницу.

Answer 2

о ArrayList в Java, сложность удалить в конце и добавить один элемент is Amortize O(1). Или, можно сказать, он почти эффективен в большинстве случаев. (В некоторых редких случаях это будет ужасно.)

Но прежде чем выбирать структуру данных, подумайте над своим дизайном.

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

2. Если вы часто найдете один мяч во всех своих шарах, то другая структура данных, такая как HashMap или HashSet, будет лучше.

3. Или вы часто удалять в середине вашего списка, возможно, LinkedList будет подходящим выбором :)

Answer 3

Я рекомендовал бы работать так, как, в которой вам необходимо открыть шары, и выбрать соответствующий интерфейс (не выполняется), например. Если вы получаете доступ только последовательно, используйте Список. Если вам нужно найти мяч по ID, подумайте о карте. Интерфейс должен соответствовать вашим требованиям с точки зрения функциональности, а не с точки зрения скорости/эффективности.

Затем выберите реализацию, например. HashMap или TreeMap, и напишите свой код.

После этого профайл - ваш код неэффективен в коде доступа к шару? Если это так, попробуйте оптимизировать, переключившись на альтернативную реализацию, более соответствующую вашим потребностям.

Answer 4

ArrayList - высоко оптимизированная и очень эффективная оболочка поверх простого массива Java. Небольшие временные накладные расходы происходят от копирования элементов массива, что происходит, когда распределенный размер меньше требуемого количества элементов. Когда вы вырастите массив в несколько сотен предметов, копирование произойдет менее десяти раз, поэтому цена, которую вы платите за незнание размера заранее, очень мала. Вы также можете уменьшить это накладные расходы, предложив начальный размер для вашего ArrayList.

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

Я повторяю шарики каждые 30 миллисекунд, используя вложенные петли, чтобы увидеть, пересекаются ли они друг с другом.

Это не имеет ничего общего с коллекцией, в которой хранятся шары. Вы можете использовать spatial index, чтобы улучшить скорость поиска пересечений.