dense_bin.hpp 11.5 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
8
9
10
#ifndef LIGHTGBM_IO_DENSE_BIN_HPP_
#define LIGHTGBM_IO_DENSE_BIN_HPP_

#include <LightGBM/bin.h>

#include <cstdint>
11
12
#include <cstring>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
13
14
15

namespace LightGBM {

Guolin Ke's avatar
Guolin Ke committed
16
17
18
19
template <typename VAL_T>
class DenseBin;

template <typename VAL_T>
20
class DenseBinIterator: public BinIterator {
Nikita Titov's avatar
Nikita Titov committed
21
 public:
Guolin Ke's avatar
Guolin Ke committed
22
23
24
  explicit DenseBinIterator(const DenseBin<VAL_T>* bin_data, uint32_t min_bin, uint32_t max_bin, uint32_t default_bin)
    : bin_data_(bin_data), min_bin_(static_cast<VAL_T>(min_bin)),
    max_bin_(static_cast<VAL_T>(max_bin)),
Guolin Ke's avatar
Guolin Ke committed
25
    default_bin_(static_cast<VAL_T>(default_bin)) {
Guolin Ke's avatar
Guolin Ke committed
26
    if (default_bin_ == 0) {
27
      offset_ = 1;
Guolin Ke's avatar
Guolin Ke committed
28
    } else {
29
      offset_ = 0;
Guolin Ke's avatar
Guolin Ke committed
30
31
    }
  }
32
  inline uint32_t RawGet(data_size_t idx) override;
Guolin Ke's avatar
Guolin Ke committed
33
34
  inline uint32_t Get(data_size_t idx) override;
  inline void Reset(data_size_t) override { }
Nikita Titov's avatar
Nikita Titov committed
35
36

 private:
Guolin Ke's avatar
Guolin Ke committed
37
38
39
40
  const DenseBin<VAL_T>* bin_data_;
  VAL_T min_bin_;
  VAL_T max_bin_;
  VAL_T default_bin_;
41
  uint8_t offset_;
Guolin Ke's avatar
Guolin Ke committed
42
};
Guolin Ke's avatar
Guolin Ke committed
43
/*!
Hui Xue's avatar
Hui Xue committed
44
* \brief Used to store bins for dense feature
Guolin Ke's avatar
Guolin Ke committed
45
46
47
* Use template to reduce memory cost
*/
template <typename VAL_T>
48
class DenseBin: public Bin {
Nikita Titov's avatar
Nikita Titov committed
49
 public:
Guolin Ke's avatar
Guolin Ke committed
50
  friend DenseBinIterator<VAL_T>;
Guolin Ke's avatar
Guolin Ke committed
51
  explicit DenseBin(data_size_t num_data)
Guolin Ke's avatar
Guolin Ke committed
52
    : num_data_(num_data), data_(num_data_, static_cast<VAL_T>(0)) {
Guolin Ke's avatar
Guolin Ke committed
53
54
55
56
57
58
59
60
61
  }

  ~DenseBin() {
  }

  void Push(int, data_size_t idx, uint32_t value) override {
    data_[idx] = static_cast<VAL_T>(value);
  }

Guolin Ke's avatar
Guolin Ke committed
62
63
64
65
66
67
68
  void ReSize(data_size_t num_data) override {
    if (num_data_ != num_data) {
      num_data_ = num_data;
      data_.resize(num_data_);
    }
  }

Guolin Ke's avatar
Guolin Ke committed
69
  BinIterator* GetIterator(uint32_t min_bin, uint32_t max_bin, uint32_t default_bin) const override;
Guolin Ke's avatar
Guolin Ke committed
70

Guolin Ke's avatar
Guolin Ke committed
71
  void ConstructHistogram(const data_size_t* data_indices, data_size_t num_data,
72
                          const score_t* ordered_gradients, const score_t* ordered_hessians,
73
                          HistogramBinEntry* out) const override {
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
    const data_size_t rest = num_data & 0x3;
    data_size_t i = 0;
    for (; i < num_data - rest; i += 4) {
      const VAL_T bin0 = data_[data_indices[i]];
      const VAL_T bin1 = data_[data_indices[i + 1]];
      const VAL_T bin2 = data_[data_indices[i + 2]];
      const VAL_T bin3 = data_[data_indices[i + 3]];

      out[bin0].sum_gradients += ordered_gradients[i];
      out[bin1].sum_gradients += ordered_gradients[i + 1];
      out[bin2].sum_gradients += ordered_gradients[i + 2];
      out[bin3].sum_gradients += ordered_gradients[i + 3];

      out[bin0].sum_hessians += ordered_hessians[i];
      out[bin1].sum_hessians += ordered_hessians[i + 1];
      out[bin2].sum_hessians += ordered_hessians[i + 2];
      out[bin3].sum_hessians += ordered_hessians[i + 3];

      ++out[bin0].cnt;
      ++out[bin1].cnt;
      ++out[bin2].cnt;
      ++out[bin3].cnt;
    }
    for (; i < num_data; ++i) {
      const VAL_T bin = data_[data_indices[i]];
      out[bin].sum_gradients += ordered_gradients[i];
      out[bin].sum_hessians += ordered_hessians[i];
      ++out[bin].cnt;
    }
  }

