| 74 | } |
| 75 | |
| 76 | std::vector<double> GreedyFindBin(const double* distinct_values, const int* counts, |
| 77 | int num_distinct_values, int max_bin, |
| 78 | size_t total_cnt, int min_data_in_bin) { |
| 79 | std::vector<double> bin_upper_bound; |
| 80 | CHECK(max_bin > 0); |
| 81 | if (num_distinct_values <= max_bin) { |
| 82 | bin_upper_bound.clear(); |
| 83 | int cur_cnt_inbin = 0; |
| 84 | for (int i = 0; i < num_distinct_values - 1; ++i) { |
| 85 | cur_cnt_inbin += counts[i]; |
| 86 | if (cur_cnt_inbin >= min_data_in_bin) { |
| 87 | auto val = Common::GetDoubleUpperBound((distinct_values[i] + distinct_values[i + 1]) / 2.0); |
| 88 | if (bin_upper_bound.empty() || !Common::CheckDoubleEqualOrdered(bin_upper_bound.back(), val)) { |
| 89 | bin_upper_bound.push_back(val); |
| 90 | cur_cnt_inbin = 0; |
| 91 | } |
| 92 | } |
| 93 | } |
| 94 | cur_cnt_inbin += counts[num_distinct_values - 1]; |
| 95 | bin_upper_bound.push_back(std::numeric_limits<double>::infinity()); |
| 96 | } else { |
| 97 | if (min_data_in_bin > 0) { |
| 98 | max_bin = std::min(max_bin, static_cast<int>(total_cnt / min_data_in_bin)); |
| 99 | max_bin = std::max(max_bin, 1); |
| 100 | } |
| 101 | double mean_bin_size = static_cast<double>(total_cnt) / max_bin; |
| 102 | |
| 103 | // mean size for one bin |
| 104 | int rest_bin_cnt = max_bin; |
| 105 | int rest_sample_cnt = static_cast<int>(total_cnt); |
| 106 | std::vector<bool> is_big_count_value(num_distinct_values, false); |
| 107 | for (int i = 0; i < num_distinct_values; ++i) { |
| 108 | if (counts[i] >= mean_bin_size) { |
| 109 | is_big_count_value[i] = true; |
| 110 | --rest_bin_cnt; |
| 111 | rest_sample_cnt -= counts[i]; |
| 112 | } |
| 113 | } |
| 114 | mean_bin_size = static_cast<double>(rest_sample_cnt) / rest_bin_cnt; |
| 115 | std::vector<double> upper_bounds(max_bin, std::numeric_limits<double>::infinity()); |
| 116 | std::vector<double> lower_bounds(max_bin, std::numeric_limits<double>::infinity()); |
| 117 | |
| 118 | int bin_cnt = 0; |
| 119 | lower_bounds[bin_cnt] = distinct_values[0]; |
| 120 | int cur_cnt_inbin = 0; |
| 121 | for (int i = 0; i < num_distinct_values - 1; ++i) { |
| 122 | if (!is_big_count_value[i]) { |
| 123 | rest_sample_cnt -= counts[i]; |
| 124 | } |
| 125 | cur_cnt_inbin += counts[i]; |
| 126 | // need a new bin |
| 127 | if (is_big_count_value[i] || cur_cnt_inbin >= mean_bin_size || |
| 128 | (is_big_count_value[i + 1] && cur_cnt_inbin >= std::max(1.0, mean_bin_size * 0.5f))) { |
| 129 | upper_bounds[bin_cnt] = distinct_values[i]; |
| 130 | ++bin_cnt; |
| 131 | lower_bounds[bin_cnt] = distinct_values[i + 1]; |
| 132 | if (bin_cnt >= max_bin - 1) { break; } |
| 133 | cur_cnt_inbin = 0; |
no test coverage detected