tile_utils.cc 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155
  1. // Copyright 2020 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. #include "components/query_tiles/internal/tile_utils.h"
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <limits>
  8. #include "base/memory/raw_ptr.h"
  9. #include "base/rand_util.h"
  10. #include "base/strings/string_util.h"
  11. #include "components/query_tiles/internal/tile_config.h"
  12. namespace query_tiles {
  13. namespace {
  14. struct TileComparator {
  15. explicit TileComparator(std::map<std::string, double>* tile_score_map)
  16. : tile_score_map(tile_score_map) {}
  17. inline bool operator()(const std::unique_ptr<Tile>& a,
  18. const std::unique_ptr<Tile>& b) {
  19. return (*tile_score_map)[a->id] > (*tile_score_map)[b->id];
  20. }
  21. raw_ptr<std::map<std::string, double>> tile_score_map;
  22. };
  23. void SortTiles(std::vector<std::unique_ptr<Tile>>* tiles,
  24. std::map<std::string, TileStats>* tile_stats,
  25. std::map<std::string, double>* score_map,
  26. base::Time now_time) {
  27. if (!tiles || tiles->empty())
  28. return;
  29. // Some tiles do not have scores, so the first step is to calculate scores
  30. // for them.
  31. double last_score = std::numeric_limits<double>::max();
  32. TileStats last_tile_stats(now_time, last_score);
  33. size_t new_tile_index = 0;
  34. // Find any tiles that don't have scores, and add new entries for them.
  35. for (size_t i = 0; i < tiles->size(); ++i) {
  36. auto iter = tile_stats->find((*tiles)[i]->id);
  37. // Found a new tile. Skip it for now, will add the entry when we found the
  38. // first
  39. if (iter == tile_stats->end())
  40. continue;
  41. double new_score = CalculateTileScore(iter->second, now_time);
  42. // If the previous tiles are new tiles, fill them with the same tile stats
  43. // from the neighbor that has the minimum score. Using the same tile stats
  44. // will allow tiles to have the same rate of decay over time.
  45. if (i > new_tile_index) {
  46. double min_score = std::min(new_score, last_score);
  47. TileStats new_stats =
  48. new_score > last_score ? last_tile_stats : iter->second;
  49. // For new tiles at the beginning, give them a score higher than the
  50. // minimum score, so that they have a chance to show if the top ranked
  51. // tiles have not been clicked recently.
  52. if (new_tile_index == 0) {
  53. double min_score_for_new_front_tiles =
  54. TileConfig::GetMinimumScoreForNewFrontTiles();
  55. if (min_score < min_score_for_new_front_tiles) {
  56. min_score = min_score_for_new_front_tiles;
  57. new_stats = TileStats(now_time, min_score);
  58. }
  59. }
  60. for (size_t j = new_tile_index; j < i; ++j) {
  61. tile_stats->emplace((*tiles)[j]->id, new_stats);
  62. score_map->emplace((*tiles)[j]->id, min_score);
  63. }
  64. }
  65. // Move |new_tile_index| to the next one that might not have
  66. // a score.
  67. new_tile_index = i + 1;
  68. last_score = new_score;
  69. last_tile_stats = iter->second;
  70. score_map->emplace((*tiles)[i]->id, last_score);
  71. }
  72. // Fill the new tiles at the end with 0 score.
  73. if (new_tile_index < tiles->size()) {
  74. TileStats new_stats(now_time, 0);
  75. for (size_t j = new_tile_index; j < tiles->size(); ++j) {
  76. tile_stats->emplace((*tiles)[j]->id, new_stats);
  77. score_map->emplace((*tiles)[j]->id, 0);
  78. }
  79. }
  80. // Sort the tiles in descending order.
  81. std::sort(tiles->begin(), tiles->end(), TileComparator(score_map));
  82. for (auto& tile : *tiles)
  83. SortTiles(&tile->sub_tiles, tile_stats, score_map, now_time);
  84. }
  85. // Check if a tile's score is expired due to inactivity and should be
  86. // recalculated.
  87. int GetDaysPassedSinceLastClick(const TileStats& tile_stats,
  88. base::Time current_time) {
  89. if (tile_stats.last_clicked_time >= current_time)
  90. return 0;
  91. return (current_time - tile_stats.last_clicked_time).InDaysFloored();
  92. }
  93. } // namespace
  94. void TileShuffler::Shuffle(std::vector<Tile>* tiles, int start) const {
  95. base::RandomShuffle(tiles->begin() + start, tiles->end());
  96. }
  97. void SortTilesAndClearUnusedStats(
  98. std::vector<std::unique_ptr<Tile>>* tiles,
  99. std::map<std::string, TileStats>* tile_stats) {
  100. if (!tiles || tiles->empty())
  101. return;
  102. base::Time now_time = base::Time::Now();
  103. std::map<std::string, double> score_map;
  104. SortTiles(tiles, tile_stats, &score_map, now_time);
  105. auto iter = tile_stats->begin();
  106. while (iter != tile_stats->end()) {
  107. if (score_map.find(iter->first) == score_map.end() &&
  108. (GetDaysPassedSinceLastClick(iter->second, now_time) >=
  109. TileConfig::GetNumDaysToResetTileScore())) {
  110. iter = tile_stats->erase(iter);
  111. } else {
  112. iter++;
  113. }
  114. }
  115. }
  116. double CalculateTileScore(const TileStats& tile_stats,
  117. base::Time current_time) {
  118. // Reset the score if the tile has not been clicked for a long time.
  119. int days_passed_since_last_click =
  120. GetDaysPassedSinceLastClick(tile_stats, current_time);
  121. if (days_passed_since_last_click >= TileConfig::GetNumDaysToResetTileScore())
  122. return 0;
  123. return tile_stats.score * exp(TileConfig::GetTileScoreDecayLambda() *
  124. days_passed_since_last_click);
  125. }
  126. bool IsTrendingTile(const std::string& tile_id) {
  127. return base::StartsWith(tile_id, "trending_");
  128. }
  129. void ShuffleTiles(std::vector<Tile>* tiles, const TileShuffler& shuffler) {
  130. size_t starting_index = TileConfig::GetTileShufflePosition();
  131. if (tiles->size() <= starting_index + 1)
  132. return;
  133. shuffler.Shuffle(tiles, starting_index);
  134. }
  135. } // namespace query_tiles