Задачка на std::multiset або пошук по полях структури

Попалася невелика задачка, десь на 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;

віртуальний 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;
віртуальний 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) << "ЦЕНТР"
<< 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 години.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.