1
\$\begingroup\$

I am a C++ beginner and am working on a bit of code which calculates the pairwise cosine similarities between vectors. The vectors are TF-IDF vectors and the similarities are used to determine similarity between texts (documents).

My code and approach outlined below work as expected, but runs into performance issues when datasets get larger. The number of vectors often runs into the thousands and the vectors can be quite large themselves (thousands of elements).

I have done the following to try and optimize the code:

  • In the nested loop, set j equal to i to only calculate similarities one way, i.e. only return results for one side of the diagonal of the similarity matrix;
  • Passing the vectors as const references to cosine_similarity to avoid the overhead of copying the vectors;
  • Defined v1i and v2i outside of the loop in cosine_similarity to only look them up once inside the loop (as opposed to using v1[i] and v2[i] in the dot product and sum of squares calculations);
  • Check for dot_product == 0 in cosine_similarity to avoid magnitude calculation when it is not necessary.

Here's what I have:

// Vector containing all the vectors to compare (populated somewhere else)
std::vector< std::vector<double> > vector_of_vectors;

// Get the number of vectors
int number_of_vectors = vector_of_vectors.size();

// Get the size of a vector (all vectors have the same size)
int vector_size = vector_of_vectors[0].size();

// Vector to store the results
std::vector<double> similarities;

// Nested loop for similarity calculation
for (int i=0; i<number_of_vectors; ++i) {
    for (int j=i; j<number_of_vectors; ++j) {
        if (i == j) {
            similarities.push_back(1);
        } else {
            similarities.push_back(cosine_similarity(vector_of_vectors[i], vector_of_vectors[j], vector_size));
        }
    }
}

double cosine_similarity(const std::vector<double>& v1, const std::vector<double>& v2, const int& vector_size) {
    // Cross-vector dot product
    double dot_product = 0;

    // Sum of squares of first vector
    double ss1 = 0;

    // Sum of squares of second vector
    double ss2 = 0;

    double v1i;
    double v2i;
    for (int i=0; i<vector_size; ++i) {
        v1i = v1[i];
        v2i = v2[i];

        dot_product += (v1i * v2i);
        ss1 += (v1i * v1i);         
        ss2 += (v2i * v2i);         
    }

    if (dot_product == 0) {
        return 0;
    } else {
        double magnitude = sqrt(ss1 * ss2);
        return dot_product / magnitude;
    }
}

I'm quite happy about how it works, but have the feeling there are some things I could do to make this much faster. Any ideas?

\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview@SE. Is there more to say as to what the code presented is to accomplish or how it is used? \$\endgroup\$ – greybeard May 13 at 10:31
  • \$\begingroup\$ Thank you. That's a good addition indeed - the vectors are TF-IDF vectors and are used for determining similarity between texts. Will add this to the question. \$\endgroup\$ – ACDSL May 13 at 10:34
0
\$\begingroup\$
  • Not so much about performance. The cosine similarity can be expressed in a more concise (and maybe even more performant) way with STL:

    dot_product = std::inner_product(v1.begin(), v1.end(), v2.begin());
    ss1 = std::inner_product(v1.begin(), v1.end(), v1.begin());
    ss2 = std::inner_product(v2.begin(), v2.end(), v2.begin());
    

    This of course assumes that the vectors are of the same size.

  • Since you want it for every pair of vectors, nothing can be done to speed thins up algorithmically. There are \$O(n^2)\$ pairs, so the performance is bound to be quadratic.

  • cosine_similarity works with each vector many times, and recomputes its length (ss1/ss2) many times. Compute them all in advance. It is probably the biggest performance gain you can achieve.

  • There is no need to pass vector_size by reference.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you! Tried using std::inner_product, but that seems significantly less performant for some reason. Excellent suggestion to precompute all sums of squares - this seems to give me a boost of about 20%! \$\endgroup\$ – ACDSL May 13 at 20:51

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.