feature_histogram.hpp 35.6 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
6
7
#ifndef LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_
#define LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_

8
#include <LightGBM/bin.h>
Guolin Ke's avatar
Guolin Ke committed
9
#include <LightGBM/dataset.h>
10
#include <LightGBM/utils/array_args.h>
Guolin Ke's avatar
Guolin Ke committed
11

12
#include <algorithm>
13
#include <cmath>
14
15
16
17
18
19
#include <cstring>
#include <memory>
#include <utility>
#include <vector>

#include "split_info.hpp"
Guolin Ke's avatar
Guolin Ke committed
20

21
namespace LightGBM {
Guolin Ke's avatar
Guolin Ke committed
22

Guolin Ke's avatar
Guolin Ke committed
23
class FeatureMetainfo {
24
 public:
Guolin Ke's avatar
Guolin Ke committed
25
  int num_bin;
Guolin Ke's avatar
Guolin Ke committed
26
  MissingType missing_type;
27
  int8_t offset = 0;
Guolin Ke's avatar
Guolin Ke committed
28
  uint32_t default_bin;
Guolin Ke's avatar
Guolin Ke committed
29
  int8_t monotone_type;
Guolin Ke's avatar
Guolin Ke committed
30
  double penalty;
Guolin Ke's avatar
Guolin Ke committed
31
  /*! \brief pointer of tree config */
Guolin Ke's avatar
Guolin Ke committed
32
  const Config* config;
33
  BinType bin_type;
Guolin Ke's avatar
Guolin Ke committed
34
};
Guolin Ke's avatar
Guolin Ke committed
35
36
37
38
/*!
* \brief FeatureHistogram is used to construct and store a histogram for a feature.
*/
class FeatureHistogram {
39
 public:
Guolin Ke's avatar
Guolin Ke committed
40
  FeatureHistogram() {
Guolin Ke's avatar
Guolin Ke committed
41
    data_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
42
  }
Guolin Ke's avatar
Guolin Ke committed
43

Guolin Ke's avatar
Guolin Ke committed
44
45
46
  ~FeatureHistogram() {
  }

Guolin Ke's avatar
Guolin Ke committed
47
48
49
50
51
  /*! \brief Disable copy */
  FeatureHistogram& operator=(const FeatureHistogram&) = delete;
  /*! \brief Disable copy */
  FeatureHistogram(const FeatureHistogram&) = delete;

Guolin Ke's avatar
Guolin Ke committed
52
53
54
55
56
  /*!
  * \brief Init the feature histogram
  * \param feature the feature data for this histogram
  * \param min_num_data_one_leaf minimal number of data in one leaf
  */
57
  void Init(hist_t* data, const FeatureMetainfo* meta) {
Guolin Ke's avatar
Guolin Ke committed
58
59
    meta_ = meta;
    data_ = data;
60
    if (meta_->bin_type == BinType::NumericalBin) {
61
62
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdNumerical, this, std::placeholders::_1,
        std::placeholders::_2, std::placeholders::_3, std::placeholders::_4, std::placeholders::_5, std::placeholders::_6);
63
    } else {
64
65
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdCategorical, this, std::placeholders::_1,
        std::placeholders::_2, std::placeholders::_3, std::placeholders::_4, std::placeholders::_5, std::placeholders::_6);
66
    }
67
    rand_ = Random(meta_->config->extra_seed);
Guolin Ke's avatar
Guolin Ke committed
68
69
  }

70
  hist_t* RawData() {
Guolin Ke's avatar
Guolin Ke committed
71
    return data_;
Guolin Ke's avatar
Guolin Ke committed
72
73
74
75
76
77
  }
  /*!
  * \brief Subtract current histograms with other
  * \param other The histogram that want to subtract
  */
  void Subtract(const FeatureHistogram& other) {
78
79
    for (int i = 0; i < (meta_->num_bin - meta_->offset) * 2; ++i) {
      data_[i] -= other.data_[i];
Guolin Ke's avatar
Guolin Ke committed
80
81
    }
  }
82

83
84
  void FindBestThreshold(double sum_gradient, double sum_hessian, data_size_t num_data,
    double min_constraint, double max_constraint, SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
85
    output->default_left = true;
Guolin Ke's avatar
Guolin Ke committed
86
    output->gain = kMinScore;
Guolin Ke's avatar
Guolin Ke committed
87
    find_best_threshold_fun_(sum_gradient, sum_hessian + 2 * kEpsilon, num_data, min_constraint, max_constraint, output);
Guolin Ke's avatar
Guolin Ke committed
88
    output->gain *= meta_->penalty;
89
90
  }

91
92
  void FindBestThresholdNumerical(double sum_gradient, double sum_hessian, data_size_t num_data,
    double min_constraint, double max_constraint, SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
93
    is_splittable_ = false;
Guolin Ke's avatar
Guolin Ke committed
94
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
95
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
96
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
97
    int rand_threshold = 0;
98
    if (meta_->num_bin - 2 > 0) {
99
100
101
      rand_threshold = rand_.NextInt(0, meta_->num_bin - 2);
    }
    bool is_rand = meta_->config->extra_trees;
Guolin Ke's avatar
Guolin Ke committed
102
103
    if (meta_->num_bin > 2 && meta_->missing_type != MissingType::None) {
      if (meta_->missing_type == MissingType::Zero) {
104
105
106
        if (is_rand) {
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, true, false, rand_threshold);
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, true, false, rand_threshold);
107
        } else {
108
109
110
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, true, false, rand_threshold);
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, true, false, rand_threshold);
        }
