Бинарный поиск в таблице значений 1С

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

Немного теории. Что такое бинарный поиск? Бинарный поиск – это поиск некого числового значения по отсортированному массиву (или любому другому списку). Сначала, весь массив делится пополам (отсюда и название — бинарный), потом определяется в какой половине находится искомое число, следующим шагом опять найденная половина делится пополам, опять определяется в какой половине находится искомое число, и т.д, пока не будет найдена нужная позиция. Два условия выполнения бинарного поиска: массив должен состоять из числовых элементов, а также числовые элементы массива должны быть отсортированы по порядку. Разберем наглядно «на кошках», ну то есть на таблице (массиве), как работает алгоритм бинарного поиска, а потом сделаем обработку, которая будет искать в таблице значений нужное число. Кто хочет более подробно познакомиться с работой алгоритмов и в том числе бинарного поиска, рекомендую книгу «Грокаем алгоритмы» Адитья Бхаргава, из которой и был взят этот алгоритм.

И так, вот у нас есть массив с числовыми элементами, которые отсортированы по порядку:

12345678910

Нам нужно найти элемент массива с числом, скажем 8.

Сначала мы ищем тот элемент, который является серединой этого массива, для этого берем значение первого элемента массива, складываем с последним значением и делим пополам: (1+10)/2  = 5.5 ≈ 5

Т.е. у нас элемент со значением 5 середина массива:

12345678910

Проверим, равняется ли искомое число значению 5. Не равняется: 5 ≠ 8

Теперь, нам нужно определить больше искомое число значению в середине или нет, и в зависимости от этого взять правую или левую половину для следующей итерации. В нашем случае искомое число больше: 8 > 5, значит, берем правую половину.

5678910

Ищем в этом интервале середину: (5 + 10)/2 = 7.5 ≈ 7

Проверим, равняется ли искомое значение значению в середине. Не равняется: 7 ≠ 8

А также 8 у нас больше 7, поэтому опять берем правую половину:

78910

Опять ищем середину в этом интервале: (7+10)/2 = 8.5 ≈ 8

Проверим, равняется ли искомое значение значению в середине. Равняется: 8 = 8! Бинго!

Мы нашли элемент массива с искомым значением 8.

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

Выполним следующую задачу. Создадим таблицу значений с одной колонкой Индекс (тип Число), эту таблицу значений мы заполним так, чтобы значения в колонке Индекс увеличивались по порядку цифрами от 1 до N (число N можно будет ввести в поле ввода). На форме можно будет задать некое, и произвести поиск по таблице значений, чтобы был найден элемент таблицы, у которого значение в колонке Индекс соответствует заданному числу. Сначала мы это сделаем методом бинарного поиска, а потом при помощи метода Найти таблицы значений.

Создадим для удобства внешнюю обработку, у обработки создадим основную форму, на которой разместим реквизиты ИскомоеЧисло, КоличествоЭлементов – тип Число, ТаблицаДляПоиска – тип ТаблицаЗначений с колонкой Индекс.  А также две команды «Заполнить таблицу» и «Бинарный поиск».

Управляемая форма внешней обработки 1С

При выполнении команды «Заполнить таблицу» будем заполнять таблицу значений на форме числам от 1 до значения поля КоличествоЭлементов.

&НаСервере
Процедура ЗаполнитьТаблицуНаСервере()

	Для н = 1 по КоличествоЭлементов Цикл 
		НовСтр = ТаблицаДляПоиска.Добавить();
		НовСтр.Индекс = н;
	КонецЦикла;	
	
	
КонецПроцедуры

&НаКлиенте
Процедура ЗаполнитьТаблицу(Команда)
	
	Если КоличествоЭлементов = 0 Тогда 
		ПоказатьПредупреждение(,"Укажите количество элементов таблицы");
		Возврат;
	КонецЕсли;	
	
	ЗаполнитьТаблицуНаСервере();
КонецПроцедуры

Создадим обработчики команды «Бинарный поиск» на сервере и на клиенте.  И первым делом в клиентском обработчике проверим, что таблица не пустая.

&НаСервере
Процедура БинарныйПоискНаСервере()

	
		 
КонецПроцедуры	

&НаКлиенте
Процедура БинарныйПоиск(Команда)

	Если ТаблицаДляПоиска.Количество() = 0 Тогда 
		Сообщить("Таблица пустая");
                Возврат;
	КонецЕсли;	
	
	
        БинарныйПоискНаСервере();
	
КонецПроцедуры

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

ТЗДляПоиска = ТаблицаДляПоиска.Выгрузить();

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

