Java. Поиск самого частого символа в файле

186

27 июля 2018, 23:20

Недавно изучаю Java, назрел вопрос.

Есть текстовый файл, в котором может встретиться любой существующий символ. Нужно найти символ, который встречается в файле чаще всего. Особенность в том что файл может быть большим(~1GB+). Как это сделать эффективно?

Моя реалицация:

public class Test{
    public static void main(String[] args) {
        try (BufferedReader reader = new BufferedReader(new FileReader("test.txt"))) {
            long[] unicodeArray = new long[65536];
            while (reader.ready()) {
                char[] charArray = reader.readLine().toCharArray();
                for (char c : charArray) {
                    unicodeArray[(int) c]++;
                }
            }
            for (int i = 0; i < unicodeArray.length; i++) {
                if (unicodeArray[i] > 0) {
                    System.out.println("Symbol: " + (char) i + " Freq: " + unicodeArray[i]);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Работает порядка минуты для файла 800мб. Я так понимаю что это не плохой результат, но в целом можно гораздо лучше.

Можно как - то улучшить код? И есть ли в этой реализации какие - нибудь косяки вплане логики? Заранее благодарю.

Answer 1

Вы тратите время на парсинг файла через FileReader. Выкиньте его и используйте напрямую FileInputStream

Далее, вы подсчитываете символы, но ничего не говорите о кодировке файла. Пусть это будет UTF-16BE

try (InputStream reader = new FileInputStream("test.txt")) {
    long[] unicodeArray = new long[65536];
    byte[] buf = new byte[4096];
    int len;
    short maxChar;
    long maxCharCnt = 0;
    while ((len = reader.read(buf)) > 0) {
        for (int i = 0; i < len; i += 2) {
            short c = (buf[i] << 8) | (buf[i + 1] & 0xff);
            unicodeArray[c]++;
            if (unicodeArray[c] > maxCharCnt) {
                maxChar = c;
                maxCharCnt = unicodeArray[c];
        }
    }
    System.out.println((char)maxChar);
}

Где

(buf[i] << 8) | (buf[i + 1] & 0xff);

получение двухбайтового числа из двух байт

buf[i] << 8 - сдвигаем на 8 бит влево первый байт
buf[i + 1] & 0xff - т.к. результат short, то все операнды расширяются до этого типа, путем копирования старшего бита в добавочные. Этой операцией мы очищаем добавочные биты и оставляем исходный байт
(buf[i] << 8) | (buf[i + 1] & 0xff) - Выполняем логическое ИЛИ над двумя операндами

Answer 2

Уверен, не самый эффективный алгоритм, но лаконичный и на моей машине обрабатывает трёхгигабайтный файл за 21 секунду.

Map<Character, Long> chars = Files.lines(Paths.get("big.txt"))
                                  .parallel()
                                  .flatMapToInt(String::chars)
                                  .mapToObj(c -> (char) c)
                                  .filter(Character::isLetter)
                                  .map(Character::toLowerCase)
                                  .collect(Collectors.groupingBy(Function.identity(), 
                                                                 Collectors.counting()));
char mostFrequent = chars.entrySet()
                         .stream()
                         .max(Comparator.comparing(Map.Entry::getValue))
                         .map(Map.Entry::getKey)
                         .get();