MCPcopy Create free account
hub / github.com/apache/arrow / Finalize

Function Finalize

cpp/src/arrow/compute/kernels/aggregate_mode.cc:78–117  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

76// suboptimal for tiny or large n, possibly okay as we're not in hot path
77template <typename InType, typename Generator>
78Status Finalize(KernelContext* ctx, const DataType& type, ExecResult* out,
79 Generator&& gen) {
80 using CType = typename TypeTraits<InType>::CType;
81
82 using ValueCountPair = std::pair<CType, uint64_t>;
83 auto gt = [](const ValueCountPair& lhs, const ValueCountPair& rhs) {
84 const bool rhs_is_nan = rhs.first != rhs.first; // nan as largest value
85 return lhs.second > rhs.second ||
86 (lhs.second == rhs.second && (lhs.first < rhs.first || rhs_is_nan));
87 };
88
89 std::priority_queue<ValueCountPair, std::vector<ValueCountPair>, decltype(gt)> min_heap(
90 std::move(gt));
91
92 const ModeOptions& options = ModeState::Get(ctx);
93 while (true) {
94 const ValueCountPair& value_count = gen();
95 DCHECK_NE(value_count.second, 0);
96 if (value_count.second == kCountEOF) break;
97 if (static_cast<int64_t>(min_heap.size()) < options.n) {
98 min_heap.push(value_count);
99 } else if (gt(value_count, min_heap.top())) {
100 min_heap.pop();
101 min_heap.push(value_count);
102 }
103 }
104 const int64_t n = min_heap.size();
105
106 CType* mode_buffer;
107 int64_t* count_buffer;
108 ARROW_ASSIGN_OR_RAISE(std::tie(mode_buffer, count_buffer),
109 PrepareOutput<InType>(n, ctx, type, out));
110
111 for (int64_t i = n - 1; i >= 0; --i) {
112 std::tie(mode_buffer[i], count_buffer[i]) = min_heap.top();
113 min_heap.pop();
114 }
115
116 return Status::OK();
117}
118
119// count value occurrences for integers with narrow value range
120// O(1) space, O(n) time

Callers 2

OutputResultMethod · 0.85
~AwsInstanceMethod · 0.85

Calls 6

GetFunction · 0.50
genFunction · 0.50
ARROW_ASSIGN_OR_RAISEFunction · 0.50
OKFunction · 0.50
sizeMethod · 0.45
pushMethod · 0.45

Tested by

no test coverage detected