OmniSciDB  ca0c39ec8f
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
quantile::detail::TDigest< RealType, IndexType > Class Template Reference

#include <quantile.h>

+ Collaboration diagram for quantile::detail::TDigest< RealType, IndexType >:

Public Types

using Memory = CentroidsMemory< RealType, IndexType >
 

Public Member Functions

 TDigest ()=default
 
DEVICE TDigest (Memory &mem)
 
DEVICE TDigest (RealType q, SimpleAllocator *simple_allocator, IndexType buf_allocate, IndexType centroids_allocate)
 
DEVICE Centroids< RealType,
IndexType > & 
centroids ()
 
DEVICE void add (RealType value)
 
DEVICE void allocate ()
 
DEVICE void mergeBuffer ()
 
DEVICE void mergeBufferFinal ()
 
DEVICE void mergeSorted (RealType *sums, IndexType *counts, IndexType size)
 
DEVICE void mergeTDigest (TDigest &t_digest)
 
DEVICE VectorView< IndexType
const > 
partialSumOfCounts (IndexType *const buf) const
 
DEVICE RealType quantile (VectorView< IndexType const > const partial_sum, RealType const q) const
 
DEVICE RealType quantile (RealType const q) const
 
DEVICE RealType quantile ()
 
DEVICE void setBuffer (Memory &mem)
 
DEVICE void setCentroids (Memory &mem)
 
DEVICE void setCentroids (VectorView< RealType > const sums, VectorView< IndexType > const counts)
 
DEVICE IndexType totalWeight () const
 

Private Member Functions

DEVICE RealType max () const
 
DEVICE RealType min () const
 
DEVICE IndexType maxCardinality (IndexType const sum, IndexType const total_weight, RealType const c)
 
DEVICE void mergeCentroids (Centroids< RealType, IndexType > &)
 
DEVICE RealType firstCentroid (RealType const x) const
 
DEVICE RealType interiorCentroid (RealType const x, IndexType const idx1, IndexType const prefix_sum) const
 
DEVICE RealType lastCentroid (RealType const x, IndexType const N) const
 
DEVICE RealType oneCentroid (RealType const x) const
 
DEVICE RealType slope (IndexType const idx1, IndexType const idx2) const
 

Private Attributes

Centroids< RealType, IndexType > buf_
 
Centroids< RealType, IndexType > centroids_
 
bool forward_ {true}
 
std::once_flag merge_buffer_final_once_
 
std::optional< RealType > const q_ {std::nullopt}
 
bool const use_linear_scaling_function_ {false}
 
SimpleAllocator *const simple_allocator_ {nullptr}
 
IndexType const buf_allocate_ {0}
 
IndexType const centroids_allocate_ {0}
 

Detailed Description

template<typename RealType, typename IndexType = size_t>
class quantile::detail::TDigest< RealType, IndexType >

Definition at line 184 of file quantile.h.

Member Typedef Documentation

template<typename RealType , typename IndexType = size_t>
using quantile::detail::TDigest< RealType, IndexType >::Memory = CentroidsMemory<RealType, IndexType>

Definition at line 222 of file quantile.h.

Constructor & Destructor Documentation

template<typename RealType , typename IndexType = size_t>
quantile::detail::TDigest< RealType, IndexType >::TDigest ( )
default
template<typename RealType , typename IndexType = size_t>
DEVICE quantile::detail::TDigest< RealType, IndexType >::TDigest ( Memory mem)
inline

Definition at line 226 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

227  : centroids_(mem.sums().data(), mem.counts().data(), mem.size()) {
228  centroids_.clear();
229  }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType = size_t>
DEVICE quantile::detail::TDigest< RealType, IndexType >::TDigest ( RealType  q,
SimpleAllocator simple_allocator,
IndexType  buf_allocate,
IndexType  centroids_allocate 
)
inline

Definition at line 231 of file quantile.h.

