Идеальное хеширование без чтения из памяти параметров h2(k)?

mayton2019, да нет, если какой-то код, в данном случае contains(k), читал дважды из памяти (при этом времени на вычисления тратил совсем немного), то уменьшение количества обращений к памяти в 2 раза увеличит скорость работы этого кода тоже почти вдвое. А contains(k) у PerfectHashTable фактически единственный метод

Идеальное хеширование без чтения из памяти параметров h2(k)?

mayton2019, ну и необязательно справочники, которые содержат данные вроде стран.
Такая хеш таблица может быть вспомогательной структорой данных в каком-то другом алгоритме, тогда время её1 построения критично.
Или, например, список каких-то (их не так много, что можно хранить в оперативке, а не на диске) user'ов в оперативной памяти сервера, на старте сервера можно сбилдить таблицу, и запомнить max id (key) user'a, и при запросе contains, если id <= max id, то идти в эту статическую хеш таблицу, иначе в динамическую

Идеальное хеширование без чтения из памяти параметров h2(k)?

mayton2019, так вариант с двумя как раз и противопоставляют варианту с одной, там как раз смысл в том, что квадрат растёт нелинейно и ((m/n)^2)*n (где (m/n)^2 размер бакета) много лучше n^2 (там примерно ((m/n)^2)*n ~ 4n получается при допустимом по времени построения размеру бакета)

Идеальное хеширование без чтения из памяти параметров h2(k)?

mayton2019, забыл упомянуть в самом вопросе, что вариант с размером хеш таблицы m = n^2, где в среднем за 2 раза удастся построить таблицу (только с одной внейшней h1, без h2i) не подходит из-за больших затрат по памяти.

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

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

Adamos, конкретно по АиСД, если уник норм, например, МФТИ или ИТМО, то они там на высоте, а вот фреймворкдроч как раз (которым промышляют на всяких курсах) не очень, да он и не нужен в вузе, в том же МФТИ фреймворки факультативом являются и не входят в основную программу

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

Adamos, например, у меня в унике, на структурах данных, их реализовывали через массив байтов, а не T, вроде бы даже аргументируя это чем-то, поэтому так в памяти отложилось и делал через массив байтов. Судя по всему, аргументы были неверны

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

Adamos, просто до этого, когда писал структуры данных в академических целях, всегда использовал std::byte *, сейчас решил посмотреть, как у других, и везде, что в бусте, что в каком-нибудь EASTL, вижу, что используют именно T *

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

Adamos, ну да, если компилятор заменит 4-х байтный инт на 8-ми байтный, то количество промахов по кэшу удвоится, но в конкретном случае, что с T *, что с std::byte * размеры массивов (в байтах) одинаковые и влиять не должно
Или Вы что-то другое имели в виду ?

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

mayton2019, забыл, извиняюсь, только что дополнил и указал это )

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

mayton2019, ну я и говорю, что скорость работы связана, скорее всего, с какими-то фичами компилятора, когда у него из-за наличия явно T *, а не std::byte *, есть больше информации и он может сделать какие-то оптимизации, и интересно какие именно ему нельзя сделать, имея std::byte *
Ну и, покопавшись в известных имплементациях, вроде EASTL, заметил, что всегда используется именно T *, значит какая-то причина есть на это

Почему T * может работать ощутимо быстрее (~ на 25-30%) в качестве хранилища данных, чем std::byte *?

mayton2019, ну я на 99% уверен, что проблема фундаментально связана с типами
Если нужно, могу привести бенчмарки, но они одинаковые
Мог в принципе и код самих структур данных привести, но мне кажется, его никто бы смотреть особо не стал, именно поэтмоу решил скинуть диффы перехода с std::byte * на T *

Является ли такой способ выделения массива объектов на хипе идиоматичным?

code_panik, а, нет даже не всем объектам, а только самому большому нужно указать самое большое выравнивание

Является ли такой способ выделения массива объектов на хипе идиоматичным?

code_panik, да, забыл упомянтуь, самим объектам ещё нужно будет указать максимальное среди наследников выравнивание через alignas()

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов, ок, понял, спасибо за подробные ответы )

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов, тут вот написано, что если T это не массив и не тип функции, то decay работает как
в примере выше, можно тогда заменить std::remove_const_t<std::remove_reference_t<T>> на std::remove_cv<std::remove_reference<T>> чтобы ещё volatile учитывался

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов,

В иной ситуации тебе в test первым параметром зайдет внезапно prvalue, для которого T будет чистым типом. Трансляция даже не остановится, т.к. std::remove_reference и std::remove_const созданы так, чтобы не замечать отсутствия того, что они призваны удалять.

А разве в случае prvalue трейты std::remove_reference+std::remove_const не сделают ничего ? Ну то есть был какой-то T, который в свою очередь prvalue, ну а std::remove_reference+std::remove_const из него сделают T, то есть - ничего ? Или я что-то не учитываю

в этом месте яб именно std::decay использовал

меня смущает, что decay может сделать array-to-pointer

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов, ещё короткий вопрос, правда совсем не по теме, он довольно маленький, поэтому задам здесь )
Если требуется задать какой-то тип T шаблонного аргумента, при этом T уже заранее инициализирован предыдущим аргументом, например, каким-нибудь const T &, а тип второго аргумента хочется записать как T от 1-го типа, например:

template<typename T>
void test(T && pointRef, std::remove_const_t<std::remove_reference_t<T>> * pointPtr) {}

И здесь, если передадут какой-нибудь const int & в качестве первого аргумента, то второй будет выводиться просто как int и будет удобно на него навесить * например
ну то есть, как я понимаю, получив 1-й аргумент T, последующие аргументы (если они есть) будут выводитсья относительно 1-го, ну и собственно цель - получить "чистый" ранее выведенный T
Нет же ничего пагубного в таком подходе ?
P.S.: можно std::decay, но у него более широкий спектр, поэтому было выбрано, как в примере

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов, ок, буду знать, спасибо за информацию :)

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов, хотел добавить насчёт Pool'а: этот паттерн же используется для объектов, создание которых относительно дорогое, чтобы вместо создания и разрушения были методы acquire() и release() соответственно. Где acquire() будет модифицировать "пару" полей объекта, приводя его в боевое состояние, а release() - сбрасывать состояние
Если честно, не совсем понял, как это связано с тем примером ), мб мы про разные пулы говорим )

Является ли такой способ выделения массива объектов на хипе идиоматичным?

Евгений Шатунов, смотрел недавно код кишков UE4 и там почти везде было сделанно именно 1-м способом, без вектора (даже без их внутреннего аналога вектора) и умных указателей, и оно было использовано не в контексте пула, а как обычный массив на куче. Поэтому такой вопрос назрел
Насчёт "идиоматичный" я имел в виду, что "принято чаще так делать", хотя судя по ответам идиотматичным как раз является вариант с вектором