  void ConstructHistogram(data_size_t num_data,
                          const score_t* ordered_gradients, const score_t* ordered_hessians,
                          HistogramBinEntry* out) const override {
    const data_size_t rest = num_data & 0x3;
    data_size_t i = 0;
    for (; i < num_data - rest; i += 4) {
      const VAL_T bin0 = data_[i];
      const VAL_T bin1 = data_[i + 1];
      const VAL_T bin2 = data_[i + 2];
      const VAL_T bin3 = data_[i + 3];

      out[bin0].sum_gradients += ordered_gradients[i];
      out[bin1].sum_gradients += ordered_gradients[i + 1];
      out[bin2].sum_gradients += ordered_gradients[i + 2];
      out[bin3].sum_gradients += ordered_gradients[i + 3];

      out[bin0].sum_hessians += ordered_hessians[i];
      out[bin1].sum_hessians += ordered_hessians[i + 1];
      out[bin2].sum_hessians += ordered_hessians[i + 2];
      out[bin3].sum_hessians += ordered_hessians[i + 3];

      ++out[bin0].cnt;
      ++out[bin1].cnt;
      ++out[bin2].cnt;
      ++out[bin3].cnt;
    }
    for (; i < num_data; ++i) {
      const VAL_T bin = data_[i];
      out[bin].sum_gradients += ordered_gradients[i];
      out[bin].sum_hessians += ordered_hessians[i];
      ++out[bin].cnt;
Guolin Ke's avatar
Guolin Ke committed
136
    }
Guolin Ke's avatar
Guolin Ke committed
137
138
  }

139
  void ConstructHistogram(const data_size_t* data_indices, data_size_t num_data,
140
                          const score_t* ordered_gradients,
141
                          HistogramBinEntry* out) const override {
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
    const data_size_t rest = num_data & 0x3;
    data_size_t i = 0;
    for (; i < num_data - rest; i += 4) {
      const VAL_T bin0 = data_[data_indices[i]];
      const VAL_T bin1 = data_[data_indices[i + 1]];
      const VAL_T bin2 = data_[data_indices[i + 2]];
      const VAL_T bin3 = data_[data_indices[i + 3]];

      out[bin0].sum_gradients += ordered_gradients[i];
      out[bin1].sum_gradients += ordered_gradients[i + 1];
      out[bin2].sum_gradients += ordered_gradients[i + 2];
      out[bin3].sum_gradients += ordered_gradients[i + 3];

      ++out[bin0].cnt;
      ++out[bin1].cnt;
      ++out[bin2].cnt;
      ++out[bin3].cnt;
    }
    for (; i < num_data; ++i) {
      const VAL_T bin = data_[data_indices[i]];
      out[bin].sum_gradients += ordered_gradients[i];
      ++out[bin].cnt;
    }
  }

