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

07.12.11

Разработка - Универсальные функции

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

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

(т.е. +45%)

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Пример
.epf 7,70Kb
52
52 Скачать (1 SM) Купить за 1 850 руб.
Пример для 7.7
.ert 59,00Kb
6
6 Скачать (1 SM) Купить за 1 850 руб.

В оригинальной функции исходная строка разбивается на блоки (по 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 не проводились замеры, чтобы определить оптимальный размер блока)

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

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

См. также

Универсальные функции Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

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

21.05.2024    17021    dimanich70    81    

135

Универсальные функции Программист Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

Задача: вставить картинку из буфера обмена на форму средствами платформы 1С.

1 стартмани

18.03.2024    3823    3    John_d    11    

57

Универсальные функции Программист Стажер Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Пришлось помучиться с GUID-ами немного, решил поделиться опытом, мало ли кому пригодится.

12.02.2024    14123    atdonya    23    

56

Универсальные функции Программист Платформа 1С v8.3 Бесплатно (free)

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

30.11.2023    5226    ke.92@mail.ru    16    

65

Мессенджеры и боты Нейросети Программист Бесплатно (free)

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

29.08.2023    8055    comol    47    

47

WEB-интеграция Универсальные функции Механизмы платформы 1С Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

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

28.08.2023    13551    YA_418728146    7    

165

Пакетная печать Печатные формы Адаптация типовых решений Универсальные функции Платформа 1С v8.3 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Россия Абонемент ($m)

Расширение для программ 1С:Управление торговлей, 1С:Комплексная автоматизация, 1С:ERP, которое позволяет распечатывать печатные формы для непроведенных документов. Можно настроить, каким пользователям, какие конкретные формы документов разрешено печатать без проведения документа.

2 стартмани

22.08.2023    3294    52    progmaster    8    

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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