0

Недавно изучаю 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мб. Я так понимаю что это не плохой результат, но в целом можно гораздо лучше.

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

7
  • 1
    Я думаю, можно попробовать распараллелить 21 июн 2018 в 13:19
  • Вас интересует символ (если да, то в какой кодировке?) или байт? 21 июн 2018 в 13:24
  • 1
    Поскольку реализация не соответствует поставленной задаче, то однозначно улучшить можно. 21 июн 2018 в 13:25
  • 1
    Попробуйте увеличить размер буфера у BufferedReader , это второй параметр конструктора. 21 июн 2018 в 13:48
  • Эникейщик, да, вы правы. Я отправил не ту версию программы. MrFylypenko, спасибо, увеличил, правда прироста по скорости не наблюдаю. Зато узнал что есть у BufferedReader такой конструктор. =)
    – KirstenLy
    21 июн 2018 в 16:01

2 ответа 2

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();
7
  • 2
    можно немного улучшить ваше решение, дописав .collect(Collectors.groupingBy(Function.identity(), () -> new TreeMap<>(Comparator.reverseOrder()), Collectors.counting())) .firstEntry()
    – Artem
    21 июн 2018 в 14:49
  • @ArtemKonovalov, а в чем плюс?
    – user194625
    21 июн 2018 в 15:10
  • 1
    @Flippy в возможности получить значение без второго потока, и сортировка в процессе формирования TreeMap быстрее, чем при переборе HashMap. 21 июн 2018 в 15:12
  • @SergeyGornostaev, понятно, спасибо)
    – user194625
    21 июн 2018 в 15:13
  • 1
    @ArtemKonovalov ваш вариант вернет самый большой символ в тексте, а не самый частый (для строки "aaaaa zzz b" - "z"), т.к. карта сортирует по ключу
    – zRrr
    21 июн 2018 в 17:10
0

Вы тратите время на парсинг файла через 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);

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

  1. buf[i] << 8 - сдвигаем на 8 бит влево первый байт
  2. buf[i + 1] & 0xff - т.к. результат short, то все операнды расширяются до этого типа, путем копирования старшего бита в добавочные. Этой операцией мы очищаем добавочные биты и оставляем исходный байт
  3. (buf[i] << 8) | (buf[i + 1] & 0xff) - Выполняем логическое ИЛИ над двумя операндами
5
  • Думаю, самым главным в чтении больших файлов является размер буфера. Его лучше сделать ка можно больше 21 июн 2018 в 13:46
  • @SerhiiDikobrazko Первое утверждение верное, второе нет. Размер буфера должен быть пропорционален размеру кластера и системных буферов. Конкретный размер нужно проверять. Но больше чем 8192 байта смысла ставить нет. Прироста уже не получите 21 июн 2018 в 13:58
  • Спасибо за ответ, классная идея использовать byte[] buf. Только я не могу понять что вы в этой строке делаете, можете объяснить? short c = (buf[i] << 8) || (buf[i + 1] & 0xff); Я так понял что это: "buf[i + 1] & 0xff" оставляет только младший бит. "buf[i] << 8" это просто смещение, но почему на 8 байт и что получается в итоге?
    – KirstenLy
    21 июн 2018 в 18:20
  • Или поделитесь ссылкой где про это можно почитать, а то я завис на этой строке капитально.
    – KirstenLy
    21 июн 2018 в 18:20
  • Я дополнил ответ. Читать про битовые операции 22 июн 2018 в 15:14

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.