gifts2017

Простая и быстрая эмуляция операций с битовыми строками

Опубликовал Сергей (ildarovich) в раздел Программирование - Практика программирования

Битовые строки могли бы упростить реализацию некоторых алгоритмов на языке платформы «1С: Предприятие 8». Но пока в платформе операций с битовыми строками нет.  В то же время уже сделанные попытки смоделировать эти операции преобразованиями над числами опираются на циклы обработки отдельных битов, что плохо сказывается на скорости их работы. Предлагается новое простое решение, основанное на представлении битовых строк строками символов «0» и «1». Приводится примеры кода выполнения основных логических операций AND, OR, XOR, NO без использования циклов.
В качестве прикладной задачи рассмотрено получение последовательных значений кода Грэя, который можно использовать для ускорения перебора вариантов.

В статье «Расчет SHA-1 хеша средствами 1С. Битовые операции в 1С или урок двоичной математики» приведен набор функций, позволяющий работать с числами как с битовыми строками. В основе всех приведенных там функций лежат циклы побитовой обработки.

Альтернативным способом представления битовых строк как чисел является их представление символьными строками. Хранение битовых строк как символьных строк из «0» и «1» хоть и отнимает в 8 (16) раз больше памяти, но дает возможность избавиться от циклов при выполнении логических операций над строками.

1. Функция "ИЛИ"

Например, операция логического «или» (or, дизъюнкции) входных битовых строк Х и У может быть выполнена так:

СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "1")

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

Нули = СтрЗаменить(Формат(1, "ЧВН=; ЧГ=0; ЧЦ=" + Разрядность), "1", "0");
ФорматнаяСтрока = "ЧН=" + Нули + "; ЧВН=; ЧГ=0; ЧЦ=" + Разрядность;

Например, в соответствии с правилами выполнения логической операции «или» для исходных строк

Х = «0101»;

У = «0011»

будет получен результат:

Ф = «0111».

Другими словами, строка преобразуется в десятичное число, затем десятичные числа складываются. В результате отдельные разряды приобретают значения "0", "1" или "2". Затем из числа снова образуется строка, в которой "2", стоящая на месте сложения двух единиц, меняется на "1" в соответствии с правилами выполнения данной логической операции.

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

Из-за особенностей работы функции «формат» длина битовых (символьных) строк, обрабатываемых таким образом, ограничена 309 битами (символами).

2. Функция "XOR"

Так же просто выглядит операция логическое «исключающее или» (xor, неравнозначность):

СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "0")

Для примера можно взять две 64-х разрядных строки:

Х = «1000110100011101010111111010101000000011111101000111110000000111»;

У = «1000110100011101010111111110101000000011111101000111110000000111»

и получить следующий правильный результат:

Ф = «0000000000000000000000000100000000000000000000000000000000000000».

3. Функция "НЕ"

Еще проще выглядит операция логического отрицания «не» (no, отрицание):

СтрЗаменить(СтрЗаменить(СтрЗаменить(Х, "1", "_"), "0", "1"), "_", 0)

4. Функция "И"

Несколько сложнее выглядит операция логического «и» (and, конъюнкция):

СтрЗаменить(СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "1", "0"), "2", "1")

5. Замечания и уточнения 

Хотя основной сценарий использования операций над битовыми строками предполагает, что они имеют равную длину, соответствующую заранее выбранной фиксированной разрядности, функции работают и со строками разной длины, если она меньше заданной разрядности. При этом строки выравниваются ПО ПРАВОМУ КРАЮ. Конечно, при желании это можно изменить, чуть усложнив код.

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

Проверка быстродействия приведенного приема показывает выигрыш примерно в 15 раз по сравнению с функциями, приведенными в статье "Битовые операции в 1С или урок двоичной математики ".

Немаленьким бонусом является возможность подсчета числа единиц (нулей) в строке с использованием встроенной функции языка СтрЧислоВхождений(БитоваяСтрока, «1»), что для чисел требует оптимизации даже на уровне ассемблера [Обстоятельно о подсчёте единичных битов ].

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

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

Вот, например, так выполняется операция инкремента (младший разряд слева):

Яма = Найти(Х, "0");
Х = Лев(Нули, Яма - 1) + "1" + Сред(Х, Яма + 1)

 

