Быстрый 64-битный идентификатор целого ID Поиск / Поиск

Question

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

Давайте использовать сценарий наихудшего случая: каждый идентификатор используется. Это 64 бит, так что вы идете: 18446744073709551616 ID для поиска. Большая часть данных хранится в базе данных, и наша программа поиска возвращает либо указатель, либо нулевой указатель. Нулевой указатель означает, что программа должна получить доступ к базе данных для загрузки объекта, после чего у нее будет указатель.

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

Еще одна идея, которая у меня возникла, - создать статический раздел пространства, дерево, в котором каждая ветвь разделяется на степени 2 ветвей, но только до разумной глубины. Использование побитового оператора в идентификаторе вместо оператора модуля, чтобы выяснить, к какой ветви он принадлежит на каждом уровне. Каждая возможная ветвь в дереве всегда существует, но на некоторой глубине они останавливаются, и бинарный поиск все еще требуется, потому что точное число значений все еще неизвестно.

Какие у вас идеи?

Answer 1

Это классический случай хеш-карты. Во-первых, поймите, сколько идентификаторов вы можете иметь одновременно. 2 ^ 64 - это нонсенс, так как даже структура данных, в которой хранятся эти идентификаторы и указатели на объекты, уже будет не менее 268,435,445 ТБ. Теперь нет ничего плохого в использовании 64-битных идентификаторов, но определите, сколько объектов вы будете иметь активными одновременно, выберите разумное число, например, 5 000, и используйте хэш-карту, скажем, в 10 раз превышающую количество объектов. Если ваш коэффициент загрузки достаточно низок и ваша хэш-функция достаточно хороша, вы получите амортизированное время доступа O (1).

Answer 2

Даже если число активных объектов будет намного больше, скажем, 1 миллион, вы все равно можете использовать относительно небольшую хэш-карту, например карту размером 10000. Каждый элемент карты указывает на связанный список идентификаторов. Эти списки ищутся с помощью простого линейного поиска. Если хеш-функция выбрана правильно, идентификаторы будут распределены равномерно (или близко к этому) по 10000 записям в хэш-карте. Таким образом, каждая запись хеш-таблицы будет содержать около 100 идентификаторов. Линейный поиск такого списка занимает в среднем 50 сравнений.

В одном из моих приложений количество символов было около 1000. Я использовал простой линейный поиск. Анализ производительности показал, что 90% процессорного времени уходит на поиск таблиц. Затем я создал хеш-таблицу, состоящую всего из 32 записей -> загрузка процессора при поиске в таблице опустилась ниже 4%. Задача решена. Увеличение хеш-таблицы не окажет заметного влияния на скорость (менее 4%), поэтому я оставил ее в размере 32.

Вывод: вы можете использовать хеш-таблицу, которая меньше, чем количество элементов. Для этого требуется среднее количество сравнений (общее количество идентификаторов / размер хеш-таблицы / 2). Выберите размер хеш-таблицы, достаточно большой, чтобы сократить время ЦП для поиска в таблице до небольшой доли общего времени ЦП.

Answer 3

«Какие у тебя идеи?»

Я бы сначала использовал std::map и думал о реализации своего собственного решения, только если производительность была бы плохой.

http://www.cplusplus.com/reference/stl/map/