19 May 2013

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

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

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

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.

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

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

Read more
21 Dec 2012

Рекурсивный перебор каталогов + прокрутка JScrollPane

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

Это моя первая статья в данном разделе. В ней я хочу уделить внимание особенностям работы с файловой системой в Java, алгоритму рекурсивного перебора каталогов и файлов, а также механизму реализации автоматической прокрутки JScrollPane во время динамического выведения текста на JTextArea.

N.B. Код проекта можно скачать здесь:

Рекурсивный вызов функции, т.е. вызов функцией самой себя из собственного тела, используется нечасто, однако во многих случаях он существенно упрощает задачу, помогая избавится от циклов, а в некоторых случаях просто незаменим.

Рассмотрим простейший пример с вычислением факториала, то есть произведения 1*2*3*4*…*n, где n - натуральное число. Можно взять быка за рога и забабахать вот такой цикл:

int result = 1;
if (n == 0 || n == 1){
    System.out.println(result);
} else {
    for (int i = 2; i <= n; i++){
        result *= i;
    }
}
System.out.println(result);

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

Вместо этого можно использовать рекурсию, и обойтись всего 7 строками:

int factorial(int n){
    if (n == 0){
        return 1;
    } else{
        return n * factorial(n-1);
    }
}

Известно, что самое лучшее решение - это простейшее решение. Действительно, цикл гораздо нагляднее и понятен интуитивно. Рекурсия же сложнее для понимания и восприятия. Однако, мы не ищем лёгких путей и стараемся написать красивый и правильный код, а значит должны использовать весь арсенал языка Java.

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

Код главного класса:

package filewalker;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

/**
 * Главный класс программы
 * Здесь происходит только отрисовка окна приложения
 * @author rad1kal
*/
public class FileWalker{
    private static JFrame frame;
    static MainPanel panel;
    
    public static void main(String[] args) {
        Dimension ScreenSize = Toolkit.getDefaultToolkit().getScreenSize();
        int x = ScreenSize.width / 2 - 600;
        int y = ScreenSize.height / 2 - 300;
        panel = new MainPanel();
        frame = new JFrame("FileWalker: рекурсивный поиск каталогов/файлов");
        frame.setLocation(x, y);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setPreferredSize(new Dimension(1200, 600));
        frame.pack();
        frame.add(panel);
        frame.setVisible(true);
        
        //реализуем слушатель клавиатуры средствами ActionMap
        
        ActionMap am = frame.getRootPane().getActionMap();
        InputMap im = frame.getRootPane().getInputMap(
                JComponent.WHEN_ANCESTOR_OF_FOCUSED_COMPONENT);
        im.put(KeyStroke.getKeyStroke(KeyEvent.VK_ESCAPE, 0), "QUIT");
        am.put("QUIT", new AbstractAction(){
            @Override
            public void actionPerformed(ActionEvent e){
                frame.dispose();
                System.exit(0);
            }
        });
    }
}

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

package filewalker;

import java.awt.*;
import java.awt.event.*;
import java.io.FileNotFoundException;
import javax.swing.*;

/**
 * Класс, описывающий главную панель
 * @author rad1kal
 * @version 1.0
 */
class MainPanel extends JPanel{
    private ScrollPane outputField;
    private JTextField directoryInputField;

    MainPanel(){
        super();
        setLayout(new GridBagLayout());
        GridBagConstraints c = new GridBagConstraints();
        
        JLabel label = new JLabel("Введите путь к корневому каталогу:");
        c.insets = new Insets(10,20,0,0);
        c.anchor = GridBagConstraints.WEST;
        add(label, c);
        
        directoryInputField = new JTextField();
        c.fill = GridBagConstraints.HORIZONTAL;
        c.anchor = GridBagConstraints.CENTER;
        c.gridy = 1;
        c.insets = new Insets(10, 20, 0, 20);
        add(directoryInputField, c);
        
        JButton button = new JButton("Вывести все подкаталоги/файлы");
        button.addActionListener(new MainPanel.ButtonListener());
        button.setFocusable(false);
        c.gridy = 2;
        c.insets = new Insets(10, 0, 10, 0);
        c.anchor = GridBagConstraints.CENTER;
        c.fill = 0;
        add(button, c);
        
        outputField = new ScrollPane();
        c.insets = new Insets(0, 5, 0, 5);
        c.gridy = 3;
        c.weightx = 1;
        c.weighty = 10;
        c.fill = GridBagConstraints.BOTH;
        add(outputField, c);
        
        label = new JLabel("Нажмите Esc для завершения работы.");
        c.anchor = GridBagConstraints.CENTER;
        c.insets = new Insets(10,20,10,0);
        c.gridy = 4;
        c.weighty = 0;
        add(label, c);
    }
    
    /**
     * Обработчик нажатия кнопки
     * @author rad1kal
     */
    private class ButtonListener implements ActionListener{
        @Override
        public void actionPerformed(ActionEvent e){
            outputField.clearAll();
            String str = directoryInputField.getText();
            Walker walker;
            try{
                walker = new Walker(str, outputField);
            } catch (FileNotFoundException ex){
                outputField.showWarningMessage();
                return;
            }
            Thread t = new Thread(walker);
            t.start();
        }
    }
}