6. Практическое применение: код Грэя

В качестве примера применения данного подхода предлагается реализация функции, получающей следующее значение двоичного кода Грэя [ссылка]. Этот код отличается тем, что каждое следующее значение кода отличается от предыдущего только в одном разряде, при этом в N разрядах содержится ровно 2^N значений. Данный код удобно использовать при решении задач перебора, поскольку на каждый итерации становится возможным не формировать тестовый набор заново, а получать его из предыдущего включением или исключением всего одного элемента.

Правило получения следующего значения таково [http://rsdn.ru/article/alg/gray.xml]: если число единиц в текущем значении кода четно, то инвертируется первый бит текущего значения кода, в противном случае инвертируется бит, следующий за первой единицей.

В итоге получается следующая функция:

Функция СледующийПоГрэю(Код, Позиция = 0)
            Нули = СтрЗаменить(Код, "1", "0");
            ФорматнаяСтрока = "ЧН=" + Нули + "; ЧВН=; ЧГ=0; ЧЦ=" + СтрДлина(Код);
            Позиция = ?(СтрЧислоВхождений(Код, "1") % 2 = 0, 1, Найти(Код, "1") + 1);
            Маска = "1" + Сред(Нули, Позиция + 1);
            Возврат СтрЗаменить(Формат(Число(Код) + Число(Маска), ФорматнаяСтрока), "2", "0");
КонецФункции

При последовательности вызовов с начальным значением «0000» функция производит следующую последовательность значений кода:

1000

1100

0100

0110

1110

1010

0010

0011

1011

1111

0111

0101

1101

1001

0001

0000

и так далее.

Выводы

Конечно, генерацией кода Грэя применение битовых строк не исчерпывается.

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

Кроме того, можно надеяться, что с появлением нового простого инструмента круг решаемых этим инструментом задач также расширится.

Приложение

Далее приведен весь код в виде набора функций, необходимых для обработки "битовых строк":

Перем Нули, Единицы, ФорматнаяСтрока;

Функция Неравнозначность(Х, У)
	Возврат СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "0")	
КонецФункции

Функция Дизъюнкция(Х, У)
	Возврат СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "1")
КонецФункции

Функция Конъюнкция(Х, У)
	Возврат СтрЗаменить(СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока)
, "1", "0"), "2", "1")	
КонецФункции

Функция Отрицание(Х)
	Возврат Формат(Число(Единицы) - Число(Х), ФорматнаяСтрока)	
КонецФункции

Функция Сдвиг(Х, У)
	Возврат Формат(Число(Х), ФорматнаяСтрока + "; ЧС=" + У)	          
КонецФункции

Функция _Отрицание(Х)
	Возврат СтрЗаменить(СтрЗаменить(СтрЗаменить(Х, "1", "_"), "0", "1"), "_", 0)	
КонецФункции

Функция Инкремент(Х)
	Яма = Найти(Х, "0");
	Возврат ?(Яма = 0, Х, Лев(Нули, Яма - 1) + "1" + Сред(Х, Яма + 1))	
КонецФункции

Функция Декремент(Х)
	Пик = Найти(Х, "1");
	Возврат ?(Пик = 0, Х, Лев(Единицы, Пик - 1) + "0" + Сред(Х, Пик + 1))	
КонецФункции

Функция СледующийПоГрэю(Код, Место = 0)
	Место = ?(СтрЧислоВхождений(Код, "1") % 2, Найти(Код, "1") + 1, 1);
	Маска = "1" + Сред(Нули, Место + 1);
	Возврат СтрЗаменить(Формат(Число(Код) + Число(Маска), ФорматнаяСтрока), "2", "0");	
КонецФункции