Guolin Ke's avatar
Guolin Ke committed
111
      } else {
112
113
114
115
116
117
118
        if (is_rand) {
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, true, rand_threshold);
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, false, true, rand_threshold);
        } else {
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, true, rand_threshold);
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, false, true, rand_threshold);
        }
Guolin Ke's avatar
Guolin Ke committed
119
      }
120
    } else {
121
122
123
124
125
      if (is_rand) {
        FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, false, rand_threshold);
      } else {
        FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, false, rand_threshold);
      }
Guolin Ke's avatar
Guolin Ke committed
126
127
128
129
      // fix the direction error when only have 2 bins
      if (meta_->missing_type == MissingType::NaN) {
        output->default_left = false;
      }
Guolin Ke's avatar
Guolin Ke committed
130
    }
Guolin Ke's avatar
Guolin Ke committed
131
    output->gain -= min_gain_shift;
Guolin Ke's avatar
Guolin Ke committed
132
133
134
    output->monotone_type = meta_->monotone_type;
    output->min_constraint = min_constraint;
    output->max_constraint = max_constraint;
Guolin Ke's avatar
Guolin Ke committed
135
  }
136

137
  void FindBestThresholdCategorical(double sum_gradient, double sum_hessian, data_size_t num_data,
138
    double min_constraint, double max_constraint, SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
139
    output->default_left = false;
140
    double best_gain = kMinScore;
141
    data_size_t best_left_count = 0;
ChenZhiyong's avatar
ChenZhiyong committed
142
143
    double best_sum_left_gradient = 0;
    double best_sum_left_hessian = 0;
144
145
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
146

Guolin Ke's avatar
Guolin Ke committed
147
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
ChenZhiyong's avatar
ChenZhiyong committed
148
    bool is_full_categorical = meta_->missing_type == MissingType::None;
149
    int used_bin = meta_->num_bin - 1 + is_full_categorical;
ChenZhiyong's avatar
ChenZhiyong committed
150

Guolin Ke's avatar
Guolin Ke committed
151
    std::vector<int> sorted_idx;
Guolin Ke's avatar
Guolin Ke committed
152
153
    double l2 = meta_->config->lambda_l2;
    bool use_onehot = meta_->num_bin <= meta_->config->max_cat_to_onehot;
154
155
    int best_threshold = -1;
    int best_dir = 1;
156
    const double cnt_factor = num_data / sum_hessian;
157
158
    if (use_onehot) {
      for (int t = 0; t < used_bin; ++t) {
159
160
161
        const auto grad = GET_GRAD(data_, t);
        const auto hess = GET_HESS(data_, t);
        data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
162
        // if data not enough, or sum hessian too small
163
        if (cnt < meta_->config->min_data_in_leaf
164
            || hess < meta_->config->min_sum_hessian_in_leaf) continue;
165
        data_size_t other_count = num_data - cnt;
166
        // if data not enough
Guolin Ke's avatar
Guolin Ke committed
167
        if (other_count < meta_->config->min_data_in_leaf) continue;
ChenZhiyong's avatar
ChenZhiyong committed
168

169
        double sum_other_hessian = sum_hessian - hess - kEpsilon;
170
        // if sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
171
        if (sum_other_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
ChenZhiyong's avatar
ChenZhiyong committed
172

173
        double sum_other_gradient = sum_gradient - grad;
174
        // current split gain
175
        double current_gain = GetSplitGains(sum_other_gradient, sum_other_hessian, grad, hess + kEpsilon,
176
          meta_->config->lambda_l1, l2, meta_->config->max_delta_step, min_constraint, max_constraint, 0);
177
        // gain with split is worse than without split
ChenZhiyong's avatar
ChenZhiyong committed
178
        if (current_gain <= min_gain_shift) continue;
179
180

        // mark to is splittable
ChenZhiyong's avatar
ChenZhiyong committed
181
        is_splittable_ = true;
182
        // better split point
ChenZhiyong's avatar
ChenZhiyong committed
183
        if (current_gain > best_gain) {
184
          best_threshold = t;
185
186
187
          best_sum_left_gradient = grad;
          best_sum_left_hessian = hess + kEpsilon;
          best_left_count = cnt;
ChenZhiyong's avatar
ChenZhiyong committed
188
          best_gain = current_gain;
189
190
191
192
        }
      }
    } else {
      for (int i = 0; i < used_bin; ++i) {
193
        if (Common::RoundInt(GET_HESS(data_, i) * cnt_factor) >= meta_->config->cat_smooth) {
194
195
196
197
198
          sorted_idx.push_back(i);
        }
      }
      used_bin = static_cast<int>(sorted_idx.size());

Guolin Ke's avatar
Guolin Ke committed
199
      l2 += meta_->config->cat_l2;
200
201

      auto ctr_fun = [this](double sum_grad, double sum_hess) {
Guolin Ke's avatar
Guolin Ke committed
202
        return (sum_grad) / (sum_hess + meta_->config->cat_smooth);
203
204
      };
      std::sort(sorted_idx.begin(), sorted_idx.end(),
205
206
207
        [this, &ctr_fun](int i, int j) {
          return ctr_fun(GET_GRAD(data_, i), GET_HESS(data_, i)) < ctr_fun(GET_GRAD(data_, j), GET_HESS(data_, j));
        });
208
209
210
211
212

      std::vector<int> find_direction(1, 1);
      std::vector<int> start_position(1, 0);
      find_direction.push_back(-1);
      start_position.push_back(used_bin - 1);
Guolin Ke's avatar
Guolin Ke committed
213
      const int max_num_cat = std::min(meta_->config->max_cat_threshold, (used_bin + 1) / 2);
214
215
216
217
218
      int max_threshold = std::max(std::min(max_num_cat, used_bin) - 1, 0);
      int rand_threshold = 0;
      if (max_threshold > 0) {
        rand_threshold = rand_.NextInt(0, max_threshold);
      }
219

220
221
222
223
      is_splittable_ = false;
      for (size_t out_i = 0; out_i < find_direction.size(); ++out_i) {
        auto dir = find_direction[out_i];
        auto start_pos = start_position[out_i];
Guolin Ke's avatar
Guolin Ke committed
224
        data_size_t min_data_per_group = meta_->config->min_data_per_group;
225
226
227
228
229
230
231
        data_size_t cnt_cur_group = 0;
        double sum_left_gradient = 0.0f;
        double sum_left_hessian = kEpsilon;
        data_size_t left_count = 0;
        for (int i = 0; i < used_bin && i < max_num_cat; ++i) {
          auto t = sorted_idx[start_pos];
          start_pos += dir;
232
233
234
          const auto grad = GET_GRAD(data_, t);
          const auto hess = GET_HESS(data_, t);
          data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
235

236
237
238
239
          sum_left_gradient += grad;
          sum_left_hessian += hess;
          left_count += cnt;
          cnt_cur_group += cnt;
240

Guolin Ke's avatar
Guolin Ke committed
241
          if (left_count < meta_->config->min_data_in_leaf
242
              || sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
243
          data_size_t right_count = num_data - left_count;
Guolin Ke's avatar
Guolin Ke committed
244
          if (right_count < meta_->config->min_data_in_leaf || right_count < min_data_per_group) break;
245
246

          double sum_right_hessian = sum_hessian - sum_left_hessian;
Guolin Ke's avatar
Guolin Ke committed
247
          if (sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) break;
248
249
250
251
252
253

          if (cnt_cur_group < min_data_per_group) continue;

          cnt_cur_group = 0;

          double sum_right_gradient = sum_gradient - sum_left_gradient;
254
255
          if (!meta_->config->extra_trees || i == rand_threshold) {
            double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
256
              meta_->config->lambda_l1, l2, meta_->config->max_delta_step, min_constraint, max_constraint, 0);
257
258
259
260
261
262
263
264
265
266
            if (current_gain <= min_gain_shift) continue;
            is_splittable_ = true;
            if (current_gain > best_gain) {
              best_left_count = left_count;
              best_sum_left_gradient = sum_left_gradient;
              best_sum_left_hessian = sum_left_hessian;
              best_threshold = i;
              best_gain = current_gain;
              best_dir = dir;
            }
267
          }
ChenZhiyong's avatar
ChenZhiyong committed
268
        }
269
270
      }
    }
271

272
    if (is_splittable_) {
Guolin Ke's avatar
Guolin Ke committed
273
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
274
        meta_->config->lambda_l1, l2, meta_->config->max_delta_step, min_constraint, max_constraint);
275
276
277
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
278
279
280
      output->right_output = CalculateSplittedLeafOutput(
        sum_gradient - best_sum_left_gradient, sum_hessian - best_sum_left_hessian,
        meta_->config->lambda_l1, l2, meta_->config->max_delta_step, min_constraint, max_constraint);
281
282
283
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
284
      output->gain = best_gain - min_gain_shift;
285
286
287
      if (use_onehot) {
        output->num_cat_threshold = 1;
        output->cat_threshold = std::vector<uint32_t>(1, static_cast<uint32_t>(best_threshold));
ChenZhiyong's avatar
ChenZhiyong committed
288
      } else {
289
290
291
292
293
294
295
296
297
298
299
300
        output->num_cat_threshold = best_threshold + 1;
        output->cat_threshold = std::vector<uint32_t>(output->num_cat_threshold);
        if (best_dir == 1) {
          for (int i = 0; i < output->num_cat_threshold; ++i) {
            auto t = sorted_idx[i];
            output->cat_threshold[i] = t;
          }
        } else {
          for (int i = 0; i < output->num_cat_threshold; ++i) {
            auto t = sorted_idx[used_bin - 1 - i];
            output->cat_threshold[i] = t;
          }
ChenZhiyong's avatar
ChenZhiyong committed
301
302
        }
      }
Guolin Ke's avatar
Guolin Ke committed
303
304
305
      output->monotone_type = 0;
      output->min_constraint = min_constraint;
      output->max_constraint = max_constraint;
306
    }
307
308
  }

