gifts2017

Расчет хэш-функции в запросе

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

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

1. Используемый способ вычисления значения хэш-функции

Для расчета значения хэш-функции строковых значений может использоваться следующая формула

h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N, где P - некоторое простое число, например, 31.

То есть, значение хэш-функции является суммой произведения кодов символов строки на члены степенного ряда 1, 31, 31^2, 31^3, 31^4 и так далее. При этом все расчеты выполняются по модулю 2^32, то есть при вычислениях отбрасываются все двоичные разряды, старше тридцать второго. Такой способ расчета хэш-функции приводится, например, в статье "Алгоритмы хэширования в задачах на строки".

Таблица степенного ряда, содержащая две колонки: "Позиция" и "ЧленРяда" будет иметь вид:

Позиция ЧленРяда
1  1
2  31
3  961
4  29791
5  923521
6  28629151
7  887503681
8

 1742810335

9

  2487512833

10

4098453791

11 2498015937
12 129082719
... ...

 

Интересно, что в таблице степенного ряда элемент в 12-ой позиции оказался меньше элемента в 11-й позиции, который, в свою очередь, оказался меньше элемента в 10-й позиции за счет расчета степени в кольце 2^32.

2. Текст основного запроса 

Если таблица с исходными данными имеет две колонки: колонку "НомерСтроки" и строковую колонку "Аргумент", а таблица степенного ряда уже построена, то запрос для расчета Хэш-функции будет иметь вид:

ВЫБРАТЬ
	Данные.НомерСтроки,
	ПОДСТРОКА(Данные.Аргумент, Ряд.Позиция, 1) КАК Символ,
	Ряд.ЧленРяда
ПОМЕСТИТЬ ОтдельныеСимволы
ИЗ
	ИсходныеДанные КАК Данные,
	СтепеннойРяд КАК Ряд
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Символы.НомерСтроки,
	СУММА(Символы.ЧленРяда * Таблица.Код) КАК СуммаПроизведений
ПОМЕСТИТЬ СырыеДанные
ИЗ
	ОтдельныеСимволы КАК Символы
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ КодоваяТаблица КАК Таблица
		ПО Символы.Символ = Таблица.Символ
			И (Символы.Символ ПОДОБНО Таблица.Символ)

СГРУППИРОВАТЬ ПО
	Символы.НомерСтроки
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Данные.НомерСтроки,
	Данные.СуммаПроизведений - ((ВЫРАЗИТЬ(Данные.СуммаПроизведений / 4294967296 + 0.5 КАК ЧИСЛО(20, 0))) - 1) * 4294967296 КАК Хэш
ПОМЕСТИТЬ ВыходныеДанные
ИЗ
	СырыеДанные КАК Данные

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

3. Запросы для формирования вспомогательных таблиц

В основном запросе, кроме таблицы степенного ряда, используется таблица "КодоваяТаблица", сопоставляющая каждому используемому символу его код:

Символ Код
... ...
A 65
B 66
... ...

 

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

Функция НаборСимволов(КодировкаТекста = "windows-1251", Ответ = "")
	
	Для КодСимвола = 1 По 255 Цикл 
		Ответ = Ответ + Символ(КодСимвола)
	КонецЦикла;
	
	ТекстовыйДокумент = Новый ТекстовыйДокумент;
	
	ТекстовыйДокумент.УстановитьТекст(Ответ);
	
	ПутьКФайлу = ПолучитьИмяВременногоФайла();
	
	ТекстовыйДокумент.Записать(ПутьКФайлу, "ISO-8859-1", "");
	
	ТекстовыйДокумент.Прочитать(ПутьКФайлу, КодировкаТекста, "");
	
	Ответ = ТекстовыйДокумент.ПолучитьТекст();
	
	Возврат Ответ 	
	
КонецФункции

Следующий запрос осуществляет ввод этого набора символов во временную таблицу "КодоваяТаблица". В результате указанная таблица фактически является таблицей перекодировки символов юникода  в коды ascii. Те символы юникода, которые не попали в таблицу перекодировки, при расчете хэш-функции учтены не будут.

 

ВЫБРАТЬ
	ПОДСТРОКА(&НаборСимволов, Ряд.Позиция, 1) КАК Символ,
	Ряд.Позиция КАК Код
ПОМЕСТИТЬ КодоваяТаблица
ИЗ
	НачалоРяда КАК Ряд

ИНДЕКСИРОВАТЬ ПО
	Символ

 

Для расчета степенного ряда используется один начальный запрос

ВЫБРАТЬ
	1 КАК Позиция,
	1 КАК ЧленРяда,
	ЛОЖЬ КАК Край
ПОМЕСТИТЬ НачалоРяда

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	2,
	31,
	ИСТИНА

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

ВЫБРАТЬ
	Ряд.Позиция,
	Ряд.ЧленРяда,
	ЛОЖЬ КАК Край
