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

Если кто-то помнит, некоторое время назад на форуме обсуждался вопрос применения регулярных выражений к содержимому файла в потоковом режиме, то есть без предварительного считывания всего файла в память: http://forum.vingrad.ru/index.php?showtopic=50114&st=0. В ходе обсуждения было найдено решение, использующее MappedByteBuffer и основанное на факте, что методы поиска регекспов принимают в качестве аргументов не String, а интерфейс CharSequence.

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

Итак, задача:

Требуется класс, который реализует интерфейс CharSequence:

Код

public Interface CharSequence {     public char charAt(int index);     public int length() ;     public CharSequence subSequence(int start, int end); }

Класс должен открывать указанный текстовый файл и дольше вести себя как CharSequence, скрывая детали того, откуда берутся данные.

Если бы имелось взаимно однозначное соответствие между позицией символа в строке и смещением байта (байтов) в файле, то реализация получилась бы достаточно тривиальной: позиционирование внутри файла, буферное чтение, декодирование на лету и пр.

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

Поэтому в качестве первого варианта попробую такой подход:

1. При открытии файла выполняется его полный побуферный проход с заполнением следующей информации:

номер, смещение в файле, длина в байтах, позиция в строке, длина в символах.

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

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

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



Это сообщение отредактировал(а) Stampede - 17.8.2005, 00:00

Решил предложить два варианта решения проблемы с поиском в файлах. Оба варианта далеко не универсальны и в данном случае вряд ли подойдут и больно уж простые чтобы никому не приходили в голову Но может быть кому-то поможет при решении похожих задач.
Вариант 1. Если поиск выполняется в простом текстовом файле с переносами строк и весь текст файла представлен в одной кодировке (то есть в файле ASCII нет полей, заколдированных, например, в UNICODE), то подойдет такое решение:

Код

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.regex.Matcher; import java.util.regex.Pattern; ... FileInputStream fstream = new FileInputStream(         "filename"); InputStreamReader isr = new InputStreamReader(fstream, "ISO-8859-1");          // BufferedReader - класс, предназначенный для буферизованного чтения // потоков. Размер буфера, используемый для временного хранения данных // можно задать в конструкторе BufferedReader bufInput = new BufferedReader(isr); Pattern p = Pattern.compile("a*b"); try {     String line = bufInput.readLine();     while (line != null) {         Matcher m = p.matcher(line);         if (m.find() == true) {                 // делаем что-нибудь со строкой и печатаем ее                         ...                  System.out.println(line);         }         line = bufInput.readLine();     }     bufInput.close(); } catch (Exception e) {     e.printStackTrace(); }

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

Код

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.io.StreamTokenizer; ... FileInputStream fstream = new FileInputStream("filename"); InputStreamReader isr = new InputStreamReader(fstream, "windows-1251"); BufferedReader bufInput = new BufferedReader(isr); try {                  StreamTokenizer st = new StreamTokenizer(bufInput);     for (;;) {         int token = st.nextToken();         if (token == StreamTokenizer.TT_EOF) break;         // делаем что-то с токеном и печатаем его                ...         else System.out.println(st.toString());     }     bufInput.close(); } catch (Exception e) {     e.printStackTrace(); }

Используется тот же самый класс java.io.BufferedReader. Анализируя соседние токены можно находить относительно сложные выражения. Хотя скорость работы в этом случае будет скорее всего значительно ниже, да и ограничений гораздо больше.

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

Завтра напишу, что получается.

Если найти строку с началом документа, а потом анализировать строки насчет наличия значений полей до тех пор пока не встретится конец документа, наверное можно все сделать в один проход. Хотя надо конечно видеть формат файла, так сложно что-то сказать.

Отчитуюсь

Компонент написан, мослает как по маслу Спасибо всем, кто принимал участие в обсуждении (в обоих топиках). Несколько замечаний относительно реализации.

В общем, примерно как все задумывалось (см. первый пост), так и получилось. Но не обошлось и без трюков.

Прежде всего, наткнулся на классическую проблему "рисовальщика дорожной разметки", или "чем дальше в лес, тем толще партизаны". То есть по мере углубления в файл на поиск соответствующего описателя буфера уходило все больше и больше времени (количество описателей измерялось тысячами). Пришлось для их хранения вместо List'а приспособить TreeSet.

Далее, возник вопрос: что возвращать в качестве subSequence? Дело в том, что у меня в результате парсинга получалась приличная структура со вложенными дескрипторами участков текста, и к каждому из них нужно было применять всякие регекспы. Поэтому вызов charAt(int index) самого внутреннего дескриптора должен был по идее отфутболивать запрос вверх по иерархии (с откорректированным индексом на величину смещения позиции самого дескриптора), и так до тех пор, пока он не добрался бы до моего основного класса, который уже мог бы полезть в соответствующий буфер и считать нужный символ.

Поэтому пришлось написать вспомогательный класс, реализующий CharSequence, который бы служил окошком во внутренности содержащего объекта типа CharSequence. Самым корневым родителем в этом случае, естественно, оказывался объект моего класса.

Кэш буферов я сделал в виде простого списка заданного размера. Каждый раз при обращении к charAt() находится нужный описатель буфера. Если соответствующий ему собственно буфер обнаруживается в кэше, он передвигается в голову списка. Если нет, буфер считывается с диска и также помещается в голову. Хвостовой элемент при этом удаляется. Кстати, мне уже не первый раз приходится пользоваться подобной штукой, так что даже непонятно, почему ее нет в составе Collections (или я что-то пропустил?).

И последняя вешь, которую я хотел бы упомянуть, это проблема с методом toString(). Если бы я в своем классе subSequence реализовал ее как parent.toString().substring(start, end), то для получения даже самой малюсенькой строчечки во внутреннем Subsequence пришлось бы по цепочке инстанциировать все строки, принадлежащие предкам, и это было бы очень накладно. Поэтому я сделал так. чтобы все промежуточные сиквенсы реализовывали дополнительный метод, String getString(int start, int end). то есть просто отфутболивали его наверх со смещением. И тогда основной класс уже считывал строку ровно такой длины, которая требовалась в исходном вызове. Для этого пришлось ввести дополнительный интерфейс, наследующий от CharSequence, и кое-что маленько срефакторить, но это, конечно, мелочи.

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

При кэше в 4 буфера по 64 k обработка файла длиной 10 мег занимает 40 секунд.

Тот же файл в прежней версии (весь файл в памяти) обрабатывался 35 секунд.

Расход памяти - 16 и 42 мега соответственно.

Чистый итог: получилось дешево и кошерно

Цитата(Stampede @ 17.8.2005, 00:59)

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

В принципе эту проблему можно решить используя CharsetDecoder.averageCharsPerByte(), но для некоторых кодировок (тот же UTF-8) это число дробное.

Цитата

В принципе эту проблему можно решить используя CharsetDecoder.averageCharsPerByte()

Вот и строители наши тоже дома строят с точностью плюс-минус пол кирпича.

Цитата(Zandr @ 25.8.2005, 13:11)

Вот и строители наши тоже дома строят с точностью плюс-минус пол кирпича.

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

Кстати, отличная мысль.

Например, в моем случае все тексты - в банальном ASCII. Если принять это за данность, то код получится действительно совершенно тривиальным. В частности, отпадает необходимости в предварительном сканировании и хранении описателей (которые могут занимать прилично памяти в случае длинного файла).

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

Тогда для простых кодировок будет инстанциироваться простая реализация, а для всяких китайских - сложная. И все детали скрыты! Ура!

LSD, держи в репу