Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have few years of experience with web and I recently started learning C++ and I feel a bit lost, so I would like to ask to for some tips how to improve my code overall. This text summarizer should get the sentences with the highest weight (most important ones).

Header file:

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <set>
#include <fstream>
#include <unordered_map>
#include <map>

typedef std::vector<std::set<std::string>> setWords;

class SmartAnalyzer
{
private:
    double sentence_intersection(std::set<std::string> const& a, std::set<std::string> const& b);
    std::vector<std::string> parseSentences(std::string const& text);
    setWords stringSets(std::string const& text);
    std::string format(std::string text, bool const& includeDot = false);

public:
    SmartAnalyzer() {}
    std::string getSummary(std::string title, std::string const& text, int const& limit);
};

Cpp file:

#include "stdafx.h"
#include "SmartlyParser.h"

double SmartAnalyzer::sentence_intersection(std::set<std::string> const& a, std::set<std::string> const& b)
{
    std::vector<std::string> common;
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(common));
    return (double) common.size() / ((a.size() + b.size()) / 2);
}

std::vector<std::string> SmartAnalyzer::parseSentences(std::string const& text) 
{
    std::vector<std::string> output;
    std::istringstream iss(text);
    std::string token;

    while (std::getline(iss, token, '.')) {
        output.push_back(token);
    }

    return output;
}

setWords SmartAnalyzer::stringSets(std::string const& text)
{
    setWords output;
    std::istringstream iss(text), current;
    std::string token;

    while (std::getline(iss, token, '.')) {
        current.clear();
        current.str(token);
        output.push_back(std::set<std::string>((std::istream_iterator<std::string>(current)), std::istream_iterator<std::string>()));
    }

    return output;
}

std::string SmartAnalyzer::format(std::string text, bool const& includeDot)
{
    text.erase(std::remove_if(text.begin(), text.end(), [includeDot](char c) { return c == ',' || c == '!' || c == '"' || (includeDot && c == '.' ); }), text.end());
    std::transform(text.begin(), text.end(), text.begin(), ::tolower);
    return text;
}

std::string SmartAnalyzer::getSummary(std::string title, std::string const& text, int const& limit)
{
    std::vector<std::string> sentences = parseSentences(text);
    int sentLen = sentences.size();

    setWords sentencesC = stringSets(format(text));
    std::set<std::string> titles = std::set<std::string>((std::istream_iterator<std::string>(std::istringstream(format(title, true)))), std::istream_iterator<std::string>());

    double sum;
    std::map<double, int> sentencesWeight;

    for (int i = 0; i < sentLen; i++) 
    {
        sum = 0;
        for (int j = 0; j < sentLen; j++)
        {
            if (i == j) { /* find intersection with the title, instead of self */
                sum += sentence_intersection(sentencesC[i], titles) * 2;
                continue;
            }
            sum += sentence_intersection(sentencesC[i], sentencesC[j]);
        }
        sentencesWeight.insert({ sum, i });
    }

    std::string output;

    for (std::map<double, int>::reverse_iterator it = sentencesWeight.rbegin(); it != sentencesWeight.rend(); ++it)
    {
        if (std::string(sentences[it->second] + output).size() > limit) {
            break;
        }
        output += sentences[it->second] + ".";
    }

    if (output.empty())
    {
        output = sentences[sentencesWeight.rbegin()->second];
        std::size_t pos = output.size();

        while ((pos = output.rfind(',', pos)) != std::string::npos && output.size() > limit)
        {
            output = output.substr(0, pos);
            pos--;
        }

        output += '.';
    }

    return output;
}

int _tmain()
{
    std::ifstream ifs("F:\\Analyzer\\text.txt");
    std::string content((std::istreambuf_iterator<char>(ifs)), (std::istreambuf_iterator<char>()));

    std::string title = "Stack, overflow";

    SmartAnalyzer a;
    std::cout << a.getSummary(title, content, 5 * 36); 

    getchar();
    return 0;
}

I will really appreciate all kind of tips/improvements and advice on how to start writing in the C++ standards.

Am I using the classes right and not just C with classes?

