«Эффективный калькулятор частоты слов в Java»

«1. Обзор

В этом руководстве мы покажем различные способы реализации счетчика слов в Java.

2. Реализации счетчиков

Давайте начнем с простого подсчета количества слов в этом массиве:

static String[] COUNTRY_NAMES 
  = { "China", "Australia", "India", "USA", "USSR", "UK", "China", 
  "France", "Poland", "Austria", "India", "USA", "Egypt", "China" };

Если мы хотим обрабатывать огромные файлы, нам нужно использовать другие варианты, описанные здесь.

2.1. Карта с целыми числами

Одним из самых простых решений было бы создать карту, сохранить слова в качестве ключей и количество вхождений в качестве значений:

Map<String, Integer> counterMap = new HashMap<>();

for (String country : COUNTRY_NAMES) { 
    counterMap.compute(country, (k, v) -> v == null ? 1 : v + 1); 
}

assertEquals(3, counterMap.get("China").intValue());
assertEquals(2, counterMap.get("India").intValue());

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

Однако этот метод создания счетчика неэффективен, так как Integer неизменяем, поэтому каждый раз, когда мы увеличиваем счетчик, мы создаем новый объект Integer.

2.2. Stream API

Теперь давайте воспользуемся Stream API Java 8, параллельными потоками и сборщиком groupingBy():

@Test
public void whenMapWithLambdaAndWrapperCounter_runsSuccessfully() {
    Map<String, Long> counterMap = new HashMap<>();
 
    Stream.of(COUNTRY_NAMES)
      .collect(Collectors.groupingBy(k -> k, ()-> counterMap,
	    Collectors.counting());

    assertEquals(3, counterMap.get("China").intValue());
    assertEquals(2, counterMap.get("India").intValue());
}

Точно так же мы могли бы использовать parallelStream:

@Test
public void whenMapWithLambdaAndWrapperCounter_runsSuccessfully() {
    Map<String, Long> counterMap = new HashMap<>();
 
    Stream.of(COUNTRY_NAMES).parallel()
      .collect(Collectors.groupingBy(k -> k, ()-> counterMap,
	    Collectors.counting());

    assertEquals(3, counterMap.get("China").intValue());
    assertEquals(2, counterMap.get("India").intValue());
}

2.3. Map With a Integer Array

Далее, давайте воспользуемся Map, которая заключает счетчик в массив Integer, используемый в качестве значения:

@Test
public void whenMapWithPrimitiveArrayCounter_runsSuccessfully() {
    Map<String, int[]> counterMap = new HashMap<>();

    counterWithPrimitiveArray(counterMap);

    assertEquals(3, counterMap.get("China")[0]);
    assertEquals(2, counterMap.get("India")[0]);
}
 
private void counterWithPrimitiveArray(Map<String, int[]> counterMap) {
    for (String country : COUNTRY_NAMES) {
        counterMap.compute(country, (k, v) -> v == null ? 
          new int[] { 0 } : v)[0]++;
    }
}

Обратите внимание, как мы создали простую HashMap с массивами int в качестве значений.

В методе counterWithPrimitiveArray при переборе каждого значения массива мы:

вызываем get на counterMap, передавая название страны в качестве ключа, проверяя, присутствует ли уже ключ или нет. Если запись уже существует, мы создаем новый экземпляр примитивного целочисленного массива с одной «1». Если запись отсутствует, мы увеличиваем значение счетчика, присутствующего в массиве.

Этот метод лучше, чем реализация-оболочка, поскольку он создает меньше объектов.

2.4. Карта с MutableInteger

Далее давайте создадим объект-оболочку, который встраивает примитивный целочисленный счетчик, как показано ниже:

private static class MutableInteger {
    int count = 1;
	
    public void increment() {
        this.count++;
    }
	
    // getter and setter
}

Давайте посмотрим, как мы можем использовать вышеуказанный класс в качестве счетчика:

@Test
public void whenMapWithMutableIntegerCounter_runsSuccessfully() {
    Map<String, MutableInteger> counterMap = new HashMap<>();

    mapWithMutableInteger(counterMap);

    assertEquals(3, counterMap.get("China").getCount());
    assertEquals(2, counterMap.get("India").getCount());
}
private void counterWithMutableInteger(
  Map<String, MutableInteger> counterMap) {
    for (String country : COUNTRY_NAMES) {
        counterMap.compute(country, (k, v) -> v == null 
          ? new MutableInteger(0) : v).increment();
    }
}

В метод mapWithMutableInteger, перебирая каждую страну в массиве COUNTRY_NAMES, мы:

вызываем get на counterMap, передавая название страны в качестве ключа, проверяя, присутствует ли ключ уже или нет. Если запись отсутствует, мы создаем экземпляр MutableInteger, который устанавливает значение счетчика равным 1. Мы увеличиваем значение счетчика, представленное в MutableInteger, если страна присутствует на карте

Этот метод создания счетчика лучше, чем метод предыдущий — поскольку мы повторно используем тот же MutableInteger и тем самым создаем меньше объектов.

Вот как работает Apache Collections HashMultiSet, где он внутри встраивает HashMap со значением MutableInteger.

3. Анализ производительности

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

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

Map<String, Integer> counterMap = new HashMap<>();
Map<String, MutableInteger> counterMutableIntMap = new HashMap<>();
Map<String, int[]> counterWithIntArrayMap = new HashMap<>();
Map<String, Long> counterWithLongWrapperMap = new HashMap<>();
 
@Benchmark
public void wrapperAsCounter() {
    counterWithWrapperObject(counterMap);
}

@Benchmark
public void lambdaExpressionWithWrapper() {
    counterWithLambdaAndWrapper(counterWithLongWrapperMap );
}

@Benchmark
public void parallelStreamWithWrapper() {
    counterWithParallelStreamAndWrapper(counterWithLongWrapperStreamMap);
}
    
@Benchmark
public void mutableIntegerAsCounter() {
    counterWithMutableInteger(counterMutableIntMap);
}
    
@Benchmark
public void mapWithPrimitiveArray() {
   counterWithPrimitiveArray(counterWithIntArrayMap);
}

4. Заключение

В этой быстрой статье мы проиллюстрировали различные способы создания счетчиков слов с помощью Java.

Реализацию этих примеров можно найти в проекте GitHub — это проект на основе Maven, поэтому его легко импортировать и запускать как есть.