| 68 | } |
| 69 | |
| 70 | std::vector<std::vector<int>> FindGroups(const std::vector<std::unique_ptr<BinMapper>>& bin_mappers, |
| 71 | const std::vector<int>& find_order, |
| 72 | int** sample_indices, |
| 73 | const int* num_per_col, |
| 74 | int num_sample_col, |
| 75 | size_t total_sample_cnt, |
| 76 | data_size_t max_error_cnt, |
| 77 | data_size_t filter_cnt, |
| 78 | data_size_t num_data, |
| 79 | bool is_use_gpu) { |
| 80 | const int max_search_group = 100; |
| 81 | const int gpu_max_bin_per_group = 256; |
| 82 | Random rand(num_data); |
| 83 | std::vector<std::vector<int>> features_in_group; |
| 84 | std::vector<std::vector<bool>> conflict_marks; |
| 85 | std::vector<int> group_conflict_cnt; |
| 86 | std::vector<size_t> group_non_zero_cnt; |
| 87 | std::vector<int> group_num_bin; |
| 88 | |
| 89 | for (auto fidx : find_order) { |
| 90 | bool is_filtered_feature = fidx >= num_sample_col; |
| 91 | const size_t cur_non_zero_cnt = is_filtered_feature ? 0: num_per_col[fidx]; |
| 92 | bool need_new_group = true; |
| 93 | std::vector<int> available_groups; |
| 94 | for (int gid = 0; gid < static_cast<int>(features_in_group.size()); ++gid) { |
| 95 | if (group_non_zero_cnt[gid] + cur_non_zero_cnt <= total_sample_cnt + max_error_cnt) { |
| 96 | if (!is_use_gpu || group_num_bin[gid] + bin_mappers[fidx]->num_bin() + (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0) |
| 97 | <= gpu_max_bin_per_group) { |
| 98 | available_groups.push_back(gid); |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | std::vector<int> search_groups; |
| 103 | if (!available_groups.empty()) { |
| 104 | int last = static_cast<int>(available_groups.size()) - 1; |
| 105 | auto indices = rand.Sample(last, std::min(last, max_search_group - 1)); |
| 106 | search_groups.push_back(available_groups.back()); |
| 107 | for (auto idx : indices) { |
| 108 | search_groups.push_back(available_groups[idx]); |
| 109 | } |
| 110 | } |
| 111 | for (auto gid : search_groups) { |
| 112 | const int rest_max_cnt = max_error_cnt - group_conflict_cnt[gid]; |
| 113 | const int cnt = is_filtered_feature ? 0 : GetConfilctCount(conflict_marks[gid], sample_indices[fidx], num_per_col[fidx], rest_max_cnt); |
| 114 | if (cnt >= 0 && cnt <= rest_max_cnt) { |
| 115 | data_size_t rest_non_zero_data = static_cast<data_size_t>( |
| 116 | static_cast<double>(cur_non_zero_cnt - cnt) * num_data / total_sample_cnt); |
| 117 | if (rest_non_zero_data < filter_cnt) { continue; } |
| 118 | need_new_group = false; |
| 119 | features_in_group[gid].push_back(fidx); |
| 120 | group_conflict_cnt[gid] += cnt; |
| 121 | group_non_zero_cnt[gid] += cur_non_zero_cnt - cnt; |
| 122 | if (!is_filtered_feature) { |
| 123 | MarkUsed(&conflict_marks[gid], sample_indices[fidx], num_per_col[fidx]); |
| 124 | } |
| 125 | if (is_use_gpu) { |
| 126 | group_num_bin[gid] += bin_mappers[fidx]->num_bin() + (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0); |
| 127 | } |
no test coverage detected