Re: [c]Unix

musonline

Нужно на "с" организовать поиск с конца файла, причём файл очень больших размеров, и нужно чтобы ресурсов отжиралось поменьше при этом.
Единственное, что приходит в голову это
File f=fopen("q");
fseek(f,0L,SEEK_END);
и далее продвигаться по байту назад по файлу.
Есть у кого более красивое решение?

Marinavo_0507

продвигаться не по байту, а блоками размером порядка 128 кбайт, а может и больше - замеряешь сам скорость

evgen5555

Более-менее нормальный алгоритм приходит в голову тут же, по-моему:
Организовываешь два куска памяти длиною с искомый кусок, один с двойной, и за каждый цикл считываешь по куску, сцепляешь и ищешь уже в нём.

musonline

Ну я тож думал по блокам лучше когда писал пост, а написал по байтам . А что-нибудь поизящней?

Marinavo_0507

два лишних копирования каждого блока?

Papazyan

Замапировать полностью в память и искать plain search.

evgen5555

А если результат больше 128K или находится на стыке одного блока с другим?

evgen5555

файл очень больших размеров

С этим будет нормально работать?

Marinavo_0507

Плохая идея:
* на 32-битных архитектурах большой файл не замапишь
* чтение вперёд быстрее, чем назад, почти всегда, и с диска, и из памяти

musonline

Это понятно. Всё правильно, но хотелось что ли как-нибудь файл перевернуть и стандартными функциями искать... Тока возможно ли это сделать не подгружая ресурсов много.

musonline

Вот именно, память важна!

Papazyan

Ну мапировать по кускам. Перед поиском делать страницы валидными читая по байту с каждой страницы от начала до конца.

vall

зависит от того какие и какого размера шаблоны ищешь.
подстроку чтоль?
мапить можно не весь файл а только кусочек.

musonline

"Замапить" что значит?Это кусок файла в память подгрузить?

Ivan8209

mmap
---
...Я работаю антинаучным аферистом...

vall

интересно где-нить в libc KMP реализован в strstr ?
глянул в glibc6 - какая-то банальщина...

musonline

Что значмит ммар

vall

системный вызов такой
man 2 mmap

Marinavo_0507

Если конечным автоматом искать, то проще наверное читать блоками.
А если ещё чем, то надо разбираться.

musonline

Ок, другие придложения есть?

vall

какие ещё нужны предложения?
строим конечный автомат. читаем блоками и скармливаем их задом наперёд в автомат.
можно асинхронный ввод вывод использовать а не ммап - типа пока ищем в блоке считывается следующий.

rosali

Ок, другие придложения есть?

Есть предложения написать _как-нибудь_. А когда убедившься, что скорость недостаточная, тогда и продолжим. Мне почему-то сдается, что проблема надуманая...

Julie16

А если результат больше 128K или находится на стыке одного блока с другим?

А вот для этого существуют конечные автоматы.
PS: сорри, уже написали.