Есть огромный файл CSV. Надо реализовать поиск по нему, т.е. если в строке встретилось всё (объединены логическим И), что записано в строке поиска, то приостановить поиск и вывести записи на экран, при нажатии далее возобновить поиск.
Подскажите можно ли как-то оптимизировать алгоритм. Сейчас поиск записи по 7-и метровому фалу занимает около минуты на эмуляторе, не говоря уже про обычный телефон.

Сейчас алгоритм следующий:
Открываем файл, читаем его в цикле, используя InputStreamReader (в коде -- reader).



Подскажите узкие места кода, где и как можно оптимизировать скорость выполнения.

У меня 3 предложения, которые лишь на 5-10% могут увеличить скорость.


1. Не знаю есть ли в JME StringBuilder, но его использовать предпочтительней.
2. Предлагаю не плодить объекты, а просто чистить (по-моему clear())
3. 
Возможно вам стоит избавиться от этой функции. Попробуйте "на лету" составлять запись.

Добавлено через 5 минут и 33 секунды
"На лету" подразумеваю следующее
1. читаем символ
2. (разделитель полей)? (Добавляем в буферный объект считанное поле) : 
__3. (разделитель строк)? (Обрабатываем буферный объект, затем чистим его, готовя к новой операции формирования записи) :
____4. (продолжаем формировать текущее поле)

Добавлено через 6 минут и 47 секунд
Посмотрите, возможно в JME есть BufferedReader, он может читать построчно.

Ну для начала 7мб файл - много, поэтому быстро скорее всего никак не сделаешь. Но ускорить можно и на мой взгляд ускорить можно за счет уменьшения количества создаваемых объектов (а именно строк и stringbuffer-ов)
    
например, как Platon написал, вот это: 

заменить на очистку b

Пересмотреть метод: 

Из того что я видел в другом посте в этом методе используется: String += (char); (добавление символа к строке) - это действие эквивалентно созданию новой строки, поэтому заменить String на StringBuffer и добавлять символы в него.

Так же пересмотреть всякие .toString методы - это тоже создание новой строки.



нет такого



тоже нет такого

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

Ок, спасибо. Это всё учту.

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



math64, нет в том-то и дело, что отдельный файл(ы), лежащий(е) на флешке в телефоне. Необходимо предоставить интерфейс для поиска по ним в виде мидлета.

Ещё несколько вопросов:
1. Эммм... А как, кстати, очистить StringBuffer? Ничего более подходящего кроме b.setLength(0); не нашел. Это правильно?
2. Что касается сбора строк (из строк и символов) -- каково быстродействие у следующих методов и когда их лучше использовать? 
   а. Функция String.concat()
   б. Функция StringBuffer.append() с последующим StringBuffer.toString();
   в. Использование += (кстати, str+="ddd" эквивалентно str=str+"ddd"?) 


Это сообщение отредактировал(а) drMIG - 12.3.2009, 17:22

a и в - создание новой строки

Вот реализация append в WTK: 

т.е. если у тебя не вызывается expandCapacity() то точно быстрее будет выполняться




ну или удалять все содержимое.

Я думаю, стоит создать свой Reader сразу конвертирующий байты в нужную кодировку и добавляющий буферизацию.
А можно наоборот, эталонные строки сконвертировать в массивы байт и искать по байтам, а конвертировать байты в строки только при успешном сравнении.

Да, с конвертированием строк это тоже хорошая идея. Возможно, отсутствие конвертирования исходных строк увеличит скорость. Гораздо легче один раз привести к нужному виду строку для поиска. Учту это.

А что вы всё-таки думаете по поводу чтения из нескольких потоков? Т.е. создаем класс-читалку, работающую как отдельный поток, в которую передаём начальную и конечную позицию для чтения. Запускаем несколько экземпляров. Т.е. одновременно идёт чтение сразу из нескольких мест файла. Когда какой-то экземпляр находит соответствие строке поиска, он отдаёт результат для отображения и продолжает работать. Я конечно понимаю, что на телефоне процессор не многоядерный, но хотя бы субъективную скорость выполнения это увеличит? И если да, то как оптимально подобрать количество потоков для чтения?

Я думаю для JME дохлый номер.

Добавлено через 3 минуты и 26 секунд
И вообще:
1. Потоков должно быть не больше числа процессоров
2. Потоков должно быть не больше числа считывающих головок в ПЗУ

не больше числа процессоров? 
Platon, чего?
а как насчет ограничения в 10000 потоков в винде? в фрибсди там конечно по-другому, я конечно понимаю что процессоров не 10000, НО, все ведь эмулируется, есть процесс, есть в нем потоки и тп. в j2me я обычно использовал не более трех одновременно запущенных потоков

Это сообщение отредактировал(а) W0LF - 14.3.2009, 02:05

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

MIDP потоки

Итог: чтение посимвольно слишком медленное впринципе, даже если вообще убрать все, кроме самого чтения. Значительное ускорение на ПК и незначительное ускорение на телефоне было достигнуто использованием для чтения функции readUTF (предварительно была написана утилитка для ПК, конвертирующая исходный файл соответствующим образом, аналогичным функции writeUTF). Значительное увеличение скорости дает лишь способ чтения:

Отсюда вопросы: 
1. Как оптимально подобрать размер байтового массива
2. Собственно, как искать. Исходные данные: массив bb и строка, которую ищем fString.

1. Смотрите на объем памяти планируемых устройств + проанализируйте сколько байт разом считывает метод read(). Не гарантируется, что массив байт будет полностью заполнен, даже если не достигнут конец файла.
2. 
можно приметить и к сконвертированной строке.

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