Использование Java Stream API для подсчета частоты слов: «Порядок — волшебное слово!»
Впервые я столкнулся с проблемой подсчета слов на курсе по большим данным. Подсчет частоты слов и отчет о них в порядке убывания с использованием Hadoop, а затем с PySpark. Быстрый поиск в Google выдаст вам все результаты, которые в основном скопированы из какого-то источника, и единственная разница заключается в именах переменных.
Я люблю Python, и программирование на Python определенно поможет вам избежать ударов головой о стену или долгих взглядов на экран, как будто вы смотрите на какое-то древнее писание (C++)! но всегда есть проблема с производительностью; Время выполнения даже небольшого текстового файла с использованием Hadoop, Spark и даже университетской кластерной компьютерной системы по-прежнему не было убедительным и не соответствовало обещаниям высокой производительности. Теперь, когда я более уверен в Java, я решил выполнить ту же задачу, используя Java на своем личном ноутбуке, и подробности для сравнения будут добавлены в конце.
Для этого нам понадобится Java 8 или более поздняя версия (предпочтительно Java 11), ваша любимая IDE или просто запуск ее на терминале, и будет достаточно некоторого знакомства с уменьшением карты или производством и потреблением. Кроме того, имея исчерпывающий список стоп-слов (бесполезных слов, таких как «the») и поскольку мы имеем дело с романами и литературными текстами, хорошей отправной точкой был бы список римских цифр.
В большинстве романов римские цифры используются для разделения глав в книгах, поэтому нам нужен список римских цифр, которые мы будем фильтровать или заменять. Здесь нет ничего особенного, за исключением того, что массив — не очень хорошая идея, мы будем сравнивать наш текст с этими списками для каждой строки, и, поскольку поиск по массиву имеет сложность O (n), это приведет к ненужным накладным расходам.
Я буду использовать книгу под названием «Анна Каренина» Толстого из Project Gutenberg. Он весит около 2 МБ и содержит ~ 15000 строк. Это не очень большой файл, поэтому я раздул его до 10 миллионов строк, а размер текстового файла составляет около 500 МБ. Все еще не очень большие данные, но они достаточно хороши, чтобы использовать некоторые методы работы с большими данными на персональном компьютере.
давайте погрузимся в код!!!
Ниже приведен примерный список римских цифр. Полный список (до 100) смотрите в конце поста.
String[] romanNumerals = {"i", "ii", "iii", "iv", "v", "vi", "vii", "viii"};Теперь, Мы не хотим считать все «The»-s, «a»-s и любые другие бесполезные слова. Я собрал длинный список английских стоп-слов из разных источников, таких как Github, NLTK и т. д. Вот небольшая часть списка:
String[] stopWords = {"a", "about", "above", "after", "again", "against"};Несколько заметок перед трансляцией….
В Java 8 лямбда-выражения представлены в java, и мы могли бы использовать метод .forEach(element -› element *2) в нашем списке для умножения элементов списка на 2 вместо написания цикла for; Это лаконично, элегантно, а некоторые могут сказать, что красиво.
Предикат
Прежде чем перейти к Predicate, вот краткое примечание о ссылке на метод. При использовании карты, сокращения и фильтрации в потоковой передаче мы могли бы использовать анонимные функции, также известные как лямбда-с, однако, если у вас уже есть четко определенный класс с соответствующими методами, мы могли бы ссылаться на методы с помощью двоеточий :: которые делает код более читабельным и менее подверженным ошибкам.
Если у вас есть класс Car с методом isFast(), мы могли бы больше не использовать Car::isFast () с нашим потоком. Однако что, если мы ищем медленные автомобили? Это заставит нас отказаться от ссылки на метод и вернуться к лямбда-выражениям filter( car -› !car.isFast()).
Другой вариант — вернуться к определению класса и написать другой метод с именем isSlow(). Что, если нам лень, или в более конкретном сценарии, может быть, мы не являемся владельцем класса и не имеем таких привилегий? тогда что? Что ж, в Java 11 представлены Predicate.not() или negate(), чтобы обратить нашу логическую логику или Predicate.
Ниже приведен фрагмент Predicate для метода «isEmpty()» класса String. Класс String имеет метод для проверки, является ли строка пустой или нет. Мы могли бы использовать фрагмент ниже:
Predicate<String> isEmpty = String::isEmpty;
Predicate<String> notEmpty = isEmpty.negate();
stream().filter(notEmpty)или что-то вроде этого для любителей однострочника:
Predicate.not(isEmpty)Запуск потока и применение фильтров и карт
Теперь нам нужно получить путь к файлу и передать его классу Files. Я не буду углубляться в это, но у нас есть два варианта: Files.lines(…) или Files.readAllLines(…); У меня была лучшая производительность с readAllLines(), но вы можете использовать другой вариант.
Files.readAllLines(Paths.get(filePath))streamSupport и сплитератор
Существует несколько способов запустить поток данных или сгенерировать потоки, но лично я предпочитаю streamSupport, поскольку он предоставляет переключатель параллелизма в своих аргументах метода потока. другие варианты: stream(), parallelStream() или stream().parallel()
StreamSupport.stream(Files.readAllLines(Paths.get(filePath)).spliterator(), true);Для любого вычисления последовательности данных нам нужен итератор. Spliterator — это объект для обхода и разделения исходных элементов в операциях, связанных с потоком. Разделитель может перемещаться по элементам по отдельности или sequentially in bulk.
Давайте построим этот конвейер (данных)
Мы передаем строки строк, нам нужно перевести слова в нижний регистр и заменить бесполезные ключевые слова пробелами.
1- Первый шаг - сделать все строчными: Punct - это регулярное выражение для удаления пунктуации, с быстрым переполнением стека вы можете получить больше информации об этом:
.map(aLine -> aLine.toLowerCase()
.replaceAll("\\p{Punct}", " ")
.split("\\s"))2- на этом шаге мы будем использовать flatMap для обработки массива строк, созданных функцией разделения: причина использования flatMap вместо карты заключается в том, что нам нужно работать с отдельной строкой (словами) сейчас, и использование карты будет нести on с массивом строк.
.flatMap(Arrays::stream)3- В этой части нам нужно сделать некоторую фильтрацию: удалить главы, римские цифры и стоп-слова:
.filter(x -> !x.startsWith("chapter"))В отличие от Python
,В Java нет ключевого слова in
, но нам нужно отфильтровать наши записи, если они существуют in в определенном списке:
children_list = ["Chrystal", "Umar", "Charity", "Kyle", "Justin"]
naughty_list = ["Chrystal", "Umar"]
for child in children_list:
if child in naughty_list:
print(child,"--> No gifts for you!")
else:
print(child, ": you'll get an X-Box")Вместо этого мы будем использовать лямбда-функцию и фильтровать их с помощью метода NoneMatch, который возвращает true, если ни один из элементов потока не соответствует заданному предикату: (равно) в этом случае:
.filter(entry -> Arrays.stream(romanNumerals).noneMatch(entry::equals))
.filter(entry -> Arrays.stream(stopWords).noneMatch(entry::equals))
.filter(notEmpty)4- Теперь пришло время поместить эти выходные данные в словарь или карту: мы назначим счет 1 всем словам, полученным в результате предыдущего процесса, и сопоставим их в формате (Ключ: Значение), например «Анна»: 1 .
.map(word -> new AbstractMap.SimpleEntry<>(word, 1))5- Время сбора: для всех записей на карте из предыдущего шага нам нужно получить его ключ и суммировать значения, если ключи равны, и сопоставить их с новым словарем (Ключ: finalCount):
.collect(toMap(AbstractMap.SimpleEntry::getKey, AbstractMap.SimpleEntry::getValue, Integer::sum))6- Мы будем передавать записи этого словаря и сортировать их на основе значения записи. Мы можем воспользоваться методом потоковой сортировки. СравнениеByValue значения элемента Dictionary(Map), как следует из названия, сравнивает значения, а не ключи, а reverseOrder возвращает значение, противоположное компаратору comPareByValue, и в конце все сортируется. Затем мы делаем еще один сбор здесь, в другой словарь, другой тип словаря.
Словари или карты не являются упорядоченными коллекциями, однако LinkedHashMaps в Java представляют собой списки, подобные словарям, в которых есть порядок. мы получаем записи из предыдущих и создаем новые записи на основе значения из пары (ключ, значение).
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
.collect(
toMap(Map.Entry::getKey,
Map.Entry::getValue,
e1, e2) -> e2, LinkedHashMap::new))7- (Почти) последний шаг: распечатайте элементы нового упорядоченного словаря.
.forEach((k, v) -> System.out.println((k + "," + v)));Порядок - волшебное слово!
Через несколько дней после завершения проекта был какой-то момент «Ага». прежде чем отмахнуться от него как от чего-то не столь значительного, я изменил всего 2 строчки кода, увеличил размер файла и вуаля, это действительно стоило сделать.
A- Как упоминалось ранее, у нас было два list, но они нужны нам только для фильтрации данных, нам все равно, является ли контейнер упорядоченным (отсюда список) или нет. Итак, я изменил списки на наборы:
Set<String> romanNumeralsSet = new HashSet<>(Arrays.asList(romanNumerals));
Set<String> badwords = new HashSet<>(Arrays.asList(stopWords));И поэтому последовали следующие изменения:
.filter(Predicate.not(romanNumeralsSet::contains))
.filter(Predicate.not(badwords::contains))для файлов небольшого размера все еще наблюдалось огромное увеличение скорости, но с учетом того, что окончательный файл содержал почти 10 миллионов строк, первый файл занял так много времени, что его пришлось отложить.
.
Последовательное и параллельное: аналогия
допустим, у нас есть 10 спортсменов и один тренер, и эти спортсмены будут выполнять такие задачи, как прыжки и ползание при перемещении из точки А в точку Б. В последовательном смысле тренер ведет каждого спортсмена из точки А в точку Б, возвращается и делает то же самое, пока все не окажутся в точке B.
для небольшого количества спортсменов это нормально: простой цикл for, перебирающий массив. Но что, если у нас сейчас есть 10 миллионов спортсменов, с распараллеливанием мы можем думать об этом как о всех доступных тренерах, предоставляемых процессором, скажем, 10, и мы разделяем и назначаем спортсменов этим тренерам (по 500 спортсменов на тренера). каждый тренер берет команду, а не отдельных лиц, и направляет их по инструкциям. Теперь, надеюсь, стало ясно, почему распараллеливание ускоряет обработку больших файлов.
и, наконец, в таблице ниже приведены 5 наиболее часто встречающихся слов: если вы, как и я, прошли через книгу, мы можем ожидать, что вы узнаете больше о Левине, который до сих пор является проигравшим в этой истории!
Слово — — — — — — — — Частота
Левин — — — — — — — — 405972
Вронский — — — — — — — 215460,
… Не могу делать хорошие таблицы со средними (по крайней мере, пока…)
Настоящие числа — 1611, 855, …, что означает, что файлы были скопированы более 252 раз.
Полный код здесь сократил длинные списки:
public class Application3
{
public static void main(String[] args)
{
long zer0 = System.nanoTime();
String filePath = "C:/Users/TheMightyLobster/IdeaProjects/myKalk2/src/com/babapour" +
"/AnnaKrennina.txt";
String[] romanNumerals = {"i", "ii", "iii", "iv", "v", "vi", "vii"};
String[] stopWords = {"a", "about", "above", "after", "again", "against",
"am", "an", "and", "any", "are", "aren", "aren't", "as", "at", "be", "because"};
Set<String> romanNumeralsSet = new HashSet<>(Arrays.asList(romanNumerals));
Set<String> badWords = new HashSet<>(Arrays.asList(stopWords));
Predicate<String> isEmpty = String::isEmpty;
Predicate<String> notEmpty = isEmpty.negate();
System.out.println("map after sorting by values in descending order: \n");
try
{
StreamSupport.stream(
Files.readAllLines(
Paths.get(filePath))
.spliterator(), true)
.map(aLine -> aLine.toLowerCase()
.replaceAll("\\p{Punct}", " ")
.split("\\s"))
.flatMap(Arrays::stream)
.filter(x -> !x.startsWith("chapter"))
.filter(Predicate.not(romanNumeralsSet::contains))
.filter(Predicate.not(badWords::contains))
.filter(Predicate.not(isEmpty))
.map(word -> new AbstractMap.SimpleEntry<>(word, 1))
.collect(toMap(AbstractMap.SimpleEntry::getKey,
AbstractMap.SimpleEntry::getValue, Integer::sum))
.entrySet()
.stream()
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
.collect(toMap(Map.Entry::getKey, Map.Entry::getValue,
(e1, e2) -> e2, LinkedHashMap::new))
.forEach((k, v) -> System.out.println((k + "," + v)));
} catch (IOException e)
{
e.printStackTrace();
}
long end = System.nanoTime();
System.out.println((end - zer0));
}
}Первоначально опубликовано на https://sadegh-babapour.github.io 18 сентября 2019 г.