КоличествоЭлементов = ТЗДляПоиска.Количество(); 

ПервоеЗначение = ТЗДляПоиска [0].Индекс;
ПоследнееЗначение = ТЗДляПоиска [КоличествоЦифр - 1].Индекс;

Зададим строку, которую ищем и переменную, в которую запишем количество итераций.

ИскомаяСтрока = Неопределено;
КоличествоЦиклов = 0;

Теперь создадим цикл Пока…Цикл, который будем выполнять пока переменная КоличествоЦиклов меньше количества элементов таблицы.

Пока КоличествоЦиклов < КоличествоЦифр Цикл 
	КоличествоЦиклов = КоличествоЦиклов + 1;	
	ПоловинноеЗначение= Цел((ПервоеЗначение + ПоследнееЗначение) / 2 ); //1	

КонецЦикла;	

В начале цикла считаем значение, которое должно быть в середине (строка //1): если у нас первое 10, а последнее 1, то половинное значение будет 5 и т.д. 

Теперь нам осталось просто определить больше или меньше искомое число найденному значению в середине.

Если ИскомоеЧисло > ЗначениеВИндексе Тогда 
	ПервоеЗначение = ПоловинныйИндекс; 	
ИначеЕсли ИскомоеЧисло < ЗначениеВИндексе Тогда  
	ПоследнееЗначение = ПоловинныйИндекс; 
Иначе 
	ИскомаяСтрока = ТаблицаДляПоиска[ПоловинныйИндекс - 1]; //2
        Прервать;
КонецЕсли;

Поскольку, в таблице значений элементы начинаются с 0, то у нас 0 элементу соответствует значение 1 в колонке Индекс, 1 элементу – значение 2, 2 элементу – 3, и т.д . Поэтому, для получения строки таблицы значений, которая соответствует среднему значению в колонке Индекс, нужно из среднего значения вычесть единицу (строка //2)

И после цикла выведем значение колонки Индекс искомой строки:

Если Не ИскомаяСтрока = Неопределено Тогда 
	Сообщить("Строку нашли, значение поля индекс " + ИскомаяСтрока.Индекс + "
			|Количество итераций в цикле: " + КоличествоИтераций);	
КонецЕсли;

Пример работы алгоритма:

Бинарный поиск по таблице значений

Полный пример кода в обрабочике:

&НаСервере
Процедура БинарныйПоискНаСервере()
	
	ТЗДляПоиска = ТаблицаДляПоиска.Выгрузить();

	КоличествоЭлементов = ТЗДляПоиска.Количество(); 

	ПервоеЗначение = ТЗДляПоиска[0].Индекс;
	ПоследнееЗначение = ТЗДляПоиска[КоличествоЭлементов - 1].Индекс;

	ИскомаяСтрока = Неопределено;
	КоличествоИтераций = 0;
	
	Пока КоличествоИтераций < КоличествоЭлементов Цикл 
		КоличествоИтераций = КоличествоИтераций + 1;
		
		ПоловинноеЗначение = Цел((ПервоеЗначение + ПоследнееЗначение)/2); 
		
		Если ЧислоПоиска > ПоловинноеЗначение Тогда 
			ПервоеЗначение = ПоловинноеЗначение;	
		ИначеЕсли ЧислоПоиска < ПоловинноеЗначение Тогда 
			ПоследнееЗначение = ПоловинноеЗначение; 
		Иначе 
			ИскомаяСтрока = ТЗДляПоиска[ПоловинноеЗначение -1];	 
			Прервать;
		КонецЕсли;	
			
	КонецЦикла;	
	
	Если Не ИскомаяСтрока = Неопределено Тогда 
		Сообщить("Строку нашли, значение поля индекс " + ИскомаяСтрока.Индекс + "
				|Количество итераций в цикле: " + КоличествоИтераций);	
	КонецЕсли;
	
КонецПроцедуры

А сейчас проверим, какой поиск при прочих равных условиях выполняется быстрее: бинарный или типовой поиск по таблице значений про помощи метода Найти.

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

&НаСервере
Процедура ОбычныйПоискНаСервере()

	ТЗДляПоиска = ТаблицаДляПоиска.Выгрузить();	
	СтрокаНайденная = ТЗДляПоиска.Найти(ИскомоеЧисло,"Индекс");
	Сообщить(СтрШаблон("Найденная строка %1", СтрокаНайденная.Индекс));	
КонецПроцедуры

&НаКлиенте
Процедура ОбычныйПоиск(Команда)
	ОбычныйПоискНаСервере();  
КонецПроцедуры

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

Команду разместим на форме и посмотрим, как она работает:

Обычный поиск по таблице значений 1С

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

Добавим расчет для бинарного поиска:

ТЗДляПоиска = ТаблицаДляПоиска.Выгрузить();

Начало = ТекущаяУниверсальнаяДатаВМиллисекундах();

ПервоеЗначение = ТЗДляПоиска[0].Индекс;
ПоследнееЗначение = ТЗДляПоиска[КоличествоЦифр - 1].Индекс;

ИскомаяСтрока = Неопределено;
КоличествоЦиклов = 0;

Пока КоличествоЦиклов < КоличествоЦифр Цикл 

	КоличествоЦиклов = КоличествоЦиклов + 1;
	
	ПоловинноеЗначение = Цел((ПервоеЗначение + ПоследнееЗначение) / 2 ); //1
	
	Если ИскомоеЧисло > ЗначениеВИндексе Тогда 
		ПервоеЗначение = ПоловинноеЗначение; 	
	ИначеЕсли ИскомоеЧисло < ЗначениеВИндексе Тогда  
		ПоследнееЗначение = ПоловинноеЗначение; 
	Иначе 
		ИскомаяСтрока = ТЗДляПоиска[ПоловинноеЗначение - 1]; //2
		Прервать;
	КонецЕсли;

КонецЦикла;	

Конец = ТекущаяУниверсальнаяДатаВМиллисекундах();
 
Разница = Конец - Начало;
 
Сообщить("При бинарном поиске прошло миллисекунд: " + Разница);

И для обычного:

Начало = ТекущаяУниверсальнаяДатаВМиллисекундах();

СтрокаНайденная = ТЗДляПоиска .Найти(ИскомоеЧисло,"Индекс");

Конец = ТекущаяУниверсальнаяДатаВМиллисекундах();
 
Разница = Конец - Начало;
 
Сообщить("При обычном поиске прошло миллисекунд: " + Разница); 

Сравним скорость выполнения бинарным и обычным поиском.

Бинарным поиском:

Бинарный поиск по таблице значений 1С

Обычным поиском:

Обычный поиск по таблице значений 1С

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

Подробно и качественно программирования в 1С дается в моей книге «Программировать в 1С за 11 шагов»

Книга «Программировать в 1С за 11 шагов»

Изучайте программирование в 1С в месте с моей книги «Программировать в 1С за 11 шагов»

  1. Книга написана понятным и простым языком — для новичка.
  2. Книга посылается на электронную почту в формате PDF. Можно открыть на любом устройстве!
  3. Научитесь понимать архитектуру 1С;
  4. Станете писать код на языке 1С;
  5. Освоите основные приемы программирования;
  6. Закрепите полученные знания при помощи задачника;

Книга «Основы разработки в 1С: Такси»

Отличное пособие по разработке в управляемом приложении 1С, как для начинающих разработчиков, так и для опытных программистов.

  1. Очень доступный и понятный язык изложения
  2. Книга посылается на электронную почту в формате PDF. Можно открыть на любом устройстве!
  3. Поймете идеологию управляемого приложения 1С
  4. Узнаете, как разрабатывать управляемое приложение;
  5. Научитесь разрабатывать управляемые формы 1С;
  6. Сможете работать с основными и нужными элементами управляемых форм
  7. Программирование под управляемым приложением станет понятным

Промо-код на скидку в 15% — 48PVXHeYu


Если Вам помог этот урок решить какую-нибудь проблему, понравился или оказался полезен, то Вы можете поддержать мой проект, перечислив любую сумму:

можно оплатить вручную:

Яндекс.Деньги — 410012882996301

Вступайте в мои группы:

Вконтакте: https://vk.com/1c_prosto
Фейсбуке: https://www.facebook.com/groups/922972144448119/
ОК: http://ok.ru/group/52970839015518
Твиттер: https://twitter.com/signum2009

2 Replies to “Бинарный поиск в таблице значений 1С”

  1. А если из школьных уроков вспомнить «золотое сечение», то сходиться метод будет ещё быстрее. А если называть «золотое сечение» вражеским словом «фибоначчи», то будет «метод фибоначчи», а не «дихотомии», который самый тупой и вы называете «бинарный» )))

    1. А если бы наше комьюнити было менее токсичным, автор писал бы чаще. А если еще посмотреть на заголовок, там не написано «Самый лучший в мире поиск по коллекции»

Добавить комментарий

Ваш адрес email не будет опубликован.