Кой е най-бързият начин за събиране на появявания на символи в 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;
    }
}

Това използва масив за запазване на броя и използва самия char като индекс на масива.
Това елиминира необходимостта да се проверява дали дадена карта съдържа дадения ключ и т.н. Също така премахва необходимостта от автоматично поставяне в кутия на символите.

И сравнението на производителността показва приблизително 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) код и копирайте всичко от там с изключение на кода, който го прави Atomic. Използването на 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]]++;
}