gifts2017

Простая и быстрая хэш функция (hash) средствами 1С (оптимизированный вариант)

Опубликовал Тарас Гулеватый (Foxx) в раздел Программирование - Практика программирования

Данная функция основана на разработке "Простая и быстрая хэш функция (hash) средствами 1С" http://infostart.ru/public/70030/
Главное отличие от оригинальной функции - оптимизация по быстродействию для больших объемов исходных данных. По результатам замеров количества генерируемых хэшей в минуту на строке длиной 1222 символа:

Оригинальная функция: 14880
Оптимизированная функция: 21528

(т.е. +45%)

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

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

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

Замер производительности

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

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

Из прочих оптимизаций по мелочи - используется длина блока 11 символов (вместо 10), и добавлена возможность принимать в качестве исходных данных двомичные данные.

Функция глХэш(ИсходныеДанные, Хэш=5381, М=33, Разрядность=18446744073709551616)

   
// приведем к строке
   
Если ТипЗнч(ИсходныеДанные) = Тип("ДвоичныеДанные") Тогда
       
СтрокаДляКодирования = Base64Строка(ИсходныеДанные);
    Иначе
       
СтрокаДляКодирования = Строка(ИсходныеДанные);
    КонецЕсли;

   
ДлинаБлока = 11;
   
НачПозиция = 1;
   
ДлинаСтроки = СтрДлина(СтрокаДляКодирования);

    Пока
НачПозиция <= ДлинаСтроки Цикл
       
СтрокаБлока = Сред(СтрокаДляКодирования, НачПозиция, ДлинаБлока);
       
ДлинаПодстроки = СтрДлина(СтрокаБлока);
        Если
ДлинаПодстроки = ДлинаБлока Тогда
           
Хэш = ((((((((((( Хэш*М + КодСимвола(СтрокаБлока, 1))*М + КодСимвола(СтрокаБлока, 2))*М
                + КодСимвола(СтрокаБлока, 3))*М + КодСимвола(СтрокаБлока, 4))*М + КодСимвола(СтрокаБлока, 5))*М
                + КодСимвола(СтрокаБлока, 6))*М + КодСимвола(СтрокаБлока, 7))*М + КодСимвола(СтрокаБлока, 8))*М
                + КодСимвола(СтрокаБлока, 9))*М + КодСимвола(СтрокаБлока, 10))*М + КодСимвола(СтрокаБлока, 11))
        Иначе
            Для
к = 1 По ДлинаПодстроки Цикл
               
Хэш = М * Хэш + КодСимвола(СтрокаБлока, к)
            КонецЦикла
        КонецЕсли;
       
Хэш = Хэш % Разрядность;
       
НачПозиция = НачПозиция + ДлинаБлока
    КонецЦикла;

    Возврат
Хэш;

КонецФункции

Код для 7.7:

Функция глХэш(ИсходныеДанные, Хэш=5381, М=33, Разрядность=18446744073709551616)

   
СтрокаДляКодирования = Строка(ИсходныеДанные);

   
ДлинаБлока = 11;
   
НачПозиция = 1;
   
ДлинаСтроки = СтрДлина(СтрокаДляКодирования);

    Пока
НачПозиция <= ДлинаСтроки Цикл
       
СтрокаБлока = Сред(СтрокаДляКодирования, НачПозиция, ДлинаБлока);
       
ДлинаПодстроки = СтрДлина(СтрокаБлока);
        Если
ДлинаПодстроки = ДлинаБлока Тогда
           
Хэш = ((((((((((( Хэш*М + КодСимв(Сред(СтрокаБлока, 1, 1)))*М + КодСимв(Сред(СтрокаБлока, 2, 1)))*М
                + КодСимв(Сред(СтрокаБлока, 3, 1)))*М + КодСимв(Сред(СтрокаБлока, 4, 1)))*М + КодСимв(Сред(СтрокаБлока, 5, 1)))*М
                + КодСимв(Сред(СтрокаБлока, 6, 1)))*М + КодСимв(Сред(СтрокаБлока, 7, 1)))*М + КодСимв(Сред(СтрокаБлока, 8, 1)))*М
                + КодСимв(Сред(СтрокаБлока, 9, 1)))*М + КодСимв(Сред(СтрокаБлока, 10, 1)))*М + КодСимв(Сред(СтрокаБлока, 11, 1)))
        Иначе
            Для
к = 1 По ДлинаПодстроки Цикл
               
Хэш = М * Хэш + КодСимв(Сред(СтрокаБлока, к, 1))
            КонецЦикла
        КонецЕсли;
       
