Wordcounter, подсчет слов в Java с помощью Lambdas и Fork / Join

В эти дни я выпустил Wordcounter , библиотеку Java и утилиту командной строки для подсчета слов в текстовых файлах и выполнения анализа количества слов, в котором интенсивно используются конструкции функционального программирования и подходы параллельных вычислений. Это моя четвертая запись для конкурса «Geeky Quickies» в SAP , после Feeder , Todor и Hanoier .

Библиотека использует лямбды JDK 8, а также новые функции JDK 7, такие как Fork / Join и NIO.2 . Он построен и может использоваться только с ранней версией JDK 8 с поддержкой лямбды .

С появлением лямбд и их вспомогательных функций в JDK 8 способ, которым мы создаем программное обеспечение на Java, изменится. Если вы хотите получить представление о том, как может выглядеть ваш Java-код через несколько лет, вы можете взглянуть на Wordcounter. В отличие от большинства доступных на данный момент ресурсов, это не простой учебник, а реально работающий проект.

Конкурсное задание попросило реализовать алгоритм с использованием Fork / Join и lambdas, который анализирует все файлы в каталоге и находит десять наиболее часто используемых слов в файлах вместе с тем, сколько раз они встречаются. Вместо того, чтобы просто придерживаться Fork / Join, я попытался найти наиболее подходящий параллельный подход для этой конкретной задачи, что привело меня к выбору Producer / Consumer для основной логики подсчета слов.

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

Последние бинарные, javadoc и исходные пакеты можно найти в разделе загрузок GitHub. Если будет достаточно интереса, я опубликую Javadoc онлайн и сделаю библиотеку доступной также в центральных репозиториях Maven.

Отзывы, комментарии и комментарии приветствуются!

обзор

Особенности библиотеки

Подсчитайте все слова в строке, отдельном текстовом файле или дереве каталогов, содержащем текстовые файлы.
Проанализируйте количество слов, чтобы найти первые N наиболее употребляемых слов, нижние N наименее употребляемых слов или общее количество слов.
Укажите, является ли символ символом слова с помощью внешнего предиката.
Укажите необязательную операцию, выполняемую над словами, например, преобразование в нижний регистр через внешнего оператора.
Выберите между непараллельными и параллельными реализациями, чтобы сравнить их производительность.
Если нужно, укажите уровень параллелизма, который будет отличаться от количества ядер.

Основные моменты программирования

Использует Producer / Consumer для чтения файлов и параллельного подсчета слов в каждом файле. Фактический механизм инкапсулирован в общей, многократно используемой реализации.
Использует Fork / Join для выполнения анализа количества слов. Здесь снова фактический механизм заключен в общую, многократно используемую реализацию.
Использует NIO.2 для обхода каталогов и чтения файлов.
Интенсивно использует функциональные интерфейсы и лямбда-выражения для передачи функций, а не данных, где это уместно.
Для двух наиболее важных классов существуют комплексные тесты модулей и производительности.
Как обычно, код чистый, хорошо структурированный и легко читаемый. Форматирование, наименование и комментарии единообразны и последовательны. Большое внимание было уделено надлежащему использованию как методов объектно-ориентированного, так и функционального программирования.

Интерфейс командной строки

Чтобы запустить программу командной строки, выполните следующую команду:

java -jar wordcounter-1.0.4.jar <options>

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

Найдите 10 самых популярных слов в каталоге «words»: -p words
Найдите нижние 5 наименее употребляемых слов в каталоге «wordsx», считая числа как символы слова, игнорируя регистр, с регистрацией информации: -p wordsx -m bottom -d 1234567890 -i -n 5 -l info

Для получения дополнительной информации об опциях интерфейса командной строки см. Интерфейс командной строки в README.

дизайн

Проект библиотеки разделяет проблему на универсальные утилиты параллельной обработки, классы, которые инкапсулируют структуры данных, используемые для представления необработанного и отсортированного количества слов, и, наконец, классы, которые выполняют подсчет и анализ с использованием возможностей предыдущих двух групп. Практически все эти классы довольно часто используют экземпляры функциональных интерфейсов, чтобы позволить конкретным настройкам их общего поведения. В результате получается код, который сильно насыщен лямбда-выражениями и ссылками на методы. Добро пожаловать в мир функционального программирования на Java!

