[Libreoffice-commits] .: Branch 'feature/calc-matrix-rework' - sc/inc sc/source
Kohei Yoshida
kohei at kemper.freedesktop.org
Mon Dec 20 12:17:46 PST 2010
sc/inc/scmatrix.hxx | 32 ++++-
sc/source/core/tool/interpr1.cxx | 77 ++++++-------
sc/source/core/tool/scmatrix.cxx | 215 ++++++++++++++++++++++++++++++---------
3 files changed, 229 insertions(+), 95 deletions(-)
New commits:
commit 16fdac1d2ba6defdb3ee8d67033a7ae205e113d0
Author: Kohei Yoshida <kyoshida at novell.com>
Date: Mon Dec 20 15:16:12 2010 -0500
Use mixed_type_matrix::const_iterator for faster element iteration.
This should speed up calculation of SUM, AVERAGE etc. on external
ranges.
diff --git a/sc/inc/scmatrix.hxx b/sc/inc/scmatrix.hxx
index 1d381b9..df744df 100644
--- a/sc/inc/scmatrix.hxx
+++ b/sc/inc/scmatrix.hxx
@@ -153,6 +153,28 @@ public:
SPARSE_EMPTY
};
+ /**
+ * When adding all numerical matrix elements for a scalar result such as
+ * summation, the interpreter wants to separate the first non-zero value
+ * with the rest of the summed values.
+ *
+ * TODO: Find out if we still need to do this. If not, we can re-write
+ * ScInterpreter::IterateParameters() to make it simpler and remove this
+ * struct.
+ */
+ struct IterateResult
+ {
+ double mfFirst;
+ double mfRest;
+ size_t mnCount;
+
+ IterateResult(double fFirst, double fRest, size_t nCount) :
+ mfFirst(fFirst), mfRest(fRest), mnCount(nCount) {}
+
+ IterateResult(const IterateResult& r) :
+ mfFirst(r.mfFirst), mfRest(r.mfRest), mnCount(r.mnCount) {}
+ };
+
/// The maximum number of elements a matrix may have at runtime.
inline static size_t GetElementsMax()
{
@@ -345,15 +367,11 @@ public:
double And() const; // logical AND of all matrix values, or NAN
double Or() const; // logical OR of all matrix values, or NAN
- double Sum() const;
- double SumSquare() const;
- double Product() const;
- double Average(bool bTextAsZero) const;
- double Min() const;
- double Max() const;
+ IterateResult Sum(bool bTextAsZero) const;
+ IterateResult SumSquare(bool bTextAsZero) const;
+ IterateResult Product(bool bTextAsZero) const;
size_t Count(bool bCountStrings) const;
-
// All other matrix functions MatMult, MInv, ... are in ScInterpreter
// to be numerically safe.
};
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index 3d1b6e4..ab698a4 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -3101,54 +3101,51 @@ namespace {
void IterateMatrix(
const ScMatrixRef& pMat, ScIterFunc eFunc, BOOL bTextAsZero,
- ULONG& rCount, short& rFuncFmtType, double& fVal, double& fRes, double& fMem, bool& bNull)
+ ULONG& rCount, short& rFuncFmtType, double& fRes, double& fMem, bool& bNull)
{
if (!pMat)
return;
- SCSIZE nC, nR;
rFuncFmtType = NUMBERFORMAT_NUMBER;
- pMat->GetDimensions(nC, nR);
- if( eFunc == ifCOUNT2 )
+ switch (eFunc)
{
- // TODO: Count everything but empty. Fix this.
- rCount += (ULONG) nC * nR;
- }
- else
- {
- for (SCSIZE nMatCol = 0; nMatCol < nC; nMatCol++)
+ case ifAVERAGE:
+ case ifSUM:
{
- for (SCSIZE nMatRow = 0; nMatRow < nR; nMatRow++)
+ ScMatrix::IterateResult aRes = pMat->Sum(bTextAsZero);
+ if (bNull)
{
- if (!pMat->IsString(nMatCol,nMatRow))
- {
- rCount++;
- fVal = pMat->GetDouble(nMatCol,nMatRow);
- switch( eFunc )
- {
- case ifAVERAGE:
- case ifSUM:
- if ( bNull && fVal != 0.0 )
- {
- bNull = false;
- fMem = fVal;
- }
- else
- fRes += fVal;
- break;
- case ifSUMSQ: fRes += fVal * fVal; break;
- case ifPRODUCT: fRes *= fVal; break;
- default: ; // nothing
- }
- }
- else if ( bTextAsZero )
- {
- rCount++;
- if ( eFunc == ifPRODUCT )
- fRes = 0.0;
- }
+ bNull = false;
+ fMem = aRes.mfFirst;
+ fRes += aRes.mfRest;
}
+ else
+ fRes += aRes.mfFirst + aRes.mfRest;
+ rCount += aRes.mnCount;
}
+ break;
+ case ifCOUNT:
+ rCount += pMat->Count(bTextAsZero);
+ break;
+ case ifCOUNT2:
+ rCount += pMat->Count(true);
+ break;
+ case ifPRODUCT:
+ {
+ ScMatrix::IterateResult aRes = pMat->Product(bTextAsZero);
+ fRes *= aRes.mfRest;
+ rCount += aRes.mnCount;
+ }
+ break;
+ case ifSUMSQ:
+ {
+ ScMatrix::IterateResult aRes = pMat->SumSquare(bTextAsZero);
+ fRes += aRes.mfRest;
+ rCount += aRes.mnCount;
+ }
+ break;
+ default:
+ ;
}
}
@@ -3452,13 +3449,13 @@ double ScInterpreter::IterateParameters( ScIterFunc eFunc, BOOL bTextAsZero )
if (nGlobalError)
break;
- IterateMatrix(pMat, eFunc, bTextAsZero, nCount, nFuncFmtType, fVal, fMem, fRes, bNull);
+ IterateMatrix(pMat, eFunc, bTextAsZero, nCount, nFuncFmtType, fRes, fMem, bNull);
}
break;
case svMatrix :
{
ScMatrixRef pMat = PopMatrix();
- IterateMatrix(pMat, eFunc, bTextAsZero, nCount, nFuncFmtType, fVal, fMem, fRes, bNull);
+ IterateMatrix(pMat, eFunc, bTextAsZero, nCount, nFuncFmtType, fRes, fMem, bNull);
}
break;
case svError:
diff --git a/sc/source/core/tool/scmatrix.cxx b/sc/source/core/tool/scmatrix.cxx
index d426d08..f3ea2a3 100644
--- a/sc/source/core/tool/scmatrix.cxx
+++ b/sc/source/core/tool/scmatrix.cxx
@@ -46,6 +46,10 @@
#include <mdds/mixed_type_matrix.hpp>
using ::std::pair;
+using ::std::for_each;
+using ::std::count_if;
+using ::std::advance;
+using ::std::unary_function;
using ::mdds::matrix_element_t;
// ============================================================================
@@ -54,7 +58,7 @@ namespace {
typedef ::mdds::mixed_type_matrix<String, sal_uInt8> MatrixImplType;
-struct ElemEqual : public ::std::unary_function<double, bool>
+struct ElemEqual : public unary_function<double, bool>
{
bool operator() (double val) const
{
@@ -62,7 +66,7 @@ struct ElemEqual : public ::std::unary_function<double, bool>
}
};
-struct ElemNotEqual : public ::std::unary_function<double, bool>
+struct ElemNotEqual : public unary_function<double, bool>
{
bool operator() (double val) const
{
@@ -70,7 +74,7 @@ struct ElemNotEqual : public ::std::unary_function<double, bool>
}
};
-struct ElemGreater : public ::std::unary_function<double, bool>
+struct ElemGreater : public unary_function<double, bool>
{
bool operator() (double val) const
{
@@ -78,7 +82,7 @@ struct ElemGreater : public ::std::unary_function<double, bool>
}
};
-struct ElemLess : public ::std::unary_function<double, bool>
+struct ElemLess : public unary_function<double, bool>
{
bool operator() (double val) const
{
@@ -86,7 +90,7 @@ struct ElemLess : public ::std::unary_function<double, bool>
}
};
-struct ElemGreaterEqual : public ::std::unary_function<double, bool>
+struct ElemGreaterEqual : public unary_function<double, bool>
{
bool operator() (double val) const
{
@@ -94,7 +98,7 @@ struct ElemGreaterEqual : public ::std::unary_function<double, bool>
}
};
-struct ElemLessEqual : public ::std::unary_function<double, bool>
+struct ElemLessEqual : public unary_function<double, bool>
{
bool operator() (double val) const
{
@@ -144,6 +148,23 @@ void compareMatrix(MatrixImplType& rMat)
return mdds::matrix_density_filled_zero;
}
+/**
+ * Return a numeric value from a matrix element no matter what its type is.
+ */
+double getNumericValue(const MatrixImplType::element& elem)
+{
+ switch (elem.m_type)
+ {
+ case mdds::element_boolean:
+ return static_cast<double>(elem.m_boolean);
+ case mdds::element_numeric:
+ return elem.m_numeric;
+ default:
+ ;
+ }
+ return 0.0;
+}
+
}
class ScMatrixImpl
@@ -211,12 +232,9 @@ public:
double And() const;
double Or() const;
- double Sum() const;
- double SumSquare() const;
- double Product() const;
- double Average(bool bTextAsZero) const;
- double Min() const;
- double Max() const;
+ ScMatrix::IterateResult Sum(bool bTextAsZero) const;
+ ScMatrix::IterateResult SumSquare(bool bTextAsZero) const;
+ ScMatrix::IterateResult Product(bool bTextAsZero) const;
size_t Count(bool bCountStrings) const;
private:
@@ -744,39 +762,155 @@ double ScMatrixImpl::Or() const
return EvalMatrix<OrEvaluator>(maMat);
}
-double ScMatrixImpl::Sum() const
+namespace {
+
+/**
+ * Function object to sum all numeric elements (including boolean). It
+ * stores the first non-zero element value into maRes.mfFirst while the rest
+ * into maRes.mfRest. This weird requirement comes from
+ * ScInterpreter::IterateParameters.
+ */
+class SumElements : public unary_function<void, MatrixImplType::element>
{
- return 0.0;
-}
+ ScMatrix::IterateResult maRes;
+ bool mbTextAsZero;
+public:
+ SumElements(bool bTextAsZero) : maRes(0.0, 0.0, 0), mbTextAsZero(bTextAsZero) {}
-double ScMatrixImpl::SumSquare() const
+ ScMatrix::IterateResult getResult() const { return maRes; }
+ void operator() (const MatrixImplType::element& elem)
+ {
+ switch (elem.m_type)
+ {
+ case mdds::element_boolean:
+ if (elem.m_boolean)
+ {
+ if (maRes.mfFirst)
+ maRes.mfFirst = 1.0;
+ else
+ maRes.mfRest += 1.0;
+ }
+ ++maRes.mnCount;
+ break;
+ case mdds::element_numeric:
+ if (elem.m_numeric != 0.0)
+ {
+ if (maRes.mfFirst)
+ maRes.mfFirst = elem.m_numeric;
+ else
+ maRes.mfRest += elem.m_numeric;
+ }
+ ++maRes.mnCount;
+ break;
+ case mdds::element_string:
+ if (mbTextAsZero)
+ ++maRes.mnCount;
+ default:
+ ;
+ }
+ }
+};
+
+class SumSquareElements : public unary_function<void, MatrixImplType::element>
{
- return 0.0;
-}
+ ScMatrix::IterateResult maRes;
+ bool mbTextAsZero;
+public:
+ SumSquareElements(bool bTextAsZero) : maRes(0.0, 0.0, 0), mbTextAsZero(bTextAsZero) {}
+ ScMatrix::IterateResult getResult() const { return maRes; }
+ void operator() (const MatrixImplType::element& elem)
+ {
+ if (elem.m_type == ::mdds::element_empty)
+ return;
+
+ if (elem.m_type == ::mdds::element_string)
+ {
+ if (mbTextAsZero)
+ ++maRes.mnCount;
+ return;
+ }
+
+ double val = getNumericValue(elem);
+ maRes.mfRest += val*val;
+ ++maRes.mnCount;
+ }
+};
-double ScMatrixImpl::Product() const
+/**
+ * Multiply all boolean and numeric elements. It skips empty elements, and
+ * optionally string elements if specified. When text as zero option is
+ * specified, it treats string elements as if they have values of zero.
+ */
+class MultiplyElements : public unary_function<void, MatrixImplType::element>
{
- return 0.0;
+ ScMatrix::IterateResult maRes;
+ bool mbTextAsZero;
+public:
+ MultiplyElements(bool bTextAsZero) : maRes(0.0, 1.0, 0), mbTextAsZero(bTextAsZero) {}
+ MultiplyElements(const MultiplyElement& r) : maRes(r.maRes), mbTextAsZero(r.mbTextAsZero) {}
+ ScMatrix::IterateResult getResult() const { return maRes; }
+
+ void operator() (const MatrixImplType::element& elem)
+ {
+ if (elem.m_type == ::mdds::element_string)
+ {
+ ++maRes.mnCount;
+ if (mbTextAsZero)
+ maRes.mfRest = 0.0;
+ }
+ else if (elem.m_type != ::mdds::element_empty)
+ {
+ ++maRes.mnCount;
+ maRes.mfRest *= getNumericValue(elem);
+ }
+ }
+};
+
+/**
+ * Predicate for counting only boolean, numeric, and optionally string
+ * elements.
+ */
+class CountNonEmptyElements : public unary_function<bool, MatrixImplType::element>
+{
+ const bool mbCountString;
+public:
+ CountNonEmptyElements(bool bCountString) : mbCountString(bCountString) {}
+ bool operator() (const MatrixImplType::element& elem) const
+ {
+ switch (elem.m_type)
+ {
+ case mdds::element_boolean:
+ case mdds::element_numeric:
+ return true;
+ case mdds::element_string:
+ return mbCountString;
+ default:
+ ;
+ }
+ return false;
+ }
+};
+
}
-double ScMatrixImpl::Average(bool bTextAsZero) const
+ScMatrix::IterateResult ScMatrixImpl::Sum(bool bTextAsZero) const
{
- return 0.0;
+ return for_each(maMat.begin(), maMat.end(), SumElements(bTextAsZero)).getResult();
}
-double ScMatrixImpl::Min() const
+ScMatrix::IterateResult ScMatrixImpl::SumSquare(bool bTextAsZero) const
{
- return 0.0;
+ return for_each(maMat.begin(), maMat.end(), SumSquareElements(bTextAsZero)).getResult();
}
-double ScMatrixImpl::Max() const
+ScMatrix::IterateResult ScMatrixImpl::Product(bool bTextAsZero) const
{
- return 0.0;
+ return for_each(maMat.begin(), maMat.end(), MultiplyElements(bTextAsZero)).getResult();
}
size_t ScMatrixImpl::Count(bool bCountStrings) const
{
- return 0;
+ return count_if(maMat.begin(), maMat.end(), CountNonEmptyElements(bCountStrings));
}
void ScMatrixImpl::CalcPosition(SCSIZE nIndex, SCSIZE& rC, SCSIZE& rR) const
@@ -1051,34 +1185,19 @@ double ScMatrix::Or() const
return pImpl->Or();
}
-double ScMatrix::Sum() const
-{
- return pImpl->Sum();
-}
-
-double ScMatrix::SumSquare() const
-{
- return pImpl->SumSquare();
-}
-
-double ScMatrix::Product() const
-{
- return pImpl->Product();
-}
-
-double ScMatrix::Average(bool bTextAsZero) const
+ScMatrix::IterateResult ScMatrix::Sum(bool bTextAsZero) const
{
- return pImpl->Average(bTextAsZero);
+ return pImpl->Sum(bTextAsZero);
}
-double ScMatrix::Min() const
+ScMatrix::IterateResult ScMatrix::SumSquare(bool bTextAsZero) const
{
- return pImpl->Min();
+ return pImpl->SumSquare(bTextAsZero);
}
-double ScMatrix::Max() const
+ScMatrix::IterateResult ScMatrix::Product(bool bTextAsZero) const
{
- return pImpl->Max();
+ return pImpl->Product(bTextAsZero);
}
size_t ScMatrix::Count(bool bCountStrings) const
More information about the Libreoffice-commits
mailing list