ПОМЕСТИТЬ ПродолженныйРяд
ИЗ
	НачалоРяда КАК Ряд

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
	Ряд.Позиция + Грань.Позиция,
	Ряд.ЧленРяда * Грань.ЧленРяда * 31,
	Ряд.Край
ИЗ
	НачалоРяда КАК Ряд
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ НачалоРяда КАК Грань
		ПО (Грань.Край)
;

////////////////////////////////////////////////////////////////////////////////
УНИЧТОЖИТЬ НачалоРяда
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	Ряд.Позиция,
	Ряд.ЧленРяда - ((ВЫРАЗИТЬ(Ряд.ЧленРяда / 4294967296 + 0.5 КАК ЧИСЛО(20, 0))) - 1) * 4294967296 КАК ЧленРяда,
	Ряд.Край
ПОМЕСТИТЬ НачалоРяда
ИЗ
	ПродолженныйРяд КАК Ряд
;

////////////////////////////////////////////////////////////////////////////////
УНИЧТОЖИТЬ ПродолженныйРяд

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

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

 

ВЫБРАТЬ
	Ряд.Позиция,
	Ряд.ЧленРяда
ПОМЕСТИТЬ СтепеннойРяд
ИЗ
	НачалоРяда КАК Ряд
ГДЕ
	Ряд.Позиция <= &ДлинаСтроки

4. Результаты испытаний

По аналогии со статьей "Несколько простых хеш-функций и их свойства" вычислена частота повторения значений в отдельных байтах получаемого значения хэш-функции. Для этого рассчитан миллион значений хэш-функции для случайных строк длиной 10 байтов, составленных из заглавных символов латинского алфавита от A до Z. Соответствующие графики приведены на Фиг.1.

Частота значений в байтах хэш-функции

Частота0 на графике обозначает частоту повторения значений нулевого байта, Частота 1 - первого и так далее.

Видно, что байты с нулевого по второй распределены практически равномерно. Исключение составляет третий байт, в поведении которого наблюдаются нежелательные закономерности. Впрочем, для практических целей это приемлемо. Действительно больших выбросов на графиках нет. Тем более, скорее всего, наличие закономерностей объясняется небольшим диапазоном использованных символов в исходной строке. 

Запрос показывает вполне приемлемую скорость расчетов. На расчет миллиона хэшей для строк из 10-ти символов на хорошем компьютере уходит примерно 100 секунд. Следовательно, один символ отнимает примерно 0.01 миллисекунды. Исходя из этого можно определить требуемое время расчета хэшей для любой исходной таблицы. Если сравнить быстродействие предлагаемого метода расчета в запросе и метода расчета значения хэш-функции в коде, описываемого в статье "Простая и быстрая хэш функция (hash) средствами 1С (оптимизированный вариант)", то получается, что предлагаемый метод на строках длинной 1222 символа показывает быстродействие примерно 12440 хэшей в минуту, то есть его скорость примерно в два раза ниже расчета хэш-функции в коде.

При необходимости, предложенную схему построения запроса, рассчитывающую хэш-функцию, можно модифицировать.Можно увеличить разрядность значения хэш-функции. Можно изменить основание степенного ряда: подойдет простое число, примерно соответствующее количеству различных символов в строке: 37, 53 и так далее. Можно увеличить кодовую таблицу, добавив весь юникод или реально встречающиеся символы. А также, во многих задачах можно не отбрасывать лишние биты после суммирования произведений. Также существует несколько других вариантов записи основного запроса: с использованием вложенных запросов или с одновременным соединением таблиц исходных данных, таблицы степенного ряда и кодовой таблицы, отличающихся более компактной записью. Приведенный вариант выбран из-за большей наглядности и стабильной скорости выполнения. 

Использованная формула не позволяет применять данный метод для задач криптогафии. Это хорошо показано в статье "Лжеотождествление электровиолончели". Там предлагается не слишком сложный метод подбора строк с нулевым значением хэш-функции. 

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

Пример 1. Разбиение множества элементов номенклатуры на классы, имеющие одинаковое сочетание значений свойств.

В конфигурации "1С: Управление торговлей" редакции 10.3 длина кода значения свойства ограничена девятью знаками, а код состоит из одних цифр. С учетом этого поставленную задачу решает следующий запрос:

