Как прочитать каждую строку ввода и вывести их в отсортированном порядке?

Question

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

Я перепробовал все интерфейсы коллекции, но ни один из них, похоже, не работает для этого вопроса:(Может кто-нибудь, пожалуйста, помогите мне? Спасибо.

Приведенный ниже код неэффективен в памяти, так как он хранит повторяющиеся строки в PriorityQueue. Надеюсь это поможет

public static void doIt(BufferedReader r, PrintWriter w) throws IOException {
    PriorityQueue<String> s=new PriorityQueue<String>();


    String   line;
    int n=0;
    while ((line = r.readLine()) != null) {


        s.add(line);
        n++;

    while (n!=0) {
        w.println(s.remove());
        n--;


    }


}

Answer 1

Идеальным подходом будет использование отсортированного мультимножества, такого как TreeMultiset Гуавы.

Если вам не разрешено использовать внешние библиотеки, вы можете заменить s.add(line) с s.add(line.intern()), Это говорит JVM поставить копию каждого уникального line в String объединить и использовать один и тот же объект среди всех ссылок.

Обратите внимание, что положить String попадание в пул может привести к тому, что они надолго задержатся, что может вызвать проблемы в долго работающих приложениях, поэтому вы не хотите делать это случайно в производственном приложении, но для вашей домашней задачи это хорошо. В случае производственного приложения вы бы хотели поставить String с в SortedMap где значение - это количество раз, когда строка появилась, но это сложнее для правильного кодирования.

Answer 2

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