Хэш = Хэш % Разрядность;
       
НачПозиция = НачПозиция + ДлинаБлока
    КонецЦикла;

    Возврат
Хэш;

КонецФункции

(Для 7.7 не проводились замеры, чтобы определить оптимальный размер блока)

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

Пример использования - см. в прилагаемом файле. Также в данном виде функция использовалась в разработке "База знаний (демо-конфигурация браузера по объектам информационной базы)" http://infostart.ru/public/100636/

Скачать файлы

Наименование Файл Версия Размер
Пример 49
.epf 7,70Kb
06.12.11
49
.epf 7,70Kb Скачать
Пример для 7.7 6
.ert 59,00Kb
07.12.11
6
.ert 59,00Kb Скачать

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Сергей Ожерельев (Поручик) 06.12.11 23:03
(0) Убери её из разделов 1С: Бухгалтерский учет 7.7; 1С: Оперативный учет 7.7; 1С: Расчет 7.7; 1C: OpenConf 7.7.
Что-то не припомню в клюшках таких функций ТипЗнч(), Тип("ДвоичныеДанные"), Base64Строка(). Или я что-то пропустил?
2. Сергей Старых (tormozit) 07.12.11 00:03
Спасибо.

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

Ниже в примере внутреннее представление структур будет различным и хэши этих представлений следовательно тоже.
А = Новый Структура;
А.Вставить("к1");
А.Вставить("к2");
Сообщить(ЗначениеВСтрокуВнутр(А));

А = Новый Структура;
А.Вставить("к2");
А.Вставить("к1");
Сообщить(ЗначениеВСтрокуВнутр(А));
...Показать Скрыть


Самое первое что приходит в голову - обходить структуру и засовывать ее в список значений, затем его сортировать и затем уже получать представление.
Но может быть кто то нашел более эффективный способ?
3. Тарас Гулеватый (Foxx) 07.12.11 01:38
(1) Поручик, да, таких функций в 7.7 нет :)
Я думал, что приведенного кода вполне достаточно для его трансляции на платформу 7.7, ведь менять там почти ничего и не нужно. Но раз пошла такая пляска, добавил код и пример для 7.7.
4. Тарас Гулеватый (Foxx) 07.12.11 01:56
(2) tormozit, боюсь, без выгрузки в промежуточную коллекцию значений не обойтись.
Еще, можно попробовать подобрать хэш-функцию, результат которой будет независим от последовательности исходных данных.
5. Илья Фамилия (Murom) 07.12.11 10:20
Интересная реализация.
Но почему бы не использовать встроенные в Windows CAPI.
HashData = Новый COMОбъект("CAPICOM.HashedData"); 
HashData.Algorithm = 1;  //Secure Hash Algorithm (SHA) that generates a 160-bit message digest.
HashData.Hash(тзСтрока.Наименование);
...Показать Скрыть

Очень удобно тем что можно выбирать разные алгоритмы хешей. Притом "стандартные" и потом можно проверять в других сторонних (не 1с) программах.
6. Сергей Ожерельев (Поручик) 07.12.11 12:11
(5) COMОбъект'ы и ВК не всегда подходят.
7. Alexander Speshilov (speshuric) 14.12.11 08:01
(0) Блочный вариант и в комментах к той статье был.
(5) CAPICOM нужно ставить отдельно, есть проблемы с использованием в 64-битной среде, не предполагается дальнейшая поддержка от MS, не работает на линуксовом сервере, не работает в веб-клиенте.
8. Sergey Cherednichenko (sergch2005) 14.12.11 08:57
Хорошая обработка. Давно искал.
9. Тарас Гулеватый (Foxx) 14.12.11 11:43
speshuric пишет:

Блочный вариант и в комментах к той статье был.

Был. Но он обладает несколькими недостатками - значительно меньшим быстродействием по сравнению с оригинальной функцией (учитывая оптимизации от alexk-is), независимо от объема исходных данных. И самое главное - он реализует другую хэш функцию, т.е. его нельзя использовать как замену оригинальной функции.
10. Alexander Speshilov (speshuric) 14.12.11 14:52
(9) Я говорю про комментарий 31. Только что проверил. Изменив только способ передачи хеша. Передал строку длиной 6400 строк, результат одинаковый, производительность той, что в комментарии немного выше. ЧЯДНТ?
11. Тарас Гулеватый (Foxx) 14.12.11 15:56
(10) Прошу прощения, про другую функцию я немного погорячился.
Правильнее будет выразиться так - упомянутая функция из 31 комментария выдает другой результат, если ее использовать "1 в 1" в том виде, как она приведена в комментарии.

Оригинальная функция (во внешней обработке в демо-примере) и моя функция (со значениями по умолчанию) используют основание 33 и начальное значение хэша 5381 (функция Бернштайна). Функция из 31 поста - использует основание 31 и начальное значение 0 (функция Кернигана и Ритчи). Причем, без возможности изменения нач. значения хэша, т.к. инициализируется в коде самой функции, а не передается в качестве параметра.

Если немного поправить код, то "функцию из 31 коммента" можно, конечно, заставить выдавать тот же самый результат :).

Про скорость. Также должен принести извинения, порывшись в исходниках обнаружил, что для "функции из 31 коммента" я делал замеры без предварительной записи ее кода в одну строку. В таком виде она будет быстрее оригинальной. Но тем не менее, медленнее моего варианта). Сделал только-что замер на компьютере, который сейчас под рукой (6400 символов):
Оригинальная функция: 1806 хэшей в минуту
"функция из 31 коммента" (с записью кода в одну строку): 2316
моя функция: 2424
12. Alexander Speshilov (speshuric) 14.12.11 16:36
Обработку не скачивал, написал на коленках простой код.
Код:
Функция глХэш(ИсходныеДанные, Хэш=5381, М=33, Разрядность=18446744073709551616)

    // приведем к строке
    Если ТипЗнч(ИсходныеДанные) = Тип("ДвоичныеДанные") Тогда
        СтрокаДляКодирования = Base64Строка(ИсходныеДанные);
    Иначе
        СтрокаДляКодирования = Строка(ИсходныеДанные);
    КонецЕсли;

    ДлинаБлока = 11;
    НачПозиция = 1;
    ДлинаСтроки = СтрДлина(СтрокаДляКодирования);

    Пока НачПозиция <= ДлинаСтроки Цикл
        СтрокаБлока = Сред(СтрокаДляКодирования, НачПозиция, ДлинаБлока);
        ДлинаПодстроки = СтрДлина(СтрокаБлока);
        Если ДлинаПодстроки = ДлинаБлока Тогда
            Хэш = ((((((((((( Хэш*М + КодСимвола(СтрокаБлока, 1))*М + КодСимвола(СтрокаБлока, 2))*М
                + КодСимвола(СтрокаБлока, 3))*М + КодСимвола(СтрокаБлока, 4))*М + КодСимвола(СтрокаБлока, 5))*М
                + КодСимвола(СтрокаБлока, 6))*М + КодСимвола(СтрокаБлока, 7))*М + КодСимвола(СтрокаБлока, 8))*М
                + КодСимвола(СтрокаБлока, 9))*М + КодСимвола(СтрокаБлока, 10))*М + КодСимвола(СтрокаБлока, 11))
        Иначе
            Для к = 1 По ДлинаПодстроки Цикл
                Хэш = М * Хэш + КодСимвола(СтрокаБлока, к)
            КонецЦикла
        КонецЕсли;
        Хэш = Хэш % Разрядность;
        НачПозиция = НачПозиция + ДлинаБлока
    КонецЦикла;

    Возврат Хэш;

КонецФункции

Функция ХэшБыстрый2(СтрокаХэш, Хэш=5381, Знач Основание = 33, Знач TABLE_SIZE = 18446744073709551616) Экспорт
   ДлинаСтроки=СтрДлина(СтрокаХэш);
   КоличествоПовторенийВРазвёртке = 60;Основание2=Основание*Основание;Основание3=Основание2*Основание;Основание4=Основание3*Основание;
   Для Сч = 0 по Цел(ДлинаСтроки/КоличествоПовторенийВРазвёртке)-1 Цикл
      //1С неэффективно работает с длинными строками, поэтому сначала откусываем кусочек
      //складывать начинаем с меньших чисел, т.к. арифметика больших затратнее
      ТекСтрока = Сред(СтрокаХэш, Сч*КоличествоПовторенийВРазвёртке+1, КоличествоПовторенийВРазвёртке);
      Хэш = КодСимвола(ТекСтрока, 4) + Основание * КодСимвола(ТекСтрока, 3) + Основание2 * КодСимвола(ТекСтрока, 2) + Основание3 * КодСимвола(ТекСтрока) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 8) + Основание * КодСимвола(ТекСтрока, 7) + Основание2 * КодСимвола(ТекСтрока, 6) + Основание3 * КодСимвола(ТекСтрока, 5) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 12) + Основание * КодСимвола(ТекСтрока, 11) + Основание2 * КодСимвола(ТекСтрока, 10) + Основание3 * КодСимвола(ТекСтрока, 9) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 16) + Основание * КодСимвола(ТекСтрока, 15) + Основание2 * КодСимвола(ТекСтрока, 14) + Основание3 * КодСимвола(ТекСтрока, 13) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 20) + Основание * КодСимвола(ТекСтрока, 19) + Основание2 * КодСимвола(ТекСтрока, 18) + Основание3 * КодСимвола(ТекСтрока, 17) + Основание4 * (Хэш % TABLE_SIZE);
      Хэш = КодСимвола(ТекСтрока, 24) + Основание * КодСимвола(ТекСтрока, 23) + Основание2 * КодСимвола(ТекСтрока, 22) + Основание3 * КодСимвола(ТекСтрока, 21) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 28) + Основание * КодСимвола(ТекСтрока, 27) + Основание2 * КодСимвола(ТекСтрока, 26) + Основание3 * КодСимвола(ТекСтрока, 25) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 32) + Основание * КодСимвола(ТекСтрока, 31) + Основание2 * КодСимвола(ТекСтрока, 30) + Основание3 * КодСимвола(ТекСтрока, 29) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 36) + Основание * КодСимвола(ТекСтрока, 35) + Основание2 * КодСимвола(ТекСтрока, 34) + Основание3 * КодСимвола(ТекСтрока, 33) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 40) + Основание * КодСимвола(ТекСтрока, 39) + Основание2 * КодСимвола(ТекСтрока, 38) + Основание3 * КодСимвола(ТекСтрока, 37) + Основание4 * (Хэш % TABLE_SIZE);
      Хэш = КодСимвола(ТекСтрока, 44) + Основание * КодСимвола(ТекСтрока, 43) + Основание2 * КодСимвола(ТекСтрока, 42) + Основание3 * КодСимвола(ТекСтрока, 41) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 48) + Основание * КодСимвола(ТекСтрока, 47) + Основание2 * КодСимвола(ТекСтрока, 46) + Основание3 * КодСимвола(ТекСтрока, 45) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 52) + Основание * КодСимвола(ТекСтрока, 51) + Основание2 * КодСимвола(ТекСтрока, 50) + Основание3 * КодСимвола(ТекСтрока, 49) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 56) + Основание * КодСимвола(ТекСтрока, 55) + Основание2 * КодСимвола(ТекСтрока, 54) + Основание3 * КодСимвола(ТекСтрока, 53) + Основание4 * Хэш;
      Хэш = КодСимвола(ТекСтрока, 60) + Основание * КодСимвола(ТекСтрока, 59) + Основание2 * КодСимвола(ТекСтрока, 58) + Основание3 * КодСимвола(ТекСтрока, 57) + Основание4 * (Хэш % TABLE_SIZE);
   КонецЦикла;
   
   Для Сч = ДлинаСтроки - ДлинаСтроки%КоличествоПовторенийВРазвёртке + 1 По ДлинаСтроки Цикл
      Хэш = Основание * Хэш + КодСимвола(СтрокаХэш, Сч);
   КонецЦикла;      
   
   Возврат Хэш%TABLE_SIZE;
   
КонецФункции

Процедура Тест()
	
	// шаблон строки
	Строка = "01234567890123456789012345678901234567890123456789012345678­90123456789012345678901234567890123456789";
	
	// размножаем шаблон
	Строка = Строка + Строка;Строка = Строка + Строка;
	Строка = Строка + Строка;Строка = Строка + Строка;
	Строка = Строка + Строка;Строка = Строка + Строка;
	//Строка = Строка + Строка;Строка = Строка + Строка; // можно и добавить - разница всё равно есть
	//Строка = Строка + Строка;Строка = Строка + Строка; 
	//Строка = Строка + Строка;Строка = Строка + Строка;
	
	СекундНаТест = 60;
	
	// выравниваемся "по секундам"
	ТекДата = ТекущаяДата();
	Пока ТекДата = ТекущаяДата() Цикл КонецЦикла;
	
	Сообщить(ТекущаяДата()); Сч = 0;
	ЖдёмДо = ТекущаяДата() + СекундНаТест;
	Пока ЖдёмДо > ТекущаяДата() Цикл
		Хэш = глХэш(Строка);  //Единственное отличие блоков
		Сч = Сч + 1;
	КонецЦикла;
	Сообщить("Хэш: " + Строка(Хэш) + Символы.Таб + "Повторов: " + Строка(Сч));
	Сообщить(ТекущаяДата());
	
	// выравниваемся "по секундам"
	ТекДата = ТекущаяДата();
	Пока ТекДата = ТекущаяДата() Цикл КонецЦикла;
	
	Сообщить(ТекущаяДата()); Сч = 0;
	ЖдёмДо = ТекущаяДата() + СекундНаТест;
	Пока ЖдёмДо > ТекущаяДата() Цикл
		Хэш = ХэшБыстрый2(Строка); //Единственное отличие блоков
		Сч = Сч + 1;
	КонецЦикла;
	Сообщить("Хэш: " + Строка(Хэш) + Символы.Таб + "Повторов: " + Строка(Сч));
	Сообщить(ТекущаяДата());
	
	Сообщить(СтрДлина(Строка));
	
КонецПроцедуры
...Показать Скрыть

Результаты (дату и час я вырезал):
В режиме отладки (8.1.15): 

<удалилдатуичас>17:37
Хэш: 6 895 681 624 527 472 005	Повторов: 2 676
<удалилдатуичас>18:37
<удалилдатуичас>18:38
Хэш: 6 895 681 624 527 472 005	Повторов: 3 442
<удалилдатуичас>19:38
6 400

Без режима отладки (8.1.15):

<удалилдатуичас>20:16
Хэш: 6 895 681 624 527 472 005	Повторов: 4 428
<удалилдатуичас>21:16
<удалилдатуичас>21:17
Хэш: 6 895 681 624 527 472 005	Повторов: 4 360
<удалилдатуичас>22:17
6 400

В режиме отладки (8.2.13): 

<удалилдатуичас>24:06
Хэш: 6 895 681 624 527 472 005	Повторов: 2 140
<удалилдатуичас>25:06
<удалилдатуичас>25:07
Хэш: 6 895 681 624 527 472 005	Повторов: 2 521
<удалилдатуичас>26:07
6 400

Без режима отладки (8.2.13):

<удалилдатуичас>26:41
Хэш: 6 895 681 624 527 472 005	Повторов: 4 690
<удалилдатуичас>27:41
14.12.2011 16:27:42
Хэш: 6 895 681 624 527 472 005	Повторов: 4 440
<удалилдатуичас>28:42
6 400
...Показать Скрыть


Выводы:
  • Да, ваш вариант быстрее на 1,5-2 процента в "боевом режиме" (как 8.1, так и 8.2)
  • Другой вариант почему-то заметно шустрее в режиме отладки. Но это искажённый показатель (почему у меня и получился другой результат)
  • 8.2 чутка быстрее в боевом и чутка медленее в отладке чем 8.1 на этой же задаче
13. Тарас Гулеватый (Foxx) 14.12.11 17:00
Да, ваш вариант быстрее на 1,5-2 процента в "боевом режиме" (как 8.1, так и 8.2)
Мда, негусто. Ради такого результата не стоило и отдельную статью публиковать, достаточно было в предыдущей публикации в комментариях отписаться. (ух, как я прошляпил на первоначальных замерах у себя...) Ну да ладно, удалять уже не буду, хоть несколько процентов, а все равно прирост).
14. Alexander Speshilov (speshuric) 14.12.11 19:48
(13) Да ладно, всё равно же быстрее. Кстати, надо будет на досуге построить графики зависимости от длины строк в итерациях в секунду и мегабайтах в секунду. Хотя бы чтоб знать предел возможностей интерпретатора.
17. Дмитрий (gosizo) 23.10.12 15:25
18. Сергей Начина (serg_gres) 06.12.12 14:41
(13) Foxx, не хочу углубляться в теорию.
Подскажите: насколько устойчив используемый Вами метод хэширования к коллизиям?
Есть задача хэшировать документы (все реквизиты будут преобразовываться в строку), и отслеживать их изменения.
Используемый алгоритм подойдет?
19. Тарас Гулеватый (Foxx) 14.12.12 03:51
(18) serg_gres, гарантий полного отсутствия коллизий вам конечно никто не даст)
Для вашей задачи, я думаю, алгоритм вполне подойдет.

Чтобы не быть совсем уж голословным:

К-во коллизий для разных хэш функций в зависимости от разрядности таблицы:

У меня используется функция Бернштайна (см. серую кривую) и 64-разрядный ключ (в графике ограничились 28-ю разрядами :))

Оценка качества разных функций по формуле Red Dragon Book

У нас кодируется UTF-8 текст (отмечено светло-голубым цветом). Как наглядно видно, функция Бернштайна вполне вписывается в "идеал" (диапазон 0.95-1.05) для всех исходников, кроме числовых.