Производительность коллекции Java при сравнении элементов

Question

Основной вопрос производительности от кого-то из C / C ++.

Я использую коллекцию (ArrayDeque), чтобы просто хранить, добавлять, удалять элементы по идентичности.Я знаю, что контракт на коллекцию должен использовать equals() при проверке равенства, например, во время remove(obj), но в моем случае я хочу использовать ссылочную семантику (например, IdentityHashMap, но мне не нужна карта).Так что я могу просто знать , что я никогда не переопределю equals() ни на одном из объектов, хранящихся в коллекции (которая объявлена ​​для хранения интерфейса).

Исходя из нативногопрограммирование, которое я не могу не задавать себе, будет ли скомпилированный код remove(obj) обходить элементы и выполнять виртуальный вызов на Object.equals() только для того, чтобы в конечном итоге сравнивать адреса?Так как я храню ссылки на интерфейсы, нет способа (?) Оптимизировать это с помощью final, поэтому компилятор не утруждает себя бесполезными вызовами (то есть встроенными), но теперь я забегаю вперед, потому что этоможет быть такая оптимизация не нужна в любом случае, и у JVM есть другие средства (девиртуализация?) для генерации оптимального кода в этом случае.

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

Answer 1

Когда вы используете метод remove, он будет вызывать метод equals для сравнения.В идеале вы должны переопределить метод equals и hashcode, чтобы использовать такие методы.В противном случае по умолчанию выполняется проверка типов и сравнение адресов.Настоятельно рекомендуется определить вашу реализацию методов equals и hashcode при использовании методов Collections.Что касается производительности, да, вы правы - все объекты в коллекции будут сканироваться линейно, пока JVM не обнаружит правильное соответствие.Это линейный поиск, поэтому временная сложность этой операции удаления займет O (n) времени.

Answer 2

Создание метода final не позволит избежать виртуального вызова, поскольку в любом случае будет использоваться код операции invokevirtual, и JVM не сможет определить, был ли метод окончательным или нет.

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