Разрядность = Мин(Разрядность, 309);
Нули = СтрЗаменить(Формат(1, "ЧВН=; ЧГ=0; ЧЦ=" + Разрядность), "1", "0");
Единицы = СтрЗаменить(Нули, "0", "1");
ФорматнаяСтрока = "ЧН=" + Нули + "; ЧВН=; ЧГ=0; ЧЦ=" + Разрядность;

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Яков Коган (Yashazz) 22.06.16 13:38
Да, иногда не хватает. Хотя тут обещали в https://wonderland.v8.1c.ru/blog/novye-instrumenty-dlya-raboty-s-dvoichnymi-dannymi-obespechivayut-kak-posledovatelnyy-dostup-k-danny/ некоторые "побайтовые операции", но не сейчас и вообще пока неясно, как реализуют...
2. Сергей (ildarovich) 22.06.16 13:52
(1) Yashazz, да, я в курсе этих планов, поэтому и написал в анонсе "пока нет". Но мне показалось, что 1С это делает в основном для задач интеграции, сопряжения с оборудованием и тому подобное, а не для алгоритмических задач, но посмотрим.
Идея была на поверхности - жалко было проходить мимо.
3. Максим *** (premier) 25.06.16 13:17
(0) ildarovich, а всё же, если реализовать алгоритм расчета SHA-1 с помощью Вашего метода, какой прирост в скорости выполнения он даст. Не тестировали?
4. Максим *** (premier) 25.06.16 13:31
(0) И ещё в примере не указано, каким значением инициализируется переменная "Разрядность".
5. Максим *** (premier) 25.06.16 13:39
(0) Функция Сдвиг(4, -2) при разрядности 8 выдает вот такой результат: 00000400. На битовую строку не похоже как-то...
6. Максим *** (premier) 25.06.16 14:08
(0) Функция Дизъюнкция(4, 2) возвращает результат 00000006, тоже на битовую строку не похоже.
Поторопился плюс поставить или не понял чего-то?
7. Максим *** (premier) 25.06.16 14:20
(0) Понял, кажется. На вход функций надо передать именно битовую строку. Тогда всё верно отрабатывает. А если я оперирую числами и хочу увидеть результат выполнения предложенных Вами функций, следует преобразовать операнды в битовые строки и обратные манипуляции проделать с результатом. Насколько я знаю, при таком преобразовании без циклов не обойтись. А так - решение интересное.
8. Андрей Акулов (DrAku1a) 27.06.16 02:55
(1) Жду с нетерпением - когда 1С это реализует. Нормальных методов разбора multipart-HTTP запроса в 1С не хватает. У меня есть решение на BASE64-строках и разделением файлов, но оно - не самое эффективное.
(0) Автору статьи - очередной респект (+++).
9. Александр Отр (ИНТЕГРА) 28.06.16 16:46
Когда попадаются подобные статьи, у меня всегда возникает вопрос - на каких проектах применялись такие методы? Интересно было бы послушать.
so-quest; freez1301; +2 Ответить 1
10. aspirator 23 (aspirator23) 02.07.16 15:03
(9) ИНТЕГРА, на ваших будущих.
11. Алексей Сафонов (newold2) 04.08.16 08:59
Перевод строки в двоичную и обратно описан https://infostart.ru/public/274498/ (частный случай применения функции Стр_Перекодировка()).
12. Роберт В е р т и н с к и й (v3rter) 09.08.16 10:38
Таки пообещали в 8.3.10 http://infostart.ru/journal/news/mir-1s/platformy-1s-predpriyatie-8-3-10-budet-luchshe-rabotat-s-dvoichnymi-dannymi%e2%80%94541161/

05.08.2016
... вы сможете выполнять прямое и обратное преобразование двоичных данных в обычную строку, строку формата Base64 и строку формата BinHex. Кроме этого сами двоичные данные вы можете преобразовать в форматы Base64, BinHex и обратно.

Аналогичные преобразования поддерживаются и для типа БуферДвоичныхДанных. Кроме этого буфер двоичных данных вы можете преобразовывать в двоичные данные и обратно.
...
Эффективное копирование с помощью чтения и записи данных.
Побитовые логические операции с буфером двоичных данных.
Получение числа из шестнадцатеричных и двоичных литералов.
13. Сергей (ildarovich) 09.08.16 11:01
(12) v3rter, да, видел эту заметку. Но там все же акцент делается на задачах интеграции, а не на алгоритмах, где могут понадобиться битовые строки.
С другой стороны, большого количества алгоритмических задач, которые могли бы показать возможности применения битовых строк (кроме уже приведенных задач с кодами), я пока не нашел.
Думал в направлении генетических алгоритмов, но пока безрезультатно.
Возможно, со временем, что-нибудь и найдется.
А новые возможности 8.3.10 очень интересны: открывают простор для творчества в области "безцикловых" преобразований данных в 1С.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа