Сравнение производительности механизма обхода JAVA

Java

Эта статья была впервые опубликована вблог мультфильма
    Пожалуйста, укажите источник:мультфильм против GitHub.IO/мультфильм - нет...

причина

В последнее время я пишу leetcodeLemonade ChangeВ то время было обнаружено, что потребление времени циклом for и циклом forEach было несовместимым, а разница в записи представления удваивалась... Обычно для реализации большей части бизнес-логики требуется помощь механизма обхода.Хотя мы заметили сравнение производительности различных операций со структурами данных, мы игнорируем разницу в производительности механизма обхода. Начал писать два дня назад, прокрастинация...

текст

На данном этапе я знаю, что есть три механизма обхода JAVA.

  • для цикла

  • цикл forEach

  • Цикл итератора

Существуют тысячи структур данных JAVA, но большинство из них представляют собой инкапсуляцию базовых структур данных.По сравнению с HashMap, который опирается на массивы узлов, нижний уровень LinkedList представляет собой связанный список.

Подводя итог, я думаю, что есть две основные структуры данных JAVA.

  • множество
  • связанный список

Если вы добавите Hash (операция Hash несовместима с массивами и связанными списками), есть три

Поскольку большая часть обычной разработки предпочитает упакованную структуру данных, я буду использовать следующую

  • ArrayList (обернутый массив)
  • LinkedList (упакованный связанный список)
  • HashSet (заброшенный массив хэши типа)

Разница во времени между этими тремя структурами данных, когда механизм обхода отличается

Некоторые люди могут спросить меня, почему я не сравниваю HashMap, потому что в дизайне JAVA сначала реализуется Map, а затем Set. Если вы читали исходный код, вы обнаружите, что: в реализации каждого подкласса Set есть сериализованная реализация Map, соответствующая атрибуту, и поскольку сложность времени поиска Hash составляет O (1), вы можете искать после того, как ключ время окупаемости примерно одинаковое, поэтому я не сравниваю HashMap.

Не по теме

Я прочитал «Crazy JAVA» и прочитал: Разработчик JAVA устанавливает значение во внутреннем массиве записей Map равным нулю и реализует Set. Поскольку я основываюсь на исходном коде и официальных документах, я не уверен, правильно это или нет, но поскольку ключи в Hash отличаются друг от друга, и элементы в Set также отличаются друг от друга, я думаю, что это вид правильный.

Для справедливости теста я возьму следующие ограничения

  • Размер каждой структуры данных установлен на три порядка.
    • 10
    • 100
    • 1000
  • Элементы генерируются с использованием случайных чисел
  • Операция обхода заключается в выводе значения текущего элемента

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

