@ProCxx - страница 864 - Telegram web archive

Александр

а вдруг спутник с орбиты уйдёт?

Andrei

Но если нужны гаранртии, то да, хеш, потом руками.

Andrei

Спасибо всем за обсуждения и Андрею в особенности за идею с хэшом

Не за что :D

Animal

Особо сильные гарантии не нужны, компаратор нужен только для тестов

Александр

тогда пофиг

Animal

Вот и я так же думаю)

Александр

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

Animal

Хорошее замечание, спасибо)

Daniil

Но если нужны гаранртии, то да, хеш, потом руками.

нубовопрос. А если тот же unordered_map находит совпадение по хешу, он потом руками делает сравнение? serachItem == resultItem?

Andrei

Да.

Александр

конечно

Александр

тем более, там коллизии очень вероятны

Daniil

окей

Andrei

тем более, там коллизии очень вероятны

А в цифрах можно? :) Для своих объектов можно довольно неплохой хешер написать.

Aidar

Там по умолчанию должны быть неплохие

Александр

А в цифрах можно? :) Для своих объектов можно довольно неплохой хешер написать.

зависит от размера объекта. для int16_t при размере баскета (или как там это называется) 65536 коллизий не будет если объект хранит в себе данных на байт 10-20, то уже без коллизий не обойтись

Александр

конкретные цифры - если N объектов на M корзин -> в среднем по N/M с одинаковым хешом

Aidar

Только ты не знаешь сколько сейчас бит используется

Александр

если объект размера значащих K бит, то есть 2^K его различных копий

🐙 Antony

нубовопрос. А если тот же unordered_map находит совпадение по хешу, он потом руками делает сравнение? serachItem == resultItem?

На случай колизий хеша. Если хеши разные - тогда значения точно нет, если хеши одинаковые - тогда либо значение есть, либо колизия => чтобы точно убедиться, надо сравнить еще и значения

Александр

сам хэш может быть довольно уникальным, но unordered берут же от него % basket_num. может от реализации еще зависеть

Aidar

Я о том же

🐙 Antony

сам хэш может быть довольно уникальным, но unordered берут же от него % basket_num. может от реализации еще зависеть

Там, кстати, в последнем GCC круто сделали: избавились от дорогих операций % и / за счет того что basket_num всегда степень двойки => компилятор заменяет их на операции сдвига и бинарного &

Aidar

Вроде это изначально так должно быть нет?

Александр

Там, кстати, в последнем GCC круто сделали: избавились от дорогих операций % и / за счет того что basket_num всегда степень двойки => компилятор заменяет их на операции сдвига и бинарного &

так вроде есть две реализации - на простых числах и на степенях двойки. там у простых чисел тоже есть какой-то плюс

Aidar

Ну яб сразу так написал еслиб мне сказали писать хэштаблицу

Александр

это вопрос похожий на "а как перевыделять память в динамических контейнерах - в 1.5 раза или по простым числам? или в 2?"

Aidar

В 2

Aidar

Потому что степень двойки

🐙 Antony

так вроде есть две реализации - на простых числах и на степенях двойки. там у простых чисел тоже есть какой-то плюс

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

Александр

вообще, хеш сам по себе считается прилично по времени (относительно /, %) - разве оптимизации того стоят?

Александр

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

не знал, спасибо

Aidar

Да это тупо логически правильно имхо

Aidar

У нас бинарная система

Aidar

Пусть тут тоже все бинарно буде

Александр

так доказано же, что идеальная система - с основанием E (основание натурального логарифма)?

Aidar

Ели очевидных фишек нет

Aidar

Ну вот тем более

🐙 Antony

вообще, хеш сам по себе считается прилично по времени (относительно /, %) - разве оптимизации того стоят?

прилично по времени для строк и типов наподобие векторов/массивов С простыми типами дела обстоят намного лучше, и замена должна ощущаться (в теории)

Andrei

Добавлю, что есть темплейтно\констекспровый хеш для статических строчек.

Александр

прилично по времени для строк и типов наподобие векторов/массивов С простыми типами дела обстоят намного лучше, и замена должна ощущаться (в теории)

хм, понятно

Aidar

А у нас уже есть статические строчки?

Aidar

В 17?

Александр

у каждого в папочке /test_some_trash есть

Aidar

Это не подходит

Aidar

Там говно

Aidar

Я смотрел

Александр

а статические строчки видимо на constexpr_allocator будут

Aidar

Тоесть можно будет статический вектор заюзать?(лолшто статический вектор)

Aidar

А статическая мапа вполне применима

Александр

не статическая, а времени компиляции

Александр

с мапой круто - да

Aidar

Ну да

Aidar

Я употребляю как статический полиморфизм не придирайся

Александр

хорошо

Александр

хотя мне статические мапы перестанут быть нужны, как только введут рефлексию для enum'ов

🐙 Antony

А у нас уже есть статические строчки?

есть string_view который должен быть constexpr в С++17 Но там еще нет требования, чтобы итераторы были юзабельны в constexpr: http://cplusplus.github.io/LWG/lwg-active.html#2938 (на самом деле, чинится вот тут http://cplusplus.github.io/LWG/lwg-active.html#2897 )