235  : q_(q)
236  , use_linear_scaling_function_(q_ && 0.1 <= *q_ && *q_ <= 0.9)
237  , simple_allocator_(simple_allocator)
238  , buf_allocate_(buf_allocate)
239  , centroids_allocate_(centroids_allocate) {}
bool const use_linear_scaling_function_
Definition: quantile.h:197
IndexType const buf_allocate_
Definition: quantile.h:199
std::optional< RealType > const q_
Definition: quantile.h:196
SimpleAllocator *const simple_allocator_
Definition: quantile.h:198
IndexType const centroids_allocate_
Definition: quantile.h:200

Member Function Documentation

template<typename RealType , typename IndexType >
DEVICE void quantile::detail::TDigest< RealType, IndexType >::add ( RealType  value)

Definition at line 591 of file quantile.h.

591  {
592  if (buf_.sums_.full()) {
593  mergeBuffer();
594  }
595  buf_.sums_.push_back(value);
596  buf_.counts_.push_back(1);
597 }
DEVICE void mergeBuffer()
Definition: quantile.h:640
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188
template<typename RealType , typename IndexType >
DEVICE void quantile::detail::TDigest< RealType, IndexType >::allocate ( )

Definition at line 601 of file quantile.h.

Referenced by agg_approx_quantile(), and approx_quantile_jit_rt().

601  {
602  if (buf_.capacity() == 0) {
603  auto* p0 = simple_allocator_->allocate(buf_allocate_ * sizeof(RealType));
604  auto* p1 = simple_allocator_->allocate(buf_allocate_ * sizeof(IndexType));
605  buf_ = Centroids<RealType, IndexType>(
606  VectorView<RealType>(reinterpret_cast<RealType*>(p0), 0, buf_allocate_),
607  VectorView<IndexType>(reinterpret_cast<IndexType*>(p1), 0, buf_allocate_));
608  p0 = simple_allocator_->allocate(centroids_allocate_ * sizeof(RealType));
609  p1 = simple_allocator_->allocate(centroids_allocate_ * sizeof(IndexType));
610  centroids_ = Centroids<RealType, IndexType>(
611  VectorView<RealType>(reinterpret_cast<RealType*>(p0), 0, centroids_allocate_),
612  VectorView<IndexType>(reinterpret_cast<IndexType*>(p1), 0, centroids_allocate_));
613  }
614 }
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188
IndexType const buf_allocate_
Definition: quantile.h:199
virtual int8_t * allocate(const size_t num_bytes, const size_t thread_idx=0)=0
SimpleAllocator *const simple_allocator_
Definition: quantile.h:198
IndexType const centroids_allocate_
Definition: quantile.h:200
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the caller graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE Centroids<RealType, IndexType>& quantile::detail::TDigest< RealType, IndexType >::centroids ( )
inline

Definition at line 241 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

241 { return centroids_; }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::firstCentroid ( RealType const  x) const
private

Definition at line 718 of file quantile.h.

718  {
719  if (x < 1) {
720  return min();
721  } else if (centroids_.size() == 1) {
722  return oneCentroid(x);
723  } else if (centroids_.counts_.front() == 2) {
724  RealType const sum = centroids_.sums_.front();
725  return x == 1 ? 0.5 * sum : sum - min();
726  } else {
727  RealType const count = centroids_.counts_.front();
728  RealType const dx = x - RealType(0.5) * (1 + count);
729  RealType const mean = (centroids_.sums_.front() - min()) / (count - 1);
730  return mean + slope(0, 0 < dx) * dx;
731  }
732 }
DEVICE RealType slope(IndexType const idx1, IndexType const idx2) const
Definition: quantile.h:852
DEVICE RealType oneCentroid(RealType const x) const
Definition: quantile.h:796
DEVICE RealType min() const
Definition: quantile.h:203
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::interiorCentroid ( RealType const  x,
IndexType const  idx1,
IndexType const  prefix_sum 
) const
private