Сравнение списков массивов

  • код

    public class TextArray {

    private static Random random;

    private static List<Integer> list1;

    private static List<Integer> list2;

    private static List<Integer> list3;

    public static void execute(){
        random=new Random();
        initArray();
        testForWith10Object();
        testForEachWith10Object();
        testIteratorWith10Object();
        testForWith100Object();
        testForEachWith100Object();
        testIteratorWith100Object();
        testForWith1000Object();
        testForEachWith1000Object();
        testIteratorWith1000Object();
    }

    private static void testForWith10Object(){
        printFor(list1);
    }

    private static void testForWith100Object(){
        printFor(list2);
    }

    private static void testForWith1000Object(){
        printFor(list3);
    }

    private static void testForEachWith10Object(){
        printForeach(list1);
    }

    private static void testForEachWith100Object(){
        printForeach(list2);
    }

    private static void testForEachWith1000Object(){
        printForeach(list3);
    }

    private static void testIteratorWith10Object() {
        printIterator(list1);
    }

    private static void testIteratorWith100Object() {
        printIterator(list2);
    }

    private static void testIteratorWith1000Object() {
        printIterator(list3);
    }

    private static void printFor(List<Integer> list){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int i=0,length=list.size();i<length;i++){
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("for for "+list.size()+":"+(end-start)+"ms");
    }

    private static void printForeach(List<Integer> list){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int temp:list){
            System.out.print(temp+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("foreach for "+list.size()+":"+(end-start)+"ms");
    }

    private static void printIterator(List<Integer> list){
        System.out.println();
        System.out.print("data:");
        Iterator<Integer> it=list.iterator();
        long start=System.currentTimeMillis();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("iterator for "+list.size()+":"+(end-start)+"ms");
    }

    private static void initArray(){
        list1=new ArrayList<>();
        list2=new ArrayList<>();
        list3=new ArrayList<>();
        for(int i=0;i<10;i++){
            list1.add(random.nextInt());
        }
        for(int i=0;i<100;i++){
            list2.add(random.nextInt());
        }
        for(int i=0;i<1000;i++){
            list3.add(random.nextInt());
        }
    }
}

  • вывод (игнорируя вывод в элементы)

    for for 10:1ms
foreach for 10:0ms
iterator for 10:2ms

for for 100:5ms
foreach for 100:4ms
iterator for 100:12ms

for for 1000:33ms
foreach for 1000:7ms
iterator for 1000:16ms
      10 100 1000
    for 1ms 5ms 33ms
    forEach 0ms 4ms 7ms
    Iterator 2ms 12ms 16ms

  • В заключение

    Производительность for является самой нестабильной, за ней следует foreach, а iterator — лучший.

  • Рекомендации

    1. В случае, когда объем данных не ясен (может быть, 1w, 10w или другое), рекомендуется использовать Iterator для обхода

    2. Когда объем данных очевиден, а величина мала, предпочтение отдается foreach.

    3. Когда вам нужно использовать индекс, накладные расходы на использование инкрементной переменной меньше, чем для

Сравнение связанных списков

  • код

    public class TextLinkedList {

    private static Random random;

    private static List<Integer> list1;

    private static List<Integer> list2;

    private static List<Integer> list3;

    public static void execute(){
        random=new Random();
        initList();
        testForWith10Object();
        testForEachWith10Object();
        testIteratorWith10Object();
        testForWith100Object();
        testForEachWith100Object();
        testIteratorWith100Object();
        testForWith1000Object();
        testForEachWith1000Object();
        testIteratorWith1000Object();
    }

    private static void testForWith10Object() {
        printFor(list1);
    }

    private static void testForEachWith10Object() {
        printForeach(list1);
    }

    private static void testIteratorWith10Object() {
        printIterator(list1);
    }

    private static void testForWith100Object() {
        printFor(list2);
    }

    private static void testForEachWith100Object() {
        printForeach(list2);
    }

    private static void testIteratorWith100Object() {
        printIterator(list2);
    }

    private static void testForWith1000Object() {
        printFor(list3);
    }

    private static void testForEachWith1000Object() {
        printForeach(list3);
    }

    private static void testIteratorWith1000Object() {
        printIterator(list3);
    }

    private static void printFor(List<Integer> list){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int i=0,size=list.size();i<size;i++){
            System.out.print(list.get(i));
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("for for "+list.size()+":"+(end-start)+"ms");
    }

    private static void printForeach(List<Integer> list){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int temp:list){
            System.out.print(temp+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("foreach for "+list.size()+":"+(end-start)+"ms");
    }

    private static void printIterator(List<Integer> list){
        System.out.println();
        System.out.print("data:");
        Iterator<Integer> it=list.iterator();
        long start=System.currentTimeMillis();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("iterator for "+list.size()+":"+(end-start)+"ms");
    }


    private static void initList() {
        list1=new LinkedList<>();
        list2=new LinkedList<>();
        list3=new LinkedList<>();
        for(int i=0;i<10;i++){
            list1.add(random.nextInt());
        }
        for(int i=0;i<100;i++){
            list2.add(random.nextInt());
        }
        for(int i=0;i<1000;i++){
            list3.add(random.nextInt());
        }
    }
}

  • вывод (игнорируя вывод в элементы)

    for for 10:0ms
foreach for 10:1ms
iterator for 10:0ms

for for 100:1ms
foreach for 100:0ms
iterator for 100:3ms

for for 1000:23ms
foreach for 1000:25ms
iterator for 1000:4ms
      10 100 1000
    for 0ms 1ms 23ms
    forEach 1ms 0ms 25ms
    Iterator 0ms 3ms 4ms

  • В заключение

    Foreach имеет самую нестабильную производительность, за ней следует for, а Iterator — лучший.

  • Рекомендации

    1. Попробуйте использовать итератор для обхода

    2. Когда вам нужно использовать индекс, накладные расходы на использование инкрементной переменной меньше, чем для

Сравнение HashSet

Примечание. Поскольку алгоритм обхода хеша несовместим с другими типами, сравнение цикла for отменяется.

  • код

    public class TextHash {

    private static Random random;

    private static Set<Integer> set1;

    private static Set<Integer> set2;

    private static Set<Integer> set3;

    public static void execute(){
        random=new Random();
        initHash();
        testIteratorWith10Object();
        testForEachWith10Object();
        testIteratorWith100Object();
        testForEachWith100Object();
        testIteratorWith1000Object();
        testForEachWith1000Object();
    }

    private static void testIteratorWith10Object() {
        printIterator(set1);
    }

    private static void testForEachWith10Object() {
        printForeach(set1);
    }

    private static void testIteratorWith100Object() {
        printIterator(set2);
    }

    private static void testForEachWith100Object() {
        printForeach(set2);
    }

    private static void testIteratorWith1000Object() {
        printIterator(set3);
    }

    private static void testForEachWith1000Object() {
        printForeach(set3);
    }

    private static void initHash() {
        set1=new HashSet<>();
        set2=new HashSet<>();
        set3=new HashSet<>();
        for(int i=0;i<10;i++){
            set1.add(random.nextInt());
        }
        for(int i=0;i<100;i++){
            set2.add(random.nextInt());
        }
        for(int i=0;i<1000;i++){
            set3.add(random.nextInt());
        }
    }

    private static void printIterator(Set<Integer> data){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        Iterator<Integer> it=data.iterator();
        while (it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("iterator for "+data.size()+":"+(end-start)+"ms");
    }

    private static void printForeach(Set<Integer> data){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int temp:data){
            System.out.print(temp+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("foreach for "+data.size()+":"+(end-start)+"ms");
    }
}

  • вывод (игнорируя вывод в элементы)

    iterator for 10:0ms
foreach for 10:0ms

iterator for 100:6ms
foreach for 100:0ms

iterator for 1000:30ms
foreach for 1000:9ms
      10 100 1000
    foreach 0ms 0ms 9ms
    Iterator 0ms 6ms 30ms

  • В заключение

    Производительность Foreach намного выше, чем у Iterator

  • Рекомендации

    В дальнейшем буду выбирать foreach, у которого хорошая производительность и на котором удобно писать.

Суммировать

  1. Производительность цикла for обычно ниже по сравнению с тремя, а стоимость увеличивается с большим отрывом. В будущем я бы предпочел использовать инкрементную переменную, а не for, даже когда мне нужно использовать индекс.
  2. Производительность Iterator является лучшей в массивах и связанных списках, которые должны быть оптимизированы разработчиками JAVA. В ситуациях, чувствительных ко времени ответа (например, веб-ответы), это предпочтительнее.
  3. Производительность foreach находится между этими двумя.Метод написания прост, и я постараюсь использовать его, когда он не зависит от времени.

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

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

Категории