Прочтите файл в обратном порядке построчно без особых затрат

Мне нужно прочитать файл i в обратном порядке, потому что теперь он должен запустить весь файл, чтобы найти то, что, как я знаю, будет в последних строках. Моя цель - сделать мое приложение более быстрым. Какой способ САМЫЙ БЫСТРЫЙ читать файл построчно в обратном порядке?

Например: Мой файл

  line1
  line2
  line3
  line4
  line5

я хочу читать

  line5
  line4
  line3
  line2
  line1

Я знаю, что есть много способов сделать это ... но какой из них даст мне меньше накладных расходов?


person LeandroC    schedule 12.09.2013    source источник
comment
stackoverflow .com / questions / 6011345 /   -  person Melih Altıntaş    schedule 12.09.2013
comment
Попробуйте этот ответ stackoverflow.com/questions/8664705/   -  person René Link    schedule 12.09.2013
comment
Вы, вероятно, найдете место для начала в коде BufferedReader#readLine()   -  person Arnaud Denoyelle    schedule 12.09.2013
comment
Вы также можете посмотреть реализацию ReverseLineInputStream в этом потоке: stackoverflow.com/questions/8664705/   -  person Arnaud Denoyelle    schedule 12.09.2013
comment
у меня вопрос, какой путь самый быстрый? я знаю, что есть много способов сделать это ... но какой из них даст мне меньше накладных расходов?   -  person LeandroC    schedule 12.09.2013
comment
@LeandroC: А как насчет RandomFileAccess?   -  person boxed__l    schedule 12.09.2013
comment
@LeandroC Тогда это не лучший вопрос. Попробуй, увидишь, тест. На самом деле сложно дать ответ, потому что файловый ввод-вывод должен выполняться последовательно, с буферизацией. Я предполагаю, что хороший способ сделать это - переопределить хороший кусок BufferedReader для работы в обратном порядке.   -  person millimoose    schedule 12.09.2013
comment
@LeandroC: проверьте this, чтобы узнать о различных методах и т. Д.   -  person boxed__l    schedule 12.09.2013
comment
@LeandroC Наивная реализация с низкими накладными расходами (та, которая считывает символы один за другим, задом наперед) на самом деле может оказаться медленнее, чем чтение файла с буферизацией, и будет ли это так, зависеть от файла размер.   -  person millimoose    schedule 12.09.2013
comment
О, и есть еще забавная разница между потоками байтов и потоками символов. Чтение файла в кодировке UTF-8 приносит еще больше крайних случаев. (Многобайтовые символы через границы блока ввода-вывода ...)   -  person millimoose    schedule 12.09.2013
comment
Мне нужно быть быстрым ... Я просто хочу знать, куда я могу пойти. прочтите все файлы в поисках. реализует буфер для работы в обратном направлении ... или что-то в этом роде ... Если бы вы были, куда бы вы пошли?   -  person LeandroC    schedule 12.09.2013
comment
Дерп. Оказывается, есть RandomAccessFile.readLine() . Итак: 1. искать где-нибудь до конца файла. 2. прочитайте неполную строку и отбросьте ее. Запомните текущий указатель файла. 3. читать строки до конца файла. Если вы найдете то, что ищете, ура! 4. Если вы этого не сделаете, поищите где-нибудь еще дальше и повторите, начиная с пункта 2., останавливаясь в предыдущей запомненной позиции. Если вы дойдете до начала файла, отпустите.   -  person millimoose    schedule 12.09.2013
comment
Тем не менее, это даст вам первое появление того, что вы ищете в данном фрагменте. Вы можете исправить это, всегда читая до конца текущего фрагмента и возвращая последнее совпадение. Основная идея состоит в том, что вы не читаете файл в обратном порядке построчно, а построчно, а затем читаете строки в каждом куске вперед. Таким образом, это не гарантирует, что вы прочитаете как можно меньше файла, чтобы найти соответствующую строку, но вы избежите чтения большей части ненужных битов. (Если вы выбираете размер блока с умом, желательно начать незадолго до нужной строки.)   -  person millimoose    schedule 12.09.2013
comment
@LeandroC (извините за то, что оставил это как комментарий, но, честно говоря, я не могу тестировать реальный код для этого.)   -  person millimoose    schedule 12.09.2013


Ответы (1)


Попробуйте, я думаю, это самый быстрый способ прочитать файл в обратном порядке.

