API tools faq
paste
kutuzzzov

Спринт 4. Урок 4. Очередь запросов

kutuzzzov
Jan 3rd, 2022 (edited)
503
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 16.20 KB | None | 0 0
raw download clone embed print report
  1. // search_server_s4_t2_solution.cpp
  2.  
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iostream>
  6. #include <map>
  7. #include <set>
  8. #include <stdexcept>
  9. #include <string>
  10. #include <utility>
  11. #include <vector>
  12. #include <stack>
  13. #include <deque>
  14.  
  15. using namespace std;
  16.  
  17. const int MAX_RESULT_DOCUMENT_COUNT = 5;
  18.  
  19. string ReadLine() {
  20.     string s;
  21.     getline(cin, s);
  22.     return s;
  23. }
  24.  
  25. int ReadLineWithNumber() {
  26.     int result;
  27.     cin >> result;
  28.     ReadLine();
  29.     return result;
  30. }
  31.  
  32. vector<string> SplitIntoWords(const string& text) {
  33.     vector<string> words;
  34.     string word;
  35.     for (const char c : text) {
  36.         if (c == ' ') {
  37.             if (!word.empty()) {
  38.                 words.push_back(word);
  39.                 word.clear();
  40.             }
  41.         } else {
  42.             word += c;
  43.         }
  44.     }
  45.     if (!word.empty()) {
  46.         words.push_back(word);
  47.     }
  48.  
  49.     return words;
  50. }
  51.  
  52. struct Document {
  53.     Document() = default;
  54.  
  55.     Document(int id, double relevance, int rating)
  56.         : id(id)
  57.         , relevance(relevance)
  58.         , rating(rating) {
  59.     }
  60.  
  61.     int id = 0;
  62.     double relevance = 0.0;
  63.     int rating = 0;
  64. };
  65.  
  66. ostream& operator<<(ostream& out, const Document& document) {
  67.     out << "{ "s
  68.         << "document_id = "s << document.id << ", "s
  69.         << "relevance = "s << document.relevance << ", "s
  70.         << "rating = "s << document.rating << " }"s;
  71.     return out;
  72. }
  73.  
  74. template <typename StringContainer>
  75. set<string> MakeUniqueNonEmptyStrings(const StringContainer& strings) {
  76.     set<string> non_empty_strings;
  77.     for (const string& str : strings) {
  78.         if (!str.empty()) {
  79.             non_empty_strings.insert(str);
  80.         }
  81.     }
  82.     return non_empty_strings;
  83. }
  84.  
  85. enum class DocumentStatus {
  86.     ACTUAL,
  87.     IRRELEVANT,
  88.     BANNED,
  89.     REMOVED,
  90. };
  91.  
  92. class SearchServer {
  93. public:
  94.     template <typename StringContainer>
  95.     explicit SearchServer(const StringContainer& stop_words)
  96.         : stop_words_(MakeUniqueNonEmptyStrings(stop_words))  // Extract non-empty stop words
  97.     {
  98.         if (!all_of(stop_words_.begin(), stop_words_.end(), IsValidWord)) {
  99.             throw invalid_argument("Some of stop words are invalid"s);
  100.         }
  101.     }
  102.  
  103.     explicit SearchServer(const string& stop_words_text)
  104.         : SearchServer(SplitIntoWords(stop_words_text))  // Invoke delegating constructor
  105.                                                          // from string container
  106.     {
  107.     }
  108.  
  109.     void AddDocument(int document_id, const string& document, DocumentStatus status, const vector<int>& ratings) {
  110.         if ((document_id < 0) || (documents_.count(document_id) > 0)) {
  111.             throw invalid_argument("Invalid document_id"s);
  112.         }
  113.         const auto words = SplitIntoWordsNoStop(document);
  114.  
  115.         const double inv_word_count = 1.0 / words.size();
  116.         for (const string& word : words) {
  117.             word_to_document_freqs_[word][document_id] += inv_word_count;
  118.         }
  119.         documents_.emplace(document_id, DocumentData{ComputeAverageRating(ratings), status});
  120.         document_ids_.push_back(document_id);
  121.     }
  122.  
  123.     template <typename DocumentPredicate>
  124.     vector<Document> FindTopDocuments(const string& raw_query, DocumentPredicate document_predicate) const {
  125.         const auto query = ParseQuery(raw_query);
  126.  
  127.         auto matched_documents = FindAllDocuments(query, document_predicate);
  128.  
  129.         sort(matched_documents.begin(), matched_documents.end(), [](const Document& lhs, const Document& rhs) {
  130.             if (abs(lhs.relevance - rhs.relevance) < 1e-6) {
  131.                 return lhs.rating > rhs.rating;
  132.             } else {
  133.                 return lhs.relevance > rhs.relevance;
  134.             }
  135.         });
  136.         if (matched_documents.size() > MAX_RESULT_DOCUMENT_COUNT) {
  137.             matched_documents.resize(MAX_RESULT_DOCUMENT_COUNT);
  138.         }
  139.  
  140.         return matched_documents;
  141.     }
  142.  
  143.     vector<Document> FindTopDocuments(const string& raw_query, DocumentStatus status) const {
  144.         return FindTopDocuments(raw_query, [status](int document_id, DocumentStatus document_status, int rating) {
  145.             return document_status == status;
  146.         });
  147.     }
  148.  
  149.     vector<Document> FindTopDocuments(const string& raw_query) const {
  150.         return FindTopDocuments(raw_query, DocumentStatus::ACTUAL);
  151.     }
  152.  
  153.     int GetDocumentCount() const {
  154.         return documents_.size();
  155.     }
  156.  
  157.     int GetDocumentId(int index) const {
  158.         return document_ids_.at(index);
  159.     }
  160.  
  161.     tuple<vector<string>, DocumentStatus> MatchDocument(const string& raw_query, int document_id) const {
  162.         const auto query = ParseQuery(raw_query);
  163.  
  164.         vector<string> matched_words;
  165.         for (const string& word : query.plus_words) {
  166.             if (word_to_document_freqs_.count(word) == 0) {
  167.                 continue;
  168.             }
  169.             if (word_to_document_freqs_.at(word).count(document_id)) {
  170.                 matched_words.push_back(word);
  171.             }
  172.         }
  173.         for (const string& word : query.minus_words) {
  174.             if (word_to_document_freqs_.count(word) == 0) {
  175.                 continue;
  176.             }
  177.             if (word_to_document_freqs_.at(word).count(document_id)) {
  178.                 matched_words.clear();
  179.                 break;
  180.             }
  181.         }
  182.         return {matched_words, documents_.at(document_id).status};
  183.     }
  184.  
  185. private:
  186.     struct DocumentData {
  187.         int rating;
  188.         DocumentStatus status;
  189.     };
  190.     const set<string> stop_words_;
  191.     map<string, map<int, double>> word_to_document_freqs_;
  192.     map<int, DocumentData> documents_;
  193.     vector<int> document_ids_;
  194.  
  195.     bool IsStopWord(const string& word) const {
  196.         return stop_words_.count(word) > 0;
  197.     }
  198.  
  199.     static bool IsValidWord(const string& word) {
  200.         // A valid word must not contain special characters
  201.         return none_of(word.begin(), word.end(), [](char c) {
  202.             return c >= '\0' && c < ' ';
  203.         });
  204.     }
  205.  
  206.     vector<string> SplitIntoWordsNoStop(const string& text) const {
  207.         vector<string> words;
  208.         for (const string& word : SplitIntoWords(text)) {
  209.             if (!IsValidWord(word)) {
  210.                 throw invalid_argument("Word "s + word + " is invalid"s);
  211.             }
  212.             if (!IsStopWord(word)) {
  213.                 words.push_back(word);
  214.             }
  215.         }
  216.         return words;
  217.     }
  218.  
  219.     static int ComputeAverageRating(const vector<int>& ratings) {
  220.         if (ratings.empty()) {
  221.             return 0;
  222.         }
  223.         int rating_sum = 0;
  224.         for (const int rating : ratings) {
  225.             rating_sum += rating;
  226.         }
  227.         return rating_sum / static_cast<int>(ratings.size());
  228.     }
  229.  
  230.     struct QueryWord {
  231.         string data;
  232.         bool is_minus;
  233.         bool is_stop;
  234.     };
  235.  
  236.     QueryWord ParseQueryWord(const string& text) const {
  237.         if (text.empty()) {
  238.             throw invalid_argument("Query word is empty"s);
  239.         }
  240.         string word = text;
  241.         bool is_minus = false;
  242.         if (word[0] == '-') {
  243.             is_minus = true;
  244.             word = word.substr(1);
  245.         }
  246.         if (word.empty() || word[0] == '-' || !IsValidWord(word)) {
  247.             throw invalid_argument("Query word "s + text + " is invalid");
  248.         }
  249.  
  250.         return {word, is_minus, IsStopWord(word)};
  251.     }
  252.  
  253.     struct Query {
  254.         set<string> plus_words;
  255.         set<string> minus_words;
  256.     };
  257.  
  258.     Query ParseQuery(const string& text) const {
  259.         Query result;
  260.         for (const string& word : SplitIntoWords(text)) {
  261.             const auto query_word = ParseQueryWord(word);
  262.             if (!query_word.is_stop) {
  263.                 if (query_word.is_minus) {
  264.                     result.minus_words.insert(query_word.data);
  265.                 } else {
  266.                     result.plus_words.insert(query_word.data);
  267.                 }
  268.             }
  269.         }
  270.         return result;
  271.     }
  272.  
  273.     // Existence required
  274.     double ComputeWordInverseDocumentFreq(const string& word) const {
  275.         return log(GetDocumentCount() * 1.0 / word_to_document_freqs_.at(word).size());
  276.     }
  277.  
  278.     template <typename DocumentPredicate>
  279.     vector<Document> FindAllDocuments(const Query& query, DocumentPredicate document_predicate) const {
  280.         map<int, double> document_to_relevance;
  281.         for (const string& word : query.plus_words) {
  282.             if (word_to_document_freqs_.count(word) == 0) {
  283.                 continue;
  284.             }
  285.             const double inverse_document_freq = ComputeWordInverseDocumentFreq(word);
  286.             for (const auto [document_id, term_freq] : word_to_document_freqs_.at(word)) {
  287.                 const auto& document_data = documents_.at(document_id);
  288.                 if (document_predicate(document_id, document_data.status, document_data.rating)) {
  289.                     document_to_relevance[document_id] += term_freq * inverse_document_freq;
  290.                 }
  291.             }
  292.         }
  293.  
  294.         for (const string& word : query.minus_words) {
  295.             if (word_to_document_freqs_.count(word) == 0) {
  296.                 continue;
  297.             }
  298.             for (const auto [document_id, _] : word_to_document_freqs_.at(word)) {
  299.                 document_to_relevance.erase(document_id);
  300.             }
  301.         }
  302.  
  303.         vector<Document> matched_documents;
  304.         for (const auto [document_id, relevance] : document_to_relevance) {
  305.             matched_documents.push_back({document_id, relevance, documents_.at(document_id).rating});
  306.         }
  307.         return matched_documents;
  308.     }
  309. };
  310.  
  311. void PrintDocument(const Document& document) {
  312.     cout << "{ "s
  313.          << "document_id = "s << document.id << ", "s
  314.          << "relevance = "s << document.relevance << ", "s
  315.          << "rating = "s << document.rating << " }"s << endl;
  316. }
  317.  
  318. void PrintMatchDocumentResult(int document_id, const vector<string>& words, DocumentStatus status) {
  319.     cout << "{ "s
  320.          << "document_id = "s << document_id << ", "s
  321.          << "status = "s << static_cast<int>(status) << ", "s
  322.          << "words ="s;
  323.     for (const string& word : words) {
  324.         cout << ' ' << word;
  325.     }
  326.     cout << "}"s << endl;
  327. }
  328.  
  329. void AddDocument(SearchServer& search_server, int document_id, const string& document, DocumentStatus status,
  330.                  const vector<int>& ratings) {
  331.     try {
  332.         search_server.AddDocument(document_id, document, status, ratings);
  333.     } catch (const invalid_argument& e) {
  334.         cout << "Ошибка добавления документа "s << document_id << ": "s << e.what() << endl;
  335.     }
  336. }
  337.  
  338. void FindTopDocuments(const SearchServer& search_server, const string& raw_query) {
  339.     cout << "Результаты поиска по запросу: "s << raw_query << endl;
  340.     try {
  341.         for (const Document& document : search_server.FindTopDocuments(raw_query)) {
  342.             PrintDocument(document);
  343.         }
  344.     } catch (const invalid_argument& e) {
  345.         cout << "Ошибка поиска: "s << e.what() << endl;
  346.     }
  347. }
  348.  
  349. void MatchDocuments(const SearchServer& search_server, const string& query) {
  350.     try {
  351.         cout << "Матчинг документов по запросу: "s << query << endl;
  352.         const int document_count = search_server.GetDocumentCount();
  353.         for (int index = 0; index < document_count; ++index) {
  354.             const int document_id = search_server.GetDocumentId(index);
  355.             const auto [words, status] = search_server.MatchDocument(query, document_id);
  356.             PrintMatchDocumentResult(document_id, words, status);
  357.         }
  358.     } catch (const invalid_argument& e) {
  359.         cout << "Ошибка матчинга документов на запрос "s << query << ": "s << e.what() << endl;
  360.     }
  361. }
  362.  
  363. template <typename Iterator>
  364. class IteratorRange {
  365. public:
  366.     IteratorRange(Iterator begin, Iterator end)
  367.         : first_(begin)
  368.         , last_(end)
  369.         , size_(distance(first_, last_)) {
  370.     }
  371.  
  372.     Iterator begin() const {
  373.         return first_;
  374.     }
  375.  
  376.     Iterator end() const {
  377.         return last_;
  378.     }
  379.  
  380.     size_t size() const {
  381.         return size_;
  382.     }
  383.  
  384. private:
  385.     Iterator first_, last_;
  386.     size_t size_;
  387. };
  388.  
  389. template <typename Iterator>
  390. ostream& operator<<(ostream& out, const IteratorRange<Iterator>& range) {
  391.     for (Iterator it = range.begin(); it != range.end(); ++it) {
  392.         out << *it;
  393.     }
  394.     return out;
  395. }
  396.  
  397. template <typename Iterator>
  398. class Paginator {
  399. public:
  400.     Paginator(Iterator begin, Iterator end, size_t page_size) {
  401.         for (size_t left = distance(begin, end); left > 0;) {
  402.             const size_t current_page_size = min(page_size, left);
  403.             const Iterator current_page_end = next(begin, current_page_size);
  404.             pages_.push_back({begin, current_page_end});
  405.  
  406.             left -= current_page_size;
  407.             begin = current_page_end;
  408.         }
  409.     }
  410.  
  411.     auto begin() const {
  412.         return pages_.begin();
  413.     }
  414.  
  415.     auto end() const {
  416.         return pages_.end();
  417.     }
  418.  
  419.     size_t size() const {
  420.         return pages_.size();
  421.     }
  422.  
  423. private:
  424.     vector<IteratorRange<Iterator>> pages_;
  425. };
  426.  
  427. template <typename Container>
  428. auto Paginate(const Container& c, size_t page_size) {
  429.     return Paginator(begin(c), end(c), page_size);
  430. }
  431.  
  432. class RequestQueue {
  433. public:
  434.     explicit RequestQueue(const SearchServer& search_server) :
  435.     search_server_(search_server) {
  436.     }
  437.    
  438.     // сделаем "обёртки" для всех методов поиска, чтобы сохранять результаты для нашей статистики
  439.    
  440.     template <typename DocumentPredicate>
  441.     vector<Document> AddFindRequest(const string& raw_query, DocumentPredicate document_predicate) {
  442.         auto result = search_server_.FindTopDocuments(raw_query, document_predicate);
  443.         if (requests_.size() >= min_in_day_) {
  444.             if (requests_[0].result.size() != 0) {
  445.             --empty_count_;
  446.             requests_.pop_back();
  447.             }
  448.         }
  449.         if (result.empty()) {
  450.             ++empty_count_;
  451.         }
  452.         requests_.push_front({result});
  453.         return result;
  454.     }
  455.  
  456.     vector<Document> AddFindRequest(const string& raw_query, DocumentStatus status) {
  457.         return AddFindRequest(raw_query, [status](int document_id, DocumentStatus document_status, int rating) {
  458.             return document_status == status;
  459.             });
  460.     }
  461.  
  462.     vector<Document> AddFindRequest(const string& raw_query) {
  463.         return AddFindRequest(raw_query, DocumentStatus::ACTUAL);
  464.     }
  465.  
  466.     int GetNoResultRequests() const {
  467.         return empty_count_;
  468.     }
  469.    
  470. private:
  471.     struct QueryResult {
  472.         vector<Document> result;
  473.     };
  474.    
  475.     deque<QueryResult> requests_;
  476.     const static int min_in_day_ = 1440;
  477.     int empty_count_ = 0;
  478.     const SearchServer& search_server_;
  479. };
  480.  
  481. int main() {
  482.     setlocale(LC_ALL, "Russian");
  483.  
  484.     SearchServer search_server("and in at"s);
  485.     RequestQueue request_queue(search_server);
  486.  
  487.     search_server.AddDocument(1, "curly cat curly tail"s, DocumentStatus::ACTUAL, {7, 2, 7});
  488.     search_server.AddDocument(2, "curly dog and fancy collar"s, DocumentStatus::ACTUAL, {1, 2, 3});
  489.     search_server.AddDocument(3, "big cat fancy collar "s, DocumentStatus::ACTUAL, {1, 2, 8});
  490.     search_server.AddDocument(4, "big dog sparrow Eugene"s, DocumentStatus::ACTUAL, {1, 3, 2});
  491.     search_server.AddDocument(5, "big dog sparrow Vasiliy"s, DocumentStatus::ACTUAL, {1, 1, 1});
  492.  
  493.     // 1439 запросов с нулевым результатом
  494.     for (int i = 0; i < 1439; ++i) {
  495.         request_queue.AddFindRequest("empty request"s);
  496.     }
  497.     // все еще 1439 запросов с нулевым результатом
  498.     request_queue.AddFindRequest("curly dog"s);
  499.     // новые сутки, первый запрос удален, 1438 запросов с нулевым результатом
  500.     request_queue.AddFindRequest("big collar"s);
  501.     // первый запрос удален, 1437 запросов с нулевым результатом
  502.     request_queue.AddFindRequest("sparrow"s);
  503.     cout << "Total empty requests: "s << request_queue.GetNoResultRequests() << endl;
  504.     return 0;
  505. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!