約4時間のコーディングのどこかで小さな問題が発生しましたが、それは面白いと感じました。
1,000万のユーザーデータベースがあります。
class User{ int id; time_t birthday; // int gender; // int city_id; // time_t time_reg; // };
頻繁でない更新を考慮して、データベースをすばやく検索する必要があります。 検索は、年齢、性別、都市などのフィールドごとに実行できます。 検索フィールドは、グループ化するか、個別に指定できます。次に例を示します。
- 市
- 都市、性別;
- 性別、年齢。
発行データは、ユーザー登録日でソートし、100ユーザーのページごとに発行する必要があります。
ヒント1： DBMSは必要な速度を提供しません。
ヒント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を選択したのは、挿入と検索に使用されるコンパレータを挿入できるためです。
私は検索を少し拡大したかったので、Alexandrescuの教訓に従って、コンパレーターを戦略として実装しました。
マルチセットメモリを保存するために、ユーザーへのポインタが保存されるため、検索条件インターフェイスは次のようになります。
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; };
| 方法 | 説明 |
|---|---|
| 一致した | ユーザー条件を満たしているかどうか |
| patternForSearch | 検索キーを生成するためのテンプレートメソッド |
| 演算子（） | 要素比較 |
| 署名 | 基準識別子として使用 |
2つの基準の実装例：
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; };
2つのフィールドを検索するために、次のテンプレートクラスと関数を導入しました。
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 :: 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時間で記述できるコードはそれほど多くないようです。