Здравствуйте, MT-Wizard, Вы писали:
MW>не согласен с настолько жестоким ударом по ничего не подозревающим программистам
Каким ещё «жестоким ударом»? Что хэш-функция перемешивает биты? Как раз наоборот, Принцип Наименьшего Удивления нарушается в случае g++, где для каких-то избранных типов хэш-функция вдруг перестаёт перемешивать биты а возвращает аргумент как есть, просто потому что у него размер такой же, как у хэш-значения. А для чего ещё у них есть такие внезапные оптимизации? Для uint8_t тоже? Для uint128_t просто младшие биты возьмёт?
У стандартных алгоритмов, использующих хэширование, должны быть перегрузки, принимающие хэш-функцию. И если достаточно «тривиальной» хэш-функции — то её тривиально и самому реализовать и явно передать. А по умолчанию пусть будет «рандомизированная» функция.
Если кто-то, как и я, наивно полагает, что std::hash<size_t>()(100) вернет 100, то разработчики стандартной библиотеки С++ в Майкрософт с ним не согласны и считают хеш так:
inline size_t _Hash_seq(const unsigned char *_First, size_t _Count)
{ // FNV-1a hash function for bytes in [_First, _First + _Count)#if defined(_WIN64)
static_assert(sizeof(size_t) == 8, "This code is for 64-bit size_t.");
const size_t _FNV_offset_basis = 14695981039346656037ULL;
const size_t _FNV_prime = 1099511628211ULL;
#else/* defined(_WIN64) */
static_assert(sizeof(size_t) == 4, "This code is for 32-bit size_t.");
const size_t _FNV_offset_basis = 2166136261U;
const size_t _FNV_prime = 16777619U;
#endif/* defined(_WIN64) */
size_t _Val = _FNV_offset_basis;
for (size_t _Next = 0; _Next < _Count; ++_Next)
{ // fold in another byte
_Val ^= (size_t)_First[_Next];
_Val *= _FNV_prime;
}
return (_Val);
}
template<class _Kty>
struct _Bitwise_hash
{ // hash functor for plain old datatypedef _Kty argument_type;
typedef size_t result_type;
size_t operator()(const _Kty& _Keyval) const
{ // hash _Keyval to size_t value by pseudorandomizing transformreturn (_Hash_seq((const unsigned char *)&_Keyval, sizeof (_Kty)));
}
};
template<>
struct hash<long long>
: public _Bitwise_hash<long long>
{ // hash functor for long long
};
Разработчики g++ лишены такой фантазии и тупо делают следующее:
MTD>>>Выбор опорной точки не поможет.
Q>>Как это не поможет?
MTD>Да вот так. На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.
Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массивы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.
MS в этом месте споткнулась (правда в .NET'е) https://github.com/dotnet/corefx/issues/24110
Здравствуйте, Qbit86, Вы писали:
Q>Каким ещё «жестоким ударом»? Что хэш-функция перемешивает биты? Как раз наоборот, Принцип Наименьшего Удивления нарушается в случае g++, где для каких-то избранных типов хэш-функция вдруг перестаёт перемешивать биты а возвращает аргумент как есть, просто потому что у него размер такой же, как у хэш-значения.
Возвращает она аргумент не потому, что он такого же размера, а потому, что лучшей хеш-функции для целого, чем вернуть само значение не придумать.
Здравствуйте, Qbit86, Вы писали:
Q>Да: «The unordered associative containers defined in 26.5 use specializations of the class template hash (23.14.1) as the default hash function.» 23.14.15
Тут написано, что неупорядоченные ассоциативные контейнеры используют специализации шаблонного класса hash как хеш-функцию по умолчанию. Здесь не сказано, что нельзя использовать этот класс просто для получения хеша. Тебе правда понадобился перевод, сам не понял?
Q>Зачем ты вообще начал под***ывать Быстрой Сортировкой, если твои познания в этой области столь фрагментарны? Ещё и отсылает почитать, смотри на него.
Ух ты как бомбануло — это хорошо На самом деле ты сам виноват — сначала сморозил про использование хеша для вычисления контрольной суммы, потом назвал детскими алгоритмы зависимые от входных данных, то есть чуть более чем дофига широко используемых. Кто тебя за язык тянул в борьбе со мной? А самое главное, ну не понравилось тебе мое мнение, что так взъелся-то?
Здравствуйте, Qbit86, Вы писали:
Q>Можешь задать этот вопрос непосредственно STL'ю (Stephan T. Lavavej).
Я этот вопрос ему непосредственно задал. Ответом было "намного важнее не допустить вырожденного (O[n]) поведения чем преследовать более частое оптимальное поведение." Т.е. при плохом наборе входных значений текущая хэш-функция всё равно прекрасно перемешает биты и распихает числа по разным бакетам, в то время как identity с радостью всё сложит в один. Я немного поспорил, потому что не согласен с настолько жестоким ударом по ничего не подозревающим программистам, но Степан уверен что так лучше, потому баг в конце концов был закрыт как "by design"
Вроде как есть для этого оправдание: в MSVC используют power-of-2 для числа бакетов, а в остальных стлях — prime number. Получается что при вычислении индекса MSVC делает битовое и, и оставшиеся биты у хэща используются те что были. В гцц/кланге берётся остаток от деления на простое число, который сам по себе достаточно сильно меняет число, но заметно тяжелее как операция. Так identity hash работает отлично для гцц/кланга, но опасен в MSVC.
Выбор степеней двойки как числа бакетов позволяет сконфигурировать контейнер эффективнее если знать входные данные и самому написать хэшфункцию под них, но очень мешает сделать быстро в общем виде. Простые числа работают ровно наоборот.
Здравствуйте, MTD, Вы писали:
Q>>Увы, стандарта у меня нет, так что ответить не смогу. Так и быть, пусть уверенность в твоей правоте продолжает держаться на этой хрупкой надежде, что хоть в стандарте-то наверное и не говорится про назначение функции std::hash. MTD>Ты какой-то смешной
Нет, ты. Со всеми этими «неавторитетными источниками» и прочими «поубеждайте меня тут».
MTD> — для тебя спор
Для меня это не спор. Я пишу комментарии не для тебя, а для аудитории, читающей этот тред. Нет цели переубедить именно тебя; это очевидно бесполезное и неблагодарное занятие.
MTD>не средство узнать что-то новое и выяснить истину
Как это, узнал же новое. Вот, например, раньше я не знал, что в Microsoft и GCC функция std::hash() реализована по-разному. И в свете того, что сказал @MT-Wizard, это вполне имеет рациональное зерно.
MTD>Выбор опорной точки не поможет.
Как это не поможет? Качество выбора опорной точки в принципе определяет скорость алгоритма Быстрой сортировки. А именно: выбор опорной точки влияет на то, насколько сбалансированными будут ветки дерева вызовов. Если одна из веток постоянно будет вырождаться в максимально длинную, то общая скорость деградирует до квадратичной.
Здравствуйте, Jack128, Вы писали:
J>Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массивы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.
Тут ты прав, я выразился не точно. Если брать крайний опорный элемент — деградируем на упорядоченных, если брать средний — на упорядоченных горкой, если брать рандом — ну как повезет. В любом случае алгоритм чувствителен к входным данным.
несколько лет назад мы увидели просадку производительности в хешированных контейнерах, где ключами являются численные типы в VS2015
мы присели и подсунули boost::hash в std::unordered_map, стало гораздо лучше ) в VS2015 делают побайтную свертку, оверкил для интегральных типов. математикой надо!
что там в VS2017 не смотрел еще, но вроде обещали улучшить
Здравствуйте, MTD, Вы писали:
MTD>Если кто-то, как и я, наивно полагает, что std::hash<size_t>()(100) вернет 100...
Я бы по умолчанию так не предполагал бы. Возможно, недостаток рандомизации может негативно отразиться в каких-нибудь алгоритмах и структурах данных. Под рандомизацией я имею в виду то желаемое свойство хэш-функции, что для близких значений аргументов обычно возвращает разбросанные хэш-значения.
MTD>то разработчики стандартной библиотеки С++ в Майкрософт с ним не согласны...
Можешь задать этот вопрос непосредственно STL'ю (Stephan T. Lavavej).
Здравствуйте, Qbit86, Вы писали:
MTD>>лучшей хеш-функции для целого, чем вернуть само значение не придумать.
Q>Ты, похоже, не читал ответы в этом треде?
Читал, а ты без кривляний объяснить можешь чем для целых плоха хеш-функция value? Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий. Переходим к хеш-таблицам, чем плоха хеш-функция k mod M, если M — простое число? Вспомним требования к хеш-функциям:
1. Быстрое вычисление
2. Минимальное число коллизий
Можешь привести за и против по этим требованиям при озвученных в первом посте подходах?
Перечитай комментарий от @MT-Wizard выше. Согласно ему:
в MSVC используют power-of-2 для числа бакетов, а в остальных стлях — prime number. Получается что при вычислении индекса MSVC делает битовое и, и оставшиеся биты у хэща используются те что были. В гцц/кланге берётся остаток от деления на простое число, который сам по себе достаточно сильно меняет число, но заметно тяжелее как операция. Так identity hash работает отлично для гцц/кланга, но опасен в MSVC.
MTD>Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий. Переходим к хеш-таблицам, чем плоха хеш-функция k mod M, если M — простое число?
Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft. Во-вторых, в любом случае (хоть степень, хоть простое), для такой функции есть плохие наборы { k_i } — для которых k_i даёт одинаковый остаток при делении на M. Скажем, арифметические прогрессии с такой разностью, или просто куча разных чисел вида p_i*M + r. Для степеней двойки получить такие наборы в «реальной жизни» кажется более правдоподобным, чем для простого M. Но тем не менее, вполне могут быть наборы из какого-нибудь решета. То есть наивная identity-хэш-функция может сносно работать для случайных наборов данных и вдруг встревать на наборах с нехитрой закономерностью.
Для того и нужна «рандомизация», она страхует от плохих наборов. Не требует «случайности» исходных данных, а сама её «генерирует». Теоретически может быть набор ключей, который породит коллизии и для конкретной рандомизированной функции, но он должен быть сконструирован специально под эту функцию, вероятность получить такое «в быту» минимальная (как у любого другого случайного набора).
Здравствуйте, Qbit86, Вы писали:
Q>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft.
К обсуждению хеш-функции отношения не имеет.
Q>Во-вторых, в любом случае (хоть степень, хоть простое), для такой функции есть плохие наборы { k_i } — для которых k_i даёт одинаковый остаток при делении на M. Скажем, арифметические прогрессии с такой разностью, или просто куча разных чисел вида p_i*M + r. Q>То есть наивная identity-хэш-функция может сносно работать для случайных наборов данных и вдруг встревать на наборах с нехитрой закономерностью.
Мы хеш-функцию обсуждаем или реализацию хеш-таблицы? Как хеш-функция реализация от Майкрософт очевидно сливает и по быстродействию и по коллизиям. По хеш-таблицам же справедливо в обе стороны, алгоритм от Майкрософт тоже может споткнуться на какой-то последовательности.
Q>Теоретически может быть набор ключей, который породит коллизии и для конкретной рандомизированной функции, но он должен быть сконструирован специально под эту функцию, вероятность получить такое «в быту» минимальная (как у любого другого случайного набора).
Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.
Здравствуйте, MTD, Вы писали:
MTD>Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий.
Важны не коллизии функции id, а коллизии при вычислении индекса корзины. Если индекс рассчитывается как k mod M, то коллизии будут при arity(k) > arity(M).
Q>>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft. MTD>К обсуждению хеш-функции отношения не имеет.
На практике имеет. Не принципиально (то есть те же рассуждения применимы к любому M). Но для степени двойки наглядно в битовом представлении: если брать k mod M, то хэш будет зависеть только от младших разрядов ключа, и не зависеть от старших. Это нежелательное поведение хэш-функции. Если M простое, то ещё куда ни шло.
MTD>Мы хеш-функцию обсуждаем или реализацию хеш-таблицы?
Это связанные вещи, так как хэш-функция используется в реализации хэш-таблиц. Об этом и говорит Stephan T. Lavavej, которого процитировал @MT-Wizard. (По-прежнему советую прочитать его комментарий.)
MTD>По хеш-таблицам же справедливо в обе стороны, алгоритм от Майкрософт тоже может споткнуться на какой-то последовательности.
На какой-то специально подобранной последовательности, которая в остальном выглядит как случайная. В то время как нерандомизированная хэш-функция может споткнуться на обычных данных, которые неслучайны, и время от времени бывают biased.
MTD>Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.
При делении на степень двойки (как в хэш-таблицах Microsoft) рандомизировать, вероятно, стоит. При делении на простое число (как в других хэш-таблицах), вероятно, нет.
Здравствуйте, Qbit86, Вы писали:
MTD>>Вообще-то это идеальная хеш-функция (такой термин есть), то есть отображает ключ в хеш без коллизий.
Q>Важны не коллизии функции id, а коллизии при вычислении индекса корзины.
Это смотря, что за задача, возможно мне хеш нужен не для таблицы.
Q>Если индекс рассчитывается как k mod M, то коллизии будут при arity(k) > arity(M).
А если у тебя количество бакетов — степень двойки и номер бакета hash(k) & M коллизий не будет что-ли?
Q>>>Во-первых, если верить @MT-Wizard, M — не простое число, а степень двойки в хэш-таблицах реализации Microsoft. MTD>>К обсуждению хеш-функции отношения не имеет.
Q>На практике имеет. Не принципиально (то есть те же рассуждения применимы к любому M). Но для степени двойки наглядно в битовом представлении: если брать k mod M, то хэш будет зависеть только от младших разрядов ключа, и не зависеть от старших. Это нежелательное поведение хэш-функции. Если M простое, то ещё куда ни шло.
На какой практике? Допустим, мне просто нужен хеш, при хеш = k коллизий гарантировано нет. Что лучше чтобы считать номер бакета деление или наложение маски я не уверен, у тебя есть информация?
Q>Это связанные вещи, так как хэш-функция используется в реализации хэш-таблиц. Об этом и говорит Stephan T. Lavavej, которого процитировал @MT-Wizard. (По-прежнему советую прочитать его комментарий.)
Я комментарий прочел, он меня не убедил, я считаю, что это переусложнение с потерей производительности, в чем профит я пока не понял.
Q>На какой-то специально подобранной последовательности, которая в остальном выглядит как случайная. В то время как нерандомизированная хэш-функция может споткнуться на обычных данных, которые неслучайны, и время от времени бывают biased.
Не убедительно. Почему в одном случае надо специально подбирать, а во втором само получится?
MTD>>Осталось понять стоит ли эта теоретическая вероятность такой реальной просадки быстродействия здесь и сейчас.
Q>При делении на степень двойки (как в хэш-таблицах Microsoft) рандомизировать, вероятно, стоит. При делении на простое число (как в других хэш-таблицах), вероятно, нет.
Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная».
MTD>Допустим, мне просто нужен хеш, при хеш = k коллизий гарантировано нет.
Так и используешь k, не вызывая никаких std::hash.
MTD>Не убедительно. Почему в одном случае надо специально подбирать, а во втором само получится?
Вот скажем ты отфильтровал из базы всех пользователей-женщин, и используешь их идентификаторы как ключи. А админ базы в своё время решил при создании всем пользователям-женщинам назначать id кратный 7, мол, их всё равно в шесть раз меньше в компании; почему нет. У тебя образовалась неявная связь, не случайная. А если у тебя рандомизация, без явной закономерности, то в такие совпадения почти невозможно попасть. Нет правдоподобных сценариев.
MTD>То есть в Майкрософте сделали фигню? Ну ок.
Почему фигню, если вычислять индекс делением на степень двойки быстрее, чем делением на простое число?
Какой авторитетный источник. В стандарте тоже написано, что использовать только с хеш-контейнерами? Почему тогда не сделана внутренней?
Q>Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная».
Да, но лучше того, что сделали в Майкрософт.
MTD>>Допустим, мне просто нужен хеш, при хеш = k коллизий гарантировано нет.
Q>Так и используешь k, не вызывая никаких std::hash.
Мне нужно через std::hash — я обобщенный код пишу.
MTD>>Не убедительно. Почему в одном случае надо специально подбирать, а во втором само получится?
Q>Вот скажем ты отфильтровал из базы всех пользователей-женщин, и используешь их идентификаторы как ключи. А админ базы в своё время решил при создании всем пользователям-женщинам назначать id кратный 7, мол, их всё равно в шесть раз меньше в компании; почему нет. У тебя образовалась неявная связь, не случайная. А если у тебя рандомизация, без явной закономерности, то в такие совпадения почти невозможно попасть. Нет правдоподобных сценариев.
Совсем не убедительно.
MTD>>То есть в Майкрософте сделали фигню? Ну ок.
Q>Почему фигню, если вычислять индекс делением на степень двойки быстрее, чем делением на простое число?
А до этого в цикле 8 раз умножить и 8 раз сделать xor. Хммм, и правда быстрее
Или не только cppreference.com, но и cplusplus.com недостаточно авторитетный источник?
MTD>В стандарте тоже написано, что использовать только с хеш-контейнерами?
Не знаю, у меня нет под рукой стандарта. Я его не покупал.
MTD>Почему тогда не сделана внутренней?
Чтобы можно было специализировать?
Q>>Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная». MTD>Да, но лучше того, что сделали в Майкрософт.
Если используются просто как контрольная сумма, то конечно лучше.
MTD>Мне нужно через std::hash — я обобщенный код пишу.
Значит, тебе не нужно через std::hash, а нужно через свою хэш-функцию со специализацией для size_t.
MTD>Совсем не убедительно.
И тем не менее, случаи biased-данных, что ломают наивные сортировки или хэш-таблицы, периодически встречаются. Не у всех и не у каждого, но не исчезающе редко.
Какой авторитетный источник. В стандарте тоже написано?
Q>>>Будут при arity(k) > arity(M). Это пример был к тому, что твоя identity — никак не «идеальная». MTD>>Да, но лучше того, что сделали в Майкрософт.
Q>Если используются просто как контрольная сумма, то конечно лучше.
Контрольная сумма и хеш вещи разные, созданы для разного. Задача хеша — мапить ключ в хеш, задача контрольной суммы — проверка целостности.
MTD>>Мне нужно через std::hash — я обобщенный код пишу.
Q>Значит, тебе не нужно через std::hash, а нужно через свою хэш-функцию со специализацией для size_t.
Я не хочу переписывать стандартную библиотеку.
Q>И тем не менее, случаи biased-данных, что ломают наивные сортировки или хэш-таблицы, периодически встречаются. Не у всех и не у каждого, но не исчезающе редко.
Из практики есть пример, когда обсуждаемая хеш-функция работала плохо? Любопытно, квиксорт — наивная сортировка?
Здравствуйте, MTD, Вы писали:
MTD>Какой авторитетный источник. В стандарте тоже написано?
Увы, стандарта у меня нет, так что ответить не смогу. Так и быть, пусть уверенность в твоей правоте продолжает держаться на этой хрупкой надежде, что хоть в стандарте-то наверное и не говорится про назначение функции std::hash.
MTD>Контрольная сумма и хеш вещи разные, созданы для разного. Задача хеша — мапить ключ в хеш, задача контрольной суммы — проверка целостности.
Ведь ты так и не открыл нам секрет, зачем используешь функцию hash. Остаётся только строить догадки.
MTD>Любопытно, квиксорт — наивная сортировка?
Тот квиксорт, как он изучается в школе — конечно, наивная. Для защиты от неудачных входных массивов при выборе пивота используется медиана трёх или другие уловки с рандомизацией. Для хрестоматийного двустрочника на Хаскеле якобы быстрой сортировки «плохие» входные данные совсем тривиальны.
Здравствуйте, Qbit86, Вы писали:
Q>Увы, стандарта у меня нет, так что ответить не смогу. Так и быть, пусть уверенность в твоей правоте продолжает держаться на этой хрупкой надежде, что хоть в стандарте-то наверное и не говорится про назначение функции std::hash.
Ты какой-то смешной — для тебя спор не средство узнать что-то новое и выяснить истину, а средство самоутвердиться.
MTD>>Контрольная сумма и хеш вещи разные, созданы для разного. Задача хеша — мапить ключ в хеш, задача контрольной суммы — проверка целостности.
Q>Ведь ты так и не открыл нам секрет, зачем используешь функцию hash. Остаётся только строить догадки.
Я std::hash использую чтобы вычислить хеш.
MTD>>Любопытно, квиксорт — наивная сортировка?
Q>Тот квиксорт, как он изучается в школе — конечно, наивная. Для защиты от неудачных входных массивов при выборе пивота используется медиана трёх или другие уловки с рандомизацией.
Конечно, конечно, это же я с ходу сказал, что оппонент не читал тему.
MTD>> — для тебя спор
Q>Нет цели переубедить именно тебя; это очевидно бесполезное и неблагодарное занятие.
И снова я начинаю, да, да.
Q>Как это, узнал же новое. Вот, например, раньше я не знал, что в Microsoft и GCC функция std::hash() реализована по-разному. И в свете того, что сказал @MT-Wizard, это вполне имеет рациональное зерно.
Еще тебе надо почитать про контрольные суммы и хеши, чтобы не путаться и про быструю сортировку, еще про стоимость операций. Не благодари.
MTD>>Выбор опорной точки не поможет.
Q>Как это не поможет?
Да вот так. На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.
Да: «The unordered associative containers defined in 26.5 use specializations of the class template hash (23.14.1) as the default hash function.» 23.14.15
MTD>Конечно, конечно, это же я с ходу сказал, что оппонент не читал тему.
Так ведь это немного досадно: кто-то тратит время, отвечает автору вопроса (не оппоненту!). А тот не читает, а просто начинает спорить с какими-то выцепленными из комментария словами.
MTD>Еще тебе надо почитать... про быструю сортировку, еще про стоимость операций. Не благодари. MTD>>>Выбор опорной точки не поможет. MTD>На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.
Слышал звон? На отсортированных данных ты получишь квадратичную сложность, если в качестве опорного будешь выбирать крайний элемент отрезка. Если будешь выбирать случайный, или хотя бы средний как в школьном учебнике, то никакой квадратичной сложности там не будет.
Зачем ты вообще начал под***ывать Быстрой Сортировкой, если твои познания в этой области столь фрагментарны? Ещё и отсылает почитать, смотри на него.
