diff options
author | Tobias Koenig <tobias.koenig@kdab.com> | 2016-01-19 17:45:42 +0100 |
---|---|---|
committer | Tobias Koenig <tobias.koenig@kdab.com> | 2016-01-21 18:57:04 +0000 |
commit | 24d851dcd2a140bf346343c5eb64d944cd1c1a87 (patch) | |
tree | c298808e3d9b41fe36a88106bc957d5b6e1910aa /src/concurrent/qtconcurrentmedian.h | |
parent | c3850dd636ab24c251942fde63f22d8f5b3a639e (diff) |
Avoid heap allocations in Median class
Create a MedianDouble class and V2 version of BlockSizeManager, which
use a fixed size array of double (since we always use 7 elements
to calculate the median anyway).
Change-Id: Ife90b90336a9a8c037b90726dee4cd2a1b8b6cd9
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
Diffstat (limited to 'src/concurrent/qtconcurrentmedian.h')
-rw-r--r-- | src/concurrent/qtconcurrentmedian.h | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/src/concurrent/qtconcurrentmedian.h b/src/concurrent/qtconcurrentmedian.h index 2ae7954b7a..e35e2aec70 100644 --- a/src/concurrent/qtconcurrentmedian.h +++ b/src/concurrent/qtconcurrentmedian.h @@ -121,6 +121,72 @@ private: bool dirty; }; +// ### Qt6: Drop Median<double> in favor of this faster MedianDouble +class MedianDouble +{ +public: + enum { BufferSize = 7 }; + + MedianDouble() + : currentMedian(), currentIndex(0), valid(false), dirty(true) + { + } + + void reset() + { + std::fill_n(values, static_cast<int>(BufferSize), 0.0); + currentIndex = 0; + valid = false; + dirty = true; + } + + void addValue(double value) + { + ++currentIndex; + if (currentIndex == BufferSize) { + currentIndex = 0; + valid = true; + } + + // Only update the cached median value when we have to, that + // is when the new value is on then other side of the median + // compared to the current value at the index. + const double currentIndexValue = values[currentIndex]; + if ((currentIndexValue > currentMedian && currentMedian > value) + || (currentMedian > currentIndexValue && value > currentMedian)) { + dirty = true; + } + + values[currentIndex] = value; + } + + bool isMedianValid() const + { + return valid; + } + + double median() + { + if (dirty) { + dirty = false; + + double sorted[BufferSize]; + ::memcpy(&sorted, &values, sizeof(sorted)); + std::sort(sorted, sorted + static_cast<int>(BufferSize)); + currentMedian = sorted[BufferSize / 2]; + } + + return currentMedian; + } + +private: + double values[BufferSize]; + double currentMedian; + int currentIndex; + bool valid; + bool dirty; +}; + } // namespace QtConcurrent #endif //Q_QDOC |