share|improve this question
1  
You should include <iterator> and not pass a temporary istringstream to an istream_iterator. The latter works due to a language extension of MSVC. If you use the MSVC++ compiler, I heavily recommend you disable language extensions (/Za) and use warning level 4. –  dyp Apr 28 at 23:40
    
Your class looks like a namespace in disguise. –  dyp Apr 28 at 23:46
    
@dyp Can you give a simple example how I can use iterator, please? Also do you have any suggestions how can I improve my class so it don't look like namespace? Thanks. –  Deepsy Apr 29 at 0:04
1  
@Deepsy minor note, classes are private by default, the the first private in SmartAnalyzer is pointless. –  OMGtechy Apr 29 at 0:12
1  
@OMGtechy Some people (me included) like to include it for consistency and clarity. –  Corbin Apr 29 at 4:01

3 Answers 3

up vote 10 down vote accepted

Using a class instead of a namespace

class SmartAnalyzer
{
private:
    double sentence_intersection(..);
    std::vector<std::string> parseSentences(..);
    setWords stringSets(..);
    std::string format(..);

public:
    SmartAnalyzer() {}
    std::string getSummary(..);
};

This class has no data members and therefore no state, nor any invariants to protect. C++ is a "multi-paradigm" language, so you can and should choose the "paradigm" or programming style that suits best for the problem.

I do not see why a class suits well to house an algorithm, that's why I said in the comments "Your class looks like a namespace in disguise.". Even if you plan to add some state later, the current member functions are just algorithms, so you can just implement them as free functions.

If those algorithms are applicable to a wider set of problems, formulate them generically and make them "public" for others to use. If they are private member functions, others cannot reuse them. Otherwise, i.e. if they're not applicable to a wide set of problems, you can put them as free functions in the source file (.cpp) instead of declaring them in the header. In that case, make their linkage internal so their names don't collide with names of functions in other source files.


The O(n²) algorithm

You used the [optimizations] and [performance] tags. As far as I can see, most time-consuming part here is the weighting algorithm:

for (int i = 0; i < sentLen; i++) 
{
    sum = 0;
    for (int j = 0; j < sentLen; j++)
    {
        if (i == j) { /* find intersection with the title, instead of self */
            sum += sentence_intersection(sentencesC[i], titles) * 2;
            continue;
        }
        sum += sentence_intersection(sentencesC[i], sentencesC[j]);
    }
    sentencesWeight.insert({ sum, i });
}

It should be obvious that this algorithm is in O(n²). To improve the performance of you program, you should try to come up with an algorithm that's asymptotically faster. A first improvement can be achieved by noticing that the correlation is symmetric in i and j. I used a std::vector to store the sentences alongside with the weighting and slightly changed the sentence_intersection algorithm, the new name is intersection_weight:

for (std::size_t i = 0; i < sentLen; i++)
{
    sentences[i].w += 2 * intersection_weight(sentencesC[i].begin(),
                                              sentencesC[i].end(),
                                              titles.begin(), titles.end());

    for (auto j = i+1; j < sentLen; j++)
    {
        auto const res = intersection_weight(sentencesC[i].begin(),
                                             sentencesC[i].end(),
                                             sentencesC[j].begin(),
                                             sentencesC[j].end());
        sentences[i].w += res;
        sentences[j].w += res;
    }
}

As this is the most time-consuming part, this optimization halves the total run-time of the program.


Size of the intersection

double SmartAnalyzer::sentence_intersection(std::set<std::string> const& a,
                                            std::set<std::string> const& b)
{
    std::vector<std::string> common;
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                          std::back_inserter(common));
    return (double)common.size() / ((a.size() + b.size()) / 2);
}

This is a most astonishing piece of code. It calculates the size of the intersection between to sets by producing the intersection and then computing its size.

Unfortunately, I couldn't find a Standard Library algorithm to do this. So I split this into two generic algorithms:

template<typename FwdIt0, typename FwdIt1, typename Comp, typename Num>
Num count_intersection(FwdIt0 beg0, FwdIt0 end0, FwdIt1 beg1, FwdIt1 end1,
                       Comp less, Num n)
