| 71 | } |
| 72 | |
| 73 | bool AliasSampling::Init(const vec_float_t& probs) { |
| 74 | size_t table_size = probs.size(); |
| 75 | |
| 76 | Clear(); |
| 77 | Resize(table_size); |
| 78 | |
| 79 | vec_int_t smaller; |
| 80 | vec_int_t larger; |
| 81 | for (size_t i = 0; i < probs.size(); ++i) { |
| 82 | alias_probs_[i] = table_size * probs[i]; |
| 83 | if (alias_probs_[i] < 1.0) { |
| 84 | smaller.emplace_back(i); |
| 85 | } else { |
| 86 | larger.emplace_back(i); |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | while (smaller.size() > 0 && larger.size() > 0) { |
| 91 | const auto s = smaller.back(); |
| 92 | smaller.pop_back(); |
| 93 | const auto l = larger.back(); |
| 94 | larger.pop_back(); |
| 95 | |
| 96 | alias_tables_[s] = l; |
| 97 | alias_probs_[l] += alias_probs_[s] - (float_t)1.0; |
| 98 | if (alias_probs_[l] < 1.0) { |
| 99 | smaller.emplace_back(l); |
| 100 | } else { |
| 101 | larger.emplace_back(l); |
| 102 | } |
| 103 | } |
| 104 | return true; |
| 105 | } |
| 106 | |
| 107 | std::unique_ptr<Sampling> NewAliasSampling(const vec_float_t* probs) { |
| 108 | return AliasSampling::Create(*probs); |