import java.io.*;  
import java.util.*;  
class FileReaderReverse  
{  
    public static void main(String[] args) throws IOException,FileNotFoundException  
    {  
        FileReader fr=new FileReader("abc.txt");  
        BufferedReader br=new BufferedReader(fr);  
        String s;  

        List<String> tmp = new ArrayList<String>();  
        do
        {  
            s = br.readLine();  
            tmp.add(s);  
        }while(s!=null);  


        for(int i=tmp.size()-1;i>=0;i--) {  
            System.out.println(tmp.get(i));  
        }  
    }  
}  
person Siddh    schedule 12.09.2013
comment
-1: Schlemiel the Painter работает не очень быстро. - person millimoose; 12.09.2013
comment
@millimoose каков самый быстрый способ прочитать файл в обратном порядке? - person Siddh; 12.09.2013
comment
Для начала поможет не буферизация всего этого в памяти. - person millimoose; 12.09.2013
comment
@millimoose: для идиотов буферизация ввода-вывода = скорость. - person Val; 12.09.2013
comment
@Val Выделение списка строк, содержащих половину гигабайта текста, когда вам нужно посмотреть только одну строку! = Скорость. (Это то, что я имел в виду, говоря здесь о буферизации, а не об использовании буферизованного ввода-вывода.) Чтение 450 мегабайт текста вам никогда не понадобится! = Скорость. Я также рассмотрел это в своем комментарии к вопросу - размер файла и то, как далеко от задней части находится необходимая строка, определяет, будет ли чтение всего файла с буферизацией побеждает чтение его части без буферизации. Кроме того, OP действительно не нужно перебирать строки в обратном порядке, поскольку ему нужно найти последнюю строку, которая эффективно соответствует некоторому предикату. - person millimoose; 12.09.2013
comment
@millimoose без буферизации вы не можете перейти к последней строке файла. - person Siddh; 12.09.2013
comment
@millimoose Вы можете читать, используя RandomAccessFile - поместите файл, используя randomAccesFile.length (), и запишите, используя BufferedWriter - person Siddh; 12.09.2013
comment
@Siddh Так почему ваш код не использует это? - person millimoose; 12.09.2013
comment
Где требование читать файлы размером в половину ГБ? О каком гигабайте ты говоришь? Почему не 10 байтов или эксабайт? Почему 1/2 ГБ? Все подходы имеют некоторые ограничения. Предлагаемый вариант является самым быстрым как для небольших, так и для гигабайтных файлов (у меня на компьютере 8 ГБ, и я могу загрузить его даже 450 МБ). Вы меняете память на скорость, почему вы теряете скорость? - person Val; 12.09.2013
comment
@millimoose Почему вы требуете от него RandomAccessFile, если он работает медленнее? Почему бы вам не развить здесь свой аргумент Шлемиэля Художника? Schlemiel не имеет отношения к буферизации всего файла. Предложение Сидда не имеет ничего общего с тем дерьмом Шлемиля, которое вы ему приписываете. Вы просто не понимаете статей, которые рекомендуете другим. - person Val; 12.09.2013
comment
@Val Вы не торгуете памятью на скорость, если фактически используете слишком много памяти. Вы также не торгуете памятью на скорость, если фактически делаете чрезмерный ввод-вывод, чтобы заполнить такой объем памяти. Это не так, как работает компромисс между памятью / компромиссом. (Это было бы так, если бы вы кэшировали данные, которые читаете, для многократного использования, избегая, таким образом, повторного чтения.) И хотя все подходы имеют ограничения, я подозреваю, что этот будет самым быстрым только в очень определенных обстоятельствах. (Когда файл маленький, а строка, которую вы хотите, не слишком близка к концу.) - person millimoose; 12.09.2013
comment
@Val Скорость теряется при этом подходе при чтении совершенно ненужного начала файла - OP упомянул, что им нужно только найти строку в конце. (Это то, что я имею в виду, говоря о Шлемиле-Художнике, - выполнение работы, которая совершенно и очевидно не нужна.) В какой-то момент накладные расходы, которые вы экономите на буферизованном вводе-выводе, не будут перевешивать чтение с передачей ненужных данных. Кроме того, я предлагал свой подход в комментариях к вопросу, это просто нетривиально, и у меня нет времени кодировать его, не говоря уже о том, чтобы протестировать его достаточно, чтобы дать его в качестве ответа. - person millimoose; 12.09.2013
comment
Подход @millimoose работает всегда, когда вам нужно прочитать файл целиком. Поскольку время ввода-вывода преобладает над любым другим доступом к памяти, нет никакой разницы во времени ответа, читаете ли вы короткий или длинный файл, если он умещается в памяти. Ваше заблуждение состоит в том, что вы думаете, что есть аппетитный напиток мирно быстрее, чем есть целиком. - person Val; 12.09.2013
comment
@Val ... Вы честно утверждаете, что для чтения файла размером 1 МБ с диска в память требуется столько же времени, сколько требуется для чтения файла размером 1 ГБ? Я хочу сказать, что съесть 1/8 яблока быстрее, чем съесть его целиком. - person millimoose; 12.09.2013
comment
@Val Смотри. OP пытается, скажем, найти, какой из нескольких файлов содержит строку с yyy. И он знает, что эта строка будет ближе к концу файла. Итак, учитывая файлы примеров в этом Gist: где вы теряете скорость при обработке file2.txt, чтение строк между aaa и xxx, на которые никогда не нужно смотреть. (Очевидно, это фиктивные файлы, представьте, что фактические входные файлы слишком велики, чтобы их можно было прочитать в память при чтении одного блока.) - person millimoose; 12.09.2013
comment
@Val Предложенный мной подход при поиске, например, sss. Ищи xxx, дочитай до конца, ничего не найду. Ищите uuu, читайте, пока не дойдете до xxx, ничего не найдете. Ищите rrr, читайте, пока наконец не найдете sss, возвращайтесь. Как видите, это потребует переноса только четверти file2.txt с диска. - person millimoose; 12.09.2013
comment
Проверьте это, он читает файл в обратном порядке, используя RandomAccessFile. stackoverflow .com / questions / 15612610 / - person Siddh; 12.09.2013
comment
@millimoose Вы не можете прочитать 1/8 яблока, когда в конечном итоге прочитаете его целиком. Предлагаемый подход является наиболее быстрым в этом случае, а не только для небольших файлов. Вы не можете сказать, что подход Сидди не самый быстрый, если он самый быстрый хотя бы для одного варианта использования (и, таким образом, довольно реальный). - person Val; 12.09.2013
comment
@Siddh Я проверил реализацию RandomAccessFile и кажется, что он не выполняет буферизацию при использовании readLine(), поэтому кажется, что чтение таким образом, вероятно, будет немного быстрее. Конечно, быстрее, но можно как-то объединить BufferedReader с RandomAccessFile, но я, честно говоря, понятия не имею, будут ли они синхронизироваться. - person millimoose; 12.09.2013