Definition at line 737 of file quantile.h.

References quantile::detail::anonymous_namespace{quantile.h}::isSingleton().

739  {
740  if (isSingleton(centroids_.counts_.begin() + idx1)) {
741  RealType const sum1 = centroids_.sums_[idx1];
742  if (x == prefix_sum - centroids_.counts_[idx1]) {
743  if (isSingleton(centroids_.counts_.begin() + idx1 - 1)) {
744  return 0.5 * (centroids_.sums_[idx1 - 1] + sum1);
745  } else if (idx1 == 1 && centroids_.counts_[0] == 2) {
746  return 0.5 * (centroids_.sums_[idx1 - 1] - min() + sum1);
747  }
748  }
749  return sum1;
750  } else {
751  RealType const dx = x + RealType(0.5) * centroids_.counts_[idx1] - prefix_sum;
752  IndexType const idx2 = idx1 + 2 * (0 < dx) - 1;
753  return centroids_.mean(idx1) + slope(idx1, idx2) * dx;
754  }
755 }
DEVICE RealType slope(IndexType const idx1, IndexType const idx2) const
Definition: quantile.h:852
DEVICE RealType min() const
Definition: quantile.h:203
DEVICE bool isSingleton(CountsIterator itr)
Definition: quantile.h:711
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

template<typename RealType , typename IndexType >
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::lastCentroid ( RealType const  x,
IndexType const  N 
) const
private

Definition at line 759 of file quantile.h.

References quantile::detail::anonymous_namespace{quantile.h}::isSingleton().

760  {
761  if (N - 1 < x) {
762  return max();
763  }
764  IndexType const idx1 = centroids_.size() - 1;
765  RealType const sum1 = centroids_.sums_[idx1];
766  IndexType const count1 = centroids_.counts_[idx1];
767  if (count1 == 1) { // => x == N - 1
768  if (isSingleton(centroids_.counts_.begin() + (idx1 - 1))) {
769  return 0.5 * (centroids_.sums_[idx1 - 1] + sum1);
770  } else if (idx1 == 1 && centroids_.counts_[0] == 2) {
771  return 0.5 * (centroids_.sums_[idx1 - 1] - min() + sum1);
772  } else {
773  return sum1;
774  }
775  } else if (count1 == 2) { // => 3 <= N
776  if (x == N - 1) {
777  return 0.5 * sum1;
778  } else if (x == N - 2) {
779  RealType const sum2 = centroids_.sums_[idx1 - 1];
780  if (isSingleton(centroids_.counts_.begin() + (idx1 - 1))) {
781  return 0.5 * (sum2 + sum1 - max());
782  } else if (idx1 == 1 && centroids_.counts_[0] == 2) {
783  return 0.5 * (sum2 - min() + sum1 - max());
784  }
785  }
786  return sum1 - max();
787  } else { // => 3 <= count1
788  RealType const dx = x + RealType(0.5) * (count1 + 1) - N;
789  RealType const mean = (sum1 - max()) / (count1 - 1);
790  return mean + slope(idx1, idx1 - (dx < 0)) * dx;
791  }
792 }
DEVICE RealType max() const
Definition: quantile.h:202
DEVICE RealType slope(IndexType const idx1, IndexType const idx2) const
Definition: quantile.h:852
constexpr unsigned N
Definition: Utm.h:110
DEVICE RealType min() const
Definition: quantile.h:203
DEVICE bool isSingleton(CountsIterator itr)
Definition: quantile.h:711
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::max ( ) const
inlineprivate

Definition at line 202 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

202 { return centroids_.max_; }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE IndexType quantile::detail::TDigest< RealType, IndexType >::maxCardinality ( IndexType const  sum,
IndexType const  total_weight,
RealType const  c 
)
private

Definition at line 619 of file quantile.h.