ВЫБРАТЬ 1 Позиция,  1 ЧленРяда
ПОМЕСТИТЬ СтепеннойРяд
ОБЪЕДИНИТЬ ВЫБРАТЬ  2, 31
ОБЪЕДИНИТЬ ВЫБРАТЬ  3, 961
ОБЪЕДИНИТЬ ВЫБРАТЬ  4, 29791
ОБЪЕДИНИТЬ ВЫБРАТЬ  5, 923521
ОБЪЕДИНИТЬ ВЫБРАТЬ  6, 28629151
ОБЪЕДИНИТЬ ВЫБРАТЬ  7, 887503681
ОБЪЕДИНИТЬ ВЫБРАТЬ  8, 1742810335
ОБЪЕДИНИТЬ ВЫБРАТЬ  9, 2487512833
ОБЪЕДИНИТЬ ВЫБРАТЬ 10, 4098453791
;
ВЫБРАТЬ ПОДСТРОКА("0123456789", Позиция, 1) КАК Символ, Позиция КАК Код
ПОМЕСТИТЬ КодоваяТаблица
ИЗ СтепеннойРяд
ИНДЕКСИРОВАТЬ ПО Символ
;
ВЫБРАТЬ Объект КАК Ссылка, Значение.Код КАК Аргумент
ПОМЕСТИТЬ ИсходныеДанные
ИЗ РегистрСведений.ЗначенияСвойствОбъектов
ГДЕ Объект ССЫЛКА Справочник.Номенклатура
;
ВЫБРАТЬ Ссылка, ПОДСТРОКА(Аргумент, Позиция, 1) КАК СимволКода, ЧленРяда
ПОМЕСТИТЬ ОтдельныеСимволы
ИЗ ИсходныеДанные, СтепеннойРяд
;
ВЫБРАТЬ Ссылка, СУММА(ЧленРяда * Код) КАК Хэш
ПОМЕСТИТЬ ВыходныеДанные
ИЗ ОтдельныеСимволы ВНУТРЕННЕЕ СОЕДИНЕНИЕ КодоваяТаблица
ПО СимволКода = Символ
СГРУППИРОВАТЬ ПО Ссылка
;
ВЫБРАТЬ Ссылка
ИЗ ВыходныеДанные
ИТОГИ ПО Хэш

Запрос будет работать в любой универсальной консоли запросов. Обход результата запроса по группировкам соответствует обходу номенклатуры по классам эквивалентности с точки зрения набора значений свойств. Заменив в одном месте наименование справочника, тем же запросом можно классифицировать контрагентов, сотрудников и другие объекты предметной области, имеющие заданные наборы свойств. 

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

Пример 2. Определение ТОП-5 состава товаров в накладных реализации

Данная задача также решается получением уникального числа для каждого набора товаров как суммы хэшей кодов номенклатуры в табличной части "Товары". Выбираются топ-5 хэшей, соответствующих наибольшему количеству накладных. Далее определяется состав хит-наборов. Учитывается, что код номенклатуры является строкой длиной 11 символов и состоит из одних цифр. В результате весь необходимый текст запроса, решающего поставленную задачу, будет иметь вид:  

ВЫБРАТЬ 1 Позиция,  1 ЧленРяда
ПОМЕСТИТЬ СтепеннойРяд
ОБЪЕДИНИТЬ ВЫБРАТЬ  2, 31
ОБЪЕДИНИТЬ ВЫБРАТЬ  3, 961
ОБЪЕДИНИТЬ ВЫБРАТЬ  4, 29791
ОБЪЕДИНИТЬ ВЫБРАТЬ  5, 923521
ОБЪЕДИНИТЬ ВЫБРАТЬ  6, 28629151
ОБЪЕДИНИТЬ ВЫБРАТЬ  7, 887503681
ОБЪЕДИНИТЬ ВЫБРАТЬ  8, 1742810335
ОБЪЕДИНИТЬ ВЫБРАТЬ  9, 2487512833
ОБЪЕДИНИТЬ ВЫБРАТЬ 10, 4098453791
ОБЪЕДИНИТЬ ВЫБРАТЬ 11, 2498015937
;
ВЫБРАТЬ ПОДСТРОКА("0123456789", Позиция, 1) КАК Символ, Позиция КАК Код
ПОМЕСТИТЬ КодоваяТаблица
ИЗ СтепеннойРяд
ИНДЕКСИРОВАТЬ ПО Символ
;
ВЫБРАТЬ Ссылка, Номенклатура.Код КАК Аргумент
ПОМЕСТИТЬ ИсходныеДанные
ИЗ Документ.РеализацияТоваровУслуг.Товары
ГДЕ Ссылка.Организация = &Организация И Ссылка.Дата МЕЖДУ &Дата1 И &Дата2
;
ВЫБРАТЬ Ссылка, ПОДСТРОКА(Аргумент, Позиция, 1) КАК СимволКода, ЧленРяда
ПОМЕСТИТЬ ОтдельныеСимволы
ИЗ ИсходныеДанные, СтепеннойРяд
;
ВЫБРАТЬ Ссылка, СУММА(ЧленРяда * Код) КАК Хэш
ПОМЕСТИТЬ ВыходныеДанные
ИЗ ОтдельныеСимволы ВНУТРЕННЕЕ СОЕДИНЕНИЕ КодоваяТаблица
ПО СимволКода = Символ И СимволКода ПОДОБНО Символ
СГРУППИРОВАТЬ ПО Ссылка
;
ВЫБРАТЬ Первые 5 Хэш, Количество(*) КАК Частота
ПОМЕСТИТЬ ХитовыеХэши
ИЗ ВыходныеДанные
СГРУППИРОВАТЬ ПО Хэш
УПОРЯДОЧИТЬ ПО Частота УБЫВ
;
ВЫБРАТЬ РАЗЛИЧНЫЕ Номенклатура, Частота
ИЗ ХитовыеХэши 
ВНУТРЕННЕЕ СОЕДИНЕНИЕ ВыходныеДанные ПО ХитовыеХэши.Хэш = ВыходныеДанные.Хэш
ВНУТРЕННЕЕ СОЕДИНЕНИЕ Документ.РеализацияТоваровУслуг.Товары КАК Товары ПО ВыходныеДанные.Ссылка = Товары.Ссылка
УПОРЯДОЧИТЬ ПО Частота УБЫВ
ИТОГИ ПО ХитовыеХэши.Хэш

 

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

 

