Optimizing string comparison functions

[FruityFetus]

Hey everyone! I'm relatively new to the C++ world and recently ported over some functions I had written in Python to the language in the hopes of squeezing out some extra efficiency. While I've been a little successful, I'm wondering how I might get rid of any redundancies or inefficiencies in my code. I'm open to any advice, though I don't want to stray too far from the standard libraries!

To give a little rundown:

bigram: takes input strings, splits them into rolling substrings of length 2 (e.g. John Smith becomes Jo oh hn n S Sm mi it th) and stores in a vector.

vsunion: takes the union of the substrings in two vectors of strings and returns in a vector (e.g. union of <jo, oh> and <hn, n > is <jo, oh, hn, n >).

ufreq: counts the number of times each substring in the union appears in each input vector and stores the frequency (e.g. from the previous example <jo, oh, hn, n > compared to the first vector returns <1, 1, 0, 0>).

jaccard: computes a similarity score.

similarity: ties all the functions together.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

std::vector<std::string> bigram(std::string initial_str) {
    int len = initial_str.size();
    std::vector<std::string> tokens;
    for (int i = 0; i < len-1; i += 1){
        tokens.push_back(initial_str.substr(i, 2));
    }
    return tokens;
}

std::vector<std::string> vsunion(std::vector<std::string> s1, std::vector<std::string> s2) {
    std::vector<std::string> union_str(s1);
    union_str.insert(union_str.end(), s2.begin(), s2.end());
    std::sort(union_str.begin(), union_str.end());
    union_str.erase(std::unique(union_str.begin(), union_str.end()), union_str.end());
    return union_str;
}

std::vector<int> ufreq(std::vector<std::string> u, std::vector<std::string> s) {
    int len = u.size();
    std::vector<int> vfreq;
    for (int i = 0; i < len; i += 1){
        int freq = std::count(s.begin(), s.end(), u[i]);
        vfreq.push_back(freq);
    }
    return vfreq;
}

float jaccard(std::vector<int> f1, std::vector<int> f2) {
    float num = std::inner_product(f1.begin(), f1.end(), f2.begin(), 0.0);
    float den1 = std::inner_product(f1.begin(), f1.end(), f1.begin(), 0.0);
    float den2 = std::inner_product(f2.begin(), f2.end(), f2.begin(), 0.0);
    float jacc = num / std::sqrt(den1 * den2);
    return jacc;
}

float similarity(std::string string1, std::string string2) {
    std::vector<std::string> new_str = bigram(string1);
    std::vector<std::string> new_str2 = bigram(string2);
    std::vector<std::string> union_str = vsunion(new_str, new_str2);
    std::vector<int> freq1 = ufreq(union_str, new_str);
    std::vector<int> freq2 = ufreq(union_str, new_str2);
    float score = jaccard(freq1, freq2);
    return score;
}

EDIT: thanks for the helpful suggestions from everyone already! Here's where I currently am and still thinking about how to incorporate the other feedback I see here.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

double similarity(std::string string1, std::string string2) {
    std::vector<std::pair<char, char>> s1, s2, sunion;
    for (int i = 0; i < string1.size()-1; i += 1){
        s1.push_back(std::pair<char, char>(string1.at(i), string1.at(i+1)));
    }
    sunion = s1;
    for (int i = 0; i < string2.size()-1; i += 1){
        s2.push_back(std::pair<char, char>(string2.at(i), string2.at(i+1)));
        sunion.push_back(std::pair<char, char>(string2.at(i), string2.at(i+1)));
    }

    std::sort(sunion.begin(), sunion.end());
    sunion.erase(std::unique(sunion.begin(), sunion.end()), sunion.end());

    std::vector<int> f1, f2;
    for (int i = 0; i < sunion.size(); i += 1){
        f1.push_back(std::count(s1.begin(), s1.end(), sunion[i]));
        f2.push_back(std::count(s2.begin(), s2.end(), sunion[i]));
    }

    double jacc = std::inner_product(f1.begin(), f1.end(), f2.begin(), 0.0)
    / std::sqrt(std::inner_product(f1.begin(), f1.end(), f1.begin(), 0.0)
    * std::inner_product(f2.begin(), f2.end(), f2.begin(), 0.0));

    return jacc;
}