621  {
622  IndexType const max_bins = centroids_.capacity(); // "compression parameter" delta
623  if (total_weight <= max_bins) {
624  return 0;
625  } else if (use_linear_scaling_function_) {
626  // Whitepaper scaling function k=0.
627  return 2 * total_weight / max_bins;
628  } else {
629  // Whitepaper scaling function k=1.
630  RealType const x = 2.0 * sum / total_weight - 1; // = 2 q_{i-1} - 1
631  RealType const f_inv = 0.5 + 0.5 * std::sin(c + std::asin(x));
632  constexpr RealType eps = 1e-5; // round-off epsilon for floor().
633  IndexType const dsum = static_cast<IndexType>(total_weight * f_inv + eps);
634  return dsum < sum ? 0 : dsum - sum;
635  }
636 }
bool const use_linear_scaling_function_
Definition: quantile.h:197
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeBuffer ( )

Definition at line 640 of file quantile.h.

References gpu_enabled::sort().

Referenced by quantile::detail::TDigest< RealType, IndexType >::mergeTDigest().

640  {
641  if (buf_.size()) {
642  gpu_enabled::sort(buf_.sums_.begin(), buf_.sums_.end());
643  buf_.min_ = buf_.sums_.front();
644  buf_.max_ = buf_.sums_.back();
646  }
647 }
DEVICE void sort(ARGS &&...args)
Definition: gpu_enabled.h:105
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188
DEVICE void mergeCentroids(Centroids< RealType, IndexType > &)
Definition: quantile.h:688

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename RealType , typename IndexType >
DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeBufferFinal ( )

Definition at line 651 of file quantile.h.

Referenced by ResultSet::calculateQuantile().

651  {
652  auto const call_once = [this] {
653  mergeBuffer();
654  assert(centroids_.size() <= buf_.capacity());
655  partialSumOfCounts(buf_.counts_.data());
656  };
657 #ifdef __CUDACC__
658  call_once();
659 #else
660  std::call_once(merge_buffer_final_once_, call_once);
661 #endif
662 }
DEVICE VectorView< IndexType const > partialSumOfCounts(IndexType *const buf) const
Definition: quantile.h:819
std::once_flag merge_buffer_final_once_
Definition: quantile.h:192
DEVICE void mergeBuffer()
Definition: quantile.h:640
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the caller graph for this function:

template<typename RealType , typename IndexType >
DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeCentroids ( Centroids< RealType, IndexType > &  buf)
private

Definition at line 688 of file quantile.h.

References quantile::detail::Centroids< RealType, IndexType >::clear(), and quantile::detail::CentroidsMerger< RealType, IndexType >::merge().

Referenced by quantile::detail::TDigest< RealType, IndexType >::mergeTDigest().

689  {
690  constexpr RealType two_pi = 6.283185307179586476925286766559005768e+00;
691  // Hoisted constant used in maxCardinality().
692  RealType const c = two_pi / centroids_.capacity();
693  // Loop over sorted sequence of buf and centroids_.
694  // Some latter centroids may be merged into the current centroid, so the number
695  // of iterations is only at most equal to the number of initial centroids.
696  using CM = CentroidsMerger<RealType, IndexType>;
697  for (CM cm(&buf, &centroids_, forward_); cm.hasNext(); cm.next()) {
698  // cm.prefixSum() == 0 on first iteration.
699  // Max cardinality for current centroid to be fully merged based on scaling function.
700  IndexType const max_cardinality = maxCardinality(cm.prefixSum(), cm.totalWeight(), c);
701  cm.merge(max_cardinality);
702  }
703  // Combine sorted centroids buf[0..curr_idx_] + centroids_[0..curr_idx_] if forward
704  centroids_.appendAndSortCurrent(buf);
705  buf.clear();
706  forward_ ^= true; // alternate merge direction on each call
707 }
DEVICE IndexType maxCardinality(IndexType const sum, IndexType const total_weight, RealType const c)
Definition: quantile.h:619
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename RealType , typename IndexType >
DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeSorted ( RealType *  sums,
IndexType *  counts,
IndexType  size 
)