Пример 3. "ВЫБРАТЬ СЛУЧАЙНЫЕ"

Не так часто, но все же встречается задачи, когда запрос должен вернуть не определенные, а некоторые случайным образом выбранные записи какой-либо таблицы.  Если имеется конструкция "ВЫБРАТЬ РАЗЛИЧНЫЕ", "ВЫБРАТЬ ПЕРВЫЕ", то отражением требования этой задачи было бы наличие в языке запросов конструкции "ВЫБРАТЬ СЛУЧАЙНЫЕ". И хотя такой конструкции нет, ее можно смоделировать. Например, присоединив (динамически в запросе) к коду элементу справочника строку текущей даты (вместе с временем)  и рассчитав хэш полученной строки, можно получить некоторое псевдослучайное число. Если отсортировать по этому числу справочник и выбрать нужное число первых элементов, то выбор будет малопредсказуемым, то есть фактически случайным. Из соображений эффективности можно сделать еще проще - добавлять текущее время (в секундах) с начала времен к получаемой сумме произведений.

Такой подход использован в следующем запросе

ВЫБРАТЬ Ссылка, Код КАК Аргумент
ПОМЕСТИТЬ ИсходныеДанные
ИЗ Справочник.Номенклатура 
ГДЕ НЕ ЭтоГруппа 
;
ВЫБРАТЬ 1 Позиция, 1 КАК ЧленРяда
ПОМЕСТИТЬ СтепеннойРяд
ОБЪЕДИНИТЬ ВЫБРАТЬ  2, 31
ОБЪЕДИНИТЬ ВЫБРАТЬ  3, 961
ОБЪЕДИНИТЬ ВЫБРАТЬ  4, 29791
ОБЪЕДИНИТЬ ВЫБРАТЬ  5, 923521
ОБЪЕДИНИТЬ ВЫБРАТЬ  6, 28629151
ОБЪЕДИНИТЬ ВЫБРАТЬ  7, 887503681
ОБЪЕДИНИТЬ ВЫБРАТЬ  8, 1742810335
ОБЪЕДИНИТЬ ВЫБРАТЬ  9, 2487512833
ОБЪЕДИНИТЬ ВЫБРАТЬ 10, 4098453791
ОБЪЕДИНИТЬ ВЫБРАТЬ 11, 2498015937
;
ВЫБРАТЬ Ссылка, РАЗНОСТЬДАТ(ДАТАВРЕМЯ(2015, 1, 1), &ТекущаяДата, СЕКУНДА) * 129082719 + 
СУММА(ЧленРяда * ВЫБОР ПОДСТРОКА(Аргумент, Позиция, 1) КОГДА ""0"" ТОГДА 1 КОГДА ""1"" ТОГДА 2 КОГДА ""2"" ТОГДА 3 КОГДА ""3"" ТОГДА 4 
КОГДА ""4"" ТОГДА 5 КОГДА ""5"" ТОГДА 6 КОГДА ""6"" ТОГДА 7 КОГДА ""7"" ТОГДА 8 КОГДА ""8"" ТОГДА 9 КОГДА ""9"" ТОГДА 10 ИНАЧЕ 0 КОНЕЦ) КАК Сумма
ПОМЕСТИТЬ СырыеДанные
ИЗ ИсходныеДанные, СтепеннойРяд
СГРУППИРОВАТЬ ПО Ссылка
;
ВЫБРАТЬ ПЕРВЫЕ 5 Ссылка КАК Элемент
ИЗ	СырыеДанные
УПОРЯДОЧИТЬ ПО	Сумма - ((ВЫРАЗИТЬ(Сумма / 16777216 + 0.5 КАК ЧИСЛО(20, 0))) - 1) * 16777216

