Эффективная сортировка строки по количеству вхождений каждого из ее символов

Question

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

String str = "aebbaaahhhhhhaabbbccdfffeegh"; 
String output = sortByCharacterOccurrencesAndTrim(str); 

В этом случае, метод «sortByCharacterOccurrencesAndTrim» должен вернуться:

String output = "habefcdg" 

В случае, когда 2 символа имеют один и тот же возникновение, их порядок в возвращаемой строке не имеет значения. Так что «habefcdg» может также равняться «habfecgd», потому что «f» и «e» встречаются 3 раза, и оба «d» и «g» встречаются один раз.

"habefcdg" would effectively be the same as "habfecgd" 

Примечание: Я хотел бы отметить, что производительность имеет значение в этом случае, так что я предпочел бы наиболее эффективный метод возможно. Я говорю это, потому что длина строки может варьироваться от 1 до максимальной длины (что, я думаю, совпадает с Integer.MAX_VALUE, но не уверен), поэтому я хочу свести к минимуму любые потенциальные узкие места.

Answer 1

«Карта и несколько петель», безусловно, самый простой способ, и, вероятно, будет очень быстро. Идея такова:

for each character 
    increment its count in the map 
Sort the map in descending order 
Output the map keys in that order 

Но 100 000 000 картографических поисков могут стать довольно дорогими. Вы могли бы ускорить его, создав массив из 65 536 целых чисел (или 128 символов, если это ASCII). Тогда:

for each character 
    array[(int)ch] += 1 

Затем вы проходите через этот массив и создать карту персонажей с ненулевых отсчетов:

for i = 0 to 65535 
    if array[i] > 0 
     map.add((char)i, array[i]) 

Затем сортировать карту, чтобы и выходных убыванию символы в таком порядке ,

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

Answer 2

Просто для удовольствия (и я не утверждаю, что это наиболее эффективное решение): как насчет некоторых Java 8 lambdas + параллельных потоков?

public String sortByCharacterOccurrencesAndTrim(String str) { 

    // build a frequency map, for each code point store its count  
    Map<Integer, Long> frequencies = 
     str.codePoints() 
      .parallel() 
      .boxed() 
      .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 

    // sort by descending frequency and collect code points into array 
    int[] output = 
     frequencies.entrySet() 
        .parallelStream() 
        .sorted(Map.Entry.<Integer, Long>comparingByValue().reversed()) 
        .mapToInt(Map.Entry::getKey) 
        .toArray(); 

    // create output string from code point array 
    return new String(output, 0, output.length); 

} 

Если вы хотите супер-эффективное решение, которое вы можете переписать выше алгоритм с использованием явных циклов, но это очень много кода, и это поздно для меня :). Идея, однако, будет одинаковой: постройте частотную карту символов, отсортируйте по частоте с использованием нисходящего порядка и постройте строку с символами.

Answer 3

Я ничего о потоках и лямбды не знаю, но я хотел бы сделать что-то вроде этого:

Map<Character, Integer> map; 
for (int i=0;i<str.length,i++){ 
    char c = s.charAt(i); 
    switch(c){ 
     case: map.containsKey(c): 
      int temp = map.get(c)++; 
      map.put(c, tmp); 
      break; 
     case: !map.containsKey(c): 
      map.put(c, tmp); 
      break; 
    } 
}   

для подсчета вхождений. Тогда это просто вопрос сортировки от наивысшего до самого низкого.

Answer 4

Примечание: Это не ответ, а просто показывает производительность тестового кода ответов на Jim Mischel и Óscar López (с параллельными потоками в ответ на comment by OP).

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 
import java.util.Random; 
import java.util.function.Function; 
import java.util.stream.Collectors; 

