ну и что что вопрос не про это

tac file | sed 'nq;d'

Последовательный seek+read с конца, инкремент счётчика при встрече '\n'. При достижении нужного значения счётчика читать файл с найденной позиции как обычно.

лучше в два прохода

первый подсчет количества строк в файле, второй вытаскивание нужной строки. Иначе нужен буфер размером с файл, в худшем случае.

лучше в два прохода
★★★★★

ммкей...

Иначе нужен буфер размером с файл

Но зачем он? Нам же нужно просто найти n штук \n с конца и вычитать все, что нужно? Ты вбрасываешь что-ли?

Идёшь с конца, находишь '\n' нужное количество раз и считываешь строку. Это с точки зрения алгоритма. На практике man tail и man head

В исходник tail посмотреть ещё не советовали?

я подходил с точки зрения консольных утилит. если исп. С, seek и читать кусками с конца, то мой подход не оправдан.

если исп. С, seek и читать кусками с конца

Но консольные утилиты разве делают по-другому?

Организовать кольцевой буфер на n строк и считывать строки из файла/потока в него.

Когда файл закончится, взять первую (самую старую) строку из буфера.

Говнорешение говнозадачи из говноконторы типа яндекса и гугля. Нет никакой нужды хранить n строк, если файл конечной длины. Хранить надо две позиции начала строк - текущей и на n строк назад. В конце файла - сдвигаемся назад и считываем.

Надо n позиций начала строк.

Перейти на length - 100 байт. Прочитать до конца (100 байтов). Посчитать сколько строк. Если нашли — вернуть ответ. Если не нашли — отмотать ещё на 100 байтов и т.д. В принципе можно тупо по 1 байту читать и двигаться назад, но чем то мне такой подход не нравится, не знаю чем.

Или просто сделать mmap и идти по массиву с конца.

не знаю чем.

Количеством обращений к девайсу?

Читай блоками с конца, как уже написали

Размер первого вычитываемого блока можно грубо прикинуть как средний_размер_строки*номер_строки*1.5 например. Если не хватило, читай дальше (т.е. ближе к началу). Блоки можно брать размером приблизительно в readahead (~порядка сотни килобайт)

Ну в любой вменяемой I/O библиотеке есть кеширование да и в ОС тоже есть кеширование, не будет там лишних обращений к девайсу.

и в ОС тоже есть кеширование

Обычно ОС предполагает что данные будут читаться последовательно, вперед. Читать данные с конца считается необычным поведением. Нужно или подсказывать вручную что именно вы собираетесь читать дальше (man readahead(2), posix_fadvise(2)) или читать большими блоками

Какая разница, ОС же не байтами кеширует. Прочитал байт, она 4 килобайта закеширует (или сколько там до начала блока было), последующие 4095 байта будут из кеша. То, что данные читаются последовательно, может повлиять на предварительную загрузку, т.е. загружается текущий блок и следующий за ним. Этой оптимизации не будет, ну и ладно.

И в чем проблема?

1. в цикле читаешь буферами, скажем, по 1кБ свой файл, затем от конца буфера отсчитываешь n или n-1 символов '\n' (n, если файл кончается на '\n' и n-1, если не кончается), запоминая текущую позицию перед чтением следующего буфера. 2. делаешь fseek на найденную позицию + 1 3. читаешь строку.

Пункты 2 и 3 можно объединить в чтение из буфера (но придется обрабатывать случаи, когда строка разрывается границами буферов).

И весь этот бред можно не делать, если ты тупо заmmap'ишь этот файл. Т.е. в этом случае ведро за тебя будет буферы читать, а тебе лишь нужно будет отсчитать n или n-1 символов '\n' назад.

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

скажем, по 1кБ свой файл

Файл не читается - читается файловый кеш. Поэтому 4к

И весь этот бред можно не делать, если ты тупо заmmap'ишь этот файл.

Только для этого нужные реверсивные функции, которые рандомный калека не напишет, а функции которые напишет калека еле-еле 100мб/с переплюнут. Если же делать как дебил - ну твой первый вариант, то профит не особый.

Т.е. в этом случае ведро за тебя будет буферы читать

Самое интересное, что оно в отличии от рандомного адепта не будет держать 2 копии в памяти и копировать форфан ещё 1раз, ну если не по дефолту.

Видимо, это лучший способ,

На основании чего ты сделал такой вывод?

Наверное на основании того, что так делают практики, а не решатели головоломок. Так делает tail и она делает это очень неплохо уже много лет подряд.

Решение с кольцевым буфером знают все. И все знают, что это не лучшее решение. thepe

Наверное на основании того, что так делают практики, а не решатели головоломок.

Во-первых сореутилс это набор протухшего говнокода и ни к какой практики отношение он не имеет.

Юзают это говно только ради переносимости, только вот кореутилс никому нахрен за пределами линукса не нужен, поэтому этот аргумент не катит.

Так делает tail и она делает это очень неплохо уже много лет подряд.

Что делает?

Я делаю одной строчкой то, что тайл делает сотной, при этом это работает быстрее: strchr_reverse(mmap(file), '\n');

Решение с кольцевым буфером знают все.

Какой нахрен кольцевой буфер? Больничка?

И все знают, что это не лучшее решение. thepe

Щито, ты к чему это вообще это высрал?

А, понятно, там какой-то анонимус задвигал про кольцевой буфер для решения этой задачи. Думал это ты.

mmap это нормальное решение, тут не спорю. Правда и не знаю, как оно себя поедет в случае, если файл непрерывно пополняется, как лог-файлы например. Так же норм будет?

читают небольшие блоки в память и ищут \n в них. Видимо, это лучший способ,

Это способ, когда нужно работать со stdin'ом, который нельзя seek() или mmap(), только читать и держать в памяти заданое кол-во строк.

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

Работает так же. Берёшь, если пишешь не под говно, ммапишь файл на ГБ/ТБ адресспейса и всё в ажуре. Сколько читать тебе скажет файлсайз.

Дефолтный же юзкейс, когда ты пишешь под говно, то делаешь мрепам на новый файлсайз.