Хитрый алгоритм поиска

[dr.MIG]

В общем пишу функцию поиска (не на VB), критическую по времени (поиск в огрооооомном файле на меееедленном устройстве). Задача в следующем -- есть строка текста (не очень большая -- где-то до 150 символов). Есть строка для поиска (слова, разделённые пробелом). Слова в ней объединяются логикой "И". Т.е. совпадение найдено, только если все фрагменты найдены в строке.
Сейчас алгоритм довольно немудрёный -- строка разбивается по пробелу самописным сплитом. Далее проверяется наличие вхождения каждого из элементов полученного массива в данную строку, если всё совпало, то выводим результат. Это можно оптимизировать выходом из цикла проверки сразу же, если что-то не совпало (сейчас этого нет ).
Ещё критическим по времени является получение строк из файлов по символу, а так же проблема с кодировкой и отсутствием функции, приводящей кирилические символы к одному регистру (надо для сравнения строк).

Для полного понимания предыстория и обсуждение тут.

У кого-нибудь будут хоть какие-нибудь советы для оптимизации алгоритма? Для меня важна каждая секунда .

[SLIM]

Тебе может помочь здесь чудо-библа Хакера. Но вот как она работает только он сможет рассказать.
Там все оптимальнее некуда как я понял

[iGrok]

Тебе может помочь здесь чудо-библа Хакера. Но вот как она работает только он сможет рассказать.
Там все оптимальнее некуда как я понял

Неа. Не поможет. Слим, если зайти по ссылке, сразу становится понятно, почему..
Это софтина на java под j2me для мобильника.

[SLIM]

Неа. Не поможет. Слим, если зайти по ссылке, сразу становится понятно, почему..
Это софтина на java под j2me для мобильника.

Да это то я видел. Только подумал что есть возможность...хотя ладно, нет так нет...

[alibek]

Отсортируй слова из строки поиска, проиндексируй их. С каждым словом также будет сопоставлен флаг найденности и счетчик позиций.
Перебирай символы текста, для каждого символа проверяй его наличие в массиве искомых слов, в текущей для слова позиции. Если найдено — увеличивай счетчик позиции. Если счетчик позиций стал больше длины слова, устанавливай флаг найденности и в дальнейшем это слово будет исключено из обработки.
Не факт, что этот способ окажется быстрее — это зависит исходных данных (если искомых слов мало, а текст для поиска большой, то он точно окажется медленнее), однако попробовать можно. У этого способа есть еще то преимущество, что время поиска предсказуемо и зависит от длины текста, в котором ищут.

[dr.MIG]

Спасибо за идею алгоритма, буду пробовать.

И ещё один вопрос, обсуждая который по ссылке выше так и не пришли к единому мнению. Ускорит ли работу поиск по файлу в несколько потоков на устройстве с одним процессором?

[alibek]

ИМХО, скорее замедлит.

[Andrey Fedorov]

ИМХО, скорее замедлит.

Я, кстати, попробовал - сбросить все слова в Recordset и искать по нему.
Собственно сброс из файла 0,7 Mb на моей машине занимает ~3..5 секунд - пока это самый медленный момент, надо соптимизировать (пока все сделано довольно тупо и возможность для оптимизации есть и немалая).
Сам же поиск набора слов в строках выполняется довольно быстро, причем получаем сразу все варианты вхождения, да и вообще все получается просто и удобно...

Но это, конечно, если делать на VB...

[dr.MIG]

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