Definition at line 665 of file quantile.h.

References gpu_enabled::fill(), VectorView< T >::set(), and quantile::detail::Centroids< RealType, IndexType >::sums_.

667  {
668  if (size) {
669  if (buf_.capacity() == 0) {
670  buf_ = Centroids<RealType, IndexType>(sums, counts, size); // Set capacity and size
671  } else {
672  buf_.sums_.set(sums, size); // Does not change capacity
673  buf_.counts_.set(counts, size);
674  }
675  gpu_enabled::fill(buf_.counts_.begin(), buf_.counts_.end(), IndexType(1));
676  buf_.min_ = buf_.sums_.front();
677  buf_.max_ = buf_.sums_.back();
679  }
680 }
DEVICE void fill(ARGS &&...args)
Definition: gpu_enabled.h:60
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188
DEVICE void mergeCentroids(Centroids< RealType, IndexType > &)
Definition: quantile.h:688

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeTDigest ( TDigest< RealType, IndexType > &  t_digest)
inline

Definition at line 257 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_, quantile::detail::TDigest< RealType, IndexType >::mergeBuffer(), and quantile::detail::TDigest< RealType, IndexType >::mergeCentroids().

257  {
258  mergeBuffer();
259  t_digest.mergeBuffer();
260  mergeCentroids(t_digest.centroids_);
261  }
DEVICE void mergeBuffer()
Definition: quantile.h:640
DEVICE void mergeCentroids(Centroids< RealType, IndexType > &)
Definition: quantile.h:688

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::min ( ) const
inlineprivate

Definition at line 203 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

203 { return centroids_.min_; }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::oneCentroid ( RealType const  x) const
private

Definition at line 796 of file quantile.h.

References anonymous_namespace{Utm.h}::N.

796  {
797  IndexType const N = centroids_.counts_.front();
798  if (N - 1 < x) { // includes case N == 1
799  return max();
800  } else if (N == 2) { // x == 1
801  return 0.5 * centroids_.sums_.front();
802  } else if (N == 3) { // 1 <= x <= 2
803  if (x == 2) {
804  return 0.5 * (centroids_.sums_.front() - min());
805  } else {
806  RealType const s = centroids_.sums_.front() - max();
807  return x == 1 ? 0.5 * s : s - min();
808  }
809  } else { // 3 < N
810  RealType const dx = x - RealType(0.5) * N;
811  RealType const mean = (centroids_.sums_.front() - (min() + max())) / (N - 2);
812  RealType const slope = 2 * (0 < dx ? max() - mean : mean - min()) / (N - 2);
813  return mean + slope * dx;
814  }
815 }
DEVICE RealType max() const
Definition: quantile.h:202
DEVICE RealType slope(IndexType const idx1, IndexType const idx2) const
Definition: quantile.h:852
constexpr unsigned N
Definition: Utm.h:110
DEVICE RealType min() const
Definition: quantile.h:203
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE VectorView< IndexType const > quantile::detail::TDigest< RealType, IndexType >::partialSumOfCounts ( IndexType *const  buf) const

Definition at line 819 of file quantile.h.

References gpu_enabled::partial_sum().

820  {
821  gpu_enabled::partial_sum(centroids_.counts_.begin(), centroids_.counts_.end(), buf);
822  return {buf, centroids_.size()};
823 }
DEVICE void partial_sum(ARGS &&...args)
Definition: gpu_enabled.h:87
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

template<typename RealType , typename IndexType >
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::quantile ( VectorView< IndexType const > const  partial_sum,
RealType const  q 
) const

Definition at line 827 of file quantile.h.

References VectorView< T >::back(), VectorView< T >::begin(), VectorView< T >::end(), anonymous_namespace{Utm.h}::N, and gpu_enabled::upper_bound().

Referenced by ResultSet::calculateQuantile().

