Grabduck

Ошибки, снижающие производительность и их устранение

:

Добрый день, уважаемый читатель.

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

1. Борьба с инвариантами
Итак, что же такое инвариант и почему с ними стоит бороться? Говоря сухим академическим языком, инвариантом называется логическое выражение, истинное перед началом выполнения цикла и после каждого прохода тела цикла. Другими словам, это условие (или величина), неизменное во время выполнения цикла.

Рассмотрим следующий пример:

String string = “некоторая строка”;
for (int i = 0; i < string.length(); i++){        //string.length() вызывается при каждом проходе цикла
        //делаем что-то
}

Это чрезвычайно распространённая ошибка, которая может существенно ударить по производительности, когда при проверке истинности выполняется сложное действие или когда количество проходов цикла очень велико. Причина в том, что метод length() никак не меняет строку, следовательно, его вызов при каждом проходе является бесполезным. Думаю, читатель уже догадался, как можно оптимизировать цикл всего одной строчкой и сделать наш код более красивым и правильным:
String string = “некоторая строка”;
int stringLenght = string.length();        //длинна строки вычисляется лишь однажды
for (int i = 0; i < stringLenght; i++){
        //делаем что-то
}

Сразу же отмечу, что если исходная строка всё же изменяется в теле цикла, то данный метод бесполезен.

2. Неявный инвариант
Рассмотрим другой пример, в котором мной была допущена ошибка, связанная с инвариантами. Ошибку я обнаружил случайно, поскольку в данном случае она не столь очевидна. Однажды я писал класс, один из методов которого сканировал большой текстовый файл в поисках строк, соответствующих определённому шаблону. Шаблон был неизменен для каждого файла, поэтому логично было бы сделать вот так:

public class Parser {
        private Pattern p;
    
        public Parser(String pattern){
                //создаём шаблон неизменный в течение всего поиска
                p = Pattern.compile(pattern);
        }

        public void parseStrings(){
                BufferedReader br;
                //инициализируем br
                String s;
                while((s = br.readLine()) != null){
                        if (checkString(s))
                                //...
                }
        }

        private boolean checkString(String s){
                return p.matcher(s).matches();
        }
}

Однако, по непонятной причине в силу неопытности я сделал так:
public class Parser{
        private String pattern;

        public Parser(String pattern){
                this.pattern = pattern;
        }

        public void parseStrings(){
                BufferedReader br;
                //...
                String s;
                while((s = br.readLine()) != null){
                        if (checkString(s))
                                //...
                }
        }

        //неэффективная реализация метода
        private boolean checkString(String s){
                //шаблон создаётся каждый раз, хотя в этом нет необходимости
                Pattern p = Pattern.compile(pattern);
                return p.matcher(s).matches();
        }
}

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

3. Эффективное удаление из середины ArrayList.
Идея написать этот раздел родилась после прочтения поста хабражителя sphinks «Java собеседование. Коллекции». Отличная статья, которую я рекомендую всем как начинающим, там и более опытным разработчикам. Считаю, что каждый откроет для себя новые и интересные факты и станет более грамотным. Но вернёмся к нашим баранам спискам. Итак, меня заинтересовал вот этот фрагмент: «…удаление последнего элемента происходит за константное время. Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это вызывает перезапись всех элементов размещённых «правее» в списке на одну позицию влево, кроме того, при удалении элементов размер массива не уменьшается, до явного вызова метода trimToSize().»
Вдумайтесь: если из списка произвольной длинны вам необходимо удалить n элементов, начиная с позиции m, то независимо от длинны списка, будут перебраны и смещены левее все элементы, начиная с позиции m+n. И это будет выполняться при каждом вызове remove(). Думаю, читатель уже прикинул, сколько это займёт времени.
sphinks также предлагает способ оптимизации удаления: «На самом деле все довольно просто и очевидно, когда знаешь, как происходит удаление одного элемента. Допустим нужно удалить n элементов с позиции m в списке. Вместо выполнения удаления одного элемента n раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» n+m позиции на n элементов левее к началу списка. Таким образом, вместо выполнения n итераций перемещения элементов списка, все выполняется за 1 проход».
Я решил реализовать предложенный алгоритм и сравнить его быстродействие с простым вызовом remove().
Получился вот такой класс:

package collectionstudy;

import java.io.*;
import java.util.ArrayList;

public class Main {
    //позиция с которой удаляем
    private static int m = 0;
    //количество удаляемых элементов
    private static int n = 0;
    //количество элементов в списке
    private static final int size = 1000000;
    //основной список (для удаления вызовом remove() и его копия для удаления путём перезаписи)
    private static ArrayList<Integer> initList, copyList;
    
    public static void main(String[] args){
        
        initList = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
            initList.add(i);
        System.out.println("Список из 1.000.000 элементов заполнен");
        
        copyList = new ArrayList<>(initList);
        System.out.println("Создана копия списка\n");
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try{
            System.out.print("С какой позиции удаляем? > ");
            m = Integer.parseInt(br.readLine());
            System.out.print("Сколько удаляем? > ");
            n = Integer.parseInt(br.readLine());
        } catch(IOException e){
            System.err.println(e.toString());
        }
        System.out.println("\nВыполняем удаление вызовом remove()...");
        long start = System.currentTimeMillis();
        
        for (int i = m - 1; i < m + n - 1; i++)
            initList.remove(i);
        
        long finish = System.currentTimeMillis() - start;
        System.out.println("Время удаления с помощью вызова remove(): " + finish);
        System.out.println("Размер исходного списка после удаления: " + initList.size());
        
        System.out.println("\nВыполняем удаление путем перезаписи...\n");
        start = System.currentTimeMillis();
        
        removeEfficiently();
        
        finish = System.currentTimeMillis() - start;
        System.out.println("Время удаления путём смещения: " + finish);
        System.out.println("Размер копии списка:" + copyList.size());
    }
    
    private static void removeEfficiently(){
        /* если необходимо удалить все элементы, начиная с указанного,
         * то удаляем элементы с конца до m
         */
        if (m + n >= size){
            int i = size - 1;
            while (i != m - 1){
                copyList.remove(i);
                i--;
            }
        } else{
            //переменная k необходима для отсчёта сдвига начиная от места вставка m
            for (int i  = m + n, k = 0; i < size; i++, k++)
               copyList.set(m + k, copyList.get(i));
            
            /* удаляем ненужные элементы в конце списка
             * удаляется всегда последний элемент, так как время этого действия
             * фиксировано и не зависит от размера списка
             */
            int i = size - 1;
            while (i != size - n - 1){
                copyList.remove(i);
                i--;
            }
            //сокращаем длину списка путём удаления пустых ячеек
            copyList.trimToSize();
        }
    }
}

Сравним?
run:
Список из 1.000.000 элементов заполнен
Создана копия списка

С какой позиции удаляем? > 600000
Сколько удаляем? > 20000

Выполняем удаление вызовом remove()...
Время удаления с помощью вызова remove(): 22359
Размер исходного списка после удаления: 980000

Выполняем удаление путем перезаписи...

Время удаления путём смещения: 62
Размер копии списка:980000
СБОРКА УСПЕШНО ЗАВЕРШЕНА (общее время: 33 секунды)

Как говориться, почувствуйте разницу! :)
Используя метод removeEfficiently() можно без особого труда написать свою, более эффективную реализацию ArrayList.

На сегодня это всё, надеюсь, что тебе было интересно и твой код станет более правильным и производительным. Комментарии, замечания и пожелания принимаются как в комментариях, так и в личку.

Успехов тебе!