5
\$\begingroup\$

I'm a complete beginner in C++. I wrote a class to compute similarity coefficients using Euclidean distance and Pearson coefficients on map data structure. I would like to know if it is possible to improve the code to make it more efficient in terms of memory and time it takes to execute the code.

Header:

#include <map>
#include <string>

extern "C" class DATAANALYTICS_API Similarity
{
    std::map<std::string, std::map<std::string, double>> data_;

public:
    Similarity(std::map<std::string, std::map<std::string, double>> &data);
    double EuclideanSimilarity(std::string a, std::string b);
    double PearsonSimilarity(std::string a, std::string b);
};

Implementation:

#include <iostream>
#include <map>
#include <string>
#include <cmath>
#include <vector>
#include "DataAnalytics.h"

Similarity::Similarity(std::map<std::string, std::map<std::string, double>> &data)
{
    data_ = data;
}

double Similarity::EuclideanSimilarity(std::string a, std::string b)
{
    double distance_squared = 0, aVal, bVal;
    for (auto const &entry : data_[a])
    {
        if (data_[b].count(entry.first) > 0)
        {
            aVal = entry.second;
            bVal = data_[b][entry.first];
            distance_squared += (aVal - bVal) * (aVal - bVal);
        }
    }
    return (1 / (1 + distance_squared));
}

double Similarity::PearsonSimilarity(std::string a, std::string b)
{
    double aVal, bVal, aExpectedValue = 0, bExpectedValue = 0, aSquaredExpectedValue = 0, bSquaredExpectedValue = 0, abExpectedValue = 0;
    std::vector<double> aValues, bValues, abValues;
    int commonItemCounter = 0;

    for (auto const &entry : data_[a])
    {
        if (data_[b].count(entry.first) > 0)
        {
            commonItemCounter++;
            aVal = entry.second;
            bVal = data_[b][entry.first];
            aValues.push_back(aVal);
            bValues.push_back(bVal);
            abValues.push_back(aVal * bVal);
        }
    }

    if (aValues.size() == 0) 
    {
        return 0;
    }
    else
    {
        for (int i = 0; i < aValues.size(); i++)
        {
            aExpectedValue += aValues[i] / commonItemCounter;
            bExpectedValue += bValues[i] / commonItemCounter;
            aSquaredExpectedValue += pow(aValues[i], 2) / commonItemCounter;
            bSquaredExpectedValue += pow(bValues[i], 2) / commonItemCounter;
            abExpectedValue += abValues[i] / commonItemCounter;
        }
        double denominator = sqrt(aSquaredExpectedValue - pow(aExpectedValue, 2)) * sqrt(bSquaredExpectedValue - pow(bExpectedValue, 2));
        if (denominator != 0)
        {
            return (abExpectedValue - (aExpectedValue * bExpectedValue)) / denominator;
        }
        else
        {
            return 0;
        }
    }
}

When I run unit tests on the two methods EuclideanSimilarity and PearsonSimilarity, they both take about 130ms to complete which is a bit strange because I'm doing a lot more in PearsonSimilarity than in EuclideanSimilarity.

\$\endgroup\$
  • \$\begingroup\$ Where do the unit tests get their data? Depending on how you did that, it may account for most of the elapsed time. \$\endgroup\$ – David K Dec 25 '17 at 18:32
  • \$\begingroup\$ Also, is measuring the time of tests a valid performance measurement? I'd expect test code to be very different from actual use code since you're specifically testing edge cases and unlikely scenarios, etc. \$\endgroup\$ – user1118321 Dec 26 '17 at 3:13
  • \$\begingroup\$ Data is a hard-coded in-memory map. \$\endgroup\$ – swdon Dec 26 '17 at 3:23
  • \$\begingroup\$ Don't pass strings by value if you don't intend to store a copy of them. \$\endgroup\$ – D. Jurcau Dec 26 '17 at 11:59
1
\$\begingroup\$

I have to admit that I don't have any familiarity with this particular problem, so I can't offer any great advice on it. That said, I do see a few things in your code that I think could be improved.

Scope

One thing I would recommend is moving variables closer to the place where they are used. You're currently defining all variables at the beginning of the function, and that makes it harder to tell what might have been changed when reading the body of the function. In PearsonSimilarity() you're using aVal, bVal, and the vectors in the first for loop. The expected values are not used until the second for loop (inside an if). I would move their declarations into the else clause of the if because of this. Further, I would move each declaration to its own line. Your lines are very long and hard to read because I have to scroll to see everything on them.

In fact, it might make sense to break up the function and call 2 smaller functions - one which calculates the commonItemCounter and the arrays, and another which processes the arrays. That's up to you.

Performance

One big thing I see that could be improved is to remove all calls to pow(). In each case you are squaring the input value. pow() is a very expensive function, and it's a single instruction to just multiply a value by itself. I would first pull the value out of the array, and then use it multiple times, like this:

    for (int i = 0; i < aValues.size(); i++)
    {
        double a = aValues [ i ];
        double b = bValues [ i ];
        double ab = abValues [ i ];
        aExpectedValue += a / commonItemCounter;
        bExpectedValue += b / commonItemCounter;
        aSquaredExpectedValue += (a * a) / commonItemCounter;
        bSquaredExpectedValue += (b * b) / commonItemCounter;
        abExpectedValue += ab / commonItemCounter;
    }

Another thing that I see that is likely to be slow is that commonItemCounter is defined as an int but is used to calculate floating point values. You should declare it as a double. And then, once you have, it might make sense (measure to be sure) to invert it and multiply by it instead of dividing by it. (This might be a non-issue on modern systems, but has been an issue in the past.)

Early Returns

Early returns are helpful when you have some "early out" conditions such as the input being out-of-range or degenerate in some way. That's not the case here, and it can be confusing to follow. In this case, I'd recommend having a return value and only a single return statement at the end like this:

double result = 0.0;
if (aValues.size() > 0)
{
    for (int i = 0; i < aValues.size(); i++)
    {
        // ... rest of loop here
    }
    double denominator = sqrt(...stuff...)
    if (denominator != 0.0)
    {
        result = (abExpectedValue - (aExpectedValue * bExpectedValue)) / denominator;
    }
}
return result;

It's fewer levels of ifs (less cyclomatic complexity) and easier to understand the flow.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your feedback, especially on the pow and helping me to reduce the ifs. I plan to take out commonItemCounter counter and use vector.size() if it doesn't slow down because I don't really need it for the computation. \$\endgroup\$ – swdon Dec 26 '17 at 4:11
  • \$\begingroup\$ Regarding variable declaration, I have a preference to declare important variables in one place. I look for a bit more consensus on that. Thanks :) \$\endgroup\$ – swdon Dec 26 '17 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.