Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
THnSparse.cxx
Go to the documentation of this file.
1// @(#)root/hist:$Id$
2// Author: Axel Naumann (2007-09-11)
3
4/*************************************************************************
5 * Copyright (C) 1995-2012, Rene Brun and Fons Rademakers. *
6 * All rights reserved. *
7 * *
8 * For the licensing terms see $ROOTSYS/LICENSE. *
9 * For the list of contributors see $ROOTSYS/README/CREDITS. *
10 *************************************************************************/
11
12#include "THnSparse.h"
13
14#include "TAxis.h"
15#include "TClass.h"
16#include "TDataMember.h"
17#include "TDataType.h"
18
19namespace {
20//______________________________________________________________________________
21//
22// THnSparseBinIter iterates over all filled bins of a THnSparse.
23//______________________________________________________________________________
24
25 class THnSparseBinIter: public ROOT::Internal::THnBaseBinIter {
26 public:
27 THnSparseBinIter(Bool_t respectAxisRange, const THnSparse* hist):
28 ROOT::Internal::THnBaseBinIter(respectAxisRange), fHist(hist),
29 fNbins(hist->GetNbins()), fIndex(-1) {
30 // Construct a THnSparseBinIter
31 fCoord = new Int_t[hist->GetNdimensions()];
32 fCoord[0] = -1;
33 }
34 ~THnSparseBinIter() override { delete [] fCoord; }
35
36 Int_t GetCoord(Int_t dim) const override;
37 Long64_t Next(Int_t* coord = nullptr) override;
38
39 private:
40 THnSparseBinIter(const THnSparseBinIter&) = delete; // intentionally unimplemented
41 THnSparseBinIter& operator=(const THnSparseBinIter&) = delete; // intentionally unimplemented
42
43 const THnSparse* fHist;
44 Int_t* fCoord; // coord buffer for fIndex; fCoord[0] == -1 if not yet calculated
45 Long64_t fNbins; // number of bins to iterate over
46 Long64_t fIndex; // current bin index
47 };
48}
49
50Int_t THnSparseBinIter::GetCoord(Int_t dim) const
51{
52 if (fCoord[0] == -1) {
53 fHist->GetBinContent(fIndex, fCoord);
54 }
55 return fCoord[dim];
56}
57
58Long64_t THnSparseBinIter::Next(Int_t* coord /*= 0*/)
59{
60 // Get next bin index (in range if RespectsAxisRange()).
61 // If coords != 0, set it to the index's axis coordinates
62 // (i.e. coord must point to an array of Int_t[fNdimension]
63 if (!fHist) return -1;
64
65 fCoord[0] = -1;
66 Int_t* useCoordBuf = fCoord;
67 if (coord) {
69 coord[0] = -1;
70 }
71
72 do {
73 ++fIndex;
74 if (fIndex >= fHist->GetNbins()) {
75 fHist = nullptr;
76 return -1;
77 }
78 if (RespectsAxisRange()) {
79 fHist->GetBinContent(fIndex, useCoordBuf);
80 }
81 } while (RespectsAxisRange()
82 && !fHist->IsInRange(useCoordBuf)
83 && (fHaveSkippedBin = kTRUE /* assignment! */));
84
85 if (coord && coord[0] == -1) {
86 if (fCoord[0] == -1) {
87 fHist->GetBinContent(fIndex, coord);
88 } else {
89 memcpy(coord, fCoord, fHist->GetNdimensions() * sizeof(Int_t));
90 }
91 }
92
93 return fIndex;
94}
95
96
97
98/** \class THnSparseCoordCompression
99THnSparseCoordCompression is a class used by THnSparse internally. It
100represents a compacted n-dimensional array of bin coordinates (indices).
101As the total number of bins in each dimension is known by THnSparse, bin
102indices can be compacted to only use the amount of bins needed by the total
103number of bins in each dimension. E.g. for a THnSparse with
104{15, 100, 2, 20, 10, 100} bins per dimension, a bin index will only occupy
10528 bits (4+7+1+5+4+7), i.e. less than a 32bit integer. The tricky part is
106the fast compression and decompression, the platform-independent storage
107(think of endianness: the bits of the number 0x123456 depend on the
108platform), and the hashing needed by THnSparseArrayChunk.
109*/
110
111
113public:
114 THnSparseCoordCompression(Int_t dim, const Int_t* nbins);
117
119
120 ULong64_t GetHashFromBuffer(const Char_t* buf) const;
121 Int_t GetBufferSize() const { return fCoordBufferSize; }
122 Int_t GetNdimensions() const { return fNdimensions; }
123 void SetCoordFromBuffer(const Char_t* buf_in, Int_t* coord_out) const;
124 ULong64_t SetBufferFromCoord(const Int_t* coord_in, Char_t* buf_out) const;
125
126protected:
128 // return the number of bits allocated by the number "n"
129 Int_t r = (n > 0);
130 while (n/=2) ++r;
131 return r;
132 }
133private:
134 Int_t fNdimensions; // number of dimensions
135 Int_t fCoordBufferSize; // size of coordbuf
136 Int_t *fBitOffsets; //[fNdimensions + 1] bit offset of each axis index
137};
138
139
140//______________________________________________________________________________
141//______________________________________________________________________________
142
143
144////////////////////////////////////////////////////////////////////////////////
145/// Initialize a THnSparseCoordCompression object with "dim" dimensions
146/// and "bins" holding the number of bins for each dimension; it
147/// stores the
148
150 fNdimensions(dim), fCoordBufferSize(0), fBitOffsets(nullptr)
151{
152 fBitOffsets = new Int_t[dim + 1];
153
154 int shift = 0;
155 for (Int_t i = 0; i < dim; ++i) {
156 fBitOffsets[i] = shift;
157 shift += GetNumBits(nbins[i] + 2);
158 }
159 fBitOffsets[dim] = shift;
160 fCoordBufferSize = (shift + 7) / 8;
161}
162
163
164////////////////////////////////////////////////////////////////////////////////
165/// Construct a THnSparseCoordCompression from another one
166
174
175
176////////////////////////////////////////////////////////////////////////////////
177/// Set this to other if different.
178
180{
181 if (&other == this) return *this;
182
183 fNdimensions = other.fNdimensions;
184 fCoordBufferSize = other.fCoordBufferSize;
185 delete [] fBitOffsets;
186 fBitOffsets = new Int_t[fNdimensions + 1];
187 memcpy(fBitOffsets, other.fBitOffsets, sizeof(Int_t) * fNdimensions);
188 return *this;
189}
190
191
192////////////////////////////////////////////////////////////////////////////////
193/// destruct a THnSparseCoordCompression
194
199
200
201////////////////////////////////////////////////////////////////////////////////
202/// Given the compressed coordinate buffer buf_in, calculate ("decompact")
203/// the bin coordinates and return them in coord_out.
204
206 Int_t* coord_out) const
207{
208 for (Int_t i = 0; i < fNdimensions; ++i) {
209 const Int_t offset = fBitOffsets[i] / 8;
210 Int_t shift = fBitOffsets[i] % 8;
211 Int_t nbits = fBitOffsets[i + 1] - fBitOffsets[i];
212 const UChar_t* pbuf = (const UChar_t*) buf_in + offset;
213 coord_out[i] = *pbuf >> shift;
214 Int_t subst = (Int_t) -1;
215 subst = subst << nbits;
216 nbits -= (8 - shift);
217 shift = 8 - shift;
218 for (Int_t n = 0; n * 8 < nbits; ++n) {
219 ++pbuf;
220 coord_out[i] += *pbuf << shift;
221 shift += 8;
222 }
223 coord_out[i] &= ~subst;
224 }
225}
226
227
228////////////////////////////////////////////////////////////////////////////////
229/// Given the cbin coordinates coord_in, calculate ("compact")
230/// the bin coordinates and return them in buf_in.
231/// Return the hash value.
232
234 Char_t* buf_out) const
235{
236 if (fCoordBufferSize <= 8) {
237 ULong64_t l64buf = 0;
238 for (Int_t i = 0; i < fNdimensions; ++i) {
239 l64buf += ((ULong64_t)((UInt_t)coord_in[i])) << fBitOffsets[i];
240 }
241 memcpy(buf_out, &l64buf, sizeof(Long64_t));
242 return l64buf;
243 }
244
245 // else: doesn't fit into a Long64_t:
247 for (Int_t i = 0; i < fNdimensions; ++i) {
248 const Int_t offset = fBitOffsets[i] / 8;
249 const Int_t shift = fBitOffsets[i] % 8;
250 ULong64_t val = coord_in[i];
251
253 *pbuf += 0xff & (val << shift);
254 val = val >> (8 - shift);
255 while (val) {
256 ++pbuf;
257 *pbuf += 0xff & val;
258 val = val >> 8;
259 }
260 }
261
263}
264
265/*
266////////////////////////////////////////////////////////////////////////////////
267/// Calculate hash from bin indexes.
268
269ULong64_t THnSparseCoordCompression::GetHashFromCoords(const Int_t* coord) const
270{
271 // Bins are addressed in two different modes, depending
272 // on whether the compact bin index fits into a Long64_t or not.
273 // If it does, we can use it as a "perfect hash" for the TExMap.
274 // If not we build a hash from the compact bin index, and use that
275 // as the TExMap's hash.
276
277 if (fCoordBufferSize <= 8) {
278 // fits into a Long64_t
279 ULong64_t hash1 = 0;
280 for (Int_t i = 0; i < fNdimensions; ++i) {
281 hash1 += coord[i] << fBitOffsets[i];
282 }
283 return hash1;
284 }
285
286 // else: doesn't fit into a Long64_t:
287 memset(coord, 0, fCoordBufferSize);
288 for (Int_t i = 0; i < fNdimensions; ++i) {
289 const Int_t offset = fBitOffsets[i] / 8;
290 const Int_t shift = fBitOffsets[i] % 8;
291 ULong64_t val = coord[i];
292
293 Char_t* pbuf = fCoordBuffer + offset;
294 *pbuf += 0xff & (val << shift);
295 val = val >> (8 - shift);
296 while (val) {
297 ++pbuf;
298 *pbuf += 0xff & val;
299 val = val >> 8;
300 }
301 }
302
303 ULong64_t hash = 5381;
304 Char_t* str = fCoordBuffer;
305 while (str - fCoordBuffer < fCoordBufferSize) {
306 hash *= 5;
307 hash += *(str++);
308 }
309 return hash;
310}
311*/
312
313
314////////////////////////////////////////////////////////////////////////////////
315/// Calculate hash from compact bin index.
316
318{
319 // Bins are addressed in two different modes, depending
320 // on whether the compact bin index fits into a Long64_t or not.
321 // If it does, we can use it as a "perfect hash" for the TExMap.
322 // If not we build a hash from the compact bin index, and use that
323 // as the TExMap's hash.
324
325 if (fCoordBufferSize <= 8) {
326 // fits into a Long64_t
327 ULong64_t hash1 = 0;
329 return hash1;
330 }
331
332 // else: doesn't fit into a Long64_t:
333 ULong64_t hash = 5381;
334 const Char_t* str = buf;
335 while (str - buf < fCoordBufferSize) {
336 hash *= 5;
337 hash += *(str++);
338 }
339 return hash;
340}
341
342
343
344
345/** \class THnSparseCompactBinCoord
346THnSparseCompactBinCoord is a class used by THnSparse internally. It
347maps between an n-dimensional array of bin coordinates (indices) and
348its compact version, the THnSparseCoordCompression.
349*/
350
352public:
353 THnSparseCompactBinCoord(Int_t dim, const Int_t* nbins);
356 const Char_t* GetBuffer() const { return fCoordBuffer; }
357 ULong64_t GetHash() const { return fHash; }
365 void SetBuffer(const Char_t* buf) {
368 }
369
370private:
371 // intentionally not implemented
373 // intentionally not implemented
375
376private:
377 ULong64_t fHash; // hash for current coordinates; 0 if not calculated
378 Char_t *fCoordBuffer; // compact buffer of coordinates
379 Int_t *fCurrentBin; // current coordinates
380};
381
382
383//______________________________________________________________________________
384//______________________________________________________________________________
385
386
387////////////////////////////////////////////////////////////////////////////////
388/// Initialize a THnSparseCompactBinCoord object with "dim" dimensions
389/// and "bins" holding the number of bins for each dimension.
390
392 THnSparseCoordCompression(dim, nbins),
393 fHash(0), fCoordBuffer(nullptr), fCurrentBin(nullptr)
394{
395 fCurrentBin = new Int_t[dim];
396 size_t bufAllocSize = GetBufferSize();
397 if (bufAllocSize < sizeof(Long64_t))
398 bufAllocSize = sizeof(Long64_t);
400}
401
402
403////////////////////////////////////////////////////////////////////////////////
404/// destruct a THnSparseCompactBinCoord
405
411
412/** \class THnSparseArrayChunk
413THnSparseArrayChunk is used internally by THnSparse.
414THnSparse stores its (dynamic size) array of bin coordinates and their
415contents (and possibly errors) in a TObjArray of THnSparseArrayChunk. Each
416of the chunks holds an array of THnSparseCompactBinCoord and the content
417(a TArray*), which is created outside (by the templated derived classes of
418THnSparse) and passed in at construction time.
419*/
420
421
422////////////////////////////////////////////////////////////////////////////////
423/// (Default) initialize a chunk. Takes ownership of cont (~THnSparseArrayChunk deletes it),
424/// and create an ArrayF for errors if "errors" is true.
425
427 fCoordinateAllocationSize(-1), fSingleCoordinateSize(coordsize), fCoordinatesSize(0),
428 fCoordinates(nullptr), fContent(cont),
429 fSumw2(nullptr)
430{
433 if (errors) Sumw2();
434}
435
436////////////////////////////////////////////////////////////////////////////////
437/// Destructor
438
440{
441 delete fContent;
442 delete [] fCoordinates;
443 delete fSumw2;
444}
445
446////////////////////////////////////////////////////////////////////////////////
447/// Create a new bin in this chunk
448
450{
451 // When streaming out only the filled chunk is saved.
452 // When reading back only the memory needed for that filled part gets
453 // allocated. We need to check whether the allowed chunk size is
454 // bigger than the allocated size. If fCoordinateAllocationSize is
455 // set to -1 this chunk has been allocated by the streamer and the
456 // buffer allocation size is defined by [fCoordinatesSize]. In that
457 // case we need to compare fCoordinatesSize to
458 // fSingleCoordinateSize * fContent->GetSize()
459 // to determine whether we need to expand the buffer.
460 if (fCoordinateAllocationSize == -1 && fContent) {
463 // need to re-allocate:
466 delete [] fCoordinates;
468 }
470 }
471
474}
475
476////////////////////////////////////////////////////////////////////////////////
477/// Turn on support of errors
478
480{
481 if (!fSumw2)
482 fSumw2 = new TArrayD(fContent->GetSize());
483 // fill the structure with the current content
484 for (Int_t bin=0; bin < fContent->GetSize(); bin++) {
485 fSumw2->fArray[bin] = fContent->GetAt(bin);
486 }
487
488}
489
490
491/** \class THnSparse
492 \ingroup Hist
493
494Efficient multidimensional histogram.
495
496Use a THnSparse instead of TH1 / TH2 / TH3 / array for histogramming when
497only a small fraction of bins is filled. A 10-dimensional histogram with 10
498bins per dimension has 10^10 bins; in a naive implementation this will not
499fit in memory. THnSparse only allocates memory for the bins that have
500non-zero bin content instead, drastically reducing both the memory usage
501and the access time.
502
503To construct a THnSparse object you must use one of its templated, derived
504classes:
505- THnSparseD (typedef for THnSparseT<ArrayD>): bin content held by a Double_t,
506- THnSparseF (typedef for THnSparseT<ArrayF>): bin content held by a Float_t,
507- THnSparseL (typedef for THnSparseT<ArrayL64>): bin content held by a Long64_t,
508- THnSparseI (typedef for THnSparseT<ArrayI>): bin content held by an Int_t,
509- THnSparseS (typedef for THnSparseT<ArrayS>): bin content held by a Short_t,
510- THnSparseC (typedef for THnSparseT<ArrayC>): bin content held by a Char_t,
511
512They take name and title, the number of dimensions, and for each dimension
513the number of bins, the minimal, and the maximal value on the dimension's
514axis. A TH2 h("h","h",10, 0., 10., 20, -5., 5.) would correspond to
515
516 Int_t bins[2] = {10, 20};
517 Double_t xmin[2] = {0., -5.};
518 Double_t xmax[2] = {10., 5.};
519 THnSparseD hs("hs", "hs", 2, bins, xmin, xmax);
520
521## Filling
522A THnSparse is filled just like a regular histogram, using
523THnSparse::Fill(x, weight), where x is a n-dimensional Double_t value.
524To take errors into account, Sumw2() must be called before filling the
525histogram.
526
527Bins are allocated as needed; the status of the allocation can be observed
528by GetSparseFractionBins(), GetSparseFractionMem().
529
530## Fast Bin Content Access
531When iterating over a THnSparse one should only look at filled bins to save
532processing time. The number of filled bins is returned by
533THnSparse::GetNbins(); the bin content for each (linear) bin number can
534be retrieved by THnSparse::GetBinContent(linidx, (Int_t*)coord).
535After the call, coord will contain the bin coordinate of each axis for the bin
536with linear index linidx. A possible call would be
537
538 std::cout << hs.GetBinContent(0, coord);
539 std::cout <<" is the content of bin [x = " << coord[0] "
540 << " | y = " << coord[1] << "]" << std::endl;
541
542## Efficiency
543TH1 and TH2 are generally faster than THnSparse for one and two dimensional
544distributions. THnSparse becomes competitive for a sparsely filled TH3
545with large numbers of bins per dimension. The tutorial sparsehist.C
546shows the turning point. On a AMD64 with 8GB memory, THnSparse "wins"
547starting with a TH3 with 30 bins per dimension. Using a THnSparse for a
548one-dimensional histogram is only reasonable if it has a huge number of bins.
549
550## Projections
551The dimensionality of a THnSparse can be reduced by projecting it to
5521, 2, 3, or n dimensions, which can be represented by a TH1, TH2, TH3, or
553a THnSparse. See the Projection() members. To only project parts of the
554histogram, call
555
556 THnSparse::GetAxis(12)->SetRange(from_bin, to_bin);
557
558## Internal Representation
559An entry for a filled bin consists of its n-dimensional coordinates and
560its bin content. The coordinates are compacted to use as few bits as
561possible; e.g. a histogram with 10 bins in x and 20 bins in y will only
562use 4 bits for the x representation and 5 bits for the y representation.
563This is handled by the internal class THnSparseCompactBinCoord.
564Bin data (content and coordinates) are allocated in chunks of size
565fChunkSize; this parameter can be set when constructing a THnSparse. Each
566chunk is represented by an object of class THnSparseArrayChunk.
567
568Translation from an n-dimensional bin coordinate to the linear index within
569the chunks is done by GetBin(). It creates a hash from the compacted bin
570coordinates (the hash of a bin coordinate is the compacted coordinate itself
571if it takes less than 8 bytes, the size of a Long64_t.
572This hash is used to lookup the linear index in the TExMap member fBins;
573the coordinates of the entry fBins points to is compared to the coordinates
574passed to GetBin(). If they do not match, these two coordinates have the same
575hash - which is extremely unlikely but (for the case where the compact bin
576coordinates are larger than 4 bytes) possible. In this case, fBinsContinued
577contains a chain of linear indexes with the same hash. Iterating through this
578chain and comparing each bin coordinates with the one passed to GetBin() will
579retrieve the matching bin.
580*/
581
582
583
584////////////////////////////////////////////////////////////////////////////////
585/// Construct an empty THnSparse.
586
588 fChunkSize(1024), fFilledBins(0), fCompactCoord(nullptr)
589{
591}
592
593////////////////////////////////////////////////////////////////////////////////
594/// Construct a THnSparse with "dim" dimensions,
595/// with chunksize as the size of the chunks.
596/// "nbins" holds the number of bins for each dimension;
597/// "xmin" and "xmax" the minimal and maximal value for each dimension.
598/// The arrays "xmin" and "xmax" can be NULL; in that case SetBinEdges()
599/// must be called for each dimension.
600
601THnSparse::THnSparse(const char* name, const char* title, Int_t dim,
602 const Int_t* nbins, const Double_t* xmin, const Double_t* xmax,
604 THnBase(name, title, dim, nbins, xmin, xmax),
605 fChunkSize(chunksize), fFilledBins(0), fCompactCoord(nullptr)
606{
607 fCompactCoord = new THnSparseCompactBinCoord(dim, nbins);
609}
610
611////////////////////////////////////////////////////////////////////////////////
612/// Construct a THnSparse with chunksize as the size of the chunks.
613/// "axes" is a vector of TAxis, its size sets the number of dimensions.
614/// This method is convenient for passing the Axes on the fly:
615/// auto h0= new THnSparseI{"h0", "", {{100, -50., 50.}, {50, -1000., 1000.}}};
616
617THnSparse::THnSparse(const char* name, const char* title,
618 const std::vector<TAxis>& axes,
620THnBase(name, title, axes),
621 fChunkSize(chunksize), fFilledBins(0), fCompactCoord(nullptr)
622{
623 const size_t dim=axes.size();
624 auto nbins=new Int_t[dim];
625 for (size_t i=0; i<dim; i++)
626 nbins[i]=axes.at(i).GetNbins();
627 fCompactCoord = new THnSparseCompactBinCoord(dim, nbins);
629 delete[] nbins;
630}
631
632////////////////////////////////////////////////////////////////////////////////
633/// Destruct a THnSparse
634
638
639////////////////////////////////////////////////////////////////////////////////
640/// Add "v" to the content of bin with index "bin"
641
643{
645 bin %= fChunkSize;
646 v += chunk->fContent->GetAt(bin);
647 return chunk->fContent->SetAt(v, bin);
648}
649
650////////////////////////////////////////////////////////////////////////////////
651/// Create a new chunk of bin content
652
661
662////////////////////////////////////////////////////////////////////////////////
663/// Initialize the storage of a histogram created via Init()
664
670
671////////////////////////////////////////////////////////////////////////////////
672///We have been streamed; set up fBins
673
675{
677 THnSparseArrayChunk* chunk = nullptr;
679 Long64_t idx = 0;
680 if (2 * GetNbins() > fBins.Capacity())
681 fBins.Expand(3 * GetNbins());
682 while ((chunk = (THnSparseArrayChunk*) iChunk())) {
683 const Int_t chunkSize = chunk->GetEntries();
684 Char_t* buf = chunk->fCoordinates;
685 const Int_t singleCoordSize = chunk->fSingleCoordinateSize;
686 const Char_t* endbuf = buf + singleCoordSize * chunkSize;
687 for (; buf < endbuf; buf += singleCoordSize, ++idx) {
688 Long64_t hash = compactCoord.GetHashFromBuffer(buf);
690 if (linidx) {
692 while (nextidx) {
693 // must be a collision, so go to fBinsContinued.
694 linidx = nextidx;
696 }
697 fBinsContinued.Add(linidx, idx + 1);
698 } else {
699 fBins.Add(hash, idx + 1);
700 }
701 }
702 }
703}
704
705////////////////////////////////////////////////////////////////////////////////
706/// Initialize storage for nbins
707
709 if (!fBins.GetSize() && fBinContent.GetSize()) {
710 FillExMap();
711 }
712 if (2 * nbins > fBins.Capacity()) {
713 fBins.Expand(3 * nbins);
714 }
715}
716
717////////////////////////////////////////////////////////////////////////////////
718/// Get the bin index for the n dimensional tuple x,
719/// allocate one if it doesn't exist yet and "allocate" is true.
720
722{
724 Int_t *coord = cc->GetCoord();
725 for (Int_t i = 0; i < fNdimensions; ++i)
726 coord[i] = GetAxis(i)->FindBin(x[i]);
727 cc->UpdateCoord();
728
730}
731
732
733////////////////////////////////////////////////////////////////////////////////
734/// Get the bin index for the n dimensional tuple addressed by "name",
735/// allocate one if it doesn't exist yet and "allocate" is true.
736
737Long64_t THnSparse::GetBin(const char* name[], Bool_t allocate /* = kTRUE */)
738{
740 Int_t *coord = cc->GetCoord();
741 for (Int_t i = 0; i < fNdimensions; ++i)
742 coord[i] = GetAxis(i)->FindBin(name[i]);
743 cc->UpdateCoord();
744
746}
747
748////////////////////////////////////////////////////////////////////////////////
749/// Get the bin index for the n dimensional coordinates coord,
750/// allocate one if it doesn't exist yet and "allocate" is true.
751
757
758////////////////////////////////////////////////////////////////////////////////
759/// Return the content of the filled bin number "idx".
760/// If coord is non-null, it will contain the bin's coordinates for each axis
761/// that correspond to the bin.
762
764{
765 if (idx >= 0) {
767 idx %= fChunkSize;
768 if (chunk && chunk->fContent->GetSize() > idx) {
769 if (coord) {
771 Int_t sizeCompact = cc->GetBufferSize();
772 cc->SetCoordFromBuffer(chunk->fCoordinates + idx * sizeCompact,
773 coord);
774
775 }
776 return chunk->fContent->GetAt(idx);
777 }
778 }
779 if (coord)
780 memset(coord, -1, sizeof(Int_t) * fNdimensions);
781 return 0.;
782}
783
784////////////////////////////////////////////////////////////////////////////////
785/// Get square of the error of bin addressed by linidx as
786/// \f$\sum weight^{2}\f$
787/// If errors are not enabled (via Sumw2() or CalculateErrors())
788/// return contents.
789
791 if (!GetCalculateErrors())
792 return GetBinContent(linidx);
793
794 if (linidx < 0) return 0.;
797 if (!chunk || chunk->fContent->GetSize() < linidx)
798 return 0.;
799
800 return chunk->fSumw2->GetAt(linidx);
801}
802
803
804////////////////////////////////////////////////////////////////////////////////
805/// Return the index for fCurrentBinIndex.
806/// If it doesn't exist then return -1, or allocate a new bin if allocate is set
807
809{
811 ULong64_t hash = cc->GetHash();
812 if (fBinContent.GetSize() && !fBins.GetSize())
813 FillExMap();
815 while (linidx) {
816 // fBins stores index + 1!
818 if (chunk->Matches((linidx - 1) % fChunkSize, cc->GetBuffer()))
819 return linidx - 1; // we store idx+1, 0 is "TExMap: not found"
820
822 if (!nextlinidx) break;
823
825 }
826 if (!allocate) return -1;
827
828 ++fFilledBins;
829
830 // allocate bin in chunk
832 Long64_t newidx = chunk ? ((Long64_t) chunk->GetEntries()) : -1;
833 if (!chunk || newidx == (Long64_t)fChunkSize) {
834 chunk = AddChunk();
835 newidx = 0;
836 }
837 chunk->AddBin(newidx, cc->GetBuffer());
838
839 // store translation between hash and bin
841 if (!linidx) {
842 // fBins didn't find it
843 if (2 * GetNbins() > fBins.Capacity())
844 fBins.Expand(3 * GetNbins());
845 fBins.Add(hash, newidx + 1);
846 } else {
847 // fBins contains one, but it's the wrong one;
848 // add entry to fBinsContinued.
850 }
851 return newidx;
852}
853
854////////////////////////////////////////////////////////////////////////////////
855/// Return THnSparseCompactBinCoord object.
856
858{
859 if (!fCompactCoord) {
860 Int_t *bins = new Int_t[fNdimensions];
861 for (Int_t d = 0; d < fNdimensions; ++d)
862 bins[d] = GetAxis(d)->GetNbins();
863 const_cast<THnSparse*>(this)->fCompactCoord
865 delete [] bins;
866 }
867 return fCompactCoord;
868}
869
870////////////////////////////////////////////////////////////////////////////////
871/// Return the amount of filled bins over all bins
872
874 Double_t nbinsTotal = 1.;
875 for (Int_t d = 0; d < fNdimensions; ++d)
876 nbinsTotal *= GetAxis(d)->GetNbins() + 2;
877 return fFilledBins / nbinsTotal;
878}
879
880////////////////////////////////////////////////////////////////////////////////
881/// Return the amount of used memory over memory that would be used by a
882/// non-sparse n-dimensional histogram. The value is approximate.
883
886 if (fFilledBins) {
888 TDataMember* dm = clArray ? clArray->GetDataMember("fArray") : nullptr;
889 arrayElementSize = dm ? dm->GetDataType()->Size() : 0;
890 }
891 if (!arrayElementSize) {
892 Warning("GetSparseFractionMem", "Cannot determine type of elements!");
893 return -1.;
894 }
895
897 if (fFilledBins && GetChunk(0)->fSumw2)
898 sizePerChunkElement += sizeof(Double_t); /* fSumw2 */
899
900 Double_t size = 0.;
902 size += + 3 * sizeof(Long64_t) * fBins.GetSize() /* TExMap */;
903
904 Double_t nbinsTotal = 1.;
905 for (Int_t d = 0; d < fNdimensions; ++d)
906 nbinsTotal *= GetAxis(d)->GetNbins() + 2;
907
909}
910
911////////////////////////////////////////////////////////////////////////////////
912/// Create an iterator over all filled bins of a THnSparse.
913/// Use THnIter instead.
914
916{
917 return new THnSparseBinIter(respectAxisRange, this);
918}
919
920////////////////////////////////////////////////////////////////////////////////
921/// Set content of bin with index "bin" to "v"
922
924{
926 chunk->fContent->SetAt(v, bin % fChunkSize);
927 ++fEntries;
928}
929
930////////////////////////////////////////////////////////////////////////////////
931/// Set error of bin with index "bin" to "e", enable errors if needed
932
934{
936 if (!chunk->fSumw2 ) {
937 // if fSumw2 is zero GetCalculateErrors should return false
938 if (GetCalculateErrors()) {
939 Error("SetBinError", "GetCalculateErrors() logic error!");
940 }
941 Sumw2(); // enable error calculation
942 }
943
944 chunk->fSumw2->SetAt(e2, bin % fChunkSize);
945}
946
947////////////////////////////////////////////////////////////////////////////////
948/// Add "e" to error of bin with index "bin", enable errors if needed
949
951{
953 if (!chunk->fSumw2 ) {
954 // if fSumw2 is zero GetCalculateErrors should return false
955 if (GetCalculateErrors()) {
956 Error("SetBinError", "GetCalculateErrors() logic error!");
957 }
958 Sumw2(); // enable error calculation
959 }
960
961 (*chunk->fSumw2)[bin % fChunkSize] += e2;
962}
963
964////////////////////////////////////////////////////////////////////////////////
965/// Enable calculation of errors
966
968{
969 if (GetCalculateErrors()) return;
970
971 fTsumw2 = 0.;
973 THnSparseArrayChunk* chunk = nullptr;
974 while ((chunk = (THnSparseArrayChunk*) iChunk()))
975 chunk->Sumw2();
976}
977
978////////////////////////////////////////////////////////////////////////////////
979/// Clear the histogram
980
982{
983 fFilledBins = 0;
984 fBins.Delete();
988}
989
#define d(i)
Definition RSha256.hxx:102
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
bool Bool_t
Boolean (0=false, 1=true) (bool)
Definition RtypesCore.h:77
int Int_t
Signed integer 4 bytes (int)
Definition RtypesCore.h:59
char Char_t
Character 1 byte (char)
Definition RtypesCore.h:51
double Double_t
Double 8 bytes.
Definition RtypesCore.h:73
long long Long64_t
Portable signed long integer 8 bytes.
Definition RtypesCore.h:83
unsigned long long ULong64_t
Portable unsigned long integer 8 bytes.
Definition RtypesCore.h:84
constexpr Bool_t kTRUE
Definition RtypesCore.h:107
const char Option_t
Option string (const char)
Definition RtypesCore.h:80
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
Option_t Option_t option
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t winding char text const char depth char const char Int_t count const char ColorStruct_t color const char Pixmap_t Pixmap_t PictureAttributes_t attr const char char ret_data h unsigned char height h offset
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t r
char name[80]
Definition TGX11.cxx:110
float xmin
float xmax
Binding & operator=(OUT(*fun)(void))
Iterator over THnBase bins (internal implementation).
Definition THnBase.h:327
Array of doubles (64 bits per element).
Definition TArrayD.h:27
Double_t * fArray
Definition TArrayD.h:30
Abstract array base class.
Definition TArray.h:31
virtual TClass * IsA() const
Definition TArray.h:58
virtual Double_t GetAt(Int_t i) const =0
Int_t GetSize() const
Definition TArray.h:47
virtual Int_t FindBin(Double_t x)
Find bin number corresponding to abscissa x.
Definition TAxis.cxx:292
Int_t GetNbins() const
Definition TAxis.h:127
TClass instances represent classes, structs and namespaces in the ROOT type system.
Definition TClass.h:84
virtual void SetOwner(Bool_t enable=kTRUE)
Set whether this collection is the owner (enable==true) of its content.
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
All ROOT classes may have RTTI (run time type identification) support added.
Definition TDataMember.h:31
TDataType * GetDataType() const
Definition TDataMember.h:76
Int_t Size() const
Get size of basic typedef'ed type.
void Expand(Int_t newsize)
Expand the TExMap.
Definition TExMap.cxx:278
Int_t GetSize() const
Definition TExMap.h:71
void Add(ULong64_t hash, Long64_t key, Long64_t value)
Add an (key,value) pair to the table. The key should be unique.
Definition TExMap.cxx:87
Long64_t GetValue(ULong64_t hash, Long64_t key)
Return the value belonging to specified key and hash value.
Definition TExMap.cxx:173
Int_t Capacity() const
Definition TExMap.h:69
void Delete(Option_t *opt="") override
Delete all entries stored in the TExMap.
Definition TExMap.cxx:163
Multidimensional histogram base.
Definition THnBase.h:45
Double_t fEntries
Number of entries, spread over chunks.
Definition THnBase.h:50
Int_t GetNdimensions() const
Definition THnBase.h:144
void ResetBase(Option_t *option="")
Clear the histogram.
Definition THnBase.cxx:1345
Bool_t GetCalculateErrors() const
Definition THnBase.h:145
Double_t fTsumw2
Total sum of weights squared; -1 if no errors are calculated.
Definition THnBase.h:52
TAxis * GetAxis(Int_t dim) const
Definition THnBase.h:134
Int_t fNdimensions
Number of dimensions.
Definition THnBase.h:47
THnSparseArrayChunk is used internally by THnSparse.
~THnSparseArrayChunk() override
Destructor.
TArrayD * fSumw2
Bin errors.
Int_t fCoordinatesSize
Size of the bin coordinate buffer.
Int_t fSingleCoordinateSize
Size of a single bin coordinate.
void Sumw2()
Turn on support of errors.
Char_t * fCoordinates
[fCoordinatesSize] compact bin coordinate buffer
TArray * fContent
Bin content.
void AddBin(Int_t idx, const Char_t *idxbuf)
Create a new bin in this chunk.
Int_t fCoordinateAllocationSize
! Size of the allocated coordinate buffer; -1 means none or fCoordinatesSize
THnSparseCompactBinCoord is a class used by THnSparse internally.
THnSparseCompactBinCoord(Int_t dim, const Int_t *nbins)
Initialize a THnSparseCompactBinCoord object with "dim" dimensions and "bins" holding the number of b...
ULong64_t GetHash() const
const Char_t * GetBuffer() const
~THnSparseCompactBinCoord()
destruct a THnSparseCompactBinCoord
THnSparseCompactBinCoord(const THnSparseCompactBinCoord &)=delete
void SetBuffer(const Char_t *buf)
void SetCoord(const Int_t *coord)
THnSparseCompactBinCoord & operator=(const THnSparseCompactBinCoord &)=delete
THnSparseCoordCompression is a class used by THnSparse internally.
Int_t GetNdimensions() const
Int_t GetNumBits(Int_t n) const
void SetCoordFromBuffer(const Char_t *buf_in, Int_t *coord_out) const
Given the compressed coordinate buffer buf_in, calculate ("decompact") the bin coordinates and return...
ULong64_t SetBufferFromCoord(const Int_t *coord_in, Char_t *buf_out) const
Given the cbin coordinates coord_in, calculate ("compact") the bin coordinates and return them in buf...
Int_t GetBufferSize() const
THnSparseCoordCompression & operator=(const THnSparseCoordCompression &other)
Set this to other if different.
ULong64_t GetHashFromBuffer(const Char_t *buf) const
Calculate hash from compact bin index.
THnSparseCoordCompression(Int_t dim, const Int_t *nbins)
Initialize a THnSparseCoordCompression object with "dim" dimensions and "bins" holding the number of ...
~THnSparseCoordCompression()
destruct a THnSparseCoordCompression
Efficient multidimensional histogram.
Definition THnSparse.h:37
Double_t GetSparseFractionBins() const
Return the amount of filled bins over all bins.
Double_t GetSparseFractionMem() const
Return the amount of used memory over memory that would be used by a non-sparse n-dimensional histogr...
void Reset(Option_t *option="") override
Clear the histogram.
void AddBinError2(Long64_t bin, Double_t e2) override
Add "e" to error of bin with index "bin", enable errors if needed.
void SetBinContent(const Int_t *idx, Double_t v)
Forwards to THnBase::SetBinContent().
Definition THnSparse.h:110
THnSparseArrayChunk * GetChunk(Int_t idx) const
Definition THnSparse.h:52
THnSparseCompactBinCoord * fCompactCoord
! Compact coordinate
Definition THnSparse.h:44
Int_t GetChunkSize() const
Definition THnSparse.h:93
Double_t GetBinContent(const Int_t *idx) const
Forwards to THnBase::GetBinContent() overload.
Definition THnSparse.h:126
Long64_t fFilledBins
Number of filled bins.
Definition THnSparse.h:40
Long64_t GetBin(const Int_t *idx) const override
Definition THnSparse.h:101
TObjArray fBinContent
Array of THnSparseArrayChunk.
Definition THnSparse.h:41
THnSparseCompactBinCoord * GetCompactCoord() const
Return THnSparseCompactBinCoord object.
void InitStorage(Int_t *nbins, Int_t chunkSize) override
Initialize the storage of a histogram created via Init()
Double_t GetBinError2(Long64_t linidx) const override
Get square of the error of bin addressed by linidx as If errors are not enabled (via Sumw2() or Calc...
THnSparse()
Construct an empty THnSparse.
THnSparseArrayChunk * AddChunk()
Create a new chunk of bin content.
virtual TArray * GenerateArray() const =0
void SetBinError2(Long64_t bin, Double_t e2) override
Set error of bin with index "bin" to "e", enable errors if needed.
void FillExMap()
We have been streamed; set up fBins.
~THnSparse() override
Destruct a THnSparse.
TExMap fBins
! Filled bins
Definition THnSparse.h:42
TExMap fBinsContinued
! Filled bins for non-unique hashes, containing pairs of (bin index 0, bin index 1)
Definition THnSparse.h:43
void AddBinContent(const Int_t *idx, Double_t v=1.)
Forwards to THnBase::AddBinContent().
Definition THnSparse.h:118
void Reserve(Long64_t nbins) override
Initialize storage for nbins.
Int_t fChunkSize
Number of entries for each chunk.
Definition THnSparse.h:39
void Sumw2() override
Enable calculation of errors.
Long64_t GetNbins() const override
Definition THnSparse.h:98
ROOT::Internal::THnBaseBinIter * CreateIter(Bool_t respectAxisRange) const override
Create an iterator over all filled bins of a THnSparse.
Long64_t GetBinIndexForCurrentBin(Bool_t allocate)
Return the index for fCurrentBinIndex.
Int_t GetEntriesFast() const
Definition TObjArray.h:58
TObject * Last() const override
Return the object in the last filled slot. Returns 0 if no entries.
Int_t GetEntries() const override
Return the number of objects in array (i.e.
void Delete(Option_t *option="") override
Remove all objects from the array AND delete all heap based objects.
void AddLast(TObject *obj) override
Add object in the next empty slot in the array.
virtual void Clear(Option_t *="")
Definition TObject.h:125
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition TObject.cxx:1057
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition TObject.cxx:1071
Double_t x[n]
Definition legend1.C:17
const Int_t n
Definition legend1.C:16