public class Test { 
    public static void main(String[] args) { 
     long start = System.currentTimeMillis(); 
     String s = buildString(); 
     System.out.println("buildString: " + (System.currentTimeMillis() - start) + "ms"); 

     start = System.currentTimeMillis(); 
     String result1 = testUsingArray(s); 
     System.out.println("testUsingArray: " + (System.currentTimeMillis() - start) + "ms"); 

     start = System.currentTimeMillis(); 
     String result2 = testUsingMap(s); 
     System.out.println("testUsingMap: " + (System.currentTimeMillis() - start) + "ms"); 

     start = System.currentTimeMillis(); 
     String result3 = testUsingStream(s); 
     System.out.println("testUsingStream: " + (System.currentTimeMillis() - start) + "ms"); 

     start = System.currentTimeMillis(); 
     String result4 = testUsingParallelStream(s); 
     System.out.println("testUsingParallelStream: " + (System.currentTimeMillis() - start) + "ms"); 

     System.out.println(result1); 
     System.out.println(result2); 
     System.out.println(result3); 
     System.out.println(result4); 
    } 
    private static String buildString() { 
     Random rnd = new Random(); 
     char[] buf = new char[100_000_000]; 
     for (int i = 0; i < buf.length; i++) 
      buf[i] = (char)(rnd.nextInt(127 - 33) + 33); 
     return new String(buf); 
    } 
    private static String testUsingArray(String s) { 
     int[] count = new int[65536]; 
     for (int i = 0; i < s.length(); i++) 
      count[s.charAt(i)]++; 
     List<CharCount> list = new ArrayList<>(); 
     for (int i = 0; i < 65536; i++) 
      if (count[i] != 0) 
       list.add(new CharCount((char)i, count[i])); 
     Collections.sort(list); 
     char[] buf = new char[list.size()]; 
     for (int i = 0; i < buf.length; i++) 
      buf[i] = list.get(i).ch; 
     return new String(buf); 
    } 
    private static String testUsingMap(String s) { 
     Map<Character, CharCount> map = new HashMap<>(); 
     for (int i = 0; i < s.length(); i++) 
      map.computeIfAbsent(s.charAt(i), CharCount::new).count++; 
     List<CharCount> list = new ArrayList<>(map.values()); 
     Collections.sort(list); 
     char[] buf = new char[list.size()]; 
     for (int i = 0; i < buf.length; i++) 
      buf[i] = list.get(i).ch; 
     return new String(buf); 
    } 
    private static String testUsingStream(String s) { 
     int[] output = s.codePoints() 
         .boxed() 
         .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 
         .entrySet() 
         .stream() 
         .sorted(Map.Entry.<Integer, Long>comparingByValue().reversed()) 
         .mapToInt(Map.Entry::getKey) 
         .toArray(); 
     return new String(output, 0, output.length); 
    } 
    private static String testUsingParallelStream(String s) { 
     int[] output = s.codePoints() 
         .parallel() 
         .boxed() 
         .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 
         .entrySet() 
         .parallelStream() 
         .sorted(Map.Entry.<Integer, Long>comparingByValue().reversed()) 
         .mapToInt(Map.Entry::getKey) 
         .toArray(); 
     return new String(output, 0, output.length); 
    } 
} 
class CharCount implements Comparable<CharCount> { 
    final char ch; 
    int count; 
    CharCount(char ch) { 
     this.ch = ch; 
    } 
    CharCount(char ch, int count) { 
     this.ch = ch; 
     this.count = count; 
    } 
    @Override 
    public int compareTo(CharCount that) { 
     return Integer.compare(that.count, this.count); // descending 
    } 
} 

Пример вывода

buildString: 974ms 
testUsingArray: 48ms 
testUsingMap: 216ms 
testUsingStream: 1279ms 
testUsingParallelStream: 442ms 
UOMP<FV{KHt`(-q6;Gl'R9nxy+.Y[=2a7^45v?E@e,>|AD_\ILpJ}8sow"Z&bCmNW1$!Sd0c]~g3BjX#fz:Q*Tkui%/r)h 
UOMP<FV{KHt`(-q6;Gl'R9nxy+.Y[=2a7^45v?E@e,>|AD_\ILpJ}8sow"Z&bCmNW1$!Sd0c]~g3BjX#fz:Q*Tkui%/r)h 
UOMP<FV{KHt`(-q6;Gl'R9nxy+.Y[=2a7^45v?E@e,>|AD_\ILpJ}8sow"Z&bCmNW1$!Sd0c]~g3BjX#fz:Q*Tkui%/r)h 
UOMP<FV{KHt`(-q6;Gl'R9nxy+.Y[=2a7^45v?E@e,>|AD_\ILpJ}8sow"Z&bCmNW1$!Sd0c]~g3BjX#fz:Q*Tkui%/r)h