309
  void GatherInfoForThreshold(double sum_gradient, double sum_hessian,
310
    uint32_t threshold, data_size_t num_data, SplitInfo* output) {
311
    if (meta_->bin_type == BinType::NumericalBin) {
312
      GatherInfoForThresholdNumerical(sum_gradient, sum_hessian, threshold, num_data, output);
313
    } else {
314
      GatherInfoForThresholdCategorical(sum_gradient, sum_hessian, threshold, num_data, output);
315
316
317
318
    }
  }

  void GatherInfoForThresholdNumerical(double sum_gradient, double sum_hessian,
319
    uint32_t threshold, data_size_t num_data, SplitInfo* output) {
320
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
321
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
322
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
323
324

    // do stuff here
325
    const int8_t offset = meta_->offset;
326
327
328
329
330
331

    double sum_right_gradient = 0.0f;
    double sum_right_hessian = kEpsilon;
    data_size_t right_count = 0;

    // set values
332
333
    bool use_na_as_missing = false;
    bool skip_default_bin = false;
334
335
    if (meta_->missing_type == MissingType::Zero) {
      skip_default_bin = true;
336
    } else if (meta_->missing_type == MissingType::NaN) {
337
338
339
      use_na_as_missing = true;
    }

340
341
    int t = meta_->num_bin - 1 - offset - use_na_as_missing;
    const int t_end = 1 - offset;
342
    const double cnt_factor = num_data / sum_hessian;
343
344
    // from right to left, and we don't need data in bin0
    for (; t >= t_end; --t) {
345
      if (static_cast<uint32_t>(t + offset) < threshold) { break; }
346
347

      // need to skip default bin
348
      if (skip_default_bin && (t + offset) == static_cast<int>(meta_->default_bin)) { continue; }
349
350
351
352
353
354
      const auto grad = GET_GRAD(data_, t);
      const auto hess = GET_HESS(data_, t);
      data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
      sum_right_gradient += grad;
      sum_right_hessian += hess;
      right_count += cnt;
355
356
357
358
359
    }
    double sum_left_gradient = sum_gradient - sum_right_gradient;
    double sum_left_hessian = sum_hessian - sum_right_hessian;
    data_size_t left_count = num_data - right_count;
    double current_gain = GetLeafSplitGain(sum_left_gradient, sum_left_hessian,
360
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step)
361
      + GetLeafSplitGain(sum_right_gradient, sum_right_hessian,
362
          meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
363
364
365
366

    // gain with split is worse than without split
    if (std::isnan(current_gain) || current_gain <= min_gain_shift) {
      output->gain = kMinScore;
367
      Log::Warning("'Forced Split' will be ignored since the gain getting worse. ");
368
      return;
369
    }
370
371
372
373

    // update split information
    output->threshold = threshold;
    output->left_output = CalculateSplittedLeafOutput(sum_left_gradient, sum_left_hessian,
374
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
375
376
377
    output->left_count = left_count;
    output->left_sum_gradient = sum_left_gradient;
    output->left_sum_hessian = sum_left_hessian - kEpsilon;
378
379
380
    output->right_output = CalculateSplittedLeafOutput(
      sum_gradient - sum_left_gradient, sum_hessian - sum_left_hessian,
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
381
382
383
384
385
386
387
388
389
    output->right_count = num_data - left_count;
    output->right_sum_gradient = sum_gradient - sum_left_gradient;
    output->right_sum_hessian = sum_hessian - sum_left_hessian - kEpsilon;
    output->gain = current_gain;
    output->gain -= min_gain_shift;
    output->default_left = true;
  }

  void GatherInfoForThresholdCategorical(double sum_gradient, double sum_hessian,
390
    uint32_t threshold, data_size_t num_data, SplitInfo* output) {
391
392
    // get SplitInfo for a given one-hot categorical split.
    output->default_left = false;
393
394
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
395
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
396
397
398
399
400
401
402
    bool is_full_categorical = meta_->missing_type == MissingType::None;
    int used_bin = meta_->num_bin - 1 + is_full_categorical;
    if (threshold >= static_cast<uint32_t>(used_bin)) {
      output->gain = kMinScore;
      Log::Warning("Invalid categorical threshold split");
      return;
    }
403
404
405
406
    const double cnt_factor = num_data / sum_hessian;
    const auto grad = GET_GRAD(data_, threshold);
    const auto hess = GET_HESS(data_, threshold);
    data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
407

Guolin Ke's avatar
Guolin Ke committed
408
    double l2 = meta_->config->lambda_l2;
409
    data_size_t left_count = cnt;
410
    data_size_t right_count = num_data - left_count;
411
    double sum_left_hessian = hess + kEpsilon;
412
    double sum_right_hessian = sum_hessian - sum_left_hessian;
413
    double sum_left_gradient = grad;
414
415
416
    double sum_right_gradient = sum_gradient - sum_left_gradient;
    // current split gain
    double current_gain = GetLeafSplitGain(sum_right_gradient, sum_right_hessian,
417
      meta_->config->lambda_l1, l2, meta_->config->max_delta_step)
418
      + GetLeafSplitGain(sum_left_gradient, sum_left_hessian,
419
          meta_->config->lambda_l1, l2, meta_->config->max_delta_step);
420
421
    if (std::isnan(current_gain) || current_gain <= min_gain_shift) {
      output->gain = kMinScore;
422
      Log::Warning("'Forced Split' will be ignored since the gain getting worse.");
423
424
425
426
      return;
    }

    output->left_output = CalculateSplittedLeafOutput(sum_left_gradient, sum_left_hessian,
427
      meta_->config->lambda_l1, l2, meta_->config->max_delta_step);
428
429
430
431
    output->left_count = left_count;
    output->left_sum_gradient = sum_left_gradient;
    output->left_sum_hessian = sum_left_hessian - kEpsilon;
    output->right_output = CalculateSplittedLeafOutput(sum_right_gradient, sum_right_hessian,
432
      meta_->config->lambda_l1, l2, meta_->config->max_delta_step);
433
434
435
436
437
438
439
440
441
    output->right_count = right_count;
    output->right_sum_gradient = sum_gradient - sum_left_gradient;
    output->right_sum_hessian = sum_right_hessian - kEpsilon;
    output->gain = current_gain - min_gain_shift;
    output->num_cat_threshold = 1;
    output->cat_threshold = std::vector<uint32_t>(1, threshold);
  }


Guolin Ke's avatar
Guolin Ke committed
442
443
444
445
  /*!
  * \brief Binary size of this histogram
  */
  int SizeOfHistgram() const {
446
    return (meta_->num_bin - meta_->offset) * kHistEntrySize;
Guolin Ke's avatar
Guolin Ke committed
447
448
449
450
451
  }

  /*!
  * \brief Restore histogram from memory
  */
Guolin Ke's avatar
Guolin Ke committed
452
  void FromMemory(char* memory_data) {
453
    std::memcpy(data_, memory_data, (meta_->num_bin - meta_->offset) * kHistEntrySize);
Guolin Ke's avatar
Guolin Ke committed
454
455
456
457
458
459
460
461
462
463
464
465
  }

  /*!
  * \brief True if this histogram can be splitted
  */
  bool is_splittable() { return is_splittable_; }

  /*!
  * \brief Set splittable to this histogram
  */
  void set_is_splittable(bool val) { is_splittable_ = val; }

466
467
468
469
470
471
472
473
474
475
476
477
  static double ThresholdL1(double s, double l1) {
    const double reg_s = std::max(0.0, std::fabs(s) - l1);
    return Common::Sign(s) * reg_s;
  }

  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step) {
    double ret = -ThresholdL1(sum_gradients, l1) / (sum_hessians + l2);
    if (max_delta_step <= 0.0f || std::fabs(ret) <= max_delta_step) {
      return ret;
    } else {
      return Common::Sign(ret) * max_delta_step;
    }
Guolin Ke's avatar
Guolin Ke committed
478
479
  }

480
 private:
Guolin Ke's avatar
Guolin Ke committed
481
  static double GetSplitGains(double sum_left_gradients, double sum_left_hessians,
482
483
484
    double sum_right_gradients, double sum_right_hessians,
    double l1, double l2, double max_delta_step,
    double min_constraint, double max_constraint, int8_t monotone_constraint) {
485
486
    double left_output = CalculateSplittedLeafOutput(sum_left_gradients, sum_left_hessians, l1, l2, max_delta_step, min_constraint, max_constraint);
    double right_output = CalculateSplittedLeafOutput(sum_right_gradients, sum_right_hessians, l1, l2, max_delta_step, min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
487
488
489
490
491
492
493
494
    if (((monotone_constraint > 0) && (left_output > right_output)) ||
      ((monotone_constraint < 0) && (left_output < right_output))) {
      return 0;
    }
    return GetLeafSplitGainGivenOutput(sum_left_gradients, sum_left_hessians, l1, l2, left_output)
      + GetLeafSplitGainGivenOutput(sum_right_gradients, sum_right_hessians, l1, l2, right_output);
  }

Guolin Ke's avatar
Guolin Ke committed
495
  /*!
496
  * \brief Calculate the output of a leaf based on regularized sum_gradients and sum_hessians
Guolin Ke's avatar
Guolin Ke committed
497
498
499
500
  * \param sum_gradients
  * \param sum_hessians
  * \return leaf output
  */
501
  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step,
502
    double min_constraint, double max_constraint) {
503
    double ret = CalculateSplittedLeafOutput(sum_gradients, sum_hessians, l1, l2, max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
504
505
506
507
508
509
    if (ret < min_constraint) {
      ret = min_constraint;
    } else if (ret > max_constraint) {
      ret = max_constraint;
    }
    return ret;
Guolin Ke's avatar
Guolin Ke committed
510
  }
Guolin Ke's avatar
Guolin Ke committed
511

Guolin Ke's avatar
Guolin Ke committed
512
513
514
515
516
517
  /*!
  * \brief Calculate the split gain based on regularized sum_gradients and sum_hessians
  * \param sum_gradients
  * \param sum_hessians
  * \return split gain
  */
518
519
520
  static double GetLeafSplitGain(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step) {
    double output = CalculateSplittedLeafOutput(sum_gradients, sum_hessians, l1, l2, max_delta_step);
    return GetLeafSplitGainGivenOutput(sum_gradients, sum_hessians, l1, l2, output);
Guolin Ke's avatar
Guolin Ke committed
521
522
523
524
525
526
  }

  static double GetLeafSplitGainGivenOutput(double sum_gradients, double sum_hessians, double l1, double l2, double output) {
    const double sg_l1 = ThresholdL1(sum_gradients, l1);
    return -(2.0 * sg_l1 * output + (sum_hessians + l2) * output * output);
  }
Guolin Ke's avatar
Guolin Ke committed
527

528
  template<bool is_rand>
Guolin Ke's avatar
Guolin Ke committed
529
  void FindBestThresholdSequence(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
530
                                 double min_gain_shift, SplitInfo* output, int dir, bool skip_default_bin, bool use_na_as_missing, int rand_threshold) {
531
    const int8_t offset = meta_->offset;
Guolin Ke's avatar
Guolin Ke committed
532
533
534
535
536
537

    double best_sum_left_gradient = NAN;
    double best_sum_left_hessian = NAN;
    double best_gain = kMinScore;
    data_size_t best_left_count = 0;
    uint32_t best_threshold = static_cast<uint32_t>(meta_->num_bin);
538
    const double cnt_factor = num_data / sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
539
540
541
542
543
    if (dir == -1) {
      double sum_right_gradient = 0.0f;
      double sum_right_hessian = kEpsilon;
      data_size_t right_count = 0;

544
545
      int t = meta_->num_bin - 1 - offset - use_na_as_missing;
      const int t_end = 1 - offset;
Guolin Ke's avatar
Guolin Ke committed
546
547
548
549

      // from right to left, and we don't need data in bin0
      for (; t >= t_end; --t) {
        // need to skip default bin
550
        if (skip_default_bin && (t + offset) == static_cast<int>(meta_->default_bin)) { continue; }
Guolin Ke's avatar
Guolin Ke committed
551

552
553
554
555
556
557
        const auto grad = GET_GRAD(data_, t);
        const auto hess = GET_HESS(data_, t);
        data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
        sum_right_gradient += grad;
        sum_right_hessian += hess;
        right_count += cnt;
Guolin Ke's avatar
Guolin Ke committed
558
        // if data not enough, or sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
559
        if (right_count < meta_->config->min_data_in_leaf
560
            || sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
Guolin Ke's avatar
Guolin Ke committed
561
562
        data_size_t left_count = num_data - right_count;
        // if data not enough
Guolin Ke's avatar
Guolin Ke committed
563
        if (left_count < meta_->config->min_data_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
564
565
566

        double sum_left_hessian = sum_hessian - sum_right_hessian;
        // if sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
567
        if (sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
568
569

        double sum_left_gradient = sum_gradient - sum_right_gradient;
570
571
572
573
574
575
576
        if (!is_rand || t - 1 + offset == rand_threshold) {
          // current split gain
          double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                              meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
                                              min_constraint, max_constraint, meta_->monotone_type);
          // gain with split is worse than without split
          if (current_gain <= min_gain_shift) continue;
Guolin Ke's avatar
Guolin Ke committed
577

578
579
580
581
582
583
584
585
586
587
588
          // mark to is splittable
          is_splittable_ = true;
          // better split point
          if (current_gain > best_gain) {
            best_left_count = left_count;
            best_sum_left_gradient = sum_left_gradient;
            best_sum_left_hessian = sum_left_hessian;
            // left is <= threshold, right is > threshold.  so this is t-1
            best_threshold = static_cast<uint32_t>(t - 1 + offset);
            best_gain = current_gain;
          }
Guolin Ke's avatar
Guolin Ke committed
589
590
        }
      }
ChenZhiyong's avatar
ChenZhiyong committed
591
    } else {
Guolin Ke's avatar
Guolin Ke committed
592
593
594
595
596
      double sum_left_gradient = 0.0f;
      double sum_left_hessian = kEpsilon;
      data_size_t left_count = 0;

      int t = 0;
597
      const int t_end = meta_->num_bin - 2 - offset;
Guolin Ke's avatar
Guolin Ke committed
598

599
      if (use_na_as_missing && offset == 1) {
Guolin Ke's avatar
Guolin Ke committed
600
601
602
        sum_left_gradient = sum_gradient;
        sum_left_hessian = sum_hessian - kEpsilon;
        left_count = num_data;
603
        for (int i = 0; i < meta_->num_bin - offset; ++i) {
604
605
606
607
608
609
          const auto grad = GET_GRAD(data_, i);
          const auto hess = GET_HESS(data_, i);
          data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
          sum_left_gradient -= grad;
          sum_left_hessian -= hess;
          left_count -= cnt;
Guolin Ke's avatar
Guolin Ke committed
610
611
612
613
        }
        t = -1;
      }

Guolin Ke's avatar
Guolin Ke committed
614
615
      for (; t <= t_end; ++t) {
        // need to skip default bin
616
        if (skip_default_bin && (t + offset) == static_cast<int>(meta_->default_bin)) { continue; }
Guolin Ke's avatar
Guolin Ke committed
617
        if (t >= 0) {
618
619
620
          sum_left_gradient += GET_GRAD(data_, t);
          sum_left_hessian += GET_HESS(data_, t);
          left_count += static_cast<data_size_t>(Common::RoundInt(GET_HESS(data_, t) * cnt_factor));
Guolin Ke's avatar
Guolin Ke committed
621
        }
Guolin Ke's avatar
Guolin Ke committed
622
        // if data not enough, or sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
623
        if (left_count < meta_->config->min_data_in_leaf
624
            || sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
Guolin Ke's avatar
Guolin Ke committed
625
626
        data_size_t right_count = num_data - left_count;
        // if data not enough
Guolin Ke's avatar
Guolin Ke committed
627
        if (right_count < meta_->config->min_data_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
628
629
630

        double sum_right_hessian = sum_hessian - sum_left_hessian;
        // if sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
631
        if (sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
632
633

        double sum_right_gradient = sum_gradient - sum_left_gradient;
634
635
636
637
638
639
640
        if (!is_rand || t + offset == rand_threshold) {
          // current split gain
          double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                              meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
                                              min_constraint, max_constraint, meta_->monotone_type);
          // gain with split is worse than without split
          if (current_gain <= min_gain_shift) continue;
Guolin Ke's avatar
Guolin Ke committed
641

642
643
644
645
646
647
648
649
650
651
          // mark to is splittable
          is_splittable_ = true;
          // better split point
          if (current_gain > best_gain) {
            best_left_count = left_count;
            best_sum_left_gradient = sum_left_gradient;
            best_sum_left_hessian = sum_left_hessian;
            best_threshold = static_cast<uint32_t>(t + offset);
            best_gain = current_gain;
          }
Guolin Ke's avatar
Guolin Ke committed
652
653
654
655
656
657
658
659
        }
      }
    }

    if (is_splittable_ && best_gain > output->gain) {
      // update split information
      output->threshold = best_threshold;
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
660
661
        meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
        min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
662
663
664
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
665
666
      output->right_output = CalculateSplittedLeafOutput(
        sum_gradient - best_sum_left_gradient, sum_hessian - best_sum_left_hessian,
667
668
        meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
        min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
669
670
671
672
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
      output->gain = best_gain;
Guolin Ke's avatar
Guolin Ke committed
673
      output->default_left = dir == -1;
Guolin Ke's avatar
Guolin Ke committed
674
675
676
    }
  }

Guolin Ke's avatar
Guolin Ke committed
677
  const FeatureMetainfo* meta_;
Guolin Ke's avatar
Guolin Ke committed
678
  /*! \brief sum of gradient of each bin */
679
  hist_t* data_;
Guolin Ke's avatar
Guolin Ke committed
680
  bool is_splittable_ = true;
681
682
  /*! \brief random number generator for extremely randomized trees */
  Random rand_;
683

Guolin Ke's avatar
Guolin Ke committed
684
  std::function<void(double, double, data_size_t, double, double, SplitInfo*)> find_best_threshold_fun_;
Guolin Ke's avatar
Guolin Ke committed
685
};
Guolin Ke's avatar
Guolin Ke committed
686
class HistogramPool {
687
 public:
Guolin Ke's avatar
Guolin Ke committed
688
689
690
691
  /*!
  * \brief Constructor
  */
  HistogramPool() {
Guolin Ke's avatar
Guolin Ke committed
692
693
    cache_size_ = 0;
    total_size_ = 0;
Guolin Ke's avatar
Guolin Ke committed
694
  }
695

Guolin Ke's avatar
Guolin Ke committed
696
697
698
699
700
  /*!
  * \brief Destructor
  */
  ~HistogramPool() {
  }
701

Guolin Ke's avatar
Guolin Ke committed
702
703
704
705
706
  /*!
  * \brief Reset pool size
  * \param cache_size Max cache size
  * \param total_size Total size will be used
  */
Guolin Ke's avatar
Guolin Ke committed
707
  void Reset(int cache_size, int total_size) {
Guolin Ke's avatar
Guolin Ke committed
708
709
710
711
712
713
714
715
716
    cache_size_ = cache_size;
    // at least need 2 bucket to store smaller leaf and larger leaf
    CHECK(cache_size_ >= 2);
    total_size_ = total_size;
    if (cache_size_ > total_size_) {
      cache_size_ = total_size_;
    }
    is_enough_ = (cache_size_ == total_size_);
    if (!is_enough_) {
717
718
719
      mapper_.resize(total_size_);
      inverse_mapper_.resize(cache_size_);
      last_used_time_.resize(cache_size_);
Guolin Ke's avatar
Guolin Ke committed
720
721
722
      ResetMap();
    }
  }
723

Guolin Ke's avatar
Guolin Ke committed
724
725
726
727
728
729
730
731
732
733
734
735
  /*!
  * \brief Reset mapper
  */
  void ResetMap() {
    if (!is_enough_) {
      cur_time_ = 0;
      std::fill(mapper_.begin(), mapper_.end(), -1);
      std::fill(inverse_mapper_.begin(), inverse_mapper_.end(), -1);
      std::fill(last_used_time_.begin(), last_used_time_.end(), 0);
    }
  }

736
  void DynamicChangeSize(const Dataset* train_data, bool is_hist_colwise, const Config* config, int cache_size, int total_size) {
Guolin Ke's avatar
Guolin Ke committed
737
    if (feature_metas_.empty()) {
738
      uint64_t bin_cnt_over_features = 0;
Guolin Ke's avatar
Guolin Ke committed
739
740
741
      int num_feature = train_data->num_features();
      feature_metas_.resize(num_feature);
      for (int i = 0; i < num_feature; ++i) {
Guolin Ke's avatar
Guolin Ke committed
742
        feature_metas_[i].num_bin = train_data->FeatureNumBin(i);
743
        bin_cnt_over_features += static_cast<uint64_t>(feature_metas_[i].num_bin);
Guolin Ke's avatar
Guolin Ke committed
744
        feature_metas_[i].default_bin = train_data->FeatureBinMapper(i)->GetDefaultBin();
Guolin Ke's avatar
Guolin Ke committed
745
        feature_metas_[i].missing_type = train_data->FeatureBinMapper(i)->missing_type();
Guolin Ke's avatar
Guolin Ke committed
746
        feature_metas_[i].monotone_type = train_data->FeatureMonotone(i);
Guolin Ke's avatar
Guolin Ke committed
747
        feature_metas_[i].penalty = train_data->FeaturePenalte(i);
Guolin Ke's avatar
Guolin Ke committed
748
        if (train_data->FeatureBinMapper(i)->GetMostFreqBin() == 0) {
749
          feature_metas_[i].offset = 1;
Guolin Ke's avatar
Guolin Ke committed
750
        } else {
751
          feature_metas_[i].offset = 0;
Guolin Ke's avatar
Guolin Ke committed
752
        }
Guolin Ke's avatar
Guolin Ke committed
753
        feature_metas_[i].config = config;
754
        feature_metas_[i].bin_type = train_data->FeatureBinMapper(i)->bin_type();
Guolin Ke's avatar
Guolin Ke committed
755
      }
756
      Log::Info("Total Bins %d", bin_cnt_over_features);
Guolin Ke's avatar
Guolin Ke committed
757
    }
Guolin Ke's avatar
Guolin Ke committed
758
    int old_cache_size = static_cast<int>(pool_.size());
Guolin Ke's avatar
Guolin Ke committed
759
    Reset(cache_size, total_size);
Guolin Ke's avatar
Guolin Ke committed
760
761
762
763
764

    if (cache_size > old_cache_size) {
      pool_.resize(cache_size);
      data_.resize(cache_size);
    }
765
    int num_total_bin = static_cast<int>(train_data->NumTotalBin());
Guolin Ke's avatar
Guolin Ke committed
766

767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
    std::vector<int> offsets;
    if (is_hist_colwise) {
      int offset = 0;
      for (int j = 0; j < train_data->num_features(); ++j) {
        offset += train_data->SubFeatureBinOffset(j);
        offsets.push_back(offset);
        auto num_bin = train_data->FeatureNumBin(j);
        if (train_data->FeatureBinMapper(j)->GetMostFreqBin() == 0) {
          num_bin -= 1;
        }
        offset += num_bin;
      }
    } else {
      num_total_bin = 1;
      for (int j = 0; j < train_data->num_features(); ++j) {
        offsets.push_back(num_total_bin);
        num_total_bin += train_data->FeatureBinMapper(j)->num_bin();
        if (train_data->FeatureBinMapper(j)->GetMostFreqBin() == 0) {
          num_total_bin -= 1;
        }
      }
    }
789
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
790
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
791
    for (int i = old_cache_size; i < cache_size; ++i) {
792
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
793
      pool_[i].reset(new FeatureHistogram[train_data->num_features()]);
794
      data_[i].resize(num_total_bin * 2);
Guolin Ke's avatar
Guolin Ke committed
795
      for (int j = 0; j < train_data->num_features(); ++j) {
796
        pool_[i][j].Init(data_[i].data() + offsets[j] * 2, &feature_metas_[j]);
Guolin Ke's avatar
Guolin Ke committed
797
      }
798
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
799
    }
800
    OMP_THROW_EX();
801
    train_data_ = train_data;
Guolin Ke's avatar
Guolin Ke committed
802
803
  }

Guolin Ke's avatar
Guolin Ke committed
804
  void ResetConfig(const Config* config) {
Guolin Ke's avatar
Guolin Ke committed
805
    int size = static_cast<int>(feature_metas_.size());
806
    #pragma omp parallel for schedule(static, 512) if (size >= 1024)
Guolin Ke's avatar
Guolin Ke committed
807
    for (int i = 0; i < size; ++i) {
Guolin Ke's avatar
Guolin Ke committed
808
      feature_metas_[i].config = config;
809
810
      feature_metas_[i].monotone_type = train_data_->FeatureMonotone(i);
      feature_metas_[i].penalty = train_data_->FeaturePenalte(i);
Guolin Ke's avatar
Guolin Ke committed
811
812
    }
  }
813

Guolin Ke's avatar
Guolin Ke committed
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
  /*!
  * \brief Get data for the specific index
  * \param idx which index want to get
  * \param out output data will store into this
  * \return True if this index is in the pool, False if this index is not in the pool
  */
  bool Get(int idx, FeatureHistogram** out) {
    if (is_enough_) {
      *out = pool_[idx].get();
      return true;
    } else if (mapper_[idx] >= 0) {
      int slot = mapper_[idx];
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;
      return true;
    } else {
830
      // choose the least used slot
Guolin Ke's avatar
Guolin Ke committed
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
      int slot = static_cast<int>(ArrayArgs<int>::ArgMin(last_used_time_));
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;

      // reset previous mapper
      if (inverse_mapper_[slot] >= 0) mapper_[inverse_mapper_[slot]] = -1;

      // update current mapper
      mapper_[idx] = slot;
      inverse_mapper_[slot] = idx;
      return false;
    }
  }

  /*!
  * \brief Move data from one index to another index
  * \param src_idx
  * \param dst_idx
  */
  void Move(int src_idx, int dst_idx) {
    if (is_enough_) {
      std::swap(pool_[src_idx], pool_[dst_idx]);
      return;
    }
    if (mapper_[src_idx] < 0) {
      return;
    }
    // get slot of src idx
    int slot = mapper_[src_idx];
    // reset src_idx
    mapper_[src_idx] = -1;

    // move to dst idx
    mapper_[dst_idx] = slot;
    last_used_time_[slot] = ++cur_time_;
    inverse_mapper_[slot] = dst_idx;
  }
868

869
 private:
Guolin Ke's avatar
Guolin Ke committed
870
  std::vector<std::unique_ptr<FeatureHistogram[]>> pool_;
871
  std::vector<std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>> data_;
Guolin Ke's avatar
Guolin Ke committed
872
  std::vector<FeatureMetainfo> feature_metas_;
Guolin Ke's avatar
Guolin Ke committed
873
874
875
876
877
878
879
  int cache_size_;
  int total_size_;
  bool is_enough_ = false;
  std::vector<int> mapper_;
  std::vector<int> inverse_mapper_;
  std::vector<int> last_used_time_;
  int cur_time_ = 0;
880
  const Dataset* train_data_;
Guolin Ke's avatar
Guolin Ke committed
881
882
};

Guolin Ke's avatar
Guolin Ke committed
883
}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
884
#endif   // LightGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_