diff options
author | mpimenov <mpimenov@users.noreply.github.com> | 2016-09-28 17:39:28 +0300 |
---|---|---|
committer | GitHub <noreply@github.com> | 2016-09-28 17:39:28 +0300 |
commit | 2143577410e715b5867addfb97bb0fdc2c18b170 (patch) | |
tree | a897df805213b862e0af9cffbe691f61f2bcd7a9 | |
parent | a7575ec0e3711220ea49a0786c69e705743d4118 (diff) | |
parent | c9ef1fa3663816af59c09311d0004a0bb546c236 (diff) |
Merge pull request #4390 from ygorshenin/fix-locality-finder
[search] Fixed locality matching code.
-rw-r--r-- | base/base.pro | 4 | ||||
-rw-r--r-- | base/time_samples.cpp | 24 | ||||
-rw-r--r-- | base/time_samples.hpp | 49 | ||||
-rw-r--r-- | base/timer.hpp | 2 | ||||
-rw-r--r-- | indexer/index.hpp | 3 | ||||
-rw-r--r-- | search/categories_cache.cpp | 101 | ||||
-rw-r--r-- | search/categories_cache.hpp | 61 | ||||
-rw-r--r-- | search/geocoder.cpp | 95 | ||||
-rw-r--r-- | search/geocoder.hpp | 21 | ||||
-rw-r--r-- | search/locality_finder.cpp | 255 | ||||
-rw-r--r-- | search/locality_finder.hpp | 49 | ||||
-rw-r--r-- | search/processor.cpp | 8 | ||||
-rw-r--r-- | search/processor.hpp | 4 | ||||
-rw-r--r-- | search/ranker.cpp | 9 | ||||
-rw-r--r-- | search/ranker.hpp | 7 | ||||
-rw-r--r-- | search/search.pro | 2 | ||||
-rw-r--r-- | search/search_integration_tests/pre_ranker_test.cpp | 9 | ||||
-rw-r--r-- | search/search_tests/locality_finder_test.cpp | 16 | ||||
-rw-r--r-- | search/search_tests/locality_selector_test.cpp | 52 | ||||
-rw-r--r-- | search/search_tests/search_tests.pro | 1 |
20 files changed, 515 insertions, 257 deletions
diff --git a/base/base.pro b/base/base.pro index d0976ea2f7..803d1b544a 100644 --- a/base/base.pro +++ b/base/base.pro @@ -10,9 +10,9 @@ include($$ROOT_DIR/common.pri) SOURCES += \ base.cpp \ condition.cpp \ - gmtime.cpp \ deferred_task.cpp \ exception.cpp \ + gmtime.cpp \ internal/message.cpp \ logging.cpp \ lower_case.cpp \ @@ -28,6 +28,7 @@ SOURCES += \ thread_checker.cpp \ thread_pool.cpp \ threaded_container.cpp \ + time_samples.cpp \ timegm.cpp \ timer.cpp \ @@ -81,6 +82,7 @@ HEADERS += \ threaded_container.hpp \ threaded_list.hpp \ threaded_priority_queue.hpp \ + time_samples.hpp \ timegm.hpp \ timer.hpp \ worker_thread.hpp \ diff --git a/base/time_samples.cpp b/base/time_samples.cpp new file mode 100644 index 0000000000..209385b060 --- /dev/null +++ b/base/time_samples.cpp @@ -0,0 +1,24 @@ +#include "base/time_samples.hpp" + +#include "std/cmath.hpp" + +namespace my +{ +void TimeSamples::Add(double seconds) +{ + m_sum += seconds; + m_sum2 += seconds * seconds; + ++m_total; +} + +double TimeSamples::GetMean() const { return m_total == 0 ? 0.0 : m_sum / m_total; } + +double TimeSamples::GetSD() const +{ + if (m_total < 2) + return 0.0; + return std::max((m_sum2 - m_sum * m_sum / static_cast<double>(m_total)) / (m_total - 1), 0.0); +} + +double TimeSamples::GetVar() const { return sqrt(GetSD()); } +} // namespace my diff --git a/base/time_samples.hpp b/base/time_samples.hpp new file mode 100644 index 0000000000..c4f1fdf072 --- /dev/null +++ b/base/time_samples.hpp @@ -0,0 +1,49 @@ +#pragma once + +#include "base/timer.hpp" + +#include "std/cstdint.hpp" + +namespace my +{ +// This class can be used in measurements of code blocks performance. +// It can accumulate time samples, and can calculate mean time and +// standard deviation. +// +// *NOTE* This class is NOT thread-safe. +class TimeSamples final +{ +public: + void Add(double seconds); + + // Mean of the accumulated time samples. + double GetMean() const; + + // Unbiased standard deviation of the accumulated time samples. + double GetSD() const; + + // Unbiased variance of the accumulated time samples. + double GetVar() const; + +private: + double m_sum = 0.0; + double m_sum2 = 0.0; + size_t m_total = 0; +}; + +// This class can be used as a single scoped time sample. It +// automatically adds time sample on destruction. +// +// *NOTE* This class is NOT thread-safe. +class ScopedTimeSample final +{ +public: + ScopedTimeSample(TimeSamples & ts) : m_ts(ts) {} + ~ScopedTimeSample() { m_ts.Add(m_t.ElapsedSeconds()); } + +private: + TimeSamples & m_ts; + my::Timer m_t; +}; + +} // namespace my diff --git a/base/timer.hpp b/base/timer.hpp index bd793f92c1..d64c66a0ac 100644 --- a/base/timer.hpp +++ b/base/timer.hpp @@ -73,4 +73,4 @@ public: time_t SecondsSinceEpochToTimeT(uint64_t secondsSinceEpoch); uint64_t TimeTToSecondsSinceEpoch(time_t time); -} +} // namespace my diff --git a/indexer/index.hpp b/indexer/index.hpp index b593e25b2f..3f43d2b707 100644 --- a/indexer/index.hpp +++ b/indexer/index.hpp @@ -54,6 +54,9 @@ public: inline feature::RegionData const & GetRegionData() const { return m_factory.GetRegionData(); } inline version::MwmVersion const & GetMwmVersion() const { return m_factory.GetMwmVersion(); } inline string const & GetCountryFileName() const { return m_file.GetCountryFile().GetName(); } + + inline bool HasSearchIndex() { return m_cont.IsExist(SEARCH_INDEX_FILE_TAG); } + inline bool HasGeometryIndex() { return m_cont.IsExist(INDEX_FILE_TAG); } }; class Index : public MwmSet diff --git a/search/categories_cache.cpp b/search/categories_cache.cpp new file mode 100644 index 0000000000..214edb360d --- /dev/null +++ b/search/categories_cache.cpp @@ -0,0 +1,101 @@ +#include "search/categories_cache.hpp" + +#include "search/mwm_context.hpp" +#include "search/query_params.hpp" +#include "search/retrieval.hpp" + +#include "indexer/ftypes_matcher.hpp" + +#include "base/assert.hpp" + +#include "std/vector.hpp" + +namespace search +{ +namespace +{ +// Performs pairwise union of adjacent bit vectors +// until at most one bit vector is left. +void UniteCBVs(vector<CBV> & cbvs) +{ + while (cbvs.size() > 1) + { + size_t i = 0; + size_t j = 0; + for (; j + 1 < cbvs.size(); j += 2) + cbvs[i++] = cbvs[j].Union(cbvs[j + 1]); + for (; j < cbvs.size(); ++j) + cbvs[i++] = move(cbvs[j]); + cbvs.resize(i); + } +} +} // namespace + +// CategoriesCache --------------------------------------------------------------------------------- +CategoriesCache::CategoriesCache(CategoriesSet const & categories, + my::Cancellable const & cancellable) + : m_categories(categories), m_cancellable(cancellable) +{ +} + +CBV CategoriesCache::Get(MwmContext const & context) +{ + if (!context.m_handle.IsAlive() || !context.m_value.HasSearchIndex()) + return CBV(); + + auto id = context.m_handle.GetId(); + auto const it = m_cache.find(id); + if (it != m_cache.cend()) + return it->second; + + auto cbv = Load(context); + m_cache[id] = cbv; + return cbv; +} + +CBV CategoriesCache::Load(MwmContext const & context) +{ + ASSERT(context.m_handle.IsAlive(), ()); + ASSERT(context.m_value.HasSearchIndex(), ()); + + QueryParams params; + params.m_tokens.resize(1); + params.m_tokens[0].resize(1); + + params.m_types.resize(1); + params.m_types[0].resize(1); + + vector<CBV> cbvs; + + m_categories.ForEach([&](strings::UniString const & key, uint32_t const type) { + params.m_tokens[0][0] = key; + params.m_types[0][0] = type; + + CBV cbv(RetrieveAddressFeatures(context, m_cancellable, params)); + if (!cbv.IsEmpty()) + cbvs.push_back(move(cbv)); + }); + + UniteCBVs(cbvs); + if (cbvs.empty()) + cbvs.emplace_back(); + + return cbvs[0]; +} + +// StreetsCache ------------------------------------------------------------------------------------ +StreetsCache::StreetsCache(my::Cancellable const & cancellable) + : m_cache(m_categories, cancellable) +{ + ftypes::IsStreetChecker::Instance().ForEachType( + [this](uint32_t type) { m_categories.Add(type); }); +} + +// VillagesCache ----------------------------------------------------------------------------------- +VillagesCache::VillagesCache(my::Cancellable const & cancellable) + : m_cache(m_categories, cancellable) +{ + ftypes::IsVillageChecker::Instance().ForEachType( + [this](uint32_t type) { m_categories.Add(type); }); +} +} // namespace search diff --git a/search/categories_cache.hpp b/search/categories_cache.hpp new file mode 100644 index 0000000000..cf2da9297f --- /dev/null +++ b/search/categories_cache.hpp @@ -0,0 +1,61 @@ +#pragma once + +#include "search/categories_set.hpp" +#include "search/cbv.hpp" + +#include "indexer/mwm_set.hpp" + +#include "base/cancellable.hpp" + +#include "std/map.hpp" + +namespace search +{ +class MwmContext; + +class CategoriesCache +{ +public: + CategoriesCache(CategoriesSet const & categories, my::Cancellable const & cancellable); + + CBV Get(MwmContext const & context); + inline void Clear() { m_cache.clear(); } + +private: + CBV Load(MwmContext const & context); + + CategoriesSet const & m_categories; + my::Cancellable const & m_cancellable; + map<MwmSet::MwmId, CBV> m_cache; +}; + +class StreetsCache +{ + public: + StreetsCache(my::Cancellable const & cancellable); + + inline CBV Get(MwmContext const & context) { return m_cache.Get(context); } + inline void Clear() { m_cache.Clear(); } + inline bool HasCategory(strings::UniString const & category) const + { + return m_categories.HasKey(category); + } + + private: + CategoriesSet m_categories; + CategoriesCache m_cache; +}; + +class VillagesCache +{ + public: + VillagesCache(my::Cancellable const & cancellable); + + inline CBV Get(MwmContext const & context) { return m_cache.Get(context); } + inline void Clear() { m_cache.Clear(); } + +private: + CategoriesSet m_categories; + CategoriesCache m_cache; +}; +} // namespace search diff --git a/search/geocoder.cpp b/search/geocoder.cpp index 2658e33300..5345d18933 100644 --- a/search/geocoder.cpp +++ b/search/geocoder.cpp @@ -205,10 +205,6 @@ WARN_UNUSED_RESULT bool GetAffiliationName(FeatureType const & ft, string & affi return false; } -bool HasSearchIndex(MwmValue const & value) { return value.m_cont.IsExist(SEARCH_INDEX_FILE_TAG); } - -bool HasGeometryIndex(MwmValue & value) { return value.m_cont.IsExist(INDEX_FILE_TAG); } - MwmSet::MwmHandle FindWorld(Index const & index, vector<shared_ptr<MwmInfo>> const & infos) { MwmSet::MwmHandle handle; @@ -335,22 +331,6 @@ size_t OrderCountries(m2::RectD const & pivot, vector<shared_ptr<MwmInfo>> & inf auto const sep = stable_partition(infos.begin(), infos.end(), intersects); return distance(infos.begin(), sep); } - -// Performs pairwise union of adjacent bit vectors -// until at most one bit vector is left. -void UniteCBVs(vector<CBV> & cbvs) -{ - while (cbvs.size() > 1) - { - size_t i = 0; - size_t j = 0; - for (; j + 1 < cbvs.size(); j += 2) - cbvs[i++] = cbvs[j].Union(cbvs[j + 1]); - for (; j < cbvs.size(); ++j) - cbvs[i++] = move(cbvs[j]); - cbvs.resize(i); - } -} } // namespace // Geocoder::Params -------------------------------------------------------------------------------- @@ -358,9 +338,12 @@ Geocoder::Params::Params() : m_mode(Mode::Everywhere) {} // Geocoder::Geocoder ------------------------------------------------------------------------------ Geocoder::Geocoder(Index const & index, storage::CountryInfoGetter const & infoGetter, - PreRanker & preRanker, my::Cancellable const & cancellable) + PreRanker & preRanker, VillagesCache & villagesCache, + my::Cancellable const & cancellable) : m_index(index) , m_infoGetter(infoGetter) + , m_streetsCache(cancellable) + , m_villagesCache(villagesCache) , m_cancellable(cancellable) , m_model(SearchModel::Instance()) , m_pivotRectsCache(kPivotRectsCacheSize, m_cancellable, Processor::kMaxViewportRadiusM) @@ -371,8 +354,6 @@ Geocoder::Geocoder(Index const & index, storage::CountryInfoGetter const & infoG , m_lastMatchedRegion(nullptr) , m_preRanker(preRanker) { - ftypes::IsStreetChecker::Instance().ForEachType([this](uint32_t type) { m_streets.Add(type); }); - ftypes::IsVillageChecker::Instance().ForEachType([this](uint32_t type) { m_villages.Add(type); }); } Geocoder::~Geocoder() {} @@ -398,7 +379,7 @@ void Geocoder::SetParams(Params const & params) m_retrievalParams = m_params; // Remove all category synonyms for streets, as they're extracted - // individually via LoadStreets. + // individually. for (size_t i = 0; i < m_params.GetNumTokens(); ++i) { auto & synonyms = m_params.GetTokens(i); @@ -410,7 +391,7 @@ void Geocoder::SetParams(Params const & params) auto e = synonyms.end(); synonyms.erase(remove_if(b + 1, e, [this](strings::UniString const & synonym) { - return m_streets.HasKey(synonym); + return m_streetsCache.HasCategory(synonym); }), e); } @@ -481,7 +462,7 @@ void Geocoder::GoImpl(vector<shared_ptr<MwmInfo>> & infos, bool inViewport) m_worldId = handle.GetId(); m_context = make_unique<MwmContext>(move(handle)); - if (HasSearchIndex(value)) + if (value.HasSearchIndex()) { BaseContext ctx; InitBaseContext(ctx); @@ -540,7 +521,7 @@ void Geocoder::GoImpl(vector<shared_ptr<MwmInfo>> & infos, bool inViewport) features = features.Intersect(viewportCBV); } - ctx.m_villages = LoadVillages(*m_context); + ctx.m_villages = m_villagesCache.Get(*m_context); auto citiesFromWorld = m_cities; FillVillageLocalities(ctx); @@ -576,7 +557,8 @@ void Geocoder::ClearCaches() m_localityRectsCache.Clear(); m_matchersCache.clear(); - m_streetsCache.clear(); + m_streetsCache.Clear(); + m_villagesCache.Clear(); m_postcodes.Clear(); } @@ -809,7 +791,7 @@ void Geocoder::ForEachCountry(vector<shared_ptr<MwmInfo>> const & infos, TFn && if (!handle.IsAlive()) continue; auto & value = *handle.GetValue<MwmValue>(); - if (!HasSearchIndex(value) || !HasGeometryIndex(value)) + if (!value.HasSearchIndex() || !value.HasGeometryIndex()) continue; fn(i, make_unique<MwmContext>(move(handle))); } @@ -950,7 +932,7 @@ void Geocoder::LimitedSearch(BaseContext & ctx, FeaturesFilter const & filter) }); if (!ctx.m_streets) - ctx.m_streets = LoadStreets(*m_context); + ctx.m_streets = m_streetsCache.Get(*m_context); MatchUnclassified(ctx, 0 /* curToken */); @@ -1364,59 +1346,6 @@ void Geocoder::MatchUnclassified(BaseContext & ctx, size_t curToken) allFeatures.ForEach(emitUnclassified); } -CBV Geocoder::LoadCategories(MwmContext & context, CategoriesSet const & categories) -{ - ASSERT(context.m_handle.IsAlive(), ()); - ASSERT(HasSearchIndex(context.m_value), ()); - - m_retrievalParams.m_tokens.resize(1); - m_retrievalParams.m_tokens[0].resize(1); - - m_retrievalParams.m_prefixTokens.clear(); - - m_retrievalParams.m_types.resize(1); - m_retrievalParams.m_types[0].resize(1); - - vector<CBV> cbvs; - - categories.ForEach([&](strings::UniString const & key, uint32_t const type) { - m_retrievalParams.m_tokens[0][0] = key; - m_retrievalParams.m_types[0][0] = type; - - CBV cbv(RetrieveAddressFeatures(context, m_cancellable, m_retrievalParams)); - if (!cbv.IsEmpty()) - cbvs.push_back(move(cbv)); - }); - - UniteCBVs(cbvs); - if (cbvs.empty()) - cbvs.emplace_back(); - - return move(cbvs[0]); -} - -CBV Geocoder::LoadStreets(MwmContext & context) -{ - if (!context.m_handle.IsAlive() || !HasSearchIndex(context.m_value)) - return CBV(); - - auto mwmId = context.m_handle.GetId(); - auto const it = m_streetsCache.find(mwmId); - if (it != m_streetsCache.cend()) - return it->second; - - auto streets = LoadCategories(context, m_streets); - m_streetsCache[mwmId] = streets; - return streets; -} - -CBV Geocoder::LoadVillages(MwmContext & context) -{ - if (!context.m_handle.IsAlive() || !HasSearchIndex(context.m_value)) - return CBV(); - return LoadCategories(context, m_villages); -} - CBV Geocoder::RetrievePostcodeFeatures(MwmContext const & context, TokenSlice const & slice) { return CBV(::search::RetrievePostcodeFeatures(context, m_cancellable, slice)); diff --git a/search/geocoder.hpp b/search/geocoder.hpp index 715e4250a3..d6b30a1e1d 100644 --- a/search/geocoder.hpp +++ b/search/geocoder.hpp @@ -1,7 +1,8 @@ #pragma once #include "search/cancel_exception.hpp" -#include "search/categories_set.hpp" +#include "search/categories_cache.hpp" +#include "search/cbv.hpp" #include "search/features_layer.hpp" #include "search/features_layer_path_finder.hpp" #include "search/geocoder_context.hpp" @@ -136,7 +137,8 @@ public: }; Geocoder(Index const & index, storage::CountryInfoGetter const & infoGetter, - PreRanker & preRanker, my::Cancellable const & cancellable); + PreRanker & preRanker, VillagesCache & villagesCache, + my::Cancellable const & cancellable); ~Geocoder(); @@ -257,12 +259,6 @@ private: // UNCLASSIFIED objects that match to all currently unused tokens. void MatchUnclassified(BaseContext & ctx, size_t curToken); - CBV LoadCategories(MwmContext & context, CategoriesSet const & categories); - - CBV LoadStreets(MwmContext & context); - - CBV LoadVillages(MwmContext & context); - // A wrapper around RetrievePostcodeFeatures. CBV RetrievePostcodeFeatures(MwmContext const & context, TokenSlice const & slice); @@ -278,10 +274,10 @@ private: storage::CountryInfoGetter const & m_infoGetter; - my::Cancellable const & m_cancellable; + StreetsCache m_streetsCache; + VillagesCache & m_villagesCache; - CategoriesSet m_streets; - CategoriesSet m_villages; + my::Cancellable const & m_cancellable; // Geocoder params. Params m_params; @@ -309,9 +305,6 @@ private: PivotRectsCache m_pivotRectsCache; LocalityRectsCache m_localityRectsCache; - // Cache of street ids in mwms. - map<MwmSet::MwmId, CBV> m_streetsCache; - // Postcodes features in the mwm that is currently being processed. Postcodes m_postcodes; diff --git a/search/locality_finder.cpp b/search/locality_finder.cpp index 92bc5251a5..7621b5f462 100644 --- a/search/locality_finder.cpp +++ b/search/locality_finder.cpp @@ -1,5 +1,7 @@ #include "search/locality_finder.hpp" +#include "search/categories_cache.hpp" +#include "search/cbv.hpp" #include "search/dummy_rank_table.hpp" #include "search/mwm_context.hpp" @@ -16,20 +18,58 @@ namespace search namespace { double const kMaxCityRadiusMeters = 30000.0; -double const kInflateRectMercator = 0.001; -class DoLoader +struct Filter { public: - DoLoader(MwmContext const & ctx, LocalityFinder::Cache & cache, RankTable const & ranks, - int8_t lang) - : m_ctx(ctx), m_cache(cache), m_ranks(ranks), m_lang(lang) + virtual ~Filter() = default; + virtual bool IsGood(uint32_t id) const = 0; +}; + +class CityFilter : public Filter +{ +public: + CityFilter(RankTable const & ranks) : m_ranks(ranks) {} + + // Filter overrides: + bool IsGood(uint32_t id) const override { return m_ranks.Get(id) != 0; } + +private: + RankTable const & m_ranks; +}; + +class VillageFilter : public Filter +{ +public: + VillageFilter(MwmContext const & ctx, VillagesCache & villages) : m_cbv(villages.Get(ctx)) {} + + // Filter overrides: + bool IsGood(uint32_t id) const override { return m_cbv.HasBit(id); } + +private: + CBV m_cbv; +}; + +class LocalitiesLoader +{ +public: + LocalitiesLoader(MwmContext const & ctx, Filter const & filter, int8_t lang, + m4::Tree<LocalityFinder::Item> & localities, + map<MwmSet::MwmId, unordered_set<uint32_t>> & loadedIds) + : m_ctx(ctx) + , m_filter(filter) + , m_lang(lang) + , m_localities(localities) + , m_loadedIds(loadedIds[m_ctx.GetId()]) { } void operator()(uint32_t id) const { - if (m_ranks.Get(id) == 0) + if (m_loadedIds.count(id) != 0) + return; + + if (!m_filter.IsGood(id)) return; FeatureType ft; @@ -43,77 +83,51 @@ public: switch (IsLocalityChecker::Instance().GetType(ft)) { case CITY: - case TOWN: break; - default: // cache only cities and towns at this moment + case TOWN: + case VILLAGE: + break; + default: return; } - if (m_cache.m_loadedIds.count(id) > 0) - return; - uint32_t const population = ftypes::GetPopulation(ft); if (population == 0) return; - double const radius = ftypes::GetRadiusByPopulation(population); - m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(ft.GetCenter(), radius); - if (!rect.IsIntersect(m_cache.m_rect)) - return; - // read item string name; if (!ft.GetName(m_lang, name) && !ft.GetName(0, name)) return; - LocalityItem item(name, population, id); - m_cache.m_tree.Add(item, rect); - m_cache.m_loadedIds.insert(id); + auto const center = ft.GetCenter(); + + LocalityFinder::Item item(name, center, population); + m_localities.Add(item, m2::RectD(center, center)); + m_loadedIds.insert(id); } private: MwmContext const & m_ctx; - LocalityFinder::Cache & m_cache; - RankTable const & m_ranks; + Filter const & m_filter; int8_t const m_lang; -}; - -class DoSelectLocality -{ -public: - DoSelectLocality(string & name, m2::PointD const & pt) - : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max()) - { - } - - void operator()(m2::RectD const & rect, LocalityItem const & item) - { - // TODO (@y, @m): replace this naive score by p-values on - // multivariate Gaussian. - double const distanceMeters = MercatorBounds::DistanceOnEarth(rect.Center(), m_pt); - double const score = - ftypes::GetPopulationByRadius(distanceMeters) / static_cast<double>(item.m_population); - if (score < m_bestScore) - { - m_bestScore = score; - m_name = item.m_name; - } - } -private: - string & m_name; - m2::PointD m_pt; - double m_bestScore; + m4::Tree<LocalityFinder::Item> & m_localities; + unordered_set<uint32_t> & m_loadedIds; }; } // namespace -// LocalityItem ------------------------------------------------------------------------------------ -LocalityItem::LocalityItem(string const & name, uint32_t population, uint32_t id) - : m_name(name), m_population(population), m_id(id) +// LocalityFinder::Item +// ------------------------------------------------------------------------------------ +LocalityFinder::Item::Item(string const & name, m2::PointD const & center, uint32_t population) + : m_name(name), m_center(center), m_population(population) { } // LocalityFinder ---------------------------------------------------------------------------------- -LocalityFinder::LocalityFinder(Index const & index) : m_index(index), m_lang(0) {} +LocalityFinder::LocalityFinder(Index const & index, VillagesCache & villagesCache) + : m_index(index), m_villagesCache(villagesCache), m_lang(0) +{ +} void LocalityFinder::SetLanguage(int8_t lang) { @@ -124,101 +138,98 @@ void LocalityFinder::SetLanguage(int8_t lang) m_lang = lang; } -void LocalityFinder::UpdateCache(Cache & cache, m2::PointD const & pt) +void LocalityFinder::GetLocality(m2::PointD const & pt, string & name) { - m2::RectD rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters); - if (cache.m_rect.IsRectInside(rect)) - return; - - rect.Add(cache.m_rect); - rect.Inflate(kInflateRectMercator, kInflateRectMercator); + m2::RectD const rect = MercatorBounds::RectByCenterXYAndSizeInMeters(pt, kMaxCityRadiusMeters); - if (!m_worldId.IsAlive()) - { - m_worldId.Reset(); - m_ranks.reset(); + bool covered = false; + m_coverage.ForEachInRect(rect, [&covered](bool) { covered = true; }); + if (!covered) + LoadVicinity(pt); - vector<shared_ptr<MwmInfo>> mwmsInfo; - m_index.GetMwmsInfo(mwmsInfo); - for (auto const & info : mwmsInfo) - { - MwmSet::MwmId id(info); - Index::MwmHandle handle = m_index.GetMwmHandleById(id); - MwmValue const * value = handle.GetValue<MwmValue>(); - if (handle.IsAlive() && value->GetHeader().GetType() == feature::DataHeader::world) - { - m_worldId = id; - m_ranks = RankTable::Load(value->m_cont); - break; - } - } - - if (!m_ranks) - m_ranks = make_unique<DummyRankTable>(); - } - - ASSERT(m_ranks.get(), ()); - - Index::MwmHandle handle = m_index.GetMwmHandleById(m_worldId); - if (!handle.IsAlive()) - return; + m_localities.ForEachInRect(rect, LocalitySelector(name, pt)); +} - cache.m_rect = rect; - MwmContext ctx(move(handle)); - ctx.ForEachIndex(rect, DoLoader(ctx, cache, *m_ranks, m_lang)); +void LocalityFinder::ClearCache() +{ + m_ranks.reset(); + m_coverage.Clear(); + m_localities.Clear(); + m_loadedIds.clear(); } -void LocalityFinder::GetLocality(m2::PointD const & pt, string & name) +void LocalityFinder::LoadVicinity(m2::PointD const & pt) { - Cache * working = nullptr; + m2::RectD const drect = + MercatorBounds::RectByCenterXYAndSizeInMeters(pt, 2 * kMaxCityRadiusMeters); - // Find suitable cache that includes needed point. - for (auto & cache : m_caches) + vector<shared_ptr<MwmInfo>> mwmsInfo; + m_index.GetMwmsInfo(mwmsInfo); + for (auto const & info : mwmsInfo) { - if (cache.m_rect.IsPointInside(pt)) + MwmSet::MwmId id(info); + Index::MwmHandle handle = m_index.GetMwmHandleById(id); + + if (!handle.IsAlive()) + continue; + + MwmValue const & value = *handle.GetValue<MwmValue>(); + auto const & header = value.GetHeader(); + switch (header.GetType()) { - working = &cache; + case feature::DataHeader::world: + { + if (!m_ranks) + m_ranks = RankTable::Load(value.m_cont); + if (!m_ranks) + m_ranks = make_unique<DummyRankTable>(); + + MwmContext ctx(move(handle)); + ctx.ForEachIndex( + drect, LocalitiesLoader(ctx, CityFilter(*m_ranks), m_lang, m_localities, m_loadedIds)); break; } + case feature::DataHeader::country: + if (header.GetBounds().IsPointInside(pt)) + { + MwmContext ctx(move(handle)); + ctx.ForEachIndex(drect, LocalitiesLoader(ctx, VillageFilter(ctx, m_villagesCache), m_lang, + m_localities, m_loadedIds)); + } + break; + case feature::DataHeader::worldcoasts: break; + } } - if (working == nullptr) - { - // Find most unused cache. - working = - &*min_element(begin(m_caches), end(m_caches), my::LessBy(&LocalityFinder::Cache::m_usage)); - working->Clear(); - } - - UpdateCache(*working, pt); - working->GetLocality(pt, name); + m_coverage.Add(true, m2::RectD(pt, pt)); } -void LocalityFinder::ClearCache() +// LocalitySelector -------------------------------------------------------------------------------- +LocalitySelector::LocalitySelector(string & name, m2::PointD const & pt) + : m_name(name), m_pt(pt), m_bestScore(numeric_limits<double>::max()) { - for (auto & cache : m_caches) - cache.Clear(); } -// LocalityFinder::Cache --------------------------------------------------------------------------- -void LocalityFinder::Cache::Clear() +void LocalitySelector::operator()(LocalityFinder::Item const & item) { - m_usage = 0; - m_tree.Clear(); - m_loadedIds.clear(); - m_rect.MakeEmpty(); -} + // TODO (@y, @m): replace this naive score by p-values on + // multivariate Gaussian. + double const distance = MercatorBounds::DistanceOnEarth(item.m_center, m_pt); -void LocalityFinder::Cache::GetLocality(m2::PointD const & pt, string & name) -{ - ++m_usage; - m_tree.ForEachInRectEx(m2::RectD(pt, pt), DoSelectLocality(name, pt)); + double const score = + ftypes::GetPopulationByRadius(distance) / static_cast<double>(item.m_population); + if (score < m_bestScore) + { + m_bestScore = score; + m_name = item.m_name; + } } -string DebugPrint(LocalityItem const & item) +string DebugPrint(LocalityFinder::Item const & item) { stringstream ss; - ss << "Name = " << item.m_name << "Population = " << item.m_population << "ID = " << item.m_id; + ss << "Name = " << item.m_name << ", Center = " << DebugPrint(item.m_center) + << ", Population = " << item.m_population; return ss.str(); } } // namespace search diff --git a/search/locality_finder.hpp b/search/locality_finder.hpp index bef8c5b5be..913971ac90 100644 --- a/search/locality_finder.hpp +++ b/search/locality_finder.hpp @@ -7,52 +7,59 @@ #include "geometry/rect2d.hpp" #include "geometry/tree4d.hpp" -#include "std/set.hpp" #include "std/unique_ptr.hpp" +#include "std/unordered_set.hpp" class Index; namespace search { -struct LocalityItem -{ - LocalityItem(string const & name, uint32_t population, uint32_t id); - - string m_name; - uint32_t m_population; - uint32_t m_id; -}; +class VillagesCache; class LocalityFinder { public: - struct Cache + struct Item { - void Clear(); - void GetLocality(m2::PointD const & pt, string & name); + Item(string const & name, m2::PointD const & center, uint32_t population); - m4::Tree<LocalityItem> m_tree; - set<uint32_t> m_loadedIds; - size_t m_usage = 0; - m2::RectD m_rect; + string m_name; + m2::PointD m_center; + uint32_t m_population; }; - LocalityFinder(Index const & index); + LocalityFinder(Index const & index, VillagesCache & villagesCache); void SetLanguage(int8_t lang); void GetLocality(m2::PointD const & pt, string & name); void ClearCache(); private: - void UpdateCache(Cache & cache, m2::PointD const & pt); + void LoadVicinity(m2::PointD const & pt); Index const & m_index; - MwmSet::MwmId m_worldId; + VillagesCache & m_villagesCache; unique_ptr<RankTable> m_ranks; - Cache m_caches[10]; + m4::Tree<bool> m_coverage; + m4::Tree<Item> m_localities; + map<MwmSet::MwmId, unordered_set<uint32_t>> m_loadedIds; + int8_t m_lang; }; -string DebugPrint(LocalityItem const & item); +class LocalitySelector +{ +public: + LocalitySelector(string & name, m2::PointD const & pt); + + void operator()(LocalityFinder::Item const & item); + +private: + string & m_name; + m2::PointD m_pt; + double m_bestScore; +}; + +string DebugPrint(LocalityFinder::Item const & item); } // namespace search diff --git a/search/processor.cpp b/search/processor.cpp index 4c96b0c704..e076df2e96 100644 --- a/search/processor.cpp +++ b/search/processor.cpp @@ -147,10 +147,14 @@ Processor::Processor(Index const & index, CategoriesHolder const & categories, , m_minDistanceOnMapBetweenResults(0.0) , m_mode(Mode::Everywhere) , m_suggestsEnabled(true) - , m_ranker(index, infoGetter, m_emitter, categories, suggests, + , m_supportOldFormat(false) + , m_viewportSearch(false) + , m_villagesCache(static_cast<my::Cancellable const &>(*this)) + , m_ranker(index, infoGetter, m_emitter, categories, suggests, m_villagesCache, static_cast<my::Cancellable const &>(*this)) , m_preRanker(index, m_ranker, kPreResultsCount) - , m_geocoder(index, infoGetter, m_preRanker, static_cast<my::Cancellable const &>(*this)) + , m_geocoder(index, infoGetter, m_preRanker, m_villagesCache, + static_cast<my::Cancellable const &>(*this)) { // Initialize keywords scorer. // Note! This order should match the indexes arrays above. diff --git a/search/processor.hpp b/search/processor.hpp index 9ce7f8de9c..0aa694a3af 100644 --- a/search/processor.hpp +++ b/search/processor.hpp @@ -1,4 +1,6 @@ #pragma once +#include "search/categories_cache.hpp" +#include "search/categories_set.hpp" #include "search/emitter.hpp" #include "search/geocoder.hpp" #include "search/mode.hpp" @@ -176,6 +178,8 @@ protected: protected: bool m_viewportSearch; + VillagesCache m_villagesCache; + Emitter m_emitter; Ranker m_ranker; PreRanker m_preRanker; diff --git a/search/ranker.cpp b/search/ranker.cpp index 1c308b24dc..9c2b5d2c58 100644 --- a/search/ranker.cpp +++ b/search/ranker.cpp @@ -279,10 +279,11 @@ size_t const Ranker::kBatchSize = 10; Ranker::Ranker(Index const & index, storage::CountryInfoGetter const & infoGetter, Emitter & emitter, CategoriesHolder const & categories, - vector<Suggest> const & suggests, my::Cancellable const & cancellable) + vector<Suggest> const & suggests, VillagesCache & villagesCache, + my::Cancellable const & cancellable) : m_reverseGeocoder(index) , m_cancellable(cancellable) - , m_locality(index) + , m_localities(index, villagesCache) , m_index(index) , m_infoGetter(infoGetter) , m_emitter(emitter) @@ -342,7 +343,7 @@ Result Ranker::MakeResult(PreResult2 const & r) const if (ftypes::IsLocalityChecker::Instance().GetType(r.GetTypes()) == ftypes::NONE) { string city; - m_locality.GetLocality(res.GetFeatureCenter(), city); + m_localities.GetLocality(res.GetFeatureCenter(), city); res.AppendCity(city); } @@ -547,6 +548,6 @@ void Ranker::UpdateResults(bool lastUpdate) void Ranker::ClearCaches() { - m_locality.ClearCache(); + m_localities.ClearCache(); } } // namespace search diff --git a/search/ranker.hpp b/search/ranker.hpp index b4e0687315..0f1950f37b 100644 --- a/search/ranker.hpp +++ b/search/ranker.hpp @@ -34,6 +34,7 @@ class CountryInfoGetter; namespace search { +class VillagesCache; class Emitter; class PreResult2Maker; @@ -73,7 +74,7 @@ public: Ranker(Index const & index, storage::CountryInfoGetter const & infoGetter, Emitter & emitter, CategoriesHolder const & categories, vector<Suggest> const & suggests, - my::Cancellable const & cancellable); + VillagesCache & villagesCache, my::Cancellable const & cancellable); virtual ~Ranker() = default; void Init(Params const & params, Geocoder::Params const & geocoderParams); @@ -97,7 +98,7 @@ public: void ClearCaches(); - inline void SetLocalityFinderLanguage(int8_t code) { m_locality.SetLanguage(code); } + inline void SetLocalityFinderLanguage(int8_t code) { m_localities.SetLanguage(code); } inline void SetLanguage(pair<int, int> const & ind, int8_t lang) { @@ -131,7 +132,7 @@ private: my::Cancellable const & m_cancellable; KeywordLangMatcher m_keywordsScorer; - mutable LocalityFinder m_locality; + mutable LocalityFinder m_localities; Index const & m_index; storage::CountryInfoGetter const & m_infoGetter; diff --git a/search/search.pro b/search/search.pro index eadec170f1..8d747347aa 100644 --- a/search/search.pro +++ b/search/search.pro @@ -12,6 +12,7 @@ HEADERS += \ algos.hpp \ approximate_string_match.hpp \ cancel_exception.hpp \ + categories_cache.hpp \ categories_set.hpp \ cbv.hpp \ common.hpp \ @@ -81,6 +82,7 @@ HEADERS += \ SOURCES += \ approximate_string_match.cpp \ + categories_cache.cpp \ cbv.cpp \ displayed_categories.cpp \ downloader_search_callback.cpp \ diff --git a/search/search_integration_tests/pre_ranker_test.cpp b/search/search_integration_tests/pre_ranker_test.cpp index 50094d1c4e..b67ce9488c 100644 --- a/search/search_integration_tests/pre_ranker_test.cpp +++ b/search/search_integration_tests/pre_ranker_test.cpp @@ -1,5 +1,6 @@ #include "testing/testing.hpp" +#include "search/categories_cache.hpp" #include "search/emitter.hpp" #include "search/intermediate_result.hpp" #include "search/model.hpp" @@ -44,9 +45,10 @@ class TestRanker : public Ranker { public: TestRanker(TestSearchEngine & engine, Emitter & emitter, vector<Suggest> const & suggests, - my::Cancellable const & cancellable, vector<PreResult1> & results) + VillagesCache & villagesCache, my::Cancellable const & cancellable, + vector<PreResult1> & results) : Ranker(static_cast<Index const &>(engine), engine.GetCountryInfoGetter(), emitter, - GetDefaultCategories(), suggests, cancellable) + GetDefaultCategories(), suggests, villagesCache, cancellable) , m_results(results) { } @@ -111,7 +113,8 @@ UNIT_CLASS_TEST(PreRankerTest, Smoke) vector<PreResult1> results; Emitter emitter; - TestRanker ranker(m_engine, emitter, m_suggests, m_cancellable, results); + VillagesCache villagesCache(m_cancellable); + TestRanker ranker(m_engine, emitter, m_suggests, villagesCache, m_cancellable, results); PreRanker preRanker(m_engine, ranker, pois.size()); PreRanker::Params params; diff --git a/search/search_tests/locality_finder_test.cpp b/search/search_tests/locality_finder_test.cpp index 3a615fe2c4..eb5847b6b5 100644 --- a/search/search_tests/locality_finder_test.cpp +++ b/search/search_tests/locality_finder_test.cpp @@ -4,6 +4,7 @@ #include "indexer/index.hpp" #include "indexer/classificator_loader.hpp" +#include "search/categories_cache.hpp" #include "search/locality_finder.hpp" #include "platform/country_file.hpp" @@ -11,21 +12,30 @@ #include "platform/local_country_file_utils.hpp" #include "platform/platform.hpp" +#include "base/cancellable.hpp" namespace { +struct TestWithClassificator +{ + TestWithClassificator() { classificator::Load(); } +}; -class LocalityFinderTest +class LocalityFinderTest : public TestWithClassificator { platform::LocalCountryFile m_worldFile; + Index m_index; + + my::Cancellable m_cancellable; + search::VillagesCache m_villagesCache; + search::LocalityFinder m_finder; m2::RectD m_worldRect; public: - LocalityFinderTest() : m_finder(m_index) + LocalityFinderTest() : m_villagesCache(m_cancellable), m_finder(m_index, m_villagesCache) { - classificator::Load(); m_worldFile = platform::LocalCountryFile::MakeForTesting("World"); try diff --git a/search/search_tests/locality_selector_test.cpp b/search/search_tests/locality_selector_test.cpp new file mode 100644 index 0000000000..53c7659cf4 --- /dev/null +++ b/search/search_tests/locality_selector_test.cpp @@ -0,0 +1,52 @@ +#include "testing/testing.hpp" + +#include "search/locality_finder.hpp" + +using namespace search; + +namespace +{ +string GetMatchedCity(m2::PointD const & point, vector<LocalityFinder::Item> const & items) +{ + string name; + LocalitySelector selector(name, point); + for (auto const & item : items) + selector(item); + return name; +} + +// TODO (@y): this test fails for now. Need to uncomment it as soon as +// locality finder will be fixed. +// +// UNIT_TEST(LocalitySelector_Test1) +// { +// auto const name = GetMatchedCity( +// m2::PointD(-97.563458662952925238, 26.796728721236661386), +// {{"Matamoros", m2::PointD(-97.506656349498797454, 26.797180986068354969), 10000}, + +// {"Brownsville", m2::PointD(-97.489103971612919963, 26.845589500139880101), 180663}}); +// TEST_EQUAL(name, "Matamoros", ()); +// } + +UNIT_TEST(LocalitySelector_Test2) +{ + vector<LocalityFinder::Item> const localities = { + {"Moscow", m2::PointD(37.617513849438893203, 67.45398133444564337), 11971516}, + {"Krasnogorsk", m2::PointD(37.340409438658895169, 67.58036703829372982), 135735}, + {"Khimki", m2::PointD(37.444994145035053634, 67.700701677882875629), 240463}, + {"Mytishchi", m2::PointD(37.733943192236807818, 67.736750571340394345), 180663}, + {"Dolgoprudny", m2::PointD(37.514259518892714595, 67.780738804428438016), 101979}}; + + { + auto const name = + GetMatchedCity(m2::PointD(37.538269143836714647, 67.535546478148901883), localities); + TEST_EQUAL(name, "Moscow", ()); + } + + { + auto const name = + GetMatchedCity(m2::PointD(37.469807099326018829, 67.666502652067720192), localities); + TEST_EQUAL(name, "Khimki", ()); + } +} +} // namespace diff --git a/search/search_tests/search_tests.pro b/search/search_tests/search_tests.pro index b08d6416e4..2bd4c2eddd 100644 --- a/search/search_tests/search_tests.pro +++ b/search/search_tests/search_tests.pro @@ -27,6 +27,7 @@ SOURCES += \ latlon_match_test.cpp \ locality_finder_test.cpp \ locality_scorer_test.cpp \ + locality_selector_test.cpp \ nearby_points_sweeper_test.cpp \ query_saver_tests.cpp \ ranking_tests.cpp \ |