Класс, реализующий основной функционал программы. На нём остановимся подробнее. Итак, мы хотим перебрать все каталоги/файлы, начиная с корневого. Зачем это нужно? Вот возможные варианты ответа:

  • мы хотим найти некоторые данные в файле, но не знаем в каком именно каталоге и файлы они находятся;

  • мы хотим считать информацию из всех/строго определённых файлов;

  • мы хотим выполнить некоторые действия с каждым/строго определённым файлом/каталогом и т.п.

В моём случае я разрабатываю приложение для поиска информации в большом массиве текстовых файлов. Многие пользователи отметят, что я занимаюсь велосипедостроением и трачу время зря, ведь есть TotalCommander с уже встроенным функционалом. Доля истины в этом есть, однако TotalCommander не всегда корректно обрабатывает *.docx и *xlsx файлы, а также прочие XML-документы. Также отмечу, что при минимальном усилии, данную программу можно приспособить для рекурсивного поиска ссылок в веб-страницах, тем более что тема уже поднималась на форуме.

Итак, вот код поисковика:

package filewalker;

import java.io.File;
import java.io.FileNotFoundException;
import javax.swing.SwingUtilities;

/**
 * Данный класс содержит методы для рекурсивного перебора каталогов,
 * начиная с корневого (указывается пользователем).
 * @author rad1kal
 * @version 2.0
 */
public class Walker implements Runnable{
    public File rootDirectory;
    private ScrollPane outputField;
    
    /**
     * Инициализирует поля RootDirectoryName. Класс бросает исключение
     * FileNotFoundException, когда введен неправильный путь к каталогу.
     * @param rootDirectoryPath путь к корневому каталогу.
     * @param outputField ссылка на панель вывода.
     */
    Walker(String rootDirectoryPath, ScrollPane outputField) throws FileNotFoundException{
        this.outputField = outputField;
        File file = new File(rootDirectoryPath);
        if (file.exists() && file.isDirectory())
            rootDirectory = file;
        else
            throw new FileNotFoundException();
    }
    
    /**
     * Запускает поиск в отдельном потоке.
     * Это необходимо для динамического вывода данных на панель.
     */
    @Override
    public void run(){
        scanDirectory(rootDirectory);
    }
    
    /**
     * Поиск всех каталогов и файлов в папке.
     * @param directory 
     */
    void scanDirectory(File directory){
        File[] files = directory.listFiles();
        if (files != null){
            for (File f : files){
                final String path = f.getAbsolutePath();
                //потокобезопасный вывод происходит здесь
                if (SwingUtilities.isEventDispatchThread()){
                    outputField.append(path);
                } else {
                    SwingUtilities.invokeLater(new Runnable(){
                        @Override
                        public void run(){
                            outputField.append(path);
                        }
                    });
                }
                //рекурсивный вызов для просмотра вложенных каталогов
                if (f.isDirectory() && !f.isHidden()){
                    scanDirectory(f);
                } 
            }
        }
    }
}

Думаю, здесь всё понятно. В конструкторе создается и проверяется ссылка на корневой каталог и если ссылка ошибочна, то далее в методе scanDirectory() получаем список всех файлов и подкаталогов, и для каждого подкаталога метод вызывается снова. Метод поиска запускается в отдельном потоке, что дает возможность реализовать анимированное прокручивание полосы прокрутки в JScrollPane. Обратите внимание на то, как реализовано потокобезопасное взаимодействие с компонентами Swing:
if (SwingUtilities.isEventDispatchThread()){
                    outputField.append(path);
                } else {
                    SwingUtilities.invokeLater(new Runnable(){
                        @Override
                        public void run(){
                            outputField.append(path);
                        }
                    });
                }

здесь метод append() вызывается из потока Event Dispatching Thread, назначением которого является обработка событий связанных с графическим интерфейсом. Добавляя строку на панель вывода мы создаем событие, требующее перерисовки интерфейса. Вызов Event Dispatching Thread позволяет синхронизировать получение строк и их вывод.
Класс, наследующий JScrollPane:
package filewalker;

import javax.swing.JScrollPane;
import javax.swing.JTextArea;

/**
 * Класс, реализующий JScrollPane и содержащий метод
 * для добавления строк и прокручивания полосы прокрутки ScrollBar
 * @author rad1kal
 * @version 1.0
 */
class ScrollPane extends JScrollPane{
    private static JTextArea jta = new JTextArea();
    private final String WARNING_MESSAGE =
            "Вы ввели неверный путь или он ссылается на регулярный файл.";
    
    ScrollPane(){
        super(jta);
        setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED);
        setHorizontalScrollBarPolicy(JScrollPane.HORIZONTAL_SCROLLBAR_AS_NEEDED);
    }
    
    /**
     * Переопределённый метод, в который добавлена прокрутка VerticalScrollBar.
     * @param s добавляемая строка.
     */
    void append(String s){
        jta.append(s.concat("\n"));
        //Прокручивает полосу прокрутки.
        getVerticalScrollBar().setValue(getVerticalScrollBar().getMaximum());
    }
    
    /**
     * Метод очищает панель вывода.
     */
    void clearAll(){
        jta.setText("");
    }
    
    /**
     * Метод выводит предупреждение о неверном пути к корневому каталогу.
     */
    void showWarningMessage(){
        jta.append(WARNING_MESSAGE);
    }
}

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

Read more