Универсальные утилиты параллельной обработки

Класс ForkJoinComputer

Класс ForkJoinComputer<T> является универсальным компьютером Fork / Join. Он делит исходный размер на 2, пока либо не достигнет указанного уровня параллелизма, либо не опустится ниже указанного порогового значения, последовательно вычислит каждую часть с использованием указанного Computer<T> , а затем объединит результаты всех вычислений с использованием указанного Merger<T> . Здесь Computer и Merger являются функциональными интерфейсами, которые определены следующим образом:

public interface Computer<T> {
    T compute(int lo, int hi);
}
     
public interface Merger<T> {
    T merge(T result1, T result2);
}

Этот класс можно использовать, просто создав его экземпляр с помощью соответствующих лямбд, а затем вызвав его метод compute .

new ForkJoinComputer<Integer>(n, 1000,
    (lo, hi) -> { int sum = 0; for (int i = lo + 1; i <= hi; i++) sum += i; return sum; },
    (a, b) -> a + b).compute();

Класс ProducerConsumerExecutor

Класс ProducerConsumerExecutor<T1, T2> является универсальным исполнителем Producer / Consumer. Он запускает одну задачу Producer<T1> и несколько задач Mediator<T1, T2> и Consumer<T2> число которых равно указанному уровню параллелизма. Производитель помещает экземпляры T1 в BlockingQueue<T1> . Посредники берут эти экземпляры оттуда, преобразуют их в T2 и помещают их в другую очередь блокировки типа BlockingQueue<T2> . Наконец, потребители берут экземпляры T2 из второй очереди блокировки и обрабатывают их.

Здесь Producer, Consumer и Mediator являются функциональными интерфейсами, которые определены следующим образом:

public interface Producer<T> {
    void produce(Block<T> block);
}
     
public interface Consumer<T> {
    void consume(T t);
}
     
public interface Mediator<T1, T2> {
    void mediate(T1 t, Block<T2> block);
}

В приведенном выше коде Block является стандартной функцией, определенной в java.util.functions . Блок, переданный методам Producer и Mediator помещает полученные данные в соответствующую очередь блокировки.

Подобно ForkJoinComputer , этот класс можно использовать, просто создав его экземпляр с помощью соответствующих лямбд, а затем вызвав его метод execute .

Классы структуры данных

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

Класс WordCounts представляет собой список слов, сопоставленных с их количеством использования.
Класс TopWordCounts представляет отсортированный список счетчиков использования слов, сопоставленных со всеми словами, имеющими такие счетчики.

Классы подсчета и анализа слов

Класс WordCounter

Класс WordCounter предоставляет метод для подсчета слов в Path представляющих файл или дерево каталогов, последовательно или параллельно. Его можно использовать, просто создав его экземпляр с помощью соответствующих лямбд, а затем вызвав метод count :

// Count all words consisting of only alphabetic chars, ignoring case, using parallel processing
WordCounts wc = new WordCounter(path, (c) -> Character.isAlphabetic(c), (s) -> s.toLowerCase(), true).count();

Параллельная реализация использует ProducerConsumerExecutor<Path, String> . Производитель просто просматривает дерево каталогов и создает экземпляры Path . Посредники считывают файлы в текстовые фрагменты, а потребители подсчитывают слова в каждом фрагменте текста и собирают их в одном экземпляре WordCounts . Это делается с помощью следующего фрагмента кода:

private WordCounts countPar() {
    final WordCounts wc = new WordCounts(parLevel);
    new ProducerConsumerExecutor<Path, String>(
        (block) -> collectPaths(block),
        (file, block) -> readFileToBlock(file, block),
        (text) -> wc.add(countWords(text, pred, op)), parLevel).execute();
    return wc;
}

Класс WordCountAnalyzer

Класс WordCountAnalyzer предоставляет методы для анализа количества слов, производимых WordCounter , например, для поиска N наиболее часто используемых слов. Его также можно использовать, просто создав его экземпляр, а затем вызвав один из его методов, таких как findTop или total :