// requires:
//   [beg0, end0) is a sorted range wrt less
//   [beg1, end1) is a sorted range wrt less
//   less is a strict weak ordering on *beg0, *beg1 and between *beg0 and *beg1
//   Num is a numerical data type
// returns:
//   the size of the intersection
{
    while (beg0 != end0 && beg1 != end1)
    {
        if      (less(*beg0, *beg1)) ++beg0;
        else if (less(*beg1, *beg0)) ++beg1;
        else
        {
            ++n;
            ++beg0;
            ++beg1;
        }
    }
    return n;
}

(Even though I've thought that you could use binary search to speed this up, the linear approach is faster in practice; probably because the sets are small and random-access is expensive.)

template<typename FwdIt0, typename FwdIt1>
double intersection_weight(FwdIt0 beg0, FwdIt0 end0, FwdIt1 beg1, FwdIt1 end1)
{
    auto const mid_size = 0.5 * (  std::distance(beg0, end0)
                                 + std::distance(beg1, end1));
    auto const intsc = count_intersection(beg0, end0, beg1, end1,
                                          std::less<>(), int());
    return intsc / mid_size;
}

Note that std::less<> is a C++1y feature, but MSVC12 (2013) already supports it.

Since these algorithms are run in a tight loop, they significantly improve performance.


High-level features

Avoid std::istringstream, std::tolower and std::set in performance-critical applications. Their overhead is typically too high. Additionally, std::tolower is arguably broken: It's locale-aware but works on single characters, which fails e.g. for German BUSSE -> buße. Additionally, there's a problem with language linkage.

If you want speed, provide your own:

inline bool is_dot(char const c)
{ return c == '.'; }

inline char ascii_tolower(char const c)
{
    if (c >= 'a' && c <= 'z') return c;
    if (c >= 'A' && c <= 'Z') return c - 'A' + 'a';
    else return c;
}

inline bool ascii_isspace(char const c)
{
    return c == ' ' || c == '\n' || c == '\r';
}

You can probably further optimize those by using some > or < comparisons as a first test (most frequent branches first). As I said, the most time-consuming part is the O(n²) algorithm, so you don't actually have to worry about speed here (but the other issues still remain).

Instead of std::istringstream, use a tokenizer (e.g. boost). Instead of std::set, use a std::vector. That's not hard, e.g. if you use

template<class Cont>
inline void setify(Cont& c)
{
    std::sort(c.begin(), c.end());
    auto const garbage_beg = std::unique(c.begin(), c.end());
    c.erase(garbage_beg, c.end());
}

The `getSummary` function

for (std::map<double, int>::reverse_iterator it = sentencesWeight.rbegin();
     it != sentencesWeight.rend();
     ++it)

Since the map is only used to get the largest elements, you could use a different comparator (std::greater) instead. Although iterating in reverse isn't that expensive, you could express your intent more clearly if you map was already in descending order.

IMHO, this function is too long. It contains the parsing, the weighting and the output. Split those three parts so they can be reused or exchanged more easily.


Excessive copying

.. is not inherently bad, since it can increase locality. But some copies are just unnecessary; for example, the whole input text is copied into an istringstream in parseSentences and from there, the individual sentences are copied into a vector.

Similarly, the text is copied in getSummary by passing it to the format function, then the result is passed to stringSets which again copies it into an istringstream to be tokenized and the tokens then copied into a std::vector<std::set<std::string>>.

Use iterators or ranges to pass data if you don't need to modify the container. This decouples algorithms from data structures and makes them more easily reusable.

Something similar to the set intersection algorithm is used here:

std::string(sentences[it->second] + output).size()

This creates a temporary string just to compute its size. You can replace it with

sentences[it->second].length() + output.length()

Run-time measurements

Using MSVC12 (2013) Update 1, and the complete works of William Shakespeare. Unfortunately, that's too much data for the O(n²) algorithm, so I just used to first 13,000 lines.

  • Run-time of the original code (at /Ox): 41 s
  • Run-time of the modified code (at /Ox): 11 s

Note that I also replaced all the std::sets with std::vectors and used custom lightweight tokenizers.

share|improve this answer
    
Aren't you fed up with giving overly good answers? :) –  Morwenn Apr 29 at 14:32
    
Nevermind @Morwenn, welcome to CR! (feel free to come say hi in The 2nd Monitor/Code Review Chat ;) –  Mat's Mug Apr 29 at 14:36
    
By the way, if speed is needed, isn't it faster to implement aswcii_tolower as a lookup table? –  Morwenn Apr 29 at 20:55
    
@Morwenn Just tried it. Doesn't seem to matter here. It isn't called inside the O(n²) loop, though. –  dyp Apr 29 at 21:17
    
@dyp Ok. Just wanted to make sure :) –  Morwenn Apr 29 at 21:19

