Что является самым быстрым способом сбора символов в java

Question

Моя цель - создать функцию, которая учитывает появление некоторых символов (символов) в строке. Идентификатор int присваивает каждому персонажу, который мне нужно подсчитать. Набор символов ограничен, и я знаю его с самого начала. Все строки состоят только из символов из подающего набора. Функция обрабатывает gazzilions линий. Мой профилировщик всегда показывает, что функция, которая собирает статистику, является самой медленной (97%), несмотря на то, что программа делает много других вещей. Сначала я использовал HashMap и такой код:

occurances = new HashMap<>(); 
    for (int symbol : line) { 
     Integer amount = 1; 
     if (occurances.containsKey(symbol)) { 
      amount += occurances.get(symbol); 
     } 
     occurances.put(symbol, amount); 
    } 

Профилировщик показал hashMap.put принимает использования

процессора 97% Затем я попытался заменить его на созданный раз ArrayList: И оптимизирован это бит litle (строки всегда длиннее 1 символа), но он все еще очень медленный.

int symbol = line[0]; 
    occurances.set(symbol, 1); 

    for (int i = 1; i < length; i++) { 
     symbol = line[i]; 
     occurances.set(symbol, 1 + occurances.get(symbol)); 
    } 

Пожалуйста, если кто-то имеет некоторые лучшие идеи, как решить эту задачу с более высокой производительности, ваша помощь будет очень appreceated.

Answer 1

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

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; 
    } 
} 

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

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

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 вы можете увидеть, что оригинальный метод должен сделать довольно немного сбора мусора, в то время как альтернативный метод не нужен.

Answer 2

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

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

Answer 3

Its вполне возможно, что не параметризуя 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) для ключевого поиска должно позволять экранирующему анализу автоматически собирать мусор.

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(); 
} 

Answer 4

Как предложил here вы можете попробовать сделать Somthing как

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

Answer 5

В коде в большинстве итераций вы выполните поиск записи в 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 или верхнюю границу, которая используется для кешированных значений), что снижает производительность.

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

В следующем коде используется вспомогательный класс, содержащий поле 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++; 
} 

---

использование также другая структура данных может также помочь. Вещи, которые приходят на ум, это Perfect Hashing или хранение данных в структуре данных, отличных от Map. Однако вместо использования ArrayList я бы рекомендовал использовать массив int[], так как это не требует никаких вызовов методов, а также устраняет необходимость в преобразованиях бокса/распаковки в/из Integer. После вычисления частот данные могут быть преобразованы в более подходящую структуру данных.