В отличие от предыдущих запросов, здесь не используется кодовая таблица. Если в коде справочника использованы одни цифры, то код цифр быстрее получается с использованием оператора "ВЫБОР". Также использованы только младшие три байта хэш функции, имеющие более равномерное распределение. Заменив наименование справочника, можно выбирать случайных контрагентов, сотрудников и так далее.

Для достижения максимального быстродействия, учитывая небольшую фиксированную длину кода элемента справочника можно записать сумму в одно выражение (инлайн). Также можно снизить затраты на сортировку, предварительно отобрав строки в соответствиями с идеей статьи Selecting Rows Randomly from a Large Table. В итоге получается следующий быстрый запрос:

ВЫБРАТЬ
	Номенклатура.Ссылка,
	Номенклатура.Код КАК Аргумент
ПОМЕСТИТЬ ИсходныеДанные
ИЗ
	Справочник.Номенклатура КАК Номенклатура
ГДЕ
	НЕ Номенклатура.ЭтоГруппа
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
	ИсходныеДанные.Ссылка,
	РАЗНОСТЬДАТ(ДАТАВРЕМЯ(2015, 1, 1), &ТекущаяДата, СЕКУНДА) * 129082719 + 1 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 1, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 31 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 2, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 961 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 3, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 29791 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 4, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 923521 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 5, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 28629151 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 6, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 887503681 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 7, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 1742810335 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 8, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 2487512833 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 9, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 4098453791 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 10, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ + 2498015937 * ВЫБОР ПОДСТРОКА(ИсходныеДанные.Аргумент, 11, 1)
		КОГДА "0"
			ТОГДА 1
		КОГДА "1"
			ТОГДА 2
		КОГДА "2"
			ТОГДА 3
		КОГДА "3"
			ТОГДА 4
		КОГДА "4"
			ТОГДА 5
		КОГДА "5"
			ТОГДА 6
		КОГДА "6"
			ТОГДА 7
		КОГДА "7"
			ТОГДА 8
		КОГДА "8"
			ТОГДА 9
		КОГДА "9"
			ТОГДА 10
		ИНАЧЕ 0
	КОНЕЦ КАК Сумма
ПОМЕСТИТЬ СырыеДанные
ИЗ
	ИсходныеДанные КАК ИсходныеДанные
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ ПЕРВЫЕ 5
	Данные.Ссылка КАК Элемент
ИЗ
	(ВЫБРАТЬ
		СырыеДанные.Ссылка КАК Ссылка,
		СырыеДанные.Сумма - ((ВЫРАЗИТЬ(СырыеДанные.Сумма / 16777216 + 0.5 КАК ЧИСЛО(20, 0))) - 1) * 16777216 КАК Сумма
	ИЗ
		СырыеДанные КАК СырыеДанные) КАК Данные,
	(ВЫБРАТЬ
		КОЛИЧЕСТВО(*) КАК Количество
	ИЗ
		ИсходныеДанные КАК ИсходныеДанные) КАК ВложенныйЗапрос
ГДЕ
	Данные.Сумма < 5 * 2 * 16777216 / ВложенныйЗапрос.Количество

УПОРЯДОЧИТЬ ПО
	Данные.Сумма

 

  

 

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Виталий Барилко (Diversus) 20.03.15 10:04
(0) Смотришь на ваши статьи по запросам и думаешь: "...Так, чем сегодня удивит ildarovich".
Мне нравятся Ваши статьи и у Вас подход совершенно не 1С-овский к решению задач. Обычно 1С-ники сначала сделают, а потом думают как оптимизировать.
Вы же идете совершенно по другому пути: теория, вперемешку с тестами и результатом всего этого является красивое и лаконичное решение да еще и запросом.
Язык запросов 1С сильно ограничен, но глядя на Ваши статьи начинаешь задумываться, а так ли это? :)
Obscurus; spogo; myr4ik07; crabzzy; Евген86; Noxie41; Йожкин Кот; soulsteps; Liris; Kinestetik; CheBurator; vladir; pit201201; forrain@rambler.ru; sorb; spetzpozh; gulchitai; dj_serega; Il; 1cWin; artbear; vadnevzorov; lustin; Evil Beaver; +24 Ответить 1
2. Игорь Пашутин (Alien_job) 20.03.15 10:04
Я правильно понял — хитрости с хешем нужны потому, что нет конкатенации строк в запросе?
3. Сергей Ожерельев (Поручик) 20.03.15 10:05
Как всегда, поставил зачёт, почитал, и даже подумал.
Evil Beaver; +1 Ответить
4. Евгений Ванжула (minimajack) 20.03.15 10:30
нафига козе боян? Что делать с коллизиями?
5. Игорь Пашутин (Alien_job) 20.03.15 10:52
Очень любопытное использование запроса. Но разве сложение хешей дает новый хеш?
(20 + 40*31) * 3 = (30 + 60 * 31)*2. Получим 6 вхождений "хеша"
Да и число 31 кажется недостаточно большим - символы с кодами большими 31 вносят дополнительную опасность смешивания результатов.
(62 + 10*31) = (31 + 11*31)

