Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения - страница 10
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
О хеш-функциях
Из предыдущих примеров становится ясно, что основную нагрузку берет на себя хеш-функция. Хеш функцию можно сделать максимально быстрой, но скорее всего в этом случае она будет сильно подвержена коллизиям. И наоборот, хеш-функцию можно сделать максимально устойчивой к появлению коллизий, но ее вычислительная сложность будет неадекватна к выполняемой задачи. Разберем два крайних примера. Пример 1, максимально быстрая хеш-функция:
Всегда будет возвращать одно и тоже число. Если наш словарь будет хранить только одно слово, то ее работы будет достаточно, т.к. это слово будет находится по индексу 0. Однако если слов будет 10, тогда все десять слов будут находится в нулевом индексе (не забываем, что у нас массив массивов).
Для второго примера обратимся к обратимому шифрованию, например на основе сети Фейстеля с количеством раундов N. Это не хеш-функция, и она не подвержена коллизиям совсем. Т.е. для двух разных строк мы получим гарантированно разные числа. Длина полученных чисел будет равна длине строки. Следовательно для строки длиной 1000 символов мы получим массив uchar размерностью 1000. Если нам нужно хранить эту строку в словаре размером 3 элемента, то согласитесь странно вычислять такой сложный код, для поиска слова всего из трех элементов.
Следовательно, всегда нужно искать золотую середину (как это было верно подмечено fxsaber'ом): нам необходима такая функция, которая быстро вычисляла бы хеш и как правило не давала бы коллизий. Давайте прикинем вероятность появления коллизий у нашей предыдущей хеш-функции:
В алфавите 26 символов. Будем считать, что количество слов начинающихся на символ 'a' равна количеству слов начинающихся на любой другой символ. Тогда если в нашем словаре 988 слов, то 38 из них будут начинаться на букву a, 38 - на букву b, 38 - на букву c, ... 38 - на букву w и 38 на букву - z. Вероятность возникновения коллизии в каждом случае будет 1/26 или 3.8461%. Если у нас 988 слов, тогда получим 988*3.8461 = 37.999 слов на каждый индекс.
Понятно, что чем больше слов на одну и туже букву, тем сложнее найти конкретное слово. В нашем случае потребуется не только вычислить индекс первой буквы, но и перебрать все слова, которые также начинаются на эту же букву, что бы уже сравнить слова точно. Что бы этого не было, можем усложнить хеш-функцию:
Т.е. мы берем уже два первых символа одного слова. Тогда возможных комбинаций будет не 26, а 26^2 = 676. Замечу, что сложность второго варианта вычисления хеш функции возросла линейно, грубо говоря в два раза, в том время как ее стойкость к коллизиям возросла нелинейно, в квадрате.
Для второго варианта, в среднем будет одна коллизия на каждые 676 слов. В нашем случае, для 988 слов будет 988/676 = 1.4615 коллизии на каждый индекс. Т.е. каждый индекс будет содержать в среднем либо одно слово, либо 2 слова. Т.е. в среднем перебора не будет вовсе (одно сравнение), либо он будет очень коротким (два сравнения).
Если отношение размер словаря к кобминациям хеш-функции стремиться к 1.0000000, то в среднем, никакого перебора не понадобиться, т.к. каждый элемент будет располагаться по своему индексу в одиночестве. Если хеш-функция будет выдавать очень большой диапазон значений, то отношение размер словаря к возможным комибинациям хеш функции всегда будет даже меньше 1.0. Например если хеш-функция будет выдвать 2^32 комбинаций тогда для любого размера N меньше 2^32 будет выполняться отношение N/2^32 < 1.0. Если N очень мало, то мы просто нормируем число полученное хеш-функцией, таким образом, что бы оно всегда находилось в пределе N:
int index = GetHashCode(word)%ArraySize(m_array);
Если хеш-функция выдает результаты равномерно, то в среднем, мы будем получать отношение 1.000. т.е. в одном индексе массива будет располагаться только одно слово. Таким образом можно сказать, что словарь это частный случай массива, в котором вместо индекса указывается ключ.
Размер массива можно легко менять под размер словаря.
Бесконечные варианты в расчет не брал.
В том то и дело, что размер словаря часто не известен. Простой пример, допустим, у нас торгует советник. Он отслеживает совершенные сделки. После появления сделки в истории, требуется связать эту сделку допустим с меджиком эксперта. Для этого логично использовать словарь. Где в качестве ключа (уникального идентификатора) используется номер сделки, а в качестве значения - магический номер эксперта. Проблема в том, что при запуске советника ни как нельзя определить заранее будут ли у нас 100 сделок, 1000 или вообще ни одной. Сколько памяти за ранее не выделяй, ее все равно будет либо мало, либо слишком много.
В том то и дело, что размер словаря часто не известен. Простой пример, допустим, у нас торгует советник. Он отслеживает совершенные сделки. После появления сделки в истории, требуется связать эту сделку допустим с меджиком эксперта. Для этого логично использовать словарь. Где в качестве ключа (уникального идентификатора) используется номер сделки, а в качестве значения - магический номер эксперта. Проблема в том, что при запуске советника ни как нельзя определить заранее будут ли у нас 100 сделок, 1000 или вообще ни одной. Сколько памяти за ранее не выделяй, ее все равно будет либо мало, либо слишком много.
Ну так понятно, что задачи разные бывают.
Я решал задачу в которой нужно было создать удобный словарь для одного человеческого языка. Размер моего массива не точен, но в чем проблема подогнать его под количество слов определенного языка? Он там легко поместится.
Например русский язык. Допустим содержит 10 000 основных слов. Все эти слова можно прекрасно поместить в моем массиве.
Первое измерение - 66 букв (малые и большие), второе измерение - количество букв в слове (до 25 например), третье измерение - совпадения по первой букве и количеству букв - 50.
Весь язык поместиться.
//----------------------------
Изначально, я решал именно эту задачу. Вы сейчас подменяете исходную задачу другой и говорите, что решение не годится.
Сколько памяти за ранее не выделяй, ее все равно будет либо мало, либо слишком много.
Верно.
Также верно как и то, что небывает универсального решения для всех задач.
Верно.
Также верно как и то, что небывает универсального решения для всех задач.
Совершенно бесспорно.
Потише товарищ. От ошибок никто не застрахован, даже ты. Поэтому будь добр, указывай на ошибки других в более мягком тоне. Сейчас исправлю.
А правильный вариант останется в секрете???
Правильного варианта хеш-таблиц и хешей в принципе быть не может - все зависит от конкретных целей и условий применения.
Это как приготовление бутерброда. Может кто-то не есть майонез или кетчуп, или он веган....
Но намазывать кетчуп на стол и ложить на него хлеб - тут как бы понятно, что это не то....
Основы по теме для ленивых:
https://www.slideshare.net/mkurnosov/6-32402313
В реальности все намного сложнее и обсуждается в соответсвующей литературе или на хороших курсах "алгоритмы и структуры данных".
Короче, хеш-функция должна работать первое: быстро, второе - нет надобности придумывать что-то совсем сложное, т.к. появление одних и тех же значений нормально разруливается внутри словаря прямым перебором. Главное, что бы не было слишком частых коллизий вот и все. В Generic за хеш функции базовых типов отвечает набор функций в файле HashFunction.mqh. Что бы убедиться, что там все просто, посмотрим как он устроен:
Целочисленные типы либо возвращаются как есть, либо для коротких целочисленных типов используется не замысловатые битовые операции преобразования. Для типов не умещающихся в 32 разряда используется исключающее или с последующим объединением правой и левой части. Для строк рассчитывается тоже не замысловатый хеш через прямой перебор. У вещественных чисел с помощью union берется битовое представление, и уже оно используется в качестве хеша.
Алгоритмы типа словарей условно делятся на две части:
Что такое CHashSet? Это коллекция (массив по своей сути) где каждый элемент уникален. Например в такой коллекции могут располагаться числа 2,5,1,7,10,15,1024. Но двух одинаковых чисел быть не может. Также в нем могут располагаться строки, вещественные числа и даже пользовательские сложные типы (об этом позже). Но для любого типа правило одно - другого такого же в словаре быть не может.
Что такое CHashMap? Это коллекция (тоже массив по своей сути), где каждым элементом является сложный тип ключ-значение:
Он устроен почти также как и CHashMap, но позволяет установить соответствие между двумя множествами так, что элемент множества 1 соответствует элементу множества 2. Это очень удобная штука, позволяющая писать очень эффективные алгоритмы запроса со среднем временем выполнения O(1).
Позже на примерах разберем построение какого-нибудь соответствия.
Интересно, что любой словарь типа ключ - значение естественны образом устанавливает такое не тривиальное отношение как один ко многим. Например, у нас имеется куча исторических ордеров, и куча сделок, которые были выполнены на их основе. Каждой сделки соответствует только один ордер, но одному ордеру может соответствовать несколько сделок. Словарь такого отношения может хранить в качестве ключа номер сделки, а в качестве значения, номер ордера, который послужил для ее открытия.