Comments 5
Если мы говорим про высокую производительность, то хотелось бы увидеть сравнительные тесты производительности вашей реализации и std::unordered_map
Случай с копированием списка странноват, вообще говоря.

PHF не используются в рантайме. Они используются во времени компиляции, чтобы дико оптимизировать словари. Например, когда мы делаем switch-case по строкам не нужно делать O(N), проходясь по каждой строке и сравнивая её с данной, либо считать хэш от всех байт переданной строки. Достаточно найти PHF от case'овых строк, который будет смотреть всего парочку бит, которые уникально характеризуют каждую из строк, узнавать, на какую похожа переданная, а затем сравнивать их (вдруг переданная не из нашего множества вообще).
> Случай с копированием списка странноват, вообще говоря.
Это задачка на собеседовании, и как любая задачка на собеседовании, к реальной жизни не имеет никакого отношения. Просто пример как такое копирование можно реализовать через хеш-таблицы.

> PHF не используются в рантайме.
У нас была задача при анализе данных транслировать строковые ключи в айдишники, по которым эти ключи сохранены в базе. Много лет назад это были обычные запросы к базе, но после увеличения трафика это стало невозможным.
Так как количество строк заранее известно и это десятки миллионов, то было решено перевести получение айдишников в отдельный микросервис, написанный на С и использующий идеальные хеш-функции.

После этого мы забыли про такие проблемы, связанные с трансляцией. Этот микросервис теперь держит >5k запросов в секунду. И слабым местом стал уже сетевой интерфейс, но это уже другая история.
Почему нельзя циклы: у компоненты связности будет один цикл, то число уравнений(ребер, ключей) будет равно числу неизвестных(узлов). Правда, тогда вместо присваивания нулевому узлу значения, нужно будет решить систему уравнений.
Также иногда переопределенная(больше одного цикла в компоненте связности) система имеет решение.
Only those users with full accounts are able to leave comments. Log in, please.