Касательно кодов номенклатуры - если использовать префиксы, то "кл0000021" == "Мк0000021".
6. Евгений Ванжула (minimajack) 20.03.15 12:30
(5) Alien_job,
>число 31 кажется недостаточно большим
существует объяснение почему именно 31 от Joshua Bloch:
The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

Effective Java
7. Сергей (ildarovich) 20.03.15 14:59
(2) Alien_job, конкатенация могла бы помочь, но до определенного предела. В запросе нельзя сравнивать (группировать) строки длиннее 1024 символа. Поэтому можно будет классифицировать наборы ограниченного количества свойств. А использование хэш-функции таких ограничений не ставит. Кроме того, это всего лишь один из примеров применения данного приема, наверняка найдутся и другие задачи.
8. Сергей (ildarovich) 20.03.15 16:33
(4) minimajack, тут приведено несколько совершенно реальных практических задач, которые быстро и просто решаются данным методом. В данных задачах коллизии не столь страшны. Кроме того, они крайне маловероятны. Ну, крайне редко случайно смешаются два разных набора товаров, получат общий суммарный рейтинг и поднимутся в топ повыше. Или в один класс раз в сто лет смешаются номенклатуры с разными наборами свойств. - Что тут страшного? А для ответственных применений можно разрядность повысить, чтобы сделать вероятность коллизий еще меньше.
9. Сергей (ildarovich) 20.03.15 16:46
(5) Alien_job, формул вычисления хэш-функций очень много. В статье ссылки приведены. Я взял известную, проверенную. Спорить о том, какая лучше, какая хуже бессмысленно, не имея конкретной статистики строк. Если коллизий окажется много, основание степени можно и поменять.
Арифметическое сложение хэшей дает новый хэш, но худшего качества. Поскольку распределение из равномерного становится нормальным, где в средней части вероятность коллизий выше. Например, по сравнению с поразрядным XOR. В данной задаче это снижение качества не кажется существенным.
Вообще говоря, первоначально было реализовано вычисление хэша в виде CRC путем моделирования работы регистра сдвига с обратными связями. Однако быстродействие того метода не удалось довести до приемлемых значений, поскольку нужно учитывать отдельные биты кодов символов. Поэтому взята более простая формула. И если она используется в Java, почему бы не использовать ее в запросе.
10. Евгений Ванжула (minimajack) 20.03.15 18:34
(8) ildarovich, на практике это означает буквально лишение премии.
пример явно не самый удачный...да и использование хэширования в 1С8 для реальных нужд в больших объемах не могу представить; тут либо производительность, либо качество подведут.
11. kolya_tlt kolya_tlt (kolya_tlt) 20.03.15 19:31
(1) Diversus, Такой же подход рекомендуют и на курсах Microsoft в баумантке, поэтому он не только 1совский
12. Сергей Лесовой (Synoecium) 23.03.15 09:11
(8)
Ну, крайне редко случайно смешаются два разных набора товаров, получат общий суммарный рейтинг и поднимутся в топ повыше. Или в один класс раз в сто лет смешаются номенклатуры с разными наборами свойств. - Что тут страшного?