  void ConstructHistogram(data_size_t num_data,
                          const score_t* ordered_gradients,
                          HistogramBinEntry* out) const override {
    const data_size_t rest = num_data & 0x3;
    data_size_t i = 0;
    for (; i < num_data - rest; i += 4) {
      const VAL_T bin0 = data_[i];
      const VAL_T bin1 = data_[i + 1];
      const VAL_T bin2 = data_[i + 2];
      const VAL_T bin3 = data_[i + 3];

      out[bin0].sum_gradients += ordered_gradients[i];
      out[bin1].sum_gradients += ordered_gradients[i + 1];
      out[bin2].sum_gradients += ordered_gradients[i + 2];
      out[bin3].sum_gradients += ordered_gradients[i + 3];

      ++out[bin0].cnt;
      ++out[bin1].cnt;
      ++out[bin2].cnt;
      ++out[bin3].cnt;
    }
    for (; i < num_data; ++i) {
      const VAL_T bin = data_[i];
      out[bin].sum_gradients += ordered_gradients[i];
      ++out[bin].cnt;
192
193
194
    }
  }

Guolin Ke's avatar
Guolin Ke committed
195
  data_size_t Split(
Guolin Ke's avatar
Guolin Ke committed
196
    uint32_t min_bin, uint32_t max_bin, uint32_t default_bin, MissingType missing_type, bool default_left,
Guolin Ke's avatar
Guolin Ke committed
197
    uint32_t threshold, data_size_t* data_indices, data_size_t num_data,
198
    data_size_t* lte_indices, data_size_t* gt_indices) const override {
Guolin Ke's avatar
Guolin Ke committed
199
200
    if (num_data <= 0) { return 0; }
    VAL_T th = static_cast<VAL_T>(threshold + min_bin);
201
202
    const VAL_T minb = static_cast<VAL_T>(min_bin);
    const VAL_T maxb = static_cast<VAL_T>(max_bin);
Guolin Ke's avatar
Guolin Ke committed
203
    VAL_T t_default_bin = static_cast<VAL_T>(min_bin + default_bin);
Guolin Ke's avatar
Guolin Ke committed
204
205
    if (default_bin == 0) {
      th -= 1;
Guolin Ke's avatar
Guolin Ke committed
206
      t_default_bin -= 1;
Guolin Ke's avatar
Guolin Ke committed
207
    }
Guolin Ke's avatar
Guolin Ke committed
208
209
    data_size_t lte_count = 0;
    data_size_t gt_count = 0;
Guolin Ke's avatar
Guolin Ke committed
210
211
    data_size_t* default_indices = gt_indices;
    data_size_t* default_count = &gt_count;
212
213
    if (missing_type == MissingType::NaN) {
      if (default_bin <= threshold) {
214
215
216
        default_indices = lte_indices;
        default_count = &lte_count;
      }
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
      data_size_t* missing_default_indices = gt_indices;
      data_size_t* missing_default_count = &gt_count;
      if (default_left) {
        missing_default_indices = lte_indices;
        missing_default_count = &lte_count;
      }
      for (data_size_t i = 0; i < num_data; ++i) {
        const data_size_t idx = data_indices[i];
        const VAL_T bin = data_[idx];
        if (bin < minb || bin > maxb || t_default_bin == bin) {
          default_indices[(*default_count)++] = idx;
        } else if (bin == maxb) {
          missing_default_indices[(*missing_default_count)++] = idx;
        } else if (bin > th) {
          gt_indices[gt_count++] = idx;
        } else {
          lte_indices[lte_count++] = idx;
234
235
236
        }
      }
    } else {
237
      if ((default_left && missing_type == MissingType::Zero) || (default_bin <= threshold && missing_type != MissingType::Zero)) {
238
239
240
241
242
        default_indices = lte_indices;
        default_count = &lte_count;
      }
      for (data_size_t i = 0; i < num_data; ++i) {
        const data_size_t idx = data_indices[i];
243
        const VAL_T bin = data_[idx];
Guolin Ke's avatar
Guolin Ke committed
244
        if (bin < minb || bin > maxb || t_default_bin == bin) {
245
          default_indices[(*default_count)++] = idx;
246
        } else if (bin > th) {
247
248
249
250
          gt_indices[gt_count++] = idx;
        } else {
          lte_indices[lte_count++] = idx;
        }
Guolin Ke's avatar
Guolin Ke committed
251
252
253
254
      }
    }
    return lte_count;
  }
Guolin Ke's avatar
Guolin Ke committed
255

Guolin Ke's avatar
Guolin Ke committed
256
  data_size_t SplitCategorical(
257
    uint32_t min_bin, uint32_t max_bin, uint32_t default_bin,
258
    const uint32_t* threshold, int num_threahold, data_size_t* data_indices, data_size_t num_data,
259
260
261
262
263
264
    data_size_t* lte_indices, data_size_t* gt_indices) const override {
    if (num_data <= 0) { return 0; }
    data_size_t lte_count = 0;
    data_size_t gt_count = 0;
    data_size_t* default_indices = gt_indices;
    data_size_t* default_count = &gt_count;
265
    if (Common::FindInBitset(threshold, num_threahold, default_bin)) {
266
267
268
269
270
271
272
273
      default_indices = lte_indices;
      default_count = &lte_count;
    }
    for (data_size_t i = 0; i < num_data; ++i) {
      const data_size_t idx = data_indices[i];
      const uint32_t bin = data_[idx];
      if (bin < min_bin || bin > max_bin) {
        default_indices[(*default_count)++] = idx;
274
      } else if (Common::FindInBitset(threshold, num_threahold, bin - min_bin)) {
275
276
277
278
279
280
281
282
        lte_indices[lte_count++] = idx;
      } else {
        gt_indices[gt_count++] = idx;
      }
    }
    return lte_count;
  }

Guolin Ke's avatar
Guolin Ke committed
283
284
285
286
287
288
289
290
291
  data_size_t num_data() const override { return num_data_; }

