Почему list.size()> 0 медленнее, чем list.isEmpty() в Java?

Почему list.size()>0 медленнее, чем list.isEmpty() в Java? Другими словами, почему isEmpty() предпочтительнее size()>0?

Когда я смотрю на реализацию в ArrayList, то похоже, что скорость должна быть одинаковой:

ArrayList.size()

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
      return size;
    }

ArrayList.isEmpty()

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
     }

Если мы просто напишем простую программу, чтобы получить время от обоих методов, этот случай size() будет принимать больше isEmpty() во всех случаях, почему это так?

Вот мой TestCode;

import java.util.List;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        List l=new Vector();
        int i=0;
        for(i=0;i<10000;i++){
            l.add(new Integer(i).toString());
        }
        System.out.println(i);
        Long sTime=System.nanoTime();
        l.size();
        Long eTime=System.nanoTime();
        l.isEmpty();
        Long eeTime=System.nanoTime();
        System.out.println(eTime-sTime);
        System.out.println(eeTime-eTime);
    }
}

Здесь eTime-sTime>eeTime-eTime во всех случаях. Почему?

Ответы

Ответ 1

Недопустимый код проверки.

Просто измените порядок, т.е. вызовите isEmpty first и size > 0 second, и вы получите противоположный результат. Это связано с загрузкой классов, кэшированием и т.д.

Ответ 2

Для ArrayLists, да - вы правы, что операции выполняются (примерно) в одно и то же время.

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

Итак, если вы абсолютно знаете, что список является реализацией ArrayList и никогда не изменится, это не имеет большого значения; но:

Это плохая практика программирования, чтобы связать себя с конкретной реализацией.
Если ситуация изменится через несколько лет после реструктуризации кода, тестирование покажет, что "это работает", но все работает менее эффективно, чем раньше.
Даже в лучшем случае size() == 0 по-прежнему не быстрее, чем isEmpty(), поэтому нет оснований для использования первого.
isEmpty - это более четкое определение того, что именно вы на самом деле заботитесь и тестируете, и поэтому ваш код становится более понятным.

(Кроме того, я бы пересмотрел использование NULL в заголовке вопроса, сам вопрос и эти операции не имеют никакого отношения к тому, являются ли любые ссылки на объекты нулевыми.)

* Я изначально написал LinkedList здесь, ссылаясь на java.util.LinkedList, хотя эта конкретная реализация явно хранит свою длину, делая здесь операцию size() O (1). Более наивная операция связанного списка может не сделать этого, и в более общем смысле нет гарантии эффективности при реализации List.

Ответ 3

Извините, но ваш тест ошибочен. Взгляните на Теория и практика Java: анатомия ошибочного микрообъектива для общего описания того, как приблизиться к эталонам.

Обновление: для правильного эталона вы должны посмотреть Japex.

Ответ 4

Ты сказал:

Здесь eTime-sTime>eeTime-eTime во всех случаях Почему?

Во-первых, это, вероятно, из-за вашего тестового кода. Вы не можете проверить скорость вызова l.size() и l.isEmpty() одновременно, так как они оба запрашивают одно и то же значение. Скорее всего, вызов l.size() загрузил размер вашего списка в ваш кэш-память процессора, и вызов l.isEmpty() в результате намного быстрее.

Вы можете попробовать вызвать l.size() пару миллионов раз и l.isEmpty() пару миллионов раз в двух отдельных программах, но теоретически компилятор может просто оптимизировать все эти вызовы, так как вы на самом деле не что-либо с результатами.

В любом случае разница в производительности между ними будет незначительной, особенно после того, как вы сделаете сравнение, которое нужно сделать, чтобы увидеть, пуст ли список (l.size() == 0). Скорее всего, сгенерированный код будет выглядеть почти полностью аналогичным. Как отмечали некоторые другие плакаты, в этом случае вы хотите оптимизировать читаемость, а не скорость.

edit: Я сам тестировал. Это в значительной степени бросок. size() и isEmpty(), используемые на Vector, дали разные результаты при длительных прогонах, но не побивали друг друга последовательно. При запуске на ArrayList size() казалось быстрее, но не сильно. Это, скорее всего, связано с тем, что доступ к Vector синхронизирован, поэтому то, что вы действительно видите при попытке сравнить доступ к этим методам, - это служебные данные синхронизации, которые могут быть очень чувствительными.

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

Ответ 5

Учитывая эти две реализации, скорость должна быть такой же, что и правда.

Но это далеко не единственно возможные реализации этих методов. Например, примитивный связанный список (тот, который не сохраняет размер отдельно) может ответить isEmpty() гораздо быстрее, чем вызов size().

Что еще более важно: isEmpty() точно описывает ваше намерение, в то время как size()==0 является излишне сложным (конечно, не слишком сложным, но любой ненужной сложности вообще следует избегать).

Ответ 6

Подсчет элементов в связанном списке может быть очень медленным.

Ответ 7

В соответствии с PMD (анализатор исходного кода на основе статического набора правил) isEmpty() является предпочтительным. Здесь вы можете найти набор правил PMD. Найдите правило UseCollectionIsEmpty.

http://pmd.sourceforge.net/rules/design.html

По моему мнению, это также помогает поддерживать целостность всего исходного кода, а не половину людей, использующих isEmpty(), а остальные используют size() == 0.

Ответ 8

.size() должен посмотреть весь список, а .isEmpty() может остановиться на первом.

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

Ответ 9

В общем случае невозможно сказать, что это быстрее, потому что это зависит от того, какую реализацию интерфейса List вы используете.

Предположим, что речь идет о ArrayList. Посмотрите исходный код ArrayList, вы можете найти его в файле src.zip в каталоге установки JDK. Исходный код методов isEmpty и size выглядит следующим образом (Sun JDK 1.6 update 16 для Windows):

public boolean isEmpty() {
    return size == 0;
}

public int size() {
    return size;
}

Вы можете легко увидеть, что оба выражения isEmpty() и size() == 0 будут сведены к точно таким же утверждениям, поэтому один, конечно, не быстрее, чем другой.

Если вам интересно, как это работает для других реализаций интерфейса List, найдите исходный код самостоятельно и узнайте.