Microsoft Visual C++

Your code has been written with MSVC and may work with it, but it fails on most of the other compilers. It's not portable at all. Here is what you could do to get rid of this MSVC dependency:

  • Use main instead of _tmain.
  • Don't #include "stdafx.h".
  • #include <iterator> to guarantee that you can access std::istream_iterator.
  • Follow @dyp's comment and do not pass a temporary std::istringstream to an std::istream_iterator:

    std::istringstream iss(format(title, true));
    std::set<std::string> titles = {
        std::istream_iterator<std::string>(iss),
        std::istream_iterator<std::string>()
    };
    

Order of the headers

You often want to add/remove headers from your code and/or check whether some header is already included. It's really easier to check whether a header has already been included or not if you keep your #include directives in alphabetical ordering:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>

That said, I also agree with @Jamal: most of your headers can be moved to the .cpp and you can get rid of <unordered_map> which is not used.

Use C++11

From what I can see, you are already using C++11. Try to use more of it:

  • Try to replace push_back with emplace_back when it makes sense. For example, in SmartAnalyzer::stringSets:

    output.emplace_back(
        std::istream_iterator<std::string>(current),
        std::istream_iterator<std::string>()
    );
    
  • Use std::begin and std::end instead of the corresponding member functions. That way, generic fragments of code may also work with C arrays. For example in SmartAnalyzer::sentence_intersection:

    std::set_intersection(std::begin(a), std::end(a),
                          std::begin(b), std::end(b),
                          std::back_inserter(common));
    
  • In this piece of code:

    std::map<double, int>::reverse_iterator it = sentencesWeight.rbegin();
    

    Do you honestly care about the full type of it? Generally, you don't, you just want to iterate, use auto to deduce the type:

    auto it = sentencesWeight.rbegin(); 
    

Other notes

Some miscellaneous comment:

  • In std::string format(std::string text, bool const& includeDot = false);, using a bool const& seems to be overkill. Simply pass bool, it will be both simpler and more readable.
  • Similarly, there are places where you pass int const& parameters. Honestly, when use use integral or floating point types, passing by const& is really too much. Pass by value.
  • Many of your lines are too long. Try to break them as I did in my examples above.
  • You used ::tolower but did not #include<cctype>.
  • Moreover, std::tolower seems to have overloads for the different char types, contrary to ::tolower. You should use the correct overload from std::tolower instead of the generic ::tolower:

    std::tolower<char>
    
share|improve this answer
  • Since any file including a header file is exposed to all its code, it's best to include as few things in a header as possible. All of those libraries but <string> and <set> are not used in the header. They should instead be moved to the .cpp file, where they are being used.

    Also, <unordered_map> is not used anywhere, so it should be removed entirely.

  • If you're still going to use std::set<std::string> in other places, which is already part of your current typedef, you may add an additional one for that. You can also have your first one in terms of the new one.

    New typedef:

    typedef std::set<std::string> StringSet;
    

    First one updated:

    typedef std::vector<StringSet> SetWords;
    

    sentence_intersection()'s parameters updated:

    double sentence_intersection(StringSet const& a, StringSet const& b);
    

    Also note that I've started the typedefs with capital letters. Since your variables and functions already use camelCase, the typedefs should probably use a different naming convention (although you don't have to use this one, either).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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