828  {
829  if (centroids_.size()) {
830  IndexType const N = partial_sum.back();
831  RealType const x = q * N;
832  auto const it1 = gpu_enabled::upper_bound(partial_sum.begin(), partial_sum.end(), x);
833  if (it1 == partial_sum.begin()) {
834  return firstCentroid(x);
835  } else if (it1 == partial_sum.end()) { // <==> 1 <= q
836  return max();
837  } else if (it1 + 1 == partial_sum.end()) {
838  return lastCentroid(x, N);
839  } else {
840  return interiorCentroid(x, it1 - partial_sum.begin(), *it1);
841  }
842  } else {
843  return centroids_.nan;
844  }
845 }
DEVICE auto upper_bound(ARGS &&...args)
Definition: gpu_enabled.h:123
DEVICE RealType max() const
Definition: quantile.h:202
DEVICE T * begin() const
Definition: VectorView.h:59
DEVICE RealType lastCentroid(RealType const x, IndexType const N) const
Definition: quantile.h:759
constexpr unsigned N
Definition: Utm.h:110
DEVICE RealType interiorCentroid(RealType const x, IndexType const idx1, IndexType const prefix_sum) const
Definition: quantile.h:737
DEVICE T & back()
Definition: VectorView.h:57
DEVICE RealType firstCentroid(RealType const x) const
Definition: quantile.h:718
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
DEVICE T * end() const
Definition: VectorView.h:67

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::quantile ( RealType const  q) const
inline

Definition at line 270 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::buf_, quantile::detail::TDigest< RealType, IndexType >::centroids_, and quantile::detail::TDigest< RealType, IndexType >::quantile().

270  {
271  return quantile({buf_.counts_.data(), centroids_.size()}, q);
272  }
DEVICE RealType quantile()
Definition: quantile.h:274
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::quantile ( )
inline

Definition at line 274 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_, quantile::detail::TDigest< RealType, IndexType >::q_, and quantile::detail::TDigest< RealType, IndexType >::quantile().

Referenced by quantile::detail::TDigest< RealType, IndexType >::quantile().

274 { return q_ ? quantile(*q_) : centroids_.nan; }
DEVICE RealType quantile()
Definition: quantile.h:274
std::optional< RealType > const q_
Definition: quantile.h:196
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE void quantile::detail::TDigest< RealType, IndexType >::setBuffer ( Memory mem)
inline

Definition at line 277 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::buf_, quantile::detail::CentroidsMemory< RealType, IndexType >::counts(), VectorView< T >::data(), quantile::detail::CentroidsMemory< RealType, IndexType >::size(), and quantile::detail::CentroidsMemory< RealType, IndexType >::sums().

277  {
278  buf_ = Centroids<RealType, IndexType>(
279  mem.sums().data(), mem.counts().data(), mem.size());
280  buf_.clear();
281  }
Centroids< RealType, IndexType > buf_
Definition: quantile.h:188

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE void quantile::detail::TDigest< RealType, IndexType >::setCentroids ( Memory mem)
inline

Definition at line 284 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_, quantile::detail::CentroidsMemory< RealType, IndexType >::counts(), VectorView< T >::data(), quantile::detail::CentroidsMemory< RealType, IndexType >::size(), and quantile::detail::CentroidsMemory< RealType, IndexType >::sums().

284  {
285  centroids_ = Centroids<RealType, IndexType>(
286  mem.sums().data(), mem.counts().data(), mem.size());
287  centroids_.clear();
288  }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE void quantile::detail::TDigest< RealType, IndexType >::setCentroids ( VectorView< RealType > const  sums,
VectorView< IndexType > const  counts 
)
inline

Definition at line 290 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

291  {
292  centroids_ = Centroids<RealType, IndexType>(sums, counts);
293  centroids_.clear();
294  }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189
template<typename RealType , typename IndexType >
DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::slope ( IndexType const  idx1,
IndexType const  idx2 
) const
private

