Кружок 1С #2. Двоичный поиск (бинарный, дихотомия) в 1С

Условие задачи

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

Итого: у нас есть введенный пользователем пароль, и нам необходимо путем перебора нескольких макетов с часто используемыми паролями, в которых на каждой строке введен пароль в нижнем регистре определить совпадает ли введенный пароль с тем, который ввел пользователь с теми паролями, которые есть в файле. Если он найден, надо написать, что пароль скомпрометирован. Обращаю внимание, что мы опускаем то, что регистр может быть другим. Будем введенную строку пользователя переводить в нижний регистр и проверять только маленькие буквы. Это упрощает задачу.

Первый вариант решения "в лоб"

В самом начале, я попытался использовать поиск "в лоб". Т.е. берем по очереди макеты с паролями и строчка, за строчкой сравниваем с тем, что ввел пользователь. Нашли - отлично, пароль скомпрометирован, если не нашли, то так и напишем.

Проблема оказалось в том, что для ~88000 часто используемых паролей это работает ОЧЕНЬ медленно. На моем компьютере это отрабатывало около 18 секунд. Пользователь не захочет ждать такое время. Значит нам нужен другой алгоритм.

Второй вариант решения: двоичный (бинарный) поиск или дихотомия

Дальше, я начал думать, как же можно было бы улучшить алгоритм. И вспомнил про двоичный поиск. Начнем с определения из вики.

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Важно, что все слова наших паролей упорядочены по алфавиту. Схематично алгоритм выглядит так:

Схема двоичного поиска

Предположим наше слово начинается на букву F.

  1. В самом начале левой точкой мы берем букву A, правой букву Z. Центральная точка у нас M.
  2. M нужная нам точка? Если бы это была искомая буква, то мы ее нашли и должны закончить, но нет, это не наша точка, продолжаем алгоритм.
  3. В каком отрезке может находится нужная нам точка F в AM или MZ?
  4. Наша искомая точка находится в AM, тогда в качестве левой точки выбираем А, в качестве правой, выбираем M и продолжаем, переходя на шаг 1.

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

Реализация алгоритма двоичного поиска на 1С

// Проверить присутствие пароля в списке скомпрометированных паролей.
// 
// Параметры:
//	Макеты - Массив - Массив, каждый элемент которого является текстовый файл со строками
//  Пароль - Строка - Пароль
// 
// Возвращаемое значение:
//  Булево - Присутствие в списке доступных паролей.
Функция ПарольСкомпрометированДихотомия(Макеты, Пароль) Экспорт
	
	Если ПустаяСтрока(Пароль) Тогда
		Возврат Ложь;
	КонецЕсли;
	
	нПароль = СокрЛП(НРег(Пароль));
	ПоловинаОтрезка = 2;
	Шагов = 0;

	// Проверка того, что пароль в нижнем регистре встречается в базах часто используемых паролей.	
	Для Каждого ТекстМакета Из Макеты Цикл
		
		// Поиск методом "Дихотомии".			
		Лево = 1;
		Право = СтрЧислоСтрок(ТекстМакета);		
		Пока Лево <= Право Цикл
			
			Центр = Лево + Цел((Право - Лево) / ПоловинаОтрезка);
			Стр = СтрПолучитьСтроку(ТекстМакета, Центр);				
			Если нПароль < Стр Тогда
				Право = Центр - 1;
			ИначеЕсли нПароль > Стр Тогда
				Лево = Центр + 1;
			Иначе
				Возврат Истина;
			КонецЕсли;
			Шагов = Шагов + 1;
			
		КонецЦикла;
		
	КонецЦикла;
	
	Возврат Ложь;
	
КонецФункции

Используйте алгоритмы друзья! В заключении приведу ссылку с видео-демонстрацией с нашего канала.

Видео с нашего канала Кружок 1С #2


Двоичный поиск в 1С 266.65 КБ
Скачать
Попробуйте «Управление IT-отделом 8» бесплатно
Автоматизация работы технической поддержки, управление IT-командой, учёт оборудования и многое другое
Попробовать бесплатно
Изображение автора статьи

Основатель и директор по развитию Софтонит. Практикующий руководитель разработки. Эксперт в области автоматизации техподдержки

Загрузка...
Поделитесь статьей
Рекомендуем почитать
Статьи Синий экран и ошибка Windows aksfridge.sys при установке драйвера защиты HASP 1С

Не так давно мы столкнулись с проблемой, когда при установке 1С (в частности в конце, когда устанавливаются драйвера защиты HASP), появляется синий экран ошибки Windows и где указано:
Код остановки: PAGE_FAULT_IN_NONPAGET_AREA
Вызвало проблему: aksfridge.sys
Давайте разберемся как эту проблему решить.

Статьи Определить пол по ФИО

Функция на встроенном языке для определения пола по фамилии имени и отчеству (ФИО)

Статьи Кружок 1С #6 Асинхронность и многопоточность. О чем умалчивает ИТС

Продолжаем формат кружка 1С и в этот раз мы решили разобраться что такое Асинхронность в 1С, и как этим пользоваться.

Статьи Кружок 1С #5. Регулярные выражения (RegExp) для 1С-ника и не только

Продолжаем формат кружка 1С и сегодня поговорили с коллегами о регулярных выражениях (RegExp), которые появятся в 1С:Предприятие в 8.3.23.

Статьи Много тестовых баз 1С и много разработчиков. Как работать, чтобы не запутаться

Иногда возникают ситуации, когда надо развернуть тестовую базу клиента / свою на серверах Windows или Linux. Тестовые базы могут понадобиться в разных ситуациях: у клиента ошибка, на нашей базе она не воспроизводится, реализуем новый функционал и хотелось бы протестировать на Linux и т.д.

А теперь представим, что это все на потоке. Что тестовых баз 1С не одна, а 20-30. И получаем проблему, что не понятно занята она сейчас кем-то или нет.

И тут начинается:

  1. База есть, названа test34214, но не понятно используется она сейчас кем-то или нет.
  2. Вопрос в зал / в TG: ребята, а кто-то использует сейчас базу test34214?
  3. Тишина.
  4. Начинаем работать и через 2 дня получаем от коллеги: "Ой, а мне нужна была эта база. Кто ее затер?"

Суть я думаю понятна. Не понятно как эту проблему решать...

0 / 0