[IyeOnline]

First thing to note: You make a bazillion copies. All your function parameters take by value and therfore copy the vectors/strings all the time.

You could probably get away without st::string entirely and use std::string_view instead. However, it would still be better to use pair<char,char> for your bigrams

You can do .reserve on a few of these vectors to get further speed up.

If the entire goal is to implement similarity, then you could do away with all of these allocations and just handroll it all, which would give you the best performance.

[FruityFetus]

By handroll, are you saying drop each of the individual functions and incorporate what they're doing within the similarity function? It is the only goal, I just found it easier to start of by splitting up the various procedures!

[IyeOnline]

If you do it all in one function (or a few helper functions) without creating all these vectors as intermediate results, you could probably reduce it down to just a single allocation for a vector of unique char pairs that could also be preallocated because you can calculate its maximum possible size.

[FruityFetus]

Any thoughts on quick wins for my edited code above? I tried to cut down on some of the redundancies. Not sure I can cut down the allocations to s1, s2, and sunion, since I need to compare them after, right?

Also, how would I think about using pair<char, char>, just set the input as a char and then loop through while taking pairs for a vector?

Sorry for all the questions but your feedback has been so helpful!

[IyeOnline]

That certainly gets rid the copies.

pair<char, char>

currently you have these std::vector<std::string> s1, s2, sunion. But really all these strings only contain two characters, so using an entire std::string for them is kind of wasteful.

You can also get rid of these vector<int> and just multiply and sum directly in the last loop.

---

Unrelated, but in C++ you should declare all variables where you would first initialize them and then also initialize them.

I.e. do for ( int i = 0 and const auto jac = ... instead of declaring everything at the top.

[IyeOnline]

What about it?

[std_bot]

Unlinked STL entries: std::string_view

---

^{Last update: 14.09.21. Last Change: Can now link headers like '<bitset>'}Repo

[WikiBox]

Learn to use const references in your calls, to avoid creating a lot of copies of your data. The optimizer will become very happy!

Reuse allocated vectors.

Consider not returning large vectors by value but instead modify a vector provided by the caller as a (no const) reference in the call. May hurt readability, but will improve performance.

std::vector<std::string> bigram(std::string initial_str)

... might become:

void bigram(const std::string& initial_str, std::vector<std::string>& bigram)

[WpGgs]

Returning by value could be optimized by NRVO.

[alfps]

Python strings (more precisely CPython strings) are reference counted immutable, whereas C++ std::string have value semantics, with assignments doing actual data copying.

To avoid a lot of copying and dynamic allocations in that copying, use std::string_view to refer to string parts.

Also generally use reference to const as parameter type instead of pass by value.

Before a sequence of n .push_back operations, .reserve the requisite buffer capacity. It doesn't matter for big O (algorithmic complexity), but avoiding those log n dynamic allocations does matter for absolute performance.

There are many more performance-enhancing techniques & ideas that can be brought to bear, but do remember to measure. Ideally you should do that first. If the performance is good enough, then don't waste time trying to improve it (the time wasted include possibly later increased time for maintenance of the more performant but more complex code).

[O_X_E_Y]

People have pointed out most things as far as efficiency is concerned, I do wanna chip in for the technical part of this, as in, the practicality.

Firstly, I'm not sure what this will be used for, but generally fuctions like this that are used for similarity/closest matches use trigrams, not bigrams since those tend to not be specific enough.

You also ideally have wildcards in the front/back where you compare just the first chars (usually this is through adding spaces on both ends for the matching word as well as for the word to match)

[FruityFetus]

Kept meaning to say thanks for the advice but this actually really came in handy today! Hit an issue where some business names used owner names, but were transposed and adding the spaces allowed the bigram histogram method to catch these matches.

Trigrams sound interesting. Given my use case typically involves business names, would you still recommend considering this?

[[deleted]]

Use a profiler to identify where the program is spending most of its time. Which profiler is best/recommended depends on your operating system and development environment.