common.h 22.3 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
#ifndef LIGHTGBM_UTILS_COMMON_FUN_H_
#define LIGHTGBM_UTILS_COMMON_FUN_H_

#include <LightGBM/utils/log.h>
5
#include <LightGBM/utils/openmp_wrapper.h>
Guolin Ke's avatar
Guolin Ke committed
6

7
#include <limits>
Guolin Ke's avatar
Guolin Ke committed
8
#include <string>
9
#include <algorithm>
10
#include <cmath>
11
12
#include <cstdint>
#include <cstdio>
Guolin Ke's avatar
Guolin Ke committed
13
#include <functional>
14
#include <iomanip>
15
#include <iterator>
16
17
#include <memory>
#include <sstream>
Guolin Ke's avatar
Guolin Ke committed
18
#include <type_traits>
19
20
#include <utility>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
21

22
23
24
25
#ifdef _MSC_VER
#include "intrin.h"
#endif

Guolin Ke's avatar
Guolin Ke committed
26
27
28
29
namespace LightGBM {

namespace Common {

30
inline static char tolower(char in) {
Guolin Ke's avatar
Guolin Ke committed
31
32
33
34
35
  if (in <= 'Z' && in >= 'A')
    return in - ('Z' - 'z');
  return in;
}

36
inline static std::string Trim(std::string str) {
Guolin Ke's avatar
Guolin Ke committed
37
  if (str.empty()) {
Guolin Ke's avatar
Guolin Ke committed
38
39
40
41
42
43
44
    return str;
  }
  str.erase(str.find_last_not_of(" \f\n\r\t\v") + 1);
  str.erase(0, str.find_first_not_of(" \f\n\r\t\v"));
  return str;
}

45
inline static std::string RemoveQuotationSymbol(std::string str) {
Guolin Ke's avatar
Guolin Ke committed
46
  if (str.empty()) {
47
48
49
50
51
52
    return str;
  }
  str.erase(str.find_last_not_of("'\"") + 1);
  str.erase(0, str.find_first_not_of("'\""));
  return str;
}
Guolin Ke's avatar
Guolin Ke committed
53

Guolin Ke's avatar
Guolin Ke committed
54
55
56
57
58
59
60
inline static bool StartsWith(const std::string& str, const std::string prefix) {
  if (str.substr(0, prefix.size()) == prefix) {
    return true;
  } else {
    return false;
  }
}
Guolin Ke's avatar
Guolin Ke committed
61

Guolin Ke's avatar
Guolin Ke committed
62
inline static std::vector<std::string> Split(const char* c_str, char delimiter) {
Guolin Ke's avatar
Guolin Ke committed
63
  std::vector<std::string> ret;
Guolin Ke's avatar
Guolin Ke committed
64
65
  std::string str(c_str);
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
66
67
68
69
70
71
72
73
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
  size_t pos = 0;
  while (pos < str.length()) {
    if (str[pos] == delimiter) {
      if (i < pos) {
        ret.push_back(str.substr(i, pos - i));
      }
      ++pos;
      i = pos;
    } else {
      ++pos;
    }
  }
  if (i < pos) {
    ret.push_back(str.substr(i));
  }
  return ret;
}

inline static std::vector<std::string> SplitLines(const char* c_str) {
  std::vector<std::string> ret;
  std::string str(c_str);
  size_t i = 0;
  size_t pos = 0;
  while (pos < str.length()) {
    if (str[pos] == '\n' || str[pos] == '\r') {
      if (i < pos) {
        ret.push_back(str.substr(i, pos - i));
      }
      // skip the line endings
      while (str[pos] == '\n' || str[pos] == '\r') ++pos;
      // new begin
      i = pos;
    } else {
      ++pos;
    }
  }
  if (i < pos) {
    ret.push_back(str.substr(i));
Guolin Ke's avatar
Guolin Ke committed
104
105
106
107
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
108
109
110
111
inline static std::vector<std::string> Split(const char* c_str, const char* delimiters) {
  std::vector<std::string> ret;
  std::string str(c_str);
  size_t i = 0;
Guolin Ke's avatar
Guolin Ke committed
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
  size_t pos = 0;
  while (pos < str.length()) {
    bool met_delimiters = false;
    for (int j = 0; delimiters[j] != '\0'; ++j) {
      if (str[pos] == delimiters[j]) {
        met_delimiters = true;
        break;
      }
    }
    if (met_delimiters) {
      if (i < pos) {
        ret.push_back(str.substr(i, pos - i));
      }
      ++pos;
      i = pos;
    } else {
      ++pos;
    }
  }
  if (i < pos) {
    ret.push_back(str.substr(i));
Guolin Ke's avatar
Guolin Ke committed
133
134
135
136
  }
  return ret;
}

137
138
139
140
template<typename T>
inline static const char* Atoi(const char* p, T* out) {
  int sign;
  T value;
Guolin Ke's avatar
Guolin Ke committed
141
142
143
144
145
146
147
  while (*p == ' ') {
    ++p;
  }
  sign = 1;
  if (*p == '-') {
    sign = -1;
    ++p;
148
  } else if (*p == '+') {
Guolin Ke's avatar
Guolin Ke committed
149
150
151
152
153
    ++p;
  }
  for (value = 0; *p >= '0' && *p <= '9'; ++p) {
    value = value * 10 + (*p - '0');
  }
154
  *out = static_cast<T>(sign * value);
Guolin Ke's avatar
Guolin Ke committed
155
156
157
158
159
160
  while (*p == ' ') {
    ++p;
  }
  return p;
}

161
template<typename T>
162
163
164
165
166
167
168
169
170
171
172
173
174
175
inline static double Pow(T base, int power) {
  if (power < 0) {
    return 1.0 / Pow(base, -power);
  } else if (power == 0) {
    return 1;
  } else if (power % 2 == 0) {
    return Pow(base*base, power / 2);
  } else if (power % 3 == 0) {
    return Pow(base*base*base, power / 3);
  } else {
    return base * Pow(base, power - 1);
  }
}

176
inline static const char* Atof(const char* p, double* out) {
Guolin Ke's avatar
Guolin Ke committed
177
  int frac;
178
  double sign, value, scale;
Guolin Ke's avatar
Guolin Ke committed
179
  *out = NAN;
Guolin Ke's avatar
Guolin Ke committed
180
181
182
183
184
  // Skip leading white space, if any.
  while (*p == ' ') {
    ++p;
  }
  // Get sign, if any.
185
  sign = 1.0;
Guolin Ke's avatar
Guolin Ke committed
186
  if (*p == '-') {
187
    sign = -1.0;
Guolin Ke's avatar
Guolin Ke committed
188
    ++p;
189
  } else if (*p == '+') {
Guolin Ke's avatar
Guolin Ke committed
190
191
192
    ++p;
  }

Guolin Ke's avatar
Guolin Ke committed
193
194
195
  // is a number
  if ((*p >= '0' && *p <= '9') || *p == '.' || *p == 'e' || *p == 'E') {
    // Get digits before decimal point or exponent, if any.
196
197
    for (value = 0.0; *p >= '0' && *p <= '9'; ++p) {
      value = value * 10.0 + (*p - '0');
Guolin Ke's avatar
Guolin Ke committed
198
    }
Guolin Ke's avatar
Guolin Ke committed
199

Guolin Ke's avatar
Guolin Ke committed
200
201
    // Get digits after decimal point, if any.
    if (*p == '.') {
202
203
      double right = 0.0;
      int nn = 0;
Guolin Ke's avatar
Guolin Ke committed
204
      ++p;
Guolin Ke's avatar
Guolin Ke committed
205
      while (*p >= '0' && *p <= '9') {
206
207
        right = (*p - '0') + right * 10.0;
        ++nn;
Guolin Ke's avatar
Guolin Ke committed
208
209
        ++p;
      }
210
      value += right / Pow(10.0, nn);
Guolin Ke's avatar
Guolin Ke committed
211
212
    }

Guolin Ke's avatar
Guolin Ke committed
213
214
    // Handle exponent, if any.
    frac = 0;
215
    scale = 1.0;
Guolin Ke's avatar
Guolin Ke committed
216
    if ((*p == 'e') || (*p == 'E')) {
Guolin Ke's avatar
Guolin Ke committed
217
      uint32_t expon;
Guolin Ke's avatar
Guolin Ke committed
218
      // Get sign of exponent, if any.
Guolin Ke's avatar
Guolin Ke committed
219
      ++p;
Guolin Ke's avatar
Guolin Ke committed
220
221
222
223
224
225
226
227
228
229
      if (*p == '-') {
        frac = 1;
        ++p;
      } else if (*p == '+') {
        ++p;
      }
      // Get digits of exponent, if any.
      for (expon = 0; *p >= '0' && *p <= '9'; ++p) {
        expon = expon * 10 + (*p - '0');
      }
230
231
232
      if (expon > 308) expon = 308;
      // Calculate scaling factor.
      while (expon >= 50) { scale *= 1E50; expon -= 50; }
Guolin Ke's avatar
Guolin Ke committed
233
      while (expon >= 8) { scale *= 1E8;  expon -= 8; }
234
      while (expon > 0) { scale *= 10.0; expon -= 1; }
Guolin Ke's avatar
Guolin Ke committed
235
    }
Guolin Ke's avatar
Guolin Ke committed
236
237
238
    // Return signed and scaled floating point result.
    *out = sign * (frac ? (value / scale) : (value * scale));
  } else {
239
    size_t cnt = 0;
240
    while (*(p + cnt) != '\0' && *(p + cnt) != ' '
241
242
243
           && *(p + cnt) != '\t' && *(p + cnt) != ','
           && *(p + cnt) != '\n' && *(p + cnt) != '\r'
           && *(p + cnt) != ':') {
244
245
      ++cnt;
    }
246
    if (cnt > 0) {
Guolin Ke's avatar
Guolin Ke committed
247
      std::string tmp_str(p, cnt);
Guolin Ke's avatar
Guolin Ke committed
248
      std::transform(tmp_str.begin(), tmp_str.end(), tmp_str.begin(), Common::tolower);
zhangjin's avatar
zhangjin committed
249
250
      if (tmp_str == std::string("na") || tmp_str == std::string("nan") ||
          tmp_str == std::string("null")) {
Guolin Ke's avatar
Guolin Ke committed
251
        *out = NAN;
252
      } else if (tmp_str == std::string("inf") || tmp_str == std::string("infinity")) {
253
        *out = sign * 1e308;
254
      } else {
255
        Log::Fatal("Unknown token %s in data file", tmp_str.c_str());
Guolin Ke's avatar
Guolin Ke committed
256
257
      }
      p += cnt;
258
    }
Guolin Ke's avatar
Guolin Ke committed
259
  }
Guolin Ke's avatar
Guolin Ke committed
260

Guolin Ke's avatar
Guolin Ke committed
261
262
263
  while (*p == ' ') {
    ++p;
  }
Guolin Ke's avatar
Guolin Ke committed
264

Guolin Ke's avatar
Guolin Ke committed
265
266
267
  return p;
}

268
inline static bool AtoiAndCheck(const char* p, int* out) {
269
270
271
272
273
274
275
  const char* after = Atoi(p, out);
  if (*after != '\0') {
    return false;
  }
  return true;
}

276
inline static bool AtofAndCheck(const char* p, double* out) {
277
278
279
280
281
282
283
  const char* after = Atof(p, out);
  if (*after != '\0') {
    return false;
  }
  return true;
}

284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
inline static unsigned CountDecimalDigit32(uint32_t n) {
#if defined(_MSC_VER) || defined(__GNUC__)
  static const uint32_t powers_of_10[] = {
    0,
    10,
    100,
    1000,
    10000,
    100000,
    1000000,
    10000000,
    100000000,
    1000000000
  };
#ifdef _MSC_VER
  unsigned long i = 0;
  _BitScanReverse(&i, n | 1);
  uint32_t t = (i + 1) * 1233 >> 12;
#elif __GNUC__
  uint32_t t = (32 - __builtin_clz(n | 1)) * 1233 >> 12;
#endif
  return t - (n < powers_of_10[t]) + 1;
#else
  if (n < 10) return 1;
  if (n < 100) return 2;
  if (n < 1000) return 3;
  if (n < 10000) return 4;
  if (n < 100000) return 5;
  if (n < 1000000) return 6;
  if (n < 10000000) return 7;
  if (n < 100000000) return 8;
  if (n < 1000000000) return 9;
  return 10;
#endif
}

inline static void Uint32ToStr(uint32_t value, char* buffer) {
  const char kDigitsLut[200] = {
322
323
324
325
326
327
328
329
330
331
    '0', '0', '0', '1', '0', '2', '0', '3', '0', '4', '0', '5', '0', '6', '0', '7', '0', '8', '0', '9',
    '1', '0', '1', '1', '1', '2', '1', '3', '1', '4', '1', '5', '1', '6', '1', '7', '1', '8', '1', '9',
    '2', '0', '2', '1', '2', '2', '2', '3', '2', '4', '2', '5', '2', '6', '2', '7', '2', '8', '2', '9',
    '3', '0', '3', '1', '3', '2', '3', '3', '3', '4', '3', '5', '3', '6', '3', '7', '3', '8', '3', '9',
    '4', '0', '4', '1', '4', '2', '4', '3', '4', '4', '4', '5', '4', '6', '4', '7', '4', '8', '4', '9',
    '5', '0', '5', '1', '5', '2', '5', '3', '5', '4', '5', '5', '5', '6', '5', '7', '5', '8', '5', '9',
    '6', '0', '6', '1', '6', '2', '6', '3', '6', '4', '6', '5', '6', '6', '6', '7', '6', '8', '6', '9',
    '7', '0', '7', '1', '7', '2', '7', '3', '7', '4', '7', '5', '7', '6', '7', '7', '7', '8', '7', '9',
    '8', '0', '8', '1', '8', '2', '8', '3', '8', '4', '8', '5', '8', '6', '8', '7', '8', '8', '8', '9',
    '9', '0', '9', '1', '9', '2', '9', '3', '9', '4', '9', '5', '9', '6', '9', '7', '9', '8', '9', '9'
332
333
334
335
336
337
338
339
340
341
342
343
344
  };
  unsigned digit = CountDecimalDigit32(value);
  buffer += digit;
  *buffer = '\0';

  while (value >= 100) {
    const unsigned i = (value % 100) << 1;
    value /= 100;
    *--buffer = kDigitsLut[i + 1];
    *--buffer = kDigitsLut[i];
  }

  if (value < 10) {
345
    *--buffer = static_cast<char>(value) + '0';
346
  } else {
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
    const unsigned i = value << 1;
    *--buffer = kDigitsLut[i + 1];
    *--buffer = kDigitsLut[i];
  }
}

inline static void Int32ToStr(int32_t value, char* buffer) {
  uint32_t u = static_cast<uint32_t>(value);
  if (value < 0) {
    *buffer++ = '-';
    u = ~u + 1;
  }
  Uint32ToStr(u, buffer);
}

362
inline static void DoubleToStr(double value, char* buffer, size_t
363
364
365
366
367
368
369
370
371
372
373
                               #ifdef _MSC_VER
                               buffer_len
                               #endif
) {
  #ifdef _MSC_VER
  sprintf_s(buffer, buffer_len, "%.17g", value);
  #else
  sprintf(buffer, "%.17g", value);
  #endif
}

Guolin Ke's avatar
Guolin Ke committed
374
375
376
377
378
379
380
381
382
383
384
385
386
387
inline static const char* SkipSpaceAndTab(const char* p) {
  while (*p == ' ' || *p == '\t') {
    ++p;
  }
  return p;
}

inline static const char* SkipReturn(const char* p) {
  while (*p == '\n' || *p == '\r' || *p == ' ') {
    ++p;
  }
  return p;
}

Guolin Ke's avatar
Guolin Ke committed
388
389
template<typename T, typename T2>
inline static std::vector<T2> ArrayCast(const std::vector<T>& arr) {
390
  std::vector<T2> ret(arr.size());
Guolin Ke's avatar
Guolin Ke committed
391
  for (size_t i = 0; i < arr.size(); ++i) {
392
    ret[i] = static_cast<T2>(arr[i]);
Guolin Ke's avatar
Guolin Ke committed
393
  }
Guolin Ke's avatar
Guolin Ke committed
394
  return ret;
Guolin Ke's avatar
Guolin Ke committed
395
396
}

397
398
template<typename T, bool is_float, bool is_unsign>
struct __TToStringHelperFast {
399
  void operator()(T value, char* buffer, size_t) const {
400
401
402
403
404
405
    Int32ToStr(value, buffer);
  }
};

template<typename T>
struct __TToStringHelperFast<T, true, false> {
406
  void operator()(T value, char* buffer, size_t
407
408
409
410
411
412
413
414
415
416
417
418
419
420
                  #ifdef _MSC_VER
                  buf_len
                  #endif
                  ) const {
    #ifdef _MSC_VER
    sprintf_s(buffer, buf_len, "%g", value);
    #else
    sprintf(buffer, "%g", value);
    #endif
  }
};

template<typename T>
struct __TToStringHelperFast<T, false, true> {
421
  void operator()(T value, char* buffer, size_t) const {
422
423
424
425
    Uint32ToStr(value, buffer);
  }
};

426
template<typename T>
427
428
inline static std::string ArrayToStringFast(const std::vector<T>& arr, size_t n) {
  if (arr.empty() || n == 0) {
429
    return std::string("");
Guolin Ke's avatar
Guolin Ke committed
430
  }
431
432
433
  __TToStringHelperFast<T, std::is_floating_point<T>::value, std::is_unsigned<T>::value> helper;
  const size_t buf_len = 16;
  std::vector<char> buffer(buf_len);
434
  std::stringstream str_buf;
435
436
437
438
439
  helper(arr[0], buffer.data(), buf_len);
  str_buf << buffer.data();
  for (size_t i = 1; i < std::min(n, arr.size()); ++i) {
    helper(arr[i], buffer.data(), buf_len);
    str_buf << ' ' << buffer.data();
Guolin Ke's avatar
Guolin Ke committed
440
  }
441
  return str_buf.str();
Guolin Ke's avatar
Guolin Ke committed
442
443
}

444
inline static std::string ArrayToString(const std::vector<double>& arr, size_t n) {
Guolin Ke's avatar
Guolin Ke committed
445
446
447
  if (arr.empty() || n == 0) {
    return std::string("");
  }
448
449
  const size_t buf_len = 32;
  std::vector<char> buffer(buf_len);
Guolin Ke's avatar
Guolin Ke committed
450
  std::stringstream str_buf;
451
452
  DoubleToStr(arr[0], buffer.data(), buf_len);
  str_buf << buffer.data();
Guolin Ke's avatar
Guolin Ke committed
453
  for (size_t i = 1; i < std::min(n, arr.size()); ++i) {
454
455
    DoubleToStr(arr[i], buffer.data(), buf_len);
    str_buf << ' ' << buffer.data();
Guolin Ke's avatar
Guolin Ke committed
456
457
458
459
  }
  return str_buf.str();
}

460
461
462
template<typename T, bool is_float>
struct __StringToTHelper {
  T operator()(const std::string& str) const {
463
464
465
    T ret = 0;
    Atoi(str.c_str(), &ret);
    return ret;
466
467
468
469
470
471
472
473
474
475
  }
};

template<typename T>
struct __StringToTHelper<T, true> {
  T operator()(const std::string& str) const {
    return static_cast<T>(std::stod(str));
  }
};

Guolin Ke's avatar
Guolin Ke committed
476
template<typename T>
477
inline static std::vector<T> StringToArray(const std::string& str, char delimiter) {
Guolin Ke's avatar
Guolin Ke committed
478
  std::vector<std::string> strs = Split(str.c_str(), delimiter);
479
480
  std::vector<T> ret;
  ret.reserve(strs.size());
481
  __StringToTHelper<T, std::is_floating_point<T>::value> helper;
482
483
  for (const auto& s : strs) {
    ret.push_back(helper(s));
Guolin Ke's avatar
Guolin Ke committed
484
485
486
487
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
488
template<typename T>
489
490
491
492
493
494
inline static std::vector<T> StringToArray(const std::string& str, int n) {
  if (n == 0) {
    return std::vector<T>();
  }
  std::vector<std::string> strs = Split(str.c_str(), ' ');
  CHECK(strs.size() == static_cast<size_t>(n));
Guolin Ke's avatar
Guolin Ke committed
495
  std::vector<T> ret;
496
497
498
499
  ret.reserve(strs.size());
  __StringToTHelper<T, std::is_floating_point<T>::value> helper;
  for (const auto& s : strs) {
    ret.push_back(helper(s));
Guolin Ke's avatar
Guolin Ke committed
500
501
502
503
  }
  return ret;
}

504
505
506
507
508
509
510
511
512
513
514
515
template<typename T, bool is_float>
struct __StringToTHelperFast {
  const char* operator()(const char*p, T* out) const {
    return Atoi(p, out);
  }
};

template<typename T>
struct __StringToTHelperFast<T, true> {
  const char* operator()(const char*p, T* out) const {
    double tmp = 0.0f;
    auto ret = Atof(p, &tmp);
516
    *out = static_cast<T>(tmp);
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
    return ret;
  }
};

template<typename T>
inline static std::vector<T> StringToArrayFast(const std::string& str, int n) {
  if (n == 0) {
    return std::vector<T>();
  }
  auto p_str = str.c_str();
  __StringToTHelperFast<T, std::is_floating_point<T>::value> helper;
  std::vector<T> ret(n);
  for (int i = 0; i < n; ++i) {
    p_str = helper(p_str, &ret[i]);
  }
  return ret;
}

535
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
536
inline static std::string Join(const std::vector<T>& strs, const char* delimiter) {
Guolin Ke's avatar
Guolin Ke committed
537
  if (strs.empty()) {
Guolin Ke's avatar
Guolin Ke committed
538
539
    return std::string("");
  }
540
  std::stringstream str_buf;
541
  str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
542
  str_buf << strs[0];
Guolin Ke's avatar
Guolin Ke committed
543
  for (size_t i = 1; i < strs.size(); ++i) {
544
545
    str_buf << delimiter;
    str_buf << strs[i];
Guolin Ke's avatar
Guolin Ke committed
546
  }
547
  return str_buf.str();
Guolin Ke's avatar
Guolin Ke committed
548
549
}

550
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
551
inline static std::string Join(const std::vector<T>& strs, size_t start, size_t end, const char* delimiter) {
Guolin Ke's avatar
Guolin Ke committed
552
553
554
  if (end - start <= 0) {
    return std::string("");
  }
Guolin Ke's avatar
Guolin Ke committed
555
556
  start = std::min(start, static_cast<size_t>(strs.size()) - 1);
  end = std::min(end, static_cast<size_t>(strs.size()));
557
  std::stringstream str_buf;
558
  str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
559
  str_buf << strs[start];
Guolin Ke's avatar
Guolin Ke committed
560
  for (size_t i = start + 1; i < end; ++i) {
561
562
    str_buf << delimiter;
    str_buf << strs[i];
Guolin Ke's avatar
Guolin Ke committed
563
  }
564
  return str_buf.str();
Guolin Ke's avatar
Guolin Ke committed
565
566
}

567
inline static int64_t Pow2RoundUp(int64_t x) {
Guolin Ke's avatar
Guolin Ke committed
568
569
570
571
572
573
574
575
576
577
  int64_t t = 1;
  for (int i = 0; i < 64; ++i) {
    if (t >= x) {
      return t;
    }
    t <<= 1;
  }
  return 0;
}

578
579
580
581
/*!
 * \brief Do inplace softmax transformaton on p_rec
 * \param p_rec The input/output vector of the values.
 */
582
inline static void Softmax(std::vector<double>* p_rec) {
583
584
  std::vector<double> &rec = *p_rec;
  double wmax = rec[0];
585
586
587
  for (size_t i = 1; i < rec.size(); ++i) {
    wmax = std::max(rec[i], wmax);
  }
588
  double wsum = 0.0f;
589
590
591
592
593
  for (size_t i = 0; i < rec.size(); ++i) {
    rec[i] = std::exp(rec[i] - wmax);
    wsum += rec[i];
  }
  for (size_t i = 0; i < rec.size(); ++i) {
594
    rec[i] /= static_cast<double>(wsum);
595
596
597
  }
}

598
inline static void Softmax(const double* input, double* output, int len) {
Guolin Ke's avatar
Guolin Ke committed
599
  double wmax = input[0];
600
  for (int i = 1; i < len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
601
    wmax = std::max(input[i], wmax);
602
603
604
  }
  double wsum = 0.0f;
  for (int i = 0; i < len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
605
606
    output[i] = std::exp(input[i] - wmax);
    wsum += output[i];
607
608
  }
  for (int i = 0; i < len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
609
    output[i] /= static_cast<double>(wsum);
610
611
612
  }
}

Guolin Ke's avatar
Guolin Ke committed
613
614
615
616
617
template<typename T>
std::vector<const T*> ConstPtrInVectorWrapper(const std::vector<std::unique_ptr<T>>& input) {
  std::vector<const T*> ret;
  for (size_t i = 0; i < input.size(); ++i) {
    ret.push_back(input.at(i).get());
618
  }
Guolin Ke's avatar
Guolin Ke committed
619
  return ret;
620
621
}

Guolin Ke's avatar
Guolin Ke committed
622
template<typename T1, typename T2>
623
inline static void SortForPair(std::vector<T1>& keys, std::vector<T2>& values, size_t start, bool is_reverse = false) {
Guolin Ke's avatar
Guolin Ke committed
624
625
626
627
628
  std::vector<std::pair<T1, T2>> arr;
  for (size_t i = start; i < keys.size(); ++i) {
    arr.emplace_back(keys[i], values[i]);
  }
  if (!is_reverse) {
629
    std::stable_sort(arr.begin(), arr.end(), [](const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) {
Guolin Ke's avatar
Guolin Ke committed
630
631
632
      return a.first < b.first;
    });
  } else {
633
    std::stable_sort(arr.begin(), arr.end(), [](const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) {
Guolin Ke's avatar
Guolin Ke committed
634
635
636
637
638
639
640
641
642
      return a.first > b.first;
    });
  }
  for (size_t i = start; i < arr.size(); ++i) {
    keys[i] = arr[i].first;
    values[i] = arr[i].second;
  }
}

643
template <typename T>
Guolin Ke's avatar
Guolin Ke committed
644
645
inline static std::vector<T*> Vector2Ptr(std::vector<std::vector<T>>& data) {
  std::vector<T*> ptr(data.size());
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
  for (size_t i = 0; i < data.size(); ++i) {
    ptr[i] = data[i].data();
  }
  return ptr;
}

template <typename T>
inline static std::vector<int> VectorSize(const std::vector<std::vector<T>>& data) {
  std::vector<int> ret(data.size());
  for (size_t i = 0; i < data.size(); ++i) {
    ret[i] = static_cast<int>(data[i].size());
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
661
inline static double AvoidInf(double x) {
Guolin Ke's avatar
Guolin Ke committed
662
663
  if (x >= 1e300) {
    return 1e300;
664
  } else if (x <= -1e300) {
Guolin Ke's avatar
Guolin Ke committed
665
    return -1e300;
Guolin Ke's avatar
Guolin Ke committed
666
667
668
669
670
  } else {
    return x;
  }
}

671
inline static float AvoidInf(float x) {
672
673
674
675
676
677
678
  if (x >= 1e38) {
    return 1e38f;
  } else if (x <= -1e38) {
    return -1e38f;
  } else {
    return x;
  }
679
680
681
}

template<typename _Iter> inline
682
683
684
685
static typename std::iterator_traits<_Iter>::value_type* IteratorValType(_Iter) {
  return (0);
}

686
template<typename _RanIt, typename _Pr, typename _VTRanIt> inline
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
static void ParallelSort(_RanIt _First, _RanIt _Last, _Pr _Pred, _VTRanIt*) {
  size_t len = _Last - _First;
  const size_t kMinInnerLen = 1024;
  int num_threads = 1;
  #pragma omp parallel
  #pragma omp master
  {
    num_threads = omp_get_num_threads();
  }
  if (len <= kMinInnerLen || num_threads <= 1) {
    std::sort(_First, _Last, _Pred);
    return;
  }
  size_t inner_size = (len + num_threads - 1) / num_threads;
  inner_size = std::max(inner_size, kMinInnerLen);
  num_threads = static_cast<int>((len + inner_size - 1) / inner_size);
703
  #pragma omp parallel for schedule(static, 1)
704
705
706
707
708
709
710
711
712
713
714
  for (int i = 0; i < num_threads; ++i) {
    size_t left = inner_size*i;
    size_t right = left + inner_size;
    right = std::min(right, len);
    if (right > left) {
      std::sort(_First + left, _First + right, _Pred);
    }
  }
  // Buffer for merge.
  std::vector<_VTRanIt> temp_buf(len);
  _RanIt buf = temp_buf.begin();
715
  size_t s = inner_size;
716
717
718
  // Recursive merge
  while (s < len) {
    int loop_size = static_cast<int>((len + s * 2 - 1) / (s * 2));
719
    #pragma omp parallel for schedule(static, 1)
720
721
722
723
724
    for (int i = 0; i < loop_size; ++i) {
      size_t left = i * 2 * s;
      size_t mid = left + s;
      size_t right = mid + s;
      right = std::min(len, right);
Guolin Ke's avatar
Guolin Ke committed
725
      if (mid >= right) { continue; }
726
727
728
729
730
731
732
      std::copy(_First + left, _First + mid, buf + left);
      std::merge(buf + left, buf + mid, _First + mid, _First + right, _First + left, _Pred);
    }
    s *= 2;
  }
}

733
template<typename _RanIt, typename _Pr> inline
734
735
736
737
static void ParallelSort(_RanIt _First, _RanIt _Last, _Pr _Pred) {
  return ParallelSort(_First, _Last, _Pred, IteratorValType(_First));
}

738
// Check that all y[] are in interval [ymin, ymax] (end points included); throws error if not
739
template <typename T>
740
inline static void CheckElementsIntervalClosed(const T *y, T ymin, T ymax, int ny, const char *callername) {
741
  auto fatal_msg = [&y, &ymin, &ymax, &callername](int i) {
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
    std::ostringstream os;
    os << "[%s]: does not tolerate element [#%i = " << y[i] << "] outside [" << ymin << ", " << ymax << "]";
    Log::Fatal(os.str().c_str(), callername, i);
  };
  for (int i = 1; i < ny; i += 2) {
    if (y[i - 1] < y[i]) {
      if (y[i - 1] < ymin) {
        fatal_msg(i - 1);
      } else if (y[i] > ymax) {
        fatal_msg(i);
      }
    } else {
      if (y[i - 1] > ymax) {
        fatal_msg(i - 1);
      } else if (y[i] < ymin) {
        fatal_msg(i);
      }
    }
  }
761
  if (ny & 1) {  // odd
762
763
    if (y[ny - 1] < ymin || y[ny - 1] > ymax) {
      fatal_msg(ny - 1);
764
765
766
767
768
769
    }
  }
}

// One-pass scan over array w with nw elements: find min, max and sum of elements;
// this is useful for checking weight requirements.
770
template <typename T1, typename T2>
771
inline static void ObtainMinMaxSum(const T1 *w, int nw, T1 *mi, T1 *ma, T2 *su) {
772
773
774
775
  T1 minw;
  T1 maxw;
  T1 sumw;
  int i;
776
  if (nw & 1) {  // odd
777
778
779
780
    minw = w[0];
    maxw = w[0];
    sumw = w[0];
    i = 2;
781
  } else {  // even
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
    if (w[0] < w[1]) {
      minw = w[0];
      maxw = w[1];
    } else {
      minw = w[1];
      maxw = w[0];
    }
    sumw = w[0] + w[1];
    i = 3;
  }
  for (; i < nw; i += 2) {
    if (w[i - 1] < w[i]) {
      minw = std::min(minw, w[i - 1]);
      maxw = std::max(maxw, w[i]);
    } else {
      minw = std::min(minw, w[i]);
      maxw = std::max(maxw, w[i - 1]);
    }
    sumw += w[i - 1] + w[i];
  }
  if (mi != nullptr) {
    *mi = minw;
  }
  if (ma != nullptr) {
    *ma = maxw;
  }
  if (su != nullptr) {
    *su = static_cast<T2>(sumw);
  }
811
812
}

813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
inline static std::vector<uint32_t> EmptyBitset(int n){
  int size = n / 32;
  if(n % 32 != 0) size++;
  return std::vector<uint32_t>(size);
}

template<typename T>
inline static void InsertBitset(std::vector<uint32_t>& vec, const T val){
    int i1 = val / 32;
    int i2 = val % 32;
    if (static_cast<int>(vec.size()) < i1 + 1) {
      vec.resize(i1 + 1, 0);
    }
    vec[i1] |= (1 << i2);  
}

829
830
template<typename T>
inline static std::vector<uint32_t> ConstructBitset(const T* vals, int n) {
831
832
833
834
835
836
837
838
839
840
841
842
  std::vector<uint32_t> ret;
  for (int i = 0; i < n; ++i) {
    int i1 = vals[i] / 32;
    int i2 = vals[i] % 32;
    if (static_cast<int>(ret.size()) < i1 + 1) {
      ret.resize(i1 + 1, 0);
    }
    ret[i1] |= (1 << i2);
  }
  return ret;
}

843
844
template<typename T>
inline static bool FindInBitset(const uint32_t* bits, int n, T pos) {
845
846
847
848
849
850
851
852
  int i1 = pos / 32;
  if (i1 >= n) {
    return false;
  }
  int i2 = pos % 32;
  return (bits[i1] >> i2) & 1;
}

853
854
855
856
857
858
859
860
861
inline static bool CheckDoubleEqualOrdered(double a, double b) {
  double upper = std::nextafter(a, INFINITY);
  return b <= upper;
}

inline static double GetDoubleUpperBound(double a) {
  return std::nextafter(a, INFINITY);;
}

862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
inline static size_t GetLine(const char* str) {
  auto start = str;
  while (*str != '\0' && *str != '\n' && *str != '\r') {
    ++str;
  }
  return str - start;
}

inline static const char* SkipNewLine(const char* str) {
  if (*str == '\r') {
    ++str;
  }
  if (*str == '\n') {
    ++str;
  }
  return str;
}

880
881
882
883
884
template <typename T>
static int Sign(T x) {
  return (x > T(0)) - (x < T(0));
}

Guolin Ke's avatar
Guolin Ke committed
885
886
887
888
889
890
891
892
893
template <typename T>
static T SafeLog(T x) {
  if (x > 0) {
    return std::log(x);
  } else {
    return -INFINITY;
  }
}

Guolin Ke's avatar
Guolin Ke committed
894
895
896
897
}  // namespace Common

}  // namespace LightGBM

Guolin Ke's avatar
Guolin Ke committed
898
#endif   // LightGBM_UTILS_COMMON_FUN_H_