Часто сталкивался с задачей поиска по подстроке в таблице значений. Ну, например, в таблице нужно найти всех Петровых, или, например, все строки, в которых значение в Колонке Х начинается на "Бел". Вариантов для себя нашел всего 2. Первый - это перебор и сравнение со значением поиска, а второй - поместить во временную таблицу и через Подобно вытащить значения. Но все это было медленно, примерно на 130 000 поиск нужных значений занимал более 1,5 секунд (это перебором), а помещение во временную таблицу не всегда возможно и тоже более секунды. Тогда сделал сделал так, отсортировал таблицу по нужному мне столбцу и далее уже из этой таблицы выбирал нужные мне данные. И скорость возросла значительно, теперь то, что я ранее выбирал за 1,5 секунды, выбирается не более 10 милисекунд.
На этом абзаце мой писательский талант иссяк. Поэтому далее в телеграфном стиле.
Описание
Создано 2 функции.
ПоискДихотомияПоСортированнойТаблице - это основная функция, которая возвращает массив найденных строк, если ничего не найдено, то вернется пустой массив.
Параметры:
тТаблица - таблица значений, отсортированная по колонке поиска по возрастанию.
КолонкаПоиска - Имя колонки, по которой собственно ищем, таблица тТаблица обязательно должна по ней быть отсортирована, иначе метод не работает.
ПоисковаяСтрока - строка, вхождение "слева" которой ищем в значениях колонки поиска
ТочныйПоиск - это признак того, что нужно искать одно конкретное значение. (Собственно аналог найтиСтроки, здесь он для универсальности, но вроде работает тоже побыстрее, правда я не проверял)
УчитыватьРегистр - признак того, что при сравнении значений необходимо учитывать регистр, т.е. если ищем "петр", то "Петров" не будет найден.
Функция ПолучитьЗначениеДляСравнения - модифицирует значение в очередной строке из Таблицы для того, чтобы его можно было сравнить с ПоисковойСтрокой.
Код функция здесь. Можно брать и вставлять в свои модули.
Функция ПоискДихотомияПоСортированнойТаблице(тТаблица,КолонкаПоиска,ПоисковаяСтрока,ТочныйПоиск = Ложь,УчитыватьРегистр=ложь) Экспорт
Результат = Новый Массив;
ПОиск = ?(УчитыватьРегистр,ПоисковаяСтрока,ВРег(ПоисковаяСтрока));
Длина=СтрДлина(ПОиск);
К = тТаблица.Количество()-1;
нИнд = Цел(К/2);
лево = 0;
право = К;
Пока Истина Цикл
нстр = тТаблица.Получить(нИнд);
Если нИнд=лево или нИнд=право Тогда
Прервать;
КонецЕсли;
Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск тогда
Прервать;
КонецЕсли;
Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)>ПОиск тогда
право = нИнд;
нИнд = Цел(лево+(нИнд-лево)/2);
КонецЕсли;
Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)<ПОиск тогда
лево = нИнд;
нИнд = Цел(право-(право -нИнд)/2);
КонецЕсли;
КонецЦикла;
Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск тогда
сч=нИнд;
Пока ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск Цикл
Результат.Вставить(0,нстр);
сч=сч-1;
Если сч<0 Тогда
Прервать;
КонецЕсли;
нстр = тТаблица.Получить(сч);
КонецЦикла;
сч=нИнд+1;
Если сч<=К Тогда
нстр = тТаблица.Получить(сч);
Пока ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск Цикл
Результат.Добавить(нстр);
сч=сч+1;
Если сч>К Тогда
Прервать;
КонецЕсли;
нстр = тТаблица.Получить(сч);
КонецЦикла;
КонецЕсли;
КонецЕсли;
Возврат Результат;
КонецФункции
Функция ПолучитьЗначениеДляСравнения(СтрокаТаблицы,КолонкаПоиска,КоличествоСимволовПоиска,ТочноеСовпадение,УчитыватьРегистр)
Если ТочноеСовпадение Тогда
Результат = ?(УчитыватьРегистр,СтрокаТаблицы[КолонкаПоиска],ВРег(СтрокаТаблицы[КолонкаПоиска]));
иначе
Результат = ?(УчитыватьРегистр,Лев(СтрокаТаблицы[КолонкаПоиска],КоличествоСимволовПоиска),Лев(ВРег(СтрокаТаблицы[КолонкаПоиска]),КоличествоСимволовПоиска));
КонецЕсли;
Возврат Результат;
КонецФункции
Как можно использовать
Например, у нас есть таблица
| ФИО | Оклад |
| Иванов Иван Иванович | 600 |
| Петров Иван Иванович | 300 |
| петров Николай Петрович | 700 |
| сидоров Иван Иванович | 400 |
Нам нужно выбрать всех Петровых.
Сначала мы сортируем таблицу по ФИО. Желательно этот метод применять таким образом, что таблица отсортирована один раз, а сам метод применяется много раз.
А далее
РезультатМассивСтрок = ПоискДихотомияПоСортированнойТаблице(таблицаСФИО,"ФИО","петров ",ложь,ложь);
В итоге в результатМассив попадут строки.
| ФИО | Оклад |
| Петров Иван Иванович | 300 |
| петров Николай Петрович | 700 |
Я например этот метод использовал для автоподстановки в поле ввода. (таблица была более 130000 строк).
Послесловие
Коллеги, жду от Вас комментарии. А может, кто-то знает более быстрый метод, а я тут изобретаю велосипед.
