Каков самый быстрый способ собрать вхождения символов в java

Вы можете попробовать что-то вроде этого:

public class CharCounter {

    final int max;
    final int[] counts;

    public CharCounter(char max) {
        this.max = (int) max;
        counts = new int[this.max + 1];
    }

    public void addCounts(char[] line) {
        for (int symbol : line) {
            counts[symbol]++;
        }
    }

    public Map<Integer, Integer> getCounts() {
        Map<Integer, Integer> countsMap = new HashMap<>();
        for (int symbol = 0; symbol < counts.length; symbol++) {
            int count = counts[symbol];
            if (count > 0) {
                countsMap.put(symbol, count);
            }
        }
        return countsMap;
    }
}

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

И сравнение производительности показывает примерно 20-кратное ускорение:

public static final char MIN = 'a';
public static final char MAX = 'f';

private static void count1(Map<Integer, Integer> occurrences, char[] line) {
    for (int symbol : line) {
        Integer amount = 1;
        if (occurrences.containsKey(symbol)) {
            amount += occurrences.get(symbol);
        }
        occurrences.put(symbol, amount);
    }
}

private static void count2(CharCounter counter, char[] line) {
    counter.addCounts(line);
}

public static void main(String[] args) {
    char[] line = new char[1000];
    for (int i = 0; i < line.length; i++) {
        line[i] = (char) ThreadLocalRandom.current().nextInt(MIN, MAX + 1);
    }

    Map<Integer, Integer> occurrences;
    CharCounter counter;

    // warmup
    occurrences = new HashMap<>();
    counter = new CharCounter(MAX);
    System.out.println("Start warmup ...");
    for (int i = 0; i < 500_000; i++) {
        count1(occurrences, line);
        count2(counter, line);
    }
    System.out.println(occurrences);
    System.out.println(counter.getCounts());
    System.out.println("Warmup done.");


    // original method
    occurrences = new HashMap<>();
    System.out.println("Start timing of original method ...");
    long start = System.nanoTime();
    for (int i = 0; i < 500_000; i++) {
        count1(occurrences, line);
    }
    System.out.println(occurrences);
    long duration1 = System.nanoTime() - start;
    System.out.println("End timing of original method.");
    System.out.println("time: " + duration1);


    // alternative method
    counter = new CharCounter(MAX);
    System.out.println("Start timing of alternative method ...");
    start = System.nanoTime();
    for (int i = 0; i < 500_000; i++) {
        count2(counter, line);
    }
    System.out.println(counter.getCounts());
    long duration2 = System.nanoTime() - start;
    System.out.println("End timing of alternative method.");
    System.out.println("time: " + duration2);

    System.out.println("Speedup: " + (double) duration1 / duration2);
}

Вывод:

Start warmup ...
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000}
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000}
Warmup done.
Start timing of original method ...
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000}
End timing of original method.
time: 7110894999
Start timing of alternative method ...
{97=77000000, 98=82000000, 99=86500000, 100=86000000, 101=80000000, 102=88500000}
End timing of alternative method.
time: 388308432
Speedup: 18.31249185698857

Кроме того, если вы добавите флаг -verbose:gc JVM, вы увидите, что исходный метод должен выполнять довольно много сбора мусора, в то время как альтернативный метод в этом не нуждается.

Как было предложено здесь, вы можете попробовать сделать что-то вроде

List<Integer> line = //get line as a list;
Map<Integer, Long> intCount = line.parallelStream()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

Очень возможно, что отсутствие параметризации HashMap вызывает множество проблем с производительностью.

Что бы я сделал, так это создал класс с именем IntegerCounter. Посмотрите на AtomicInteger (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/concurrent/atomic/AtomicInteger.java) код и скопируйте оттуда все, кроме кода, делающего его атомарным. Использование IntegerCounter и увеличение его единственного экземпляра должно сэкономить вам много мусора.

Использование new Integer(x) для поиска ключа должно позволять escape-анализу автоматически собирать мусор.

HashMap<Integer, IntegerCounter> occurances;

// since the set of characters are already known, add all of them here with an initial count of 0

for (int i = 0; i < length; i++) {
    occurances.get(new Integer(line[i])).incrementAndGet();
}

В вашем коде в большинстве итераций цикла вы будете искать запись в Map 3 раза:

1.

occurances.containsKey(symbol)

2.

occurances.get(symbol);

3.

occurances.put(symbol, amount);

Это больше, чем нужно, и вы можете просто использовать тот факт, что get возвращает null, чтобы улучшить это до 2 поисков:

Integer currentCount = occurances.get(symbol);
Integer amount = currentCount == null ? 1 : currentCount + 1;
occurances.put(symbol, amount);

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

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

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

class Container {
    public int count = 0;
}

int[] symbolSet = ...
Map<Integer, Container> occurances = new HashMap<>();
for (int s : symbolSet) {
    occurances.put(s, new Container());
}

for (int symbol : line) {
    occurances.get(symbol).count++;
}

Также может помочь использование другой структуры данных. На ум приходят следующие вещи: идеальное хэширование или сохранение данных в структуре данных, отличной от Map. Однако вместо использования ArrayList я бы рекомендовал использовать массив int[], так как это не требует вызовов каких-либо методов, а также устраняет необходимость преобразования упаковки/распаковки в/из Integer. Данные все еще могут быть преобразованы в более подходящую структуру данных после расчета частот.

вы можете преобразовать char непосредственно в int и использовать его в качестве индекса

for (i=0; ; i++){
    occurences[(int)line[i]]++;
}