diff options
author | Maxim Pimenov <m@maps.me> | 2016-07-08 16:56:15 +0300 |
---|---|---|
committer | Maxim Pimenov <m@maps.me> | 2016-07-15 17:13:35 +0300 |
commit | 333a4241832650a7fccd36b33c81b173cf2c6d9e (patch) | |
tree | 22ae64d199c190c124ae46992719b9dce70a5804 /search | |
parent | b872098f3e5c30d18e15e97097d01b0e6fc83534 (diff) |
[search] Implemented batching of search results.search-results-batching
Diffstat (limited to 'search')
-rw-r--r-- | search/geocoder.cpp | 7 | ||||
-rw-r--r-- | search/pre_ranker.cpp | 25 | ||||
-rw-r--r-- | search/pre_ranker.hpp | 26 | ||||
-rw-r--r-- | search/processor.cpp | 12 | ||||
-rw-r--r-- | search/processor.hpp | 2 | ||||
-rw-r--r-- | search/ranker.cpp | 82 | ||||
-rw-r--r-- | search/ranker.hpp | 11 |
7 files changed, 102 insertions, 63 deletions
diff --git a/search/geocoder.cpp b/search/geocoder.cpp index 74ae905ba4..f808b30609 100644 --- a/search/geocoder.cpp +++ b/search/geocoder.cpp @@ -604,14 +604,17 @@ void Geocoder::GoImpl(vector<shared_ptr<MwmInfo>> & infos, bool inViewport) m_lastMatchedRegion = nullptr; MatchRegions(ctx, REGION_TYPE_COUNTRY); - if (index < numIntersectingMaps || m_preRanker.IsEmpty()) + if (index < numIntersectingMaps || m_preRanker.NumSentResults() == 0) MatchAroundPivot(ctx); + + if (index + 1 >= numIntersectingMaps) + m_preRanker.UpdateResults(false /* lastUpdate */); }; // Iterates through all alive mwms and performs geocoding. ForEachCountry(infos, processCountry); - m_preRanker.FinalizeResults(); + m_preRanker.UpdateResults(true /* lastUpdate */); } catch (CancelException & e) { diff --git a/search/pre_ranker.cpp b/search/pre_ranker.cpp index 8eb94a74a2..1f6efbaa04 100644 --- a/search/pre_ranker.cpp +++ b/search/pre_ranker.cpp @@ -46,12 +46,15 @@ struct ComparePreResult1 }; } // namespace +// static +size_t const PreRanker::kBatchSize = 100; + PreRanker::PreRanker(Index const & index, Ranker & ranker, size_t limit) : m_index(index), m_ranker(ranker), m_limit(limit), m_pivotFeatures(index) { } -void PreRanker::FillMissingFieldsInResults() +void PreRanker::FillMissingFieldsInPreResults() { MwmSet::MwmId mwmId; MwmSet::MwmHandle mwmHandle; @@ -76,7 +79,7 @@ void PreRanker::FillMissingFieldsInResults() info.m_rank = rankTable->Get(id.m_index); }); - if (Size() <= Limit()) + if (Size() <= kBatchSize) return; m_pivotFeatures.SetPosition(m_params.m_accuratePivotCenter, m_params.m_scale); @@ -99,7 +102,7 @@ void PreRanker::Filter(bool viewportSearch) sort(m_results.begin(), m_results.end(), &PreResult1::LessDistance); - if (m_limit != 0 && m_results.size() > m_limit) + if (m_results.size() > kBatchSize) { // Priority is some kind of distance from the viewport or // position, therefore if we have a bunch of results with the same @@ -108,15 +111,15 @@ void PreRanker::Filter(bool viewportSearch) // feature id) this code randomly selects tail of the // sorted-by-priority list of pre-results. - double const last = m_results[m_limit - 1].GetDistance(); + double const last = m_results[kBatchSize - 1].GetDistance(); - auto b = m_results.begin() + m_limit - 1; + auto b = m_results.begin() + kBatchSize - 1; for (; b != m_results.begin() && b->GetDistance() == last; --b) ; if (b->GetDistance() != last) ++b; - auto e = m_results.begin() + m_limit; + auto e = m_results.begin() + kBatchSize; for (; e != m_results.end() && e->GetDistance() == last; ++e) ; @@ -132,11 +135,11 @@ void PreRanker::Filter(bool viewportSearch) minstd_rand engine; shuffle(b, e, engine); } - filtered.insert(m_results.begin(), m_results.begin() + min(m_results.size(), m_limit)); + filtered.insert(m_results.begin(), m_results.begin() + min(m_results.size(), kBatchSize)); if (!viewportSearch) { - size_t n = min(m_results.size(), m_limit); + size_t n = min(m_results.size(), kBatchSize); nth_element(m_results.begin(), m_results.begin() + n, m_results.end(), &PreResult1::LessRank); filtered.insert(m_results.begin(), m_results.begin() + n); } @@ -146,12 +149,14 @@ void PreRanker::Filter(bool viewportSearch) copy(filtered.begin(), filtered.end(), back_inserter(m_results)); } -void PreRanker::FinalizeResults() +void PreRanker::UpdateResults(bool lastUpdate) { - FillMissingFieldsInResults(); + FillMissingFieldsInPreResults(); Filter(m_viewportSearch); + m_numSentResults += m_results.size(); m_ranker.SetPreResults1(move(m_results)); m_results.clear(); + m_ranker.UpdateResults(lastUpdate); } void PreRanker::ClearCaches() { m_pivotFeatures.Clear(); } diff --git a/search/pre_ranker.hpp b/search/pre_ranker.hpp index 7c55c9e269..58ff6c39b7 100644 --- a/search/pre_ranker.hpp +++ b/search/pre_ranker.hpp @@ -34,9 +34,16 @@ public: int m_scale = 0; }; + static size_t const kBatchSize; + PreRanker(Index const & index, Ranker & ranker, size_t limit); - inline void Init(Params const & params) { m_params = params; } + inline void Init(Params const & params) + { + m_numSentResults = 0; + m_params = params; + } + inline void SetViewportSearch(bool viewportSearch) { m_viewportSearch = viewportSearch; } inline void SetAccuratePivotCenter(m2::PointD const & center) { @@ -46,22 +53,24 @@ public: template <typename... TArgs> void Emplace(TArgs &&... args) { + if (m_numSentResults >= m_limit) + return; m_results.emplace_back(forward<TArgs>(args)...); } - // Computes missing fields for all results. - void FillMissingFieldsInResults(); + // Computes missing fields for all pre-results. + void FillMissingFieldsInPreResults(); void Filter(bool viewportSearch); - // This function is used in geocoder to indicate that + // Emit a new batch of results up the pipeline (i.e. to ranker). + // Use lastUpdate in geocoder to indicate that // no more results will be added. - void FinalizeResults(); + void UpdateResults(bool lastUpdate); inline size_t Size() const { return m_results.size(); } + inline size_t NumSentResults() const { return m_numSentResults; } inline size_t Limit() const { return m_limit; } - inline bool IsEmpty() const { return Size() == 0; } - inline void Clear() { m_results.clear(); }; template <typename TFn> void ForEach(TFn && fn) @@ -79,6 +88,9 @@ private: Params m_params; bool m_viewportSearch = false; + // Amount of results sent up the pipeline. + size_t m_numSentResults = 0; + // Cache of nested rects used to estimate distance from a feature to the pivot. NestedRectsCache m_pivotFeatures; diff --git a/search/processor.cpp b/search/processor.cpp index b3cc1e97f0..0a7c40b146 100644 --- a/search/processor.cpp +++ b/search/processor.cpp @@ -165,7 +165,6 @@ void Processor::Init(bool viewportSearch) { m_tokens.clear(); m_prefix.clear(); - m_preRanker.Clear(); m_preRanker.SetViewportSearch(viewportSearch); } @@ -407,7 +406,7 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport) InitGeocoder(geocoderParams); InitPreRanker(geocoderParams); - InitRanker(); + InitRanker(geocoderParams); try { @@ -426,7 +425,6 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport) if (viewportSearch) { m_geocoder.GoInViewport(); - m_ranker.FlushViewportResults(geocoderParams); } else { @@ -434,9 +432,10 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport) m_ranker.SuggestStrings(m_ranker.GetResults()); m_geocoder.GoEverywhere(); - m_ranker.FlushResults(geocoderParams); } + m_ranker.FlushResults(); + if (!IsCancelled()) params.m_onResults(m_ranker.GetResults()); } @@ -688,7 +687,7 @@ void Processor::InitPreRanker(Geocoder::Params const & geocoderParams) m_preRanker.Init(params); } -void Processor::InitRanker() +void Processor::InitRanker(Geocoder::Params const & geocoderParams) { size_t const kResultsCount = 30; bool const viewportSearch = m_mode == Mode::Viewport; @@ -713,8 +712,9 @@ void Processor::InitRanker() params.m_prefix = m_prefix; params.m_categoryLocales = GetCategoryLocales(); params.m_accuratePivotCenter = GetPivotPoint(); + params.m_viewportSearch = viewportSearch; params.m_onResults = m_onResults; - m_ranker.Init(params); + m_ranker.Init(params, geocoderParams); } void Processor::ClearCaches() diff --git a/search/processor.hpp b/search/processor.hpp index be70b433b9..ddc340556e 100644 --- a/search/processor.hpp +++ b/search/processor.hpp @@ -100,7 +100,7 @@ public: void InitParams(QueryParams & params); void InitGeocoder(Geocoder::Params & params); void InitPreRanker(Geocoder::Params const & geocoderParams); - void InitRanker(); + void InitRanker(Geocoder::Params const & geocoderParams); void ClearCaches(); diff --git a/search/ranker.cpp b/search/ranker.cpp index 1b12aecb38..800d8ad934 100644 --- a/search/ranker.cpp +++ b/search/ranker.cpp @@ -8,6 +8,7 @@ #include "base/logging.hpp" #include "std/algorithm.hpp" +#include "std/iterator.hpp" #include "std/unique_ptr.hpp" namespace search @@ -130,6 +131,9 @@ public: }; } // namespace +// static +size_t const Ranker::kBatchSize = 10; + class PreResult2Maker { Ranker & m_ranker; @@ -284,10 +288,12 @@ Ranker::Ranker(Index const & index, storage::CountryInfoGetter const & infoGette { } -void Ranker::Init(Params const & params) +void Ranker::Init(Params const & params, Geocoder::Params const & geocoderParams) { m_params = params; + m_geocoderParams = geocoderParams; m_preResults1.clear(); + m_leftovers.clear(); m_results.Clear(); } @@ -477,56 +483,64 @@ void Ranker::ProcessSuggestions(vector<IndexedValue> & vec, Results & res) const } } -void Ranker::FlushResults(Geocoder::Params const & params) +void Ranker::UpdateResults(bool lastUpdate) { - vector<IndexedValue> values; + BailIfCancelled(); + + vector<IndexedValue> values = move(m_leftovers); + m_leftovers.clear(); vector<FeatureID> streets; - MakePreResult2(params, values, streets); + MakePreResult2(m_geocoderParams, values, streets); RemoveDuplicatingLinear(values); if (values.empty()) return; - sort(values.rbegin(), values.rend(), my::LessBy(&IndexedValue::GetRank)); - - ProcessSuggestions(values, m_results); + if (m_params.m_viewportSearch) + { + sort(values.begin(), values.end(), my::LessBy(&IndexedValue::GetDistanceToPivot)); + } + else + { + sort(values.rbegin(), values.rend(), my::LessBy(&IndexedValue::GetRank)); + ProcessSuggestions(values, m_results); + } // Emit feature results. size_t count = m_results.GetCount(); - for (size_t i = 0; i < values.size() && count < m_params.m_limit; ++i) + size_t i; + for (i = 0; i < values.size(); ++i) { + if (!lastUpdate && i >= kBatchSize && !m_params.m_viewportSearch) + break; BailIfCancelled(); - LOG(LDEBUG, (values[i])); - - auto const & preResult2 = *values[i]; - if (m_results.AddResult(MakeResult(preResult2))) - ++count; - } -} - -void Ranker::FlushViewportResults(Geocoder::Params const & geocoderParams) -{ - vector<IndexedValue> values; - vector<FeatureID> streets; - MakePreResult2(geocoderParams, values, streets); - RemoveDuplicatingLinear(values); - if (values.empty()) - return; - - sort(values.begin(), values.end(), my::LessBy(&IndexedValue::GetDistanceToPivot)); + if (m_params.m_viewportSearch) + { + m_results.AddResultNoChecks( + (*(values[i])) + .GenerateFinalResult(m_infoGetter, &m_categories, &m_params.m_preferredTypes, + m_params.m_currentLocaleCode, + nullptr /* Viewport results don't need calculated address */)); + } + else + { + if (count >= m_params.m_limit) + break; - for (size_t i = 0; i < values.size(); ++i) - { - BailIfCancelled(); + LOG(LDEBUG, (values[i])); - m_results.AddResultNoChecks( - (*(values[i])) - .GenerateFinalResult(m_infoGetter, &m_categories, &m_params.m_preferredTypes, - m_params.m_currentLocaleCode, - nullptr /* Viewport results don't need calculated address */)); + auto const & preResult2 = *values[i]; + if (m_results.AddResult(MakeResult(preResult2))) + ++count; + } } + move(values.begin() + i, values.end(), back_inserter(m_leftovers)); + + m_preResults1.clear(); + m_params.m_onResults(m_results); } +void Ranker::FlushResults() { UpdateResults(true /* lastUpdate */); } void Ranker::ClearCaches() { m_locality.ClearCache(); diff --git a/search/ranker.hpp b/search/ranker.hpp index f753c8e984..04fc003ae9 100644 --- a/search/ranker.hpp +++ b/search/ranker.hpp @@ -49,6 +49,7 @@ public: string m_pivotRegion; set<uint32_t> m_preferredTypes; bool m_suggestsEnabled = false; + bool m_viewportSearch = false; string m_query; buffer_vector<strings::UniString, 32> m_tokens; @@ -64,11 +65,13 @@ public: TOnResults m_onResults; }; + static size_t const kBatchSize; + Ranker(Index const & index, storage::CountryInfoGetter const & infoGetter, CategoriesHolder const & categories, vector<Suggest> const & suggests, my::Cancellable const & cancellable); - void Init(Params const & params); + void Init(Params const & params, Geocoder::Params const & geocoderParams); inline void SetAccuratePivotCenter(m2::PointD const & center) { @@ -91,8 +94,8 @@ public: void ProcessSuggestions(vector<IndexedValue> & vec, Results & res) const; Results & GetResults() { return m_results; } - void FlushResults(Geocoder::Params const & geocoderParams); - void FlushViewportResults(Geocoder::Params const & geocoderParams); + void UpdateResults(bool lastUpdate); + void FlushResults(); void SetPreResults1(vector<PreResult1> && preResults1) { m_preResults1 = move(preResults1); } void ClearCaches(); @@ -126,6 +129,7 @@ private: friend class PreResult2Maker; Params m_params; + Geocoder::Params m_geocoderParams; ReverseGeocoder const m_reverseGeocoder; my::Cancellable const & m_cancellable; KeywordLangMatcher m_keywordsScorer; @@ -138,6 +142,7 @@ private: vector<Suggest> const & m_suggests; vector<PreResult1> m_preResults1; + vector<IndexedValue> m_leftovers; Results m_results; }; } // namespace search |