Definition at line 852 of file quantile.h.

References quantile::detail::anonymous_namespace{quantile.h}::isSingleton(), and anonymous_namespace{Utm.h}::n.

853  {
854  IndexType const M = centroids_.size();
855  if (idx1 == idx2) { // Line segment is contained in either the first or last centroid.
856  RealType const n = static_cast<RealType>(centroids_.counts_[idx1]);
857  RealType const s = centroids_.sums_[idx1];
858  return idx1 == 0 ? 2 * (s - n * min()) / ((n - 1) * (n - 1))
859  : 2 * (n * max() - s) / ((n - 1) * (n - 1));
860  } else {
861  bool const min1 = idx1 == 0; // idx1 is the min centroid
862  bool const max1 = idx1 == M - 1; // idx1 is the max centroid
863  bool const min2 = idx2 == 0; // idx2 is the min centroid
864  bool const max2 = idx2 == M - 1; // idx2 is the max centroid
865  RealType const n1 = static_cast<RealType>(centroids_.counts_[idx1] - min1 - max1);
866  RealType const s1 = centroids_.sums_[idx1] - (min1 ? min() : max1 ? max() : 0);
867  RealType const s2 = centroids_.sums_[idx2] - (min2 ? min() : max2 ? max() : 0);
868  if (isSingleton(centroids_.counts_.begin() + idx2)) {
869  return (idx1 < idx2 ? 2 : -2) * (n1 * s2 - s1) / (n1 * n1);
870  } else {
871  RealType const n2 = static_cast<RealType>(centroids_.counts_[idx2] - min2 - max2);
872  return (idx1 < idx2 ? 2 : -2) * (n1 * s2 - n2 * s1) / (n1 * n2 * (n1 + n2));
873  }
874  }
875 }
DEVICE RealType max() const
Definition: quantile.h:202
constexpr double n
Definition: Utm.h:38
DEVICE RealType min() const
Definition: quantile.h:203
DEVICE bool isSingleton(CountsIterator itr)
Definition: quantile.h:711
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

+ Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>
DEVICE IndexType quantile::detail::TDigest< RealType, IndexType >::totalWeight ( ) const
inline

Definition at line 297 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

297 { return centroids_.totalWeight(); }
Centroids< RealType, IndexType > centroids_
Definition: quantile.h:189

Member Data Documentation

template<typename RealType , typename IndexType = size_t>
Centroids<RealType, IndexType> quantile::detail::TDigest< RealType, IndexType >::buf_
private
template<typename RealType , typename IndexType = size_t>
IndexType const quantile::detail::TDigest< RealType, IndexType >::buf_allocate_ {0}
private

Definition at line 199 of file quantile.h.

template<typename RealType , typename IndexType = size_t>
IndexType const quantile::detail::TDigest< RealType, IndexType >::centroids_allocate_ {0}
private

Definition at line 200 of file quantile.h.

template<typename RealType , typename IndexType = size_t>
bool quantile::detail::TDigest< RealType, IndexType >::forward_ {true}
private

Definition at line 190 of file quantile.h.

template<typename RealType , typename IndexType = size_t>
std::once_flag quantile::detail::TDigest< RealType, IndexType >::merge_buffer_final_once_
private

Definition at line 192 of file quantile.h.

template<typename RealType , typename IndexType = size_t>
std::optional<RealType> const quantile::detail::TDigest< RealType, IndexType >::q_ {std::nullopt}
private
template<typename RealType , typename IndexType = size_t>
SimpleAllocator* const quantile::detail::TDigest< RealType, IndexType >::simple_allocator_ {nullptr}
private

Definition at line 198 of file quantile.h.

template<typename RealType , typename IndexType = size_t>
bool const quantile::detail::TDigest< RealType, IndexType >::use_linear_scaling_function_ {false}
private

Definition at line 197 of file quantile.h.


The documentation for this class was generated from the following file: