Попалась небольшая задачка, где-то на 4 часа кодирования, которую счел занимательной.


Есть база пользователей 10 миллионов:


class User{
 int id; 
 time_t birthday; // дата рождения
 int gender;      // пол
 int city_id;     // место проживания
 time_t time_reg; // дата регистрации
};

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


  • город;
  • город, пол;
  • пол, возраст.

Данные выдачи должны быть отсортированы по дате регистрации пользователей, и выдаваться постранично по 100 пользователей.


Подсказка 1: СУБД не даст нужной скорости.
Подсказка 2: Вспомнить сложность операций со множествами, сложность стандартных алгоритмов.
Подсказка 3: Проверить время поиска реализованного алгоритма, неплохой результат это порядка 0.005 сек.


Из готовых контейнеров для этой задачи можно использовать std::vector, отсортированный по нужному кретерию поиска, и std::lower_bound с реализацией:


template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val, Compare comp);

Или использовать std::multiset. Выбрал std::multiset по причине того, что в него можно засунуть компаратор, который будет использоваться для вставки и поиска.


Захотелось заложить легкое расширение поиска, поэтому пошел по заветам Александреску и реализовал компаратор как стратегию.


Для экономии памяти multiset хранятся указатели на User, поэтому интерфейс критерии поиска выглядит так:


class AbstractCriterion
{
public:

    virtual ~AbstractCriterion() = default;

    virtual bool matched(const User &user) const noexcept = 0;

    User patternForSearch() const noexcept
    {
        User user;
        initPattern(user);
        return user;
    }

    virtual int signature() const noexcept = 0;
    virtual void initPattern(User &user) const noexcept = 0;
    virtual bool operator()(const User *first, const User *second) const noexcept = 0;
};

Метод Описание
matched соответствует User данному критерию или нет
patternForSearch шаблонный метод для формирования ключа поиска
operator() сравнение элементов
signature используется как идентификатор критерии

Примеры реализации двух критерий:


class CityCriterion: public AbstractCriterion
{
public:

    CityCriterion()
        : m_city(0)
    {
    }

    CityCriterion(int city)
        : m_city(city)
    {
    }

    bool matched(const User &user) const noexcept final
    {
        return user.cityId == m_city;
    }

    void initPattern(User &user) const noexcept final
    {
        user.cityId = m_city;
    }

    virtual int signature() const noexcept final
    {
        return Signatures::City;
    }

    bool operator()(const User *first, const User *second) const noexcept final
    {
        return first->cityId < second->cityId;
    }

private:

    int m_city;
};

class GenderCriterion: public AbstractCriterion
{
public:

    GenderCriterion()
        : m_gender(No)
    {
    }

    GenderCriterion(int gender)
        : m_gender(gender)
    {
    }

    bool matched(const User &user) const noexcept final
    {
        return user.gender == m_gender;
    }

    void initPattern(User &user) const noexcept final
    {
        user.gender = m_gender;
    }

    virtual int signature() const noexcept final
    {
        return Signatures::Gender;
    }

    bool operator()(const User *first, const User *second) const noexcept final
    {
        return first->gender < second->gender;
    }

private:

    int m_gender;
};

Необязательно ограничиваться имеющимися полями структуры. Например возраст можно вычислять:


class AgeCriterion: public AbstractCriterion
{
public:

    static const unsigned int SECONDS_IN_YEAR = 31536000;

    AgeCriterion()
        : m_age(0)
    {
        time(&m_curTime);
    }

    AgeCriterion(int age)
        : m_age(age)
    {
        time(&m_curTime);
    }

    bool matched(const User &user) const noexcept final
    {
        const unsigned int age = difftime(m_curTime, user.birthday) / SECONDS_IN_YEAR;
        return m_age == age;
    }

    void initPattern(User &user) const noexcept final
    {
        user.birthday = m_curTime - (m_age + 1) * SECONDS_IN_YEAR;
    }

    virtual int signature() const noexcept final
    {
        return Signatures::Age;
    }

    bool operator()(const User *first, const User *second) const noexcept final
    {
        const int firstAge = difftime( m_curTime, first->birthday) / SECONDS_IN_YEAR;
        const int secondAge = difftime( m_curTime, second->birthday) / SECONDS_IN_YEAR;

        return firstAge < secondAge;
    }

private:

    size_t m_age;
    time_t m_curTime;
};

Для поиска по двум полям ввел следующий шаблонный класс и функцию:


template<typename FirstCriterion, typename SecondCriterion>
class BiCriterion: public AbstractCriterion
{
public:

    BiCriterion(const FirstCriterion &first, const SecondCriterion &second)
        : m_first(first), m_second(second)
    {
    }

    bool matched(const User &user) const noexcept final
    {
        return m_first.matched(user) && m_second.matched(user);
    }

    void initPattern(User &user) const noexcept final
    {
        m_first.initPattern(user);
        m_second.initPattern(user);
    }

    int signature() const noexcept final
    {
        const auto sign1 = m_first.signature();
        const auto sign2 = m_second.signature();
        return sign1 | sign2;
    }

    bool operator()(const User *first,
                    const User *second) const noexcept final
    {
        const bool less = m_first(first, second);

        if (!less && !m_first(second, first)) {
            return m_second(first, second);
        }
        else {
            return less;
        }
    }

private:

    FirstCriterion m_first;
    SecondCriterion m_second;
};

template<typename FirstCriterion, typename SecondCriterion>
BiCriterion<FirstCriterion, SecondCriterion> AND(const FirstCriterion &first, const SecondCriterion &second)
{
    return BiCriterion<FirstCriterion, SecondCriterion>(first, second);
};

Если захочу найти мужиков в возрасте 30 лет, то


auto criterion = AND(AgeCriterion(30), GenderCriterion(Male));

std::multiset завернул в класс UserDataBase:


class UserDataBase
{
    using SetComparator = std::function<bool(User *, User *)>;
    using Multiset = std::multiset<User *, SetComparator>;

    std::vector<User *> m_users;
    std::map<int, Multiset> m_searchMap;

public:

    using SearchResultIteratorPtr = std::unique_ptr<ISearchResultIterator>;

    UserDataBase() = default;
    ~UserDataBase();

    template<typename Criterion>
    void registryCriterion(const Criterion &criterion)
    {
        m_searchMap[criterion.signature()] = Multiset(criterion);
    }

    void append(const User &user)
    {
        auto item = new User(user);
        m_users.push_back(item);

        for (auto iter = m_searchMap.begin();
             iter != m_searchMap.end();
             ++iter) {
            iter->second.insert(item);
        }
    }

    template<typename Criterion>
    SearchResultIteratorPtr search(const Criterion &criterion) const
    {
        typedef SearchResultIterator<Multiset::const_iterator, Criterion> ResultIterator;
        const auto end = Multiset::const_iterator();
        SearchResultIteratorPtr iterator(new ResultIterator(end, end, criterion));

        User pattern;
        pattern = criterion.patternForSearch();

        if (m_searchMap.count(criterion.signature())) {

            const auto &set = m_searchMap.at(criterion.signature());
            auto iter = set.find(&pattern);
            if (iter != set.end()) {
                iterator.reset(new ResultIterator(iter, set.end(), criterion));
            }
        }

        return iterator;
    }
};

Вроде все просто. Сперва регистрируем критерии поиска, потом добавляем элементы:


UserDataBase base;
base.registryCriterion(AgeCriterion());
base.registryCriterion(GenderCriterion());

base.registryCriterion(AND(AgeCriterion(), GenderCriterion()));
base.registryCriterion(AND(CityCriterion(), GenderCriterion()));
//..
for (int i = 0; i < MAX_USERS; ++i) {
    User usr;
    ifs >> usr;
    base.append(usr);
}

В самом методе поиска нет ничего интересного. Только возврящается указатель на ISearchResultIterator, что бы срезать информацию о типе.


Итератор это обертка над итератором std::multiset, хранящий критерий поиска:


template<typename MultisetIterator, typename Criterion>
class SearchResultIterator: public ISearchResultIterator
{
public:

    SearchResultIterator(MultisetIterator iter,
                         MultisetIterator end,
                         const Criterion &criterion)
        : m_iter(iter), m_end(end), m_criterion(criterion)
    {

    }

    bool isValid() const noexcept final
    {
        return (m_iter != m_end)
            && (m_criterion.matched(**m_iter));
    }

    bool next() noexcept final
    {
        if (isValid()) {
            ++m_iter;
            return m_criterion.matched(**m_iter);
        }
        else {
            return false;
        }
    }

    const User &user() const noexcept final
    {
        if (isValid()) {
            return **m_iter;
        }
        else {
            return m_emptyUser;
        }
    }

private:

    MultisetIterator m_iter;
    MultisetIterator m_end;

    Criterion m_criterion;
    User m_emptyUser;
};

Идем по std::multiset пока не дошли до конца и элементы сооветсвтуют критерию поиска.
Использование выглядит так:


auto iterator = base.search(AND(AgeCriterion(30), GenderCriterion(Male)));
if (iterator->isValid()) {
    printReuslt(iterator);
}
//... 
void printReuslt(std::unique_ptr<ISearchResultIterator> &iter)
{
    int cnt = 1;

    std::vector<User> users;
    users.reserve(100);

    do {
        users.push_back(iter->user());
        if (cnt == 100) {
            break;
        }
        ++cnt;
    }
    while (iter->next());

    std::sort(users.begin(), users.end(), timeSort);

    std::cout << std::setw(8) << "USR ID"
              << std::setw(12) << std::left << " REG"
              << std::setw(5) << std::right << "GNDG"
              << std::setw(6) << "CITY"
              << std::setw(12) << "BIRTHDAY" << std::endl;

    for (const auto &usr: users) {
        std::cout << std::setw(8) << usr.id
                  << std::setw(12) << usr.timeReg
                  << std::setw(5) << usr.gender
                  << std::setw(6) << usr.cityId
                  << std::setw(12) << usr.birthday << std::endl;
    }
}

В принципе при выводе можно не сортировать элементы по времени, если воспользоваться таким свойством, что одинаковые елементы в мультимножестве расположены в том порядке, в каком они добавлялись.


Вроде получилось не так много кода, который вполне можно написать за 4 часа.

Поделиться с друзьями
-->

Комментарии (26)


  1. Elsedar
    17.10.2016 11:40
    +9

    Вы делали сравнение с выборкой из БД? Если да, то с какой? Вы же понимаете, что просто создали кучу индексов на все нужные вам комбинации. А так же то, что всю БД вы держите в памяти. Поэтому, если выбрать in-memory БД, и создать так же много индексов, то, мне кажется, результат будет примерно таким же.


    1. RPG18
      17.10.2016 12:20
      -2

      Обычно в таких ситуациях берут какой-нибудь SQLite, который можно сделать in-memory и заводят индексы. Такое проходил когда заставили переписывать приложение с C# и его linq на C++. Тут мне взяли и поставили задачку седлать без БД.


      1. mad_god
        17.10.2016 12:44
        -2

        Мой преподаватель по СУБД только фыркал, когда я упоминал про SQLite.


        1. hd_keeper
          17.10.2016 13:03
          -6

          И есть за что.


      1. RomanArzumanyan
        17.10.2016 13:50

        Задача на собеседование или рабочий проект?


        1. RPG18
          17.10.2016 14:01
          +1

          Переписывание с C# на C++ был рабочим проектом. Грустное это дело переписывать что-либо с C#/Java на C++, в основном из-за поиска чем бы заменить ту или иную библиотеку.


          1. RomanArzumanyan
            17.10.2016 14:02

            Тогда отказ от СУБД придаёт проекту особый шарм.


            1. RPG18
              17.10.2016 14:06
              +1

              Конкретно эта задачка, была как тестовое задание. Счел её интересной.


  1. Dionis_mgn
    17.10.2016 12:16
    +1

    Ребятам из фотостраны придется сочинять новое тестовое задание =)


  1. Siemargl
    17.10.2016 12:44
    +6

    Есть более-менее стандартное решение в виде Boost Multi-index Конечно, если огромный бюст вас не пугает в проекте.


    1. RPG18
      17.10.2016 13:09

      Спасибо, не знал про Boost Multi-index. Вот за что люблю хабр, что в комментариях можно узнать что-то новое.


  1. D_T
    17.10.2016 12:44
    +4

    Еще есть boost::multi_index


  1. k0t_begemot
    17.10.2016 12:46
    -1

    Неплохо было бы выложить проект на github.


  1. ProstoTyoma
    17.10.2016 13:49

    del


  1. Shamov
    17.10.2016 14:18

    Если переделать BiCriterion таким образом, чтобы это была фабрика, то получится код на Java :)


  1. ProstoTyoma
    17.10.2016 15:50

    А зачем вам AbstractCriterion? Обязать производные классы иметь этот интерфейс?


    1. RPG18
      17.10.2016 15:58

      На будущее. Можно сделать такую штуку:


      class MultiCriterion: public AbstractCriterion
      {
      //
      void add(const std::shared_ptr<AbstractCriterion>& cri)
      {
          m_criteria.push_back(cri);
      }
      //...
      std::vector<std::shared_ptr<AbstractCriterion>> m_criteria;
      }

      т.е. можно сделать по 3 и более условиям.


  1. narick
    17.10.2016 17:00

    А как же високосные года? =)

    class AgeCriterion: public AbstractCriterion
    {
    public:
    
        static const unsigned int SECONDS_IN_YEAR = 31536000;
        ...
    


    1. RPG18
      17.10.2016 17:03

      Тогда наверное проще использоваться localtime и работать с tm


  1. DimaKurb
    17.10.2016 17:04

    интересно сравнить Ваш код с NoSQL. SQLite скорее всего будет уступать в скорости по сравнению с MongoDB.


    1. RPG18
      17.10.2016 17:12

      Я не знаю имеет ли задачка практического применения. Тут пишут, что:


      Multisets are typically implemented as binary search trees.

      Поэтому все будет зависеть от конкретной реализация дерева.


      1. DimaKurb
        17.10.2016 17:22

        да, Multiset в с++ это красно-черное дерево. и если я не ошибаюсь, то NoSQL это тоже реализация деревьев. поэтому и интересно их сравнение.


        1. gorodnev
          17.10.2016 20:36

          Совершенно необязательно, STL говорит про интерфейс, а не реализацию. Может и AVL быть, или еще что. Но самые популярные реализации на красно-черном.


  1. Videoman
    17.10.2016 22:04

    Сдается мне, что ваше решение будет жутко расточительным по памяти. Дело в том что std::*set и std::*map очень активно используют кучу внутри себя.и из-за этого, относительно, медленно добавляют/удаляют такое большое количество элементов. Такое ощущение что у вас очень мощная 64-х битная операционка с большим количеством памяти. В 32-х битном процессе такая реализация легко может вызвать OutOfMemory.
    Можно полюбопытствовать, сколько памяти занимает таким образом созданный индекс?


    1. RPG18
      17.10.2016 22:17

      4 std::multiset на 10 000 000, плюс std::vector для хранения исходных данных отъели 2.4Gb. CLion отъел 735 Mb.
      В условии задачки есть подсказка:


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


  1. Videoman
    18.10.2016 10:38

    Условие я заметил. Но тут все зависит от того, как его трактовать. Если база совсем редко изменяется, то выгоднее использовать 5-ть отсортированных std::vector-ов (четыре для индекса и один для самих структур). Будет занимать 200 + 160 = 360 Мб, Примерно в два раза меньше памяти. Ну а вообще, тут, конечно, самым оптимальным будет использование B+Tree. У него плотность будет сравнима с векторами, а скорость поиска с двоичным деревом.