А смысл в алгоритме, который может иногда давать неправильные результаты? Данная задача нормально решается кодом, например, собираем сумму кодов номенклатуры в длинную строку, а потом по этой строке группируем документы, чтобы определить какой набор встречается чаще.
Конечно это не отменяет полезность хеширования и тема раскрыта интересная.
13. Сергей (ildarovich) 23.03.15 18:53
(12) Synoecium, давайте сначала оценим вероятность неверного выбора Топ-5 наборов при использовании приведенного запроса.
Пусть есть M действительно разных наборов. Вероятность того, что два из них будет иметь одинаковый хэш, равный сумме хэш-функций кодов номенклатуры, можно оценить числом от (M-1)M/2^32/K до (M-1)M/2^32, где К - максимальное число товаров в наборе. То есть, если разных наборов 1000, то вероятность будет меньше, чем 999000/4294967296 = 0,000232598.
Далее нужно учесть то, что хэш должен совпасть у наборов, совместная встречаемость которых попадает в Топ-5. Если 5-е место чаще 10-го в два раза (предположим), то, значит, для попадания суммой в Топ-5 по отдельности наборы должны попадать в Топ-10, что дает еще 10/1000*10/1000=1/10000 шансов. Получается, что неверным выбор будет в 2,32 из 100 000 000 (ста миллиона) случаев.
Даже если вы хотите перезаложиться на этот маловероятный расклад (как делают начинающие игроки в преферанс, сильно раздражая более опытных игроков), это не будет иметь практического смысла, так как в жизни более вероятным будет несоответствие выписанных товаров реально отпущенным (пересортица) и ваш суперточный расчет перечеркнется невнимательностью кладовщиков. Возможно, есть люди, которые, выходя из дома, надевают каску, учитывая отличную от нуля вероятность попадания в них метеорита (зная площадь земли и количество долетающих до нее метеоритов, эту вероятность тоже можно посчитать). Уподобляясь этим суперперестраховщикам, для данной задачи можно увеличить разрядность хэш-функции до 64-х или посчитать еще один хэш по другому основанию степенного ряда. Тогда вероятность совпадения хэшей наборов уменьшиться еще примерно в 4 миллиарда раз.
Кажется, этого по любому должно быть достаточно, чтобы доверять сравнению наборов по таким хэшам.
14. Сергей Лесовой (Synoecium) 24.03.15 12:11
(13) ildarovich, аргументы ваши убедительны, но (говорю только за себя) хочется быть уверенным в своем алгоритме и не держать в голове, что теоретически, он может сбойнуть, хоть и очень редко. Достаточно одного раза, чтобы остался осадок.
15. Евгений Ванжула (minimajack) 24.03.15 15:53
(14) Synoecium, (13) ildarovich,
до 15 000 000 (пятнадцать миллионов) значений хеш-функция абсолютна безопасна( с учетом того что коды используются только числовые)
0000...1
0000...2
........
15000000
коллизий не было
ИМХО использовать для хэширования можно. Использовать в наборах я бы не стал
зы на java(i3)10 мил-нов хэшей(10 символов) расчитывается за 4.5 сек
16. Сергей Рудаков (fishca) 25.03.15 15:35
Хочется только сказать: "ПОБОЛЬШЕ БЫ ТАКИХ АВТОРОВ НА ИНФОСТАРТЕ"
17. Сергей (ildarovich) 27.03.15 13:37
Добавлен Пример 3, показывающий, как можно выбирать из таблиц базы данных необходимое число записей СЛУЧАЙНЫМ образом. Ранее планировал сделать отдельную публикацию на эту тему, но запрос до такой степени прост, что отдельной публикации, кажется, не заслуживает.
18. Алекс Ю (AlexO) 27.03.15 14:36
Например, присоединив к коду элементу справочника строку текущей даты
Это, опять же, костыль. Нужно добавить Дату.
И, по сути, это Дата дает "случайный порядок", который вы просто пытаетесь "поймать".
19. Сергей (ildarovich) 27.03.15 15:49
Нужно сказать, что это никакой не костыль, а общий принцип построения генераторов случайных чисел. Все они используют какой-либо "источник энтропии". Многие - текущие время. Можно посмотреть таблицу по ссылке: Генератор псевдослучайных чисел. Из таблицы видно, что, например, в Windows в качестве источника энтропии используется: текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера. Затем на основе этих данных строится хэш-функция MD5, что и дает в итоге случайное число.
В нашем случае о криптографии речь не идет и все чуть попроще: источник энтропии - только текущее время, а хэш-функция - "31".
20. Алекс Ю (AlexO) 27.03.15 16:05
(19) ildarovich,
а хэш-функция - "31".
Это потому что ответ на "Главный вопрос жизни, Вселенной и всего вообще" уже дан? )))
21. Сергей (ildarovich) 27.03.15 16:23
(20) AlexO, не совсем понял вопрос. Тут приведено несколько довольно простых запросов, помогающих решить конкретные практические задачи. Я хотел, кроме всего, чтобы был понятен принцип их построения, а конкретные числа типа 31, 37, 53 взяты для примера и из-за того, что они уже не раз проверены.

А если это отсылка к фильму "Автостопом по галактике" (отличный, кстати, фильм), то какая тут связь?
22. Роман С (Dach) 06.04.15 13:21
Сергей, при попытке выполнить в консоли запросов запрос из Примера 3 возникла следующая ошибка:

Microsoft SQL Server Native Client 11.0: The datediff function resulted in an overflow. The number of dateparts separating two date/time instances is too large. Try to use datediff with a less precise datepart.
HRESULT=80040E57, SQLSrvr: SQLSTATE=22003, state=1, Severity=10, native=535, line=1

Версия СУБД MS SQL 2012... слишком большая точность для даты?
23. Сергей (ildarovich) 06.04.15 13:31
(22) Dach, а параметр &ТекущаяДата не забыли проинициализировать? Он должен иметь тип "дата" и включать время до секунд.
24. Роман С (Dach) 06.04.15 13:41
(23) конечно, я же в консоли запросов выполнял запрос.

