В этой статье изучим бинарный поиск, а потом реализуем этот алгоритм для поиска в таблице значений 1С. И самое интересное: проведем сравнение, какой поиск выполняется быстрее: бинарный или типовой поиск по таблице значений.
Немного теории. Что такое бинарный поиск? Бинарный поиск – это поиск некого числового значения по отсортированному массиву (или любому другому списку). Сначала, весь массив делится пополам (отсюда и название — бинарный), потом определяется в какой половине находится искомое число, следующим шагом опять найденная половина делится пополам, опять определяется в какой половине находится искомое число, и т.д, пока не будет найдена нужная позиция. Два условия выполнения бинарного поиска: массив должен состоять из числовых элементов, а также числовые элементы массива должны быть отсортированы по порядку. Разберем наглядно «на кошках», ну то есть на таблице (массиве), как работает алгоритм бинарного поиска, а потом сделаем обработку, которая будет искать в таблице значений нужное число. Кто хочет более подробно познакомиться с работой алгоритмов и в том числе бинарного поиска, рекомендую книгу «Грокаем алгоритмы» Адитья Бхаргава, из которой и был взят этот алгоритм.
И так, вот у нас есть массив с числовыми элементами, которые отсортированы по порядку:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Нам нужно найти элемент массива с числом, скажем 8.
Сначала мы ищем тот элемент, который является серединой этого массива, для этого берем значение первого элемента массива, складываем с последним значением и делим пополам: (1+10)/2 = 5.5 ≈ 5
Т.е. у нас элемент со значением 5 середина массива:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Проверим, равняется ли искомое число значению 5. Не равняется: 5 ≠ 8
Теперь, нам нужно определить больше искомое число значению в середине или нет, и в зависимости от этого взять правую или левую половину для следующей итерации. В нашем случае искомое число больше: 8 > 5, значит, берем правую половину.
| 5 | 6 | 7 | 8 | 9 | 10 |
Ищем в этом интервале середину: (5 + 10)/2 = 7.5 ≈ 7
Проверим, равняется ли искомое значение значению в середине. Не равняется: 7 ≠ 8
А также 8 у нас больше 7, поэтому опять берем правую половину:
| 7 | 8 | 9 | 10 |
Опять ищем середину в этом интервале: (7+10)/2 = 8.5 ≈ 8
Проверим, равняется ли искомое значение значению в середине. Равняется: 8 = 8! Бинго!
Мы нашли элемент массива с искомым значением 8.
Поскольку, блог про 1С, реализуем это все в 1С на примере таблицы значений, и сравним, какой поиск выполняется быстрее: бинарный поиск или стандартный поиск.
Выполним следующую задачу. Создадим таблицу значений с одной колонкой Индекс (тип Число), эту таблицу значений мы заполним так, чтобы значения в колонке Индекс увеличивались по порядку цифрами от 1 до N (число N можно будет ввести в поле ввода). На форме можно будет задать некое, и произвести поиск по таблице значений, чтобы был найден элемент таблицы, у которого значение в колонке Индекс соответствует заданному числу. Сначала мы это сделаем методом бинарного поиска, а потом при помощи метода Найти таблицы значений.
Создадим для удобства внешнюю обработку, у обработки создадим основную форму, на которой разместим реквизиты ИскомоеЧисло, КоличествоЭлементов – тип Число, ТаблицаДляПоиска – тип ТаблицаЗначений с колонкой Индекс. А также две команды «Заполнить таблицу» и «Бинарный поиск».
При выполнении команды «Заполнить таблицу» будем заполнять таблицу значений на форме числам от 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", СтрокаНайденная.Индекс)); КонецПроцедуры &НаКлиенте Процедура ОбычныйПоиск(Команда) ОбычныйПоискНаСервере(); КонецПроцедуры
В этом коде нет ни чего особого: мы выгрузили также как и в предыдущей команде из данных форм коллекции таблицу значений, в которой и используем метод Найти.
Команду разместим на форме и посмотрим, как она работает:
А сейчас, и для обычного и для бинарного поиска попробуем посчитать время выполнения в миллисекундах. Но для чистоты эксперимента будем считать время именно на сам поиск по таблице значений, после выгрузки данных формы в таблицу значений.
Добавим расчет для бинарного поиска:
ТЗДляПоиска = ТаблицаДляПоиска.Выгрузить(); Начало = ТекущаяУниверсальнаяДатаВМиллисекундах(); ПервоеЗначение = ТЗДляПоиска[0].Индекс; ПоследнееЗначение = ТЗДляПоиска[КоличествоЦифр - 1].Индекс; ИскомаяСтрока = Неопределено; КоличествоЦиклов = 0; Пока КоличествоЦиклов < КоличествоЦифр Цикл КоличествоЦиклов = КоличествоЦиклов + 1; ПоловинноеЗначение = Цел((ПервоеЗначение + ПоследнееЗначение) / 2 ); //1 Если ИскомоеЧисло > ЗначениеВИндексе Тогда ПервоеЗначение = ПоловинноеЗначение; ИначеЕсли ИскомоеЧисло < ЗначениеВИндексе Тогда ПоследнееЗначение = ПоловинноеЗначение; Иначе ИскомаяСтрока = ТЗДляПоиска[ПоловинноеЗначение - 1]; //2 Прервать; КонецЕсли; КонецЦикла; Конец = ТекущаяУниверсальнаяДатаВМиллисекундах(); Разница = Конец - Начало; Сообщить("При бинарном поиске прошло миллисекунд: " + Разница);
И для обычного:
Начало = ТекущаяУниверсальнаяДатаВМиллисекундах(); СтрокаНайденная = ТЗДляПоиска .Найти(ИскомоеЧисло,"Индекс"); Конец = ТекущаяУниверсальнаяДатаВМиллисекундах(); Разница = Конец - Начало; Сообщить("При обычном поиске прошло миллисекунд: " + Разница);
Сравним скорость выполнения бинарным и обычным поиском.
Бинарным поиском:
Обычным поиском:
Наглядно видно, что бинарный поиск числового значения существенно быстрее выполняется обычного штатного поиска. Единственное ограничение: у таблицы или у массива должно быть отсортировано числовое поле, по которому осуществляется поиск. Понятно, что когда у нас таблица отсортирована, то проще обратится напрямую к значению через индекс. Пример больше теоретический, призванный показать скорость выполнения бинарного поиска по сравнению с обычным.
Подробно и качественно программирования в 1С дается в моей книге «Программировать в 1С за 11 шагов»
Книга «Программировать в 1С за 11 шагов»
Изучайте программирование в 1С в месте с моей книги «Программировать в 1С за 11 шагов»
- Книга написана понятным и простым языком — для новичка.
- Книга посылается на электронную почту в формате PDF. Можно открыть на любом устройстве!
- Научитесь понимать архитектуру 1С;
- Станете писать код на языке 1С;
- Освоите основные приемы программирования;
- Закрепите полученные знания при помощи задачника;
Книга «Основы разработки в 1С: Такси»
Отличное пособие по разработке в управляемом приложении 1С, как для начинающих разработчиков, так и для опытных программистов.
- Очень доступный и понятный язык изложения
- Книга посылается на электронную почту в формате PDF. Можно открыть на любом устройстве!
- Поймете идеологию управляемого приложения 1С
- Узнаете, как разрабатывать управляемое приложение;
- Научитесь разрабатывать управляемые формы 1С;
- Сможете работать с основными и нужными элементами управляемых форм
- Программирование под управляемым приложением станет понятным
Промо-код на скидку в 15% — 48PVXHeYu
Если Вам помог этот урок решить какую-нибудь проблему, понравился или оказался полезен, то Вы можете поддержать мой проект, перечислив любую сумму:
можно оплатить вручную:
Яндекс.Деньги — 410012882996301
Вступайте в мои группы:
Вконтакте: https://vk.com/1c_prosto
Фейсбуке: https://www.facebook.com/groups/922972144448119/
ОК: http://ok.ru/group/52970839015518
Твиттер: https://twitter.com/signum2009
А если из школьных уроков вспомнить «золотое сечение», то сходиться метод будет ещё быстрее. А если называть «золотое сечение» вражеским словом «фибоначчи», то будет «метод фибоначчи», а не «дихотомии», который самый тупой и вы называете «бинарный» )))
А если бы наше комьюнити было менее токсичным, автор писал бы чаще. А если еще посмотреть на заголовок, там не написано «Самый лучший в мире поиск по коллекции»
А где замер времени типового поиска после
ТЗДляПоиска.Индексы.Добавить(«Индекс»)
?
Комментарий для автора (учитывая, что мой предыдущий комментарий не был одобрен). Так хоть, может быть, прочитаешь перед удалением.
Бинарный поиск лучше рассматривать на примере массива, а не таблицы значений. Для таблицы значений гораздо проще (и быстрее) просто добавить индекс по нужной колонке и использовать стандартный поиск без всякой сортировки.