Каталог решений - Поиск по подстроке в таблице значений. По принципу начинается с

Часто сталкивался с задачей поиска по подстроке в таблице значений. Ну, например, в таблице нужно найти всех Петровых, или, например, все строки, в которых значение в Колонке Х начинается на "Бел". Вариантов для себя нашел всего 2. Первый — это перебор и сравнение со значением поиска, а второй — поместить во временную таблицу и через Подобно вытащить значения. Но все это было медленно, примерно на 130 000 поиск нужных значений занимал более 1,5 секунд (это перебором), а помещение во временную таблицу не всегда возможно и тоже более секунды. Тогда сделал сделал так, отсортировал таблицу по нужному мне столбцу и далее уже из этой таблицы выбирал нужные мне данные. И скорость возросла значительно, теперь то, что я ранее выбирал за 1,5 секунды, выбирается не более 10 милисекунд.

На этом абзаце мой писательский талант иссяк. Поэтому далее в телеграфном стиле.

Описание

Создано 2 функции.

ПоискДихотомияПоСортированнойТаблице — это основная функция, которая возвращает массив найденных строк, если ничего не найдено, то вернется пустой массив.

Параметры:

тТаблица — таблица значений, отсортированная по колонке поиска по возрастанию. 

КолонкаПоиска — Имя колонки, по которой собственно ищем, таблица тТаблица обязательно должна по ней быть отсортирована, иначе метод не работает.

ПоисковаяСтрока — строка, вхождение "слева" которой ищем в значениях колонки поиска

ТочныйПоиск — это признак того, что нужно искать одно конкретное значение. (Собственно аналог найтиСтроки, здесь он для универсальности, но вроде работает тоже побыстрее, правда я не проверял)

УчитыватьРегистр — признак того, что при сравнении значений необходимо учитывать регистр, т.е. если ищем "петр", то "Петров" не будет найден.

Функция ПолучитьЗначениеДляСравнения — модифицирует значение в очередной строке из Таблицы для того, чтобы его можно было сравнить с ПоисковойСтрокой.

Код функция здесь. Можно брать и вставлять в свои модули. 

  Функция ПоискДихотомияПоСортированнойТаблице(тТаблица,КолонкаПоиска,ПоисковаяСтрока,ТочныйПоиск = Ложь,УчитыватьРегистр=ложь) Экспорт
      
          Результат = Новый Массив;
          ПОиск = ?(УчитыватьРегистр,ПоисковаяСтрока,ВРег(ПоисковаяСтрока));
          Длина=СтрДлина(ПОиск);    
          К = тТаблица.Количество()-1;
          нИнд = Цел(К/2);
          лево = 0;
          право = К;
          Пока Истина Цикл 
              
              нстр = тТаблица.Получить(нИнд);
              Если нИнд=лево или нИнд=право Тогда 
                  Прервать;
              КонецЕсли;
              Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск тогда
                  Прервать;
              КонецЕсли;
              
              Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)>ПОиск тогда
                  право = нИнд;
                  нИнд = Цел(лево+(нИнд-лево)/2);
              КонецЕсли;
              
              Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)<ПОиск тогда
                  лево = нИнд;
                  нИнд = Цел(право-(право -нИнд)/2);
              КонецЕсли;
              
              
              
          КонецЦикла;
          
          
          Если ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск тогда
              сч=нИнд;
              Пока ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск Цикл
                  Результат.Вставить(0,нстр); 
                  сч=сч-1;
                  Если сч<0 Тогда 
                      Прервать;
                  КонецЕсли;
                  нстр = тТаблица.Получить(сч);
                  
              КонецЦикла;
              сч=нИнд+1;
              Если сч<=К Тогда 
                  нстр = тТаблица.Получить(сч);
                  Пока ПолучитьЗначениеДляСравнения(нстр,КолонкаПоиска,Длина,ТочныйПоиск,УчитыватьРегистр)=ПОиск Цикл 
                      Результат.Добавить(нстр);
                      сч=сч+1;
                      Если сч>К Тогда 
                          Прервать;
                      КонецЕсли;
                      нстр = тТаблица.Получить(сч);
                      
                  КонецЦикла;
                  
              КонецЕсли;
          КонецЕсли;
          
          Возврат Результат;
  
      
      
      
      
  КонецФункции
  
  Функция ПолучитьЗначениеДляСравнения(СтрокаТаблицы,КолонкаПоиска,КоличествоСимволовПоиска,ТочноеСовпадение,УчитыватьРегистр)
      
      Если ТочноеСовпадение Тогда 
          Результат = ?(УчитыватьРегистр,СтрокаТаблицы[КолонкаПоиска],ВРег(СтрокаТаблицы[КолонкаПоиска]));
      иначе
          Результат = ?(УчитыватьРегистр,Лев(СтрокаТаблицы[КолонкаПоиска],КоличествоСимволовПоиска),Лев(ВРег(СтрокаТаблицы[КолонкаПоиска]),КоличествоСимволовПоиска));
      КонецЕсли;
      Возврат Результат;
      
  КонецФункции

Как можно использовать

 Например, у нас есть таблица

Нам нужно выбрать всех Петровых.

Сначала мы сортируем таблицу по ФИО. Желательно этот метод применять таким образом, что таблица отсортирована один раз, а сам метод применяется много раз.

А далее

РезультатМассивСтрок = ПоискДихотомияПоСортированнойТаблице(таблицаСФИО,"ФИО","петров ",ложь,ложь);

В итоге в результатМассив попадут строки.

Я например этот метод использовал для автоподстановки в поле ввода. (таблица была более 130000 строк).

Послесловие

Коллеги, жду от Вас комментарии. А может, кто-то знает более быстрый метод, а я тут изобретаю велосипед.