  /*! \brief not ordered bin for dense feature */
  OrderedBin* CreateOrderedBin() const override { return nullptr; }

  void FinishLoad() override {}

  void LoadFromMemory(const void* memory, const std::vector<data_size_t>& local_used_indices) override {
    const VAL_T* mem_data = reinterpret_cast<const VAL_T*>(memory);
Guolin Ke's avatar
Guolin Ke committed
292
    if (!local_used_indices.empty()) {
Guolin Ke's avatar
Guolin Ke committed
293
294
295
296
297
298
299
300
301
302
      for (int i = 0; i < num_data_; ++i) {
        data_[i] = mem_data[local_used_indices[i]];
      }
    } else {
      for (int i = 0; i < num_data_; ++i) {
        data_[i] = mem_data[i];
      }
    }
  }

303
  void CopySubset(const Bin* full_bin, const data_size_t* used_indices, data_size_t num_used_indices) override {
Guolin Ke's avatar
Guolin Ke committed
304
    auto other_bin = dynamic_cast<const DenseBin<VAL_T>*>(full_bin);
305
306
307
308
309
    for (int i = 0; i < num_used_indices; ++i) {
      data_[i] = other_bin->data_[used_indices[i]];
    }
  }

310
311
  void SaveBinaryToFile(const VirtualFileWriter* writer) const override {
    writer->Write(data_.data(), sizeof(VAL_T) * num_data_);
Guolin Ke's avatar
Guolin Ke committed
312
313
314
315
316
317
  }

  size_t SizesInByte() const override {
    return sizeof(VAL_T) * num_data_;
  }

318
319
320
  DenseBin<VAL_T>* Clone() override;

 private:
Guolin Ke's avatar
Guolin Ke committed
321
  data_size_t num_data_;
Guolin Ke's avatar
Guolin Ke committed
322
  std::vector<VAL_T> data_;
323
324
325

  DenseBin<VAL_T>(const DenseBin<VAL_T>& other)
    : num_data_(other.num_data_), data_(other.data_){}
Guolin Ke's avatar
Guolin Ke committed
326
327
};

328
template<typename VAL_T>
329
DenseBin<VAL_T>* DenseBin<VAL_T>::Clone() {
330
331
332
  return new DenseBin<VAL_T>(*this);
}

Guolin Ke's avatar
Guolin Ke committed
333
template <typename VAL_T>
Guolin Ke's avatar
Guolin Ke committed
334
335
336
uint32_t DenseBinIterator<VAL_T>::Get(data_size_t idx) {
  auto ret = bin_data_->data_[idx];
  if (ret >= min_bin_ && ret <= max_bin_) {
337
    return ret - min_bin_ + offset_;
Guolin Ke's avatar
Guolin Ke committed
338
339
  } else {
    return default_bin_;
Guolin Ke's avatar
Guolin Ke committed
340
341
  }
}
342

343
344
345
346
347
template <typename VAL_T>
inline uint32_t DenseBinIterator<VAL_T>::RawGet(data_size_t idx) {
  return bin_data_->data_[idx];
}

Guolin Ke's avatar
Guolin Ke committed
348
template <typename VAL_T>
Guolin Ke's avatar
Guolin Ke committed
349
350
351
BinIterator* DenseBin<VAL_T>::GetIterator(uint32_t min_bin, uint32_t max_bin, uint32_t default_bin) const {
  return new DenseBinIterator<VAL_T>(this, min_bin, max_bin, default_bin);
}
Guolin Ke's avatar
Guolin Ke committed
352

Guolin Ke's avatar
Guolin Ke committed
353
}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
354
#endif   // LightGBM_IO_DENSE_BIN_HPP_