Прикрепленные файлы:
25. Сергей (ildarovich) 06.04.15 13:49
(24) Dach, очень странно. Вычисляется всего лишь число секунд с 1.01.0001. Это не слишком большое число. Попробуйте тогда взять
РАЗНОСТЬДАТ(ДАТАВРЕМЯ(2015, 1, 1), &ТекущаяДата, СЕКУНДА)
Суть не в начальной дате. Главное, чтобы результат выражения при каждом следующем выполнении запроса давал разное число. Но а по-поводу диапазона значений аргументов в этой функции в вашей версии сервера - попробую изучить этот вопрос.
26. Роман С (Dach) 06.04.15 14:05
(25) заработало, но очень странно. Все время возвращает одну и ту же выборку, причем состав выборки меняется только если задать другую дату....
Прикрепленные файлы:
27. Сергей (ildarovich) 06.04.15 14:23
(26) Dach, так и было задумано. Энтропия должна быть внесена в запрос извне. В самом запросе нет надежного способа получения непредсказуемых значений. А так получается: перед каждым вызовом определяем текущее время и получаем сколько нужно "случайно-выбранных" элементов справочника. Случайность выбора определяется тем, что момент запуска запроса не предопределен.
28. Роман С (Dach) 06.04.15 14:24
И путем нехитрых экспериментов, методом деления пополам была найдена максимальная дата, начиная с которой идет переполнение длины возвращаемого числа:

РАЗНОСТЬДАТ(ДАТАВРЕМЯ(1947, 1, 1) : вот так не работает

РАЗНОСТЬДАТ(ДАТАВРЕМЯ(1948, 1, 1), &ТекущаяДата, СЕКУНДА) : вот так работает
29. Сергей (ildarovich) 06.04.15 14:28
(28) Dach, спасибо, на мой взгляд, так быть не должно. Видимо, это ошибка у 1С. А какая версия платформы?
30. Роман С (Dach) 06.04.15 14:30
(27) точно, прошу прощения, невнимательно прочитал описание примера)))

Хм... то есть если знать источник энтропии - то можно формировать какие-надо выборки... Все думают, что случайно, а оно на самом деле...

Знаешь энтропию - владеешь миром! ))))
31. Роман С (Dach) 06.04.15 14:31
32. Сергей (ildarovich) 06.04.15 14:40
(31) Dach, просьба: попробуйте, пожалуйста, вариант вот в таком виде:
РАЗНОСТЬДАТ(ДАТАВРЕМЯ(1, 1, 1, 0, 0, 0), &ТекущаяДата, СЕКУНДА) 
33. Роман С (Dach) 06.04.15 14:40
Теперь понятен прикладной смысл задачи вообще и ход Ваших рассуждений. То есть наверное была задача получать случайную выборку чего-нибудь. Как обеспечить случайность? Надо иметь источник энтропии и чтобы исходные данные имели уникальный ключ. Тогда надо в статью добавить фразу, что это работает только для исходных данных, где есть такой ключ - в примере это код справочника "Номенклатура". Для регистра сведений это будет уже набор измерений ну и т.д.
34. Роман С (Dach) 06.04.15 14:42
(32) РАЗНОСТЬДАТ(ДАТАВРЕМЯ(1, 1, 1, 0, 0, 0), &ТекущаяДата, СЕКУНДА) : не работает, та же ошибка
35. Сергей (ildarovich) 06.04.15 15:01
(34) Dach, в общем, понял в чем дело. Разность дат не может быть больше, чем помещается в 32 бита, то есть 2^32 = 4294967296, даже меньше 2^31 = 2147483648. Тогда получится 18.03.1947 от сегодняшней даты.
Поправил запрос. Будет еще лет шестьдесят работать.
36. Максим Зудин (kasper076) 06.04.15 15:37
Подтверждаю (22)
Microsoft SQL Server Native Client 10.0: Функция datediff вызвала переполнение. Слишком большое количество частей даты, разделяющих два экземпляра даты-времени. Попробуйте использовать функцию datediff с частью даты меньшей точности.
HRESULT=80040E57, SQLSrvr: SQLSTATE=22003, state=1, Severity=10, native=535, line=1

1С:Предприятие 8.3 (8.3.5.1517) SQL 2008R2
37. Сергей (ildarovich) 06.04.15 16:17
(36) kasper076, поправил теперь в обоих запросах. Чтобы запрос работал в SQL-базе. Нужно было в функции
РАЗНОСТЬДАТ(ДАТАВРЕМЯ(1, 1, 1), &ТекущаяДата, СЕКУНДА)
исправить первый аргумент так
РАЗНОСТЬДАТ(ДАТАВРЕМЯ(2015, 1, 1), &ТекущаяДата, СЕКУНДА)
Тогда разность дат, выраженная в числе секунд будет укладываться в величину, представимую четырехбайтным целым со знаком и запрос будет работать и в SQL-варианте.
На самом деле именно разность дат вовсе и не обязательно использовать. В другом варианте того же запроса вместо всего выражения
РАЗНОСТЬДАТ(ДАТАВРЕМЯ(2015, 1, 1), &ТекущаяДата, СЕКУНДА) * 129082719
можно ввести в запрос ОДНО случайное число, полученное объектом ГСЧ.
38. Mz Zn (yarainboy) 16.04.15 12:38
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа