1 // Copyright 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "chrome/browser/ui/app_list/search/search_result_ranker/frecency_store.h"
6
7 #include <algorithm>
8 #include <cmath>
9 #include <limits>
10 #include <utility>
11
12 #include "base/logging.h"
13 #include "base/stl_util.h"
14 #include "chrome/browser/ui/app_list/search/search_result_ranker/frecency_store.pb.h"
15
16 namespace app_list {
17
18 namespace {
19
20 // The lowest a value's score is allowed to be before it is deleted regardless
21 // of how full the store is.
22 static constexpr float kMinScoreBeforeDelete =
23 std::numeric_limits<float>::epsilon();
24
25 } // namespace
26
FrecencyStore(int value_limit,float decay_coeff)27 FrecencyStore::FrecencyStore(int value_limit, float decay_coeff)
28 : value_limit_(value_limit), decay_coeff_(decay_coeff) {
29 if (decay_coeff <= 0.0f || decay_coeff >= 1.0f) {
30 LOG(ERROR) << "FrecencyStore decay_coeff has invalid value: " << decay_coeff
31 << ", resetting to default.";
32 decay_coeff_ = 0.75f;
33 }
34 }
35
~FrecencyStore()36 FrecencyStore::~FrecencyStore() {}
37
Update(const std::string & value)38 unsigned int FrecencyStore::Update(const std::string& value) {
39 if (static_cast<unsigned int>(values_.size()) >= 2 * value_limit_)
40 Cleanup();
41
42 ValueData* data;
43 auto it = values_.find(value);
44 if (it != values_.end()) {
45 data = &it->second;
46 } else {
47 auto ret = values_.insert(std::pair<std::string, FrecencyStore::ValueData>(
48 value, {next_id_++, 0.0f, 0u}));
49 DCHECK(ret.second);
50 data = &ret.first->second;
51 }
52
53 ++num_updates_;
54 DecayScore(data);
55 data->last_score += 1.0f - decay_coeff_;
56
57 return data->id;
58 }
59
Rename(const std::string & value,const std::string & new_value)60 void FrecencyStore::Rename(const std::string& value,
61 const std::string& new_value) {
62 auto it = values_.find(value);
63
64 // If |value| doesn't exist in our map, then we have nothing to rename, so
65 // ignore. Also return if the rename is a no-op.
66 if (it == values_.end() || value == new_value)
67 return;
68 ValueData data = it->second;
69 values_.erase(it);
70
71 // If |new_value| already exists, we have a conflict. The knowledge that
72 // |value| should be renamed to |new_value| is newer than our previous
73 // knowledge about |new_value|, so prioritise the rename and delete the old
74 // |new_value|.
75 values_[new_value] = data;
76 }
77
Remove(const std::string & value)78 void FrecencyStore::Remove(const std::string& value) {
79 values_.erase(value);
80 }
81
GetId(const std::string & value)82 base::Optional<unsigned int> FrecencyStore::GetId(const std::string& value) {
83 auto it = values_.find(value);
84 if (it == values_.end())
85 return base::nullopt;
86 return it->second.id;
87 }
88
GetAll()89 const FrecencyStore::ScoreTable& FrecencyStore::GetAll() {
90 DecayAllScores();
91 return values_;
92 }
93
ToProto(FrecencyStoreProto * proto) const94 void FrecencyStore::ToProto(FrecencyStoreProto* proto) const {
95 proto->set_value_limit(value_limit_);
96 proto->set_decay_coeff(decay_coeff_);
97 proto->set_num_updates(num_updates_);
98 proto->set_next_id(next_id_);
99
100 auto* proto_values = proto->mutable_values();
101 for (auto& pair : values_) {
102 FrecencyStoreProto::ValueData proto_data;
103 proto_data.set_id(pair.second.id);
104 proto_data.set_last_score(pair.second.last_score);
105 proto_data.set_last_num_updates(pair.second.last_num_updates);
106 (*proto_values)[pair.first] = proto_data;
107 }
108 }
109
FromProto(const FrecencyStoreProto & proto)110 void FrecencyStore::FromProto(const FrecencyStoreProto& proto) {
111 value_limit_ = proto.value_limit();
112 decay_coeff_ = proto.decay_coeff();
113 num_updates_ = proto.num_updates();
114 next_id_ = proto.next_id();
115
116 ScoreTable values;
117 for (const auto& pair : proto.values()) {
118 values[pair.first] = {pair.second.id(), pair.second.last_score(),
119 pair.second.last_num_updates()};
120 }
121 values_.swap(values);
122 }
123
DecayScore(ValueData * data)124 void FrecencyStore::DecayScore(ValueData* data) {
125 int time_since_update = num_updates_ - data->last_num_updates;
126
127 if (time_since_update > 0) {
128 data->last_score *= std::pow(decay_coeff_, time_since_update);
129 data->last_num_updates = num_updates_;
130 }
131 }
132
DecayAllScores()133 void FrecencyStore::DecayAllScores() {
134 for (auto iter = values_.begin(); iter != values_.end();) {
135 ValueData& data = iter->second;
136 DecayScore(&data);
137 if (data.last_score <= kMinScoreBeforeDelete) {
138 // C++11: the return value of erase(iter) is an iterator pointing to the
139 // next element in the container.
140 iter = values_.erase(iter);
141 } else {
142 ++iter;
143 }
144 }
145 }
146
Cleanup()147 void FrecencyStore::Cleanup() {
148 if (static_cast<unsigned int>(values_.size()) < 2 * value_limit_)
149 return;
150
151 std::vector<std::pair<std::string, ValueData>> value_pairs;
152 for (auto& pair : values_) {
153 ValueData& data = pair.second;
154 DecayScore(&data);
155 if (data.last_score > kMinScoreBeforeDelete)
156 value_pairs.emplace_back(pair.first, pair.second);
157 }
158
159 std::sort(value_pairs.begin(), value_pairs.end(),
160 [](auto const& a, auto const& b) {
161 return a.second.last_score > b.second.last_score;
162 });
163
164 ScoreTable values;
165 for (unsigned int i = 0;
166 i < value_limit_ && i < static_cast<unsigned int>(value_pairs.size());
167 ++i) {
168 values.insert(value_pairs[i]);
169 }
170
171 swap(values, values_);
172 }
173
174 } // namespace app_list
175