// Find the top 10 most used words in wc
TopWordCounts twc = new WordCountAnalyzer(wc, true).findTop(10, (x, y) -> (y - x));

Типы анализа difnet реализуют внутренний интерфейс Analysis<T> , который определяется следующим образом:

interface Analysis<T> {
    T compute(int lo, int hi);
    T merge(T r1, T r2);
}

Поскольку сигнатуры вышеупомянутых двух методов имитируют функциональные интерфейсы Computer и Merger используемые ForkJoinComputer , мы можем использовать fork / join для всех типов анализа следующим образом:

public TopWordCounts findTop(int number, Comparator<Integer> comparator) {
    return analyse(new FindTopAnalysis(number, comparator));
}
 
private <T> T analyse(Analysis<T> a) {
    if (par) {
        return new ForkJoinComputer<T>(wc.getSize(), THRESHOLD, a::compute, a::merge, parLevel).compute();
    } else {
        return a.compute(0, wc.getSize());
    }
}

Для получения дополнительной информации о дизайне библиотеки см. Дизайн в README.

Производительность

Я обнаружил, что параллельная реализация подсчета слов «производитель / потребитель» прекрасно адаптируется к разному количеству ядер и скоростям ввода / вывода. Это значительно быстрее, чем последовательная реализация. В отличие от этого, параллельная реализация анализа Fork / Join только быстрее, чем последовательная, при тестировании с нереально большим количеством уникальных слов и только в незначительной степени. С небольшим количеством уникальных слов, это на самом деле медленнее, чем серийное.

В приведенных ниже таблицах сравнивается эффективность подсчета слов и проводится лучший анализ при следующих условиях:

Процессор AMD Phenom II X4 965 3,4 ГГц (4 ядра), 4 ГБ ОЗУ, Windows 7, JDK 8
Параметры по умолчанию: слова, состоящие из буквенных символов, с учетом регистра
Уровень параллелизма по умолчанию, равный количеству ядер

Производительность подсчета слов

Реализация	файлы	слова	Размер (МБ)	Время (мс)
последовательный	1	10000000	~ 65	2200-2400
Параллельно	1	10000000	~ 65	500-600
последовательный	100	10000000	~ 65	1600-1800
Параллельно	100	10000000	~ 65	500-600

Найти лучшие результаты анализа

Реализация	слова	Максимальное количество	верхний	Время (мс)
последовательный	2000000	10000000	10	200-250
Параллельно	2000000	10000000	10	200-250

Играя с кодом

Если вы хотите поиграть с кодом, я бы порекомендовал использовать последнюю бета-версию NetBeans 7.3, которая на момент написания статьи была IDE NetBeans 7.3 Beta 2 . Обратите внимание, что даже в этой версии невозможно скомпилировать лямбды в IDE, поэтому у вас есть красные метки вокруг. Однако запуск сборки Maven и запуск тестов из IDE по-прежнему работает нормально. Согласно этому сообщению в блоге , должно быть возможно использовать IntelliJ IDEA 12 EAP build 122.202 или более поздней версии с лямбдами, однако я сам не пробовал этого. Я попробовал Eclipse и обнаружил, что это проигранная игра, так как Eclipse использует собственный JDT-компилятор, который не знает лямбда-выражения.

Вывод

Это была моя первая значительная встреча с функциональным программированием на Java. Хотя Java все еще не Scala, новые функциональные программные конструкции кардинально изменили способ, которым я проектировал и реализовал Wordcounter, по сравнению с моим предыдущим кодом Java. Я считаю, что этот новый стиль программирования является мощным и выразительным, и я верю, что с выпуском Java 8 он быстро станет доминирующим.

Это было также последним заданием «Geeky Quickies» для меня. Жюри присудило мои материалы достаточно щедро, и я нашел себя победителем еще до окончания конкурса.

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

Ссылка: Wordcounter, Подсчет слов в Java с помощью Lambdas и Fork / Join от нашего партнера JCG Стояна Рачева в блоге Стояна Рачева .