0. Foxx 100 06.12.11 23:03 Сейчас в теме

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

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

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

(т.е. +45%)

Перейти к публикации

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

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

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

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


Самое первое что приходит в голову - обходить структуру и засовывать ее в список значений, затем его сортировать и затем уже получать представление.
Но может быть кто то нашел более эффективный способ?
4. Foxx 100 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. Поручик 4316 07.12.11 12:11 Сейчас в теме
(5) COMОбъект'ы и ВК не всегда подходят.
7. speshuric 1118 14.12.11 08:01 Сейчас в теме
(0) Блочный вариант и в комментах к той статье был.
(5) CAPICOM нужно ставить отдельно, есть проблемы с использованием в 64-битной среде, не предполагается дальнейшая поддержка от MS, не работает на линуксовом сервере, не работает в веб-клиенте.
8. sergch2005 14.12.11 08:57 Сейчас в теме
Хорошая обработка. Давно искал.
9. Foxx 100 14.12.11 11:43 Сейчас в теме
speshuric пишет:

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

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

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

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

Про скорость. Также должен принести извинения, порывшись в исходниках обнаружил, что для "функции из 31 коммента" я делал замеры без предварительной записи ее кода в одну строку. В таком виде она будет быстрее оригинальной. Но тем не менее, медленнее моего варианта). Сделал только-что замер на компьютере, который сейчас под рукой (6400 символов):
Оригинальная функция: 1806 хэшей в минуту
"функция из 31 коммента" (с записью кода в одну строку): 2316
моя функция: 2424
12. speshuric 1118 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 100 14.12.11 17:00 Сейчас в теме
Да, ваш вариант быстрее на 1,5-2 процента в "боевом режиме" (как 8.1, так и 8.2)
Мда, негусто. Ради такого результата не стоило и отдельную статью публиковать, достаточно было в предыдущей публикации в комментариях отписаться. (ух, как я прошляпил на первоначальных замерах у себя...) Ну да ладно, удалять уже не буду, хоть несколько процентов, а все равно прирост).
14. speshuric 1118 14.12.11 19:48 Сейчас в теме
(13) Да ладно, всё равно же быстрее. Кстати, надо будет на досуге построить графики зависимости от длины строк в итерациях в секунду и мегабайтах в секунду. Хотя бы чтоб знать предел возможностей интерпретатора.
18. serg_gres 139 06.12.12 14:41 Сейчас в теме
(13) не хочу углубляться в теорию.
Подскажите: насколько устойчив используемый Вами метод хэширования к коллизиям?
Есть задача хэшировать документы (все реквизиты будут преобразовываться в строку), и отслеживать их изменения.
Используемый алгоритм подойдет?
19. Foxx 100 14.12.12 03:51 Сейчас в теме
(18) serg_gres, гарантий полного отсутствия коллизий вам конечно никто не даст)
Для вашей задачи, я думаю, алгоритм вполне подойдет.

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

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

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

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

У нас кодируется UTF-8 текст (отмечено светло-голубым цветом). Как наглядно видно, функция Бернштайна вполне вписывается в "идеал" (диапазон 0.95-1.05) для всех исходников, кроме числовых.
17. gosizo 33 23.10.12 15:25 Сейчас в теме
Оставьте свое сообщение
Новые вопросы с вознаграждением
Автор темы объявил вознаграждение за найденный ответ, его получит тот, кто первый поможет автору.

Вакансии

Программист 1C
Москва
зарплата от 100 000 руб. до 150 000 руб.
Полный день


Руководитель проектов 1С
Санкт-Петербург
Полный день

Бизнес-архитектор 1С, ведущий консультант
Санкт-Петербург
Полный день

Программист 1С
Москва
зарплата от 120 000 руб. до 150 000 руб.
Полный день