Комментарии 5
Если мы говорим про высокую производительность, то хотелось бы увидеть сравнительные тесты производительности вашей реализации и std::unordered_map
Случай с копированием списка странноват, вообще говоря.
PHF не используются в рантайме. Они используются во времени компиляции, чтобы дико оптимизировать словари. Например, когда мы делаем switch-case по строкам не нужно делать O(N), проходясь по каждой строке и сравнивая её с данной, либо считать хэш от всех байт переданной строки. Достаточно найти PHF от case'овых строк, который будет смотреть всего парочку бит, которые уникально характеризуют каждую из строк, узнавать, на какую похожа переданная, а затем сравнивать их (вдруг переданная не из нашего множества вообще).
PHF не используются в рантайме. Они используются во времени компиляции, чтобы дико оптимизировать словари. Например, когда мы делаем switch-case по строкам не нужно делать O(N), проходясь по каждой строке и сравнивая её с данной, либо считать хэш от всех байт переданной строки. Достаточно найти PHF от case'овых строк, который будет смотреть всего парочку бит, которые уникально характеризуют каждую из строк, узнавать, на какую похожа переданная, а затем сравнивать их (вдруг переданная не из нашего множества вообще).
> Случай с копированием списка странноват, вообще говоря.
Это задачка на собеседовании, и как любая задачка на собеседовании, к реальной жизни не имеет никакого отношения. Просто пример как такое копирование можно реализовать через хеш-таблицы.
> PHF не используются в рантайме.
У нас была задача при анализе данных транслировать строковые ключи в айдишники, по которым эти ключи сохранены в базе. Много лет назад это были обычные запросы к базе, но после увеличения трафика это стало невозможным.
Так как количество строк заранее известно и это десятки миллионов, то было решено перевести получение айдишников в отдельный микросервис, написанный на С и использующий идеальные хеш-функции.
После этого мы забыли про такие проблемы, связанные с трансляцией. Этот микросервис теперь держит >5k запросов в секунду. И слабым местом стал уже сетевой интерфейс, но это уже другая история.
Это задачка на собеседовании, и как любая задачка на собеседовании, к реальной жизни не имеет никакого отношения. Просто пример как такое копирование можно реализовать через хеш-таблицы.
> PHF не используются в рантайме.
У нас была задача при анализе данных транслировать строковые ключи в айдишники, по которым эти ключи сохранены в базе. Много лет назад это были обычные запросы к базе, но после увеличения трафика это стало невозможным.
Так как количество строк заранее известно и это десятки миллионов, то было решено перевести получение айдишников в отдельный микросервис, написанный на С и использующий идеальные хеш-функции.
После этого мы забыли про такие проблемы, связанные с трансляцией. Этот микросервис теперь держит >5k запросов в секунду. И слабым местом стал уже сетевой интерфейс, но это уже другая история.
Почему нельзя циклы: у компоненты связности будет один цикл, то число уравнений(ребер, ключей) будет равно числу неизвестных(узлов). Правда, тогда вместо присваивания нулевому узлу значения, нужно будет решить систему уравнений.
Также иногда переопределенная(больше одного цикла в компоненте связности) система имеет решение.
Также иногда переопределенная(больше одного цикла в компоненте связности) система имеет решение.
Есть уже готовые хорошие протестированные решения для задачи идеального хеширования: www.gnu.org/software/gperf/gperf.html (чуть по-быстрее) и cmph.sourceforge.net/index.html (чуть по-медленнее, но использует меньше памяти)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Совсем просто про минимальное идеальное хеширование, основанное на графах