Какой самый быстрый способ найти целое число в массиве? - PullRequest
0 голосов
/ 21 февраля 2012

Проблема: Учитывая ID пользователя (целое число), быстро найти, к какой группе принадлежит пользователь.Группы будут содержать не более 15 пользователей.Кроме того, я использую libev, который не дает мне никакого контроля над параметрами, передаваемыми в событие чтения ввода-вывода, поэтому userID (дескриптор / целое число файлов) - это действительно only вещь, которую я могу использовать.

Мое решение: хэш один раз для userID в хэш-таблицу, содержащую пары groupID и userID.Второй раз хэшируйте для groupID хеш-таблицу, содержащую groupID и массив из 15 пар userID.

Решение работает, но это код сервера, который будет выполняться безбожно много раз.Интересно, будет ли двойное хеширование неэффективным и может ли быть лучшее решение?

Ответы [ 2 ]

1 голос
/ 11 ноября 2013

Вы говорите, что libev предоставляет вам только ограниченный объем данных - сам дескриптор ev_io - и делаете вывод, что все, что здесь полезно, - это дескриптор файла.Ну, как правило, вы, вероятно, правы, но есть хитрый прием, который вы можете сделать.

Поскольку с libev вы выделяете структуры самостоятельно, а затем имеете libev, инициализируете их, ничто не мешает вам выделить слишком много места.Так как libev не будет касаться этого дополнительного пространства, вы можете поместить туда свои собственные вещи.Удачи!

Так как же это работает на практике?Вы создаете новую структуру, содержащую ev_io в качестве первого члена, а затем помещаете все остальные данные после него, скажем так:

struct my_mutant_io {
    ev_io handle;
    int group_id;
};

Теперь, где бы вы ни выделяли uv_io,выделите my_mutant_io вместо этого.Поместите ваши данные туда, куда вы хотите, и как только вам нужно будет передать их в функцию libuv, просто возьмите вместо этого адрес handle:

struct my_mutant_io *mutant = malloc(sizeof(struct my_mutant_io));
if(!mutant) {
    abort();
}
mutant->group_id = /* ... */;
ev_io_init(&mutant, some_callback, fd, EV_READ);

Вы дали libev ev_ioи не удивительно, что на самом деле это просто часть большей структуры.Теперь давайте перейдем к обратному вызову.Ты вернешь свой ev_io, но подожди!Поскольку ev_io является первым членом структуры, его адрес совпадает с адресом нашего мутанта.Мы можем привести ev_io * обратно к struct my_mutant_io * и использовать его.(Только не говорите строгим псевдонимам богов.)

Структуру, подобную этой, чаще всего называют дубинкой.

0 голосов
/ 21 февраля 2012

Я бы отсортировал userID в массиве групп и использовал бы алгоритм двоичного поиска.

Сделайте то же самое с groupid, создайте класс или структуру, которые содержат groupID и массив идентификаторов пользователей.

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


Edit:

Бинарный поиск может быть полезен для небольшого объема данных, в то время как «Хэш-карта» всегда будет занимать то же время, что и ваш объем данных.

Итак, вот ссылка на другой вопрос со сравнениями двух решений: Что быстрее, поиск по хэшу или бинарный поиск?

Я должен признать, что ты был прав!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...