Попалась небольшая задачка, где-то на 4 часа кодирования, которую счел занимательной.
Есть база пользователей 10 миллионов
class User{
int id;
time_t birthday; // дата рождения
int gender; // пол
int city_id; // место проживания
time_t time_reg; // дата регистрации
};Нужно сделать быстрый поиск по базе, с учетом ее не частого обновления. Поиск может проходить по полям: возрасту, полу, городу. Поля поиска могут быть указаны в группировке или отдельно, например:
- город;
- город, пол;
- пол, возраст.
Данные выдачи должны быть отсортированы по дате регистрации пользователей, и выдаваться постранично по 100 пользователей.
Подсказка 1: СУБД не даст нужной скорости.
Подсказка 2: Вспомнить сложность операций со множествами, сложность стандартных алгоритмов.
Подсказка 3: Проверить время поиска реализованного алгоритма, неплохой результат это порядка 0.005 сек.
