2
\$\begingroup\$

I've made a program that outputs you the most common word in txt file. Does anybody know how to optimize it so that it would work for bigger files and run faster?

#include <iostream>
#include <string>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int main()
{
    ifstream in("file.txt");

    if(!in){
        cerr << "Could not open file.txt.";
        return EXIT_FAILURE;
    }

    string str, str2, strn, tab[10000], tab2[10000];
    int i, k, j, n, l, tabl;
    char c = 179;
    vector<int> tabs;
    vector<string> stringi;

    while(getline(in, str2)){
        str += str2;
        str += ' ';
    }
    k = 0;
    for(i = 0; i < str.length(); i++){
        if(str[i] != ' ' && str[i] != '.' && str[i] != '\t' && str[i] != ','
           && str[i] != ';' && str[i] != ':' && str[i] != '}' && str[i] != '{'){
            tab[k] += tolower(str[i]);
        }else{
            k++;
        }
        if(str[i] == '.' || str[i] == '\t' || str[i] == ',' || str[i] == ';'
        || str[i] == ':' || str[i] == '}' || str[i] == '{') {
            k--;
        }
    }
    tabl = k;

    k = 0;
    for(i = 0; i < tabl; i++){
        for(j = 0; j < tabl; j++){
            if(tab[i] == tab[j]){
                k++;
            }
        }
        tabs.push_back(k);
        k = 0;
    }
    for(i = 0; i < tabl; i++){
        for(j = 0; j < tabl-1; j++){
            if(tab[j] < tab[j+1]){
                n = tabs.at(j);
                tabs.at(j) = tabs.at(j+1);
                tabs.at(j+1) = n;
                strn = tab[j];
                tab[j] = tab[j+1];
                tab[j+1] = strn;
            }
        }
    }
    for(i = 0; i < tabl; i++){
        for(j = 0; j < tabl-1; j++){
            if(tabs.at(j) < tabs.at(j+1)){
                n = tabs.at(j);
                tabs.at(j) = tabs.at(j+1);
                tabs.at(j+1) = n;
                strn = tab[j];
                tab[j] = tab[j+1];
                tab[j+1] = strn;
            }
        }
    }
    tab2[0] = tab[0];
    for(i = 0; i < tabl; i++){
        if(tab[i] != tab[i+1]){
            tab2[i] = tab[i+1];
        }
    }
    k = 1;
    l++;
    for(i = 0; i < tabl; i++){
        if(!tab2[i].empty()){
            l++;
        }
    }
    cout << "------------------------------------" << endl;
    cout << "|--->TABLE OF MOST COMMON WORDS<---|" << endl;
    cout << "------------------------------------" << endl;
    for(i = 0; i < tabl; i++){
        if(!tab2[i].empty() && k <= 20 ){
            cout << c << k++ << "." << '\t' << c << tab2[i] << '\t' << c << "*" <<
            tabs.at(i+1)
            << '\t'  << c << roundf(((float)tabs.at(i+1)*100/l)*100)/100 << "%" <<
            endl;
        }
    }
    cout << "------------------------------------" << endl ;
    cout << "|----->Dif. strings: " << '\t' << l << "<-------|" << endl ;
    cout << "------------------------------------" << endl;

    return 0;
}

Output image:

enter image description here

\$\endgroup\$
  • 3
    \$\begingroup\$ Hi, I think this program is hard to follow. Everything is in main(). You don't use any functions. There are no comments either. Reviewers are going to spend a majority of their time understanding your code before reviewing. \$\endgroup\$ – Quaxton Hale Oct 13 '14 at 0:41
  • 1
    \$\begingroup\$ You are reusing the k variable. First as the number of strings, then as the number of occurrences of each string. Plus, you have several variables with names differing by one letter. These differences are subtle. As if it weren't confusing enough, I'm sorry...but -.- \$\endgroup\$ – Quaxton Hale Oct 13 '14 at 1:05
  • \$\begingroup\$ This code is broken in a couple of ways. First, I had to make some fixes to it so that it would compile. Next, the first file on which I ran it caused a core dump. Try cleaning up the code, making sure it actually runs and post the revised version when you're done. This code isn't really ready for review yet. \$\endgroup\$ – Edward Oct 13 '14 at 1:50
  • \$\begingroup\$ Why is this closed? Looks like it works to me. \$\endgroup\$ – Martin York Oct 13 '14 at 17:38
3
\$\begingroup\$

Overall

You seem to have stuffed everything into a single function. This makes it harder than necessary to follow. A couple of functions to break things up into manageable units would probably be a good idea (its part of self documenting code).

Your naming convention is also a bit shoddy.

    string str, str2, strn, tab[10000], tab2[10000];
    int i, k, j, n, l, tabl;
    char c = 179;
    vector<int> tabs;
    vector<string> stringi;

None of these names coneys any meaning of what they are being used for. Just like functions variables should be given meaningful names so that reading the code becomes self explanatory.

    std::string   inputLine;
    std::getline(std::cin, inputLine);

There is no real reason to use built-in C-arrays. std::vector and std::array are always going to be a better alternative (unless you are yourself building a container).

Basic Code Review

Prefer to use C++ header files:

#include <math.h>

// Prefer
#include <cmath>

It is guaranteed to know about namespaces and put the functions into it. It also includes some templated maths functions that are not available from C (that you may or may not get when using math.h)

How many time must we say this! Did you not read any of the other previous review? Don't do this

using namespace std;

See: Why is “using namespace std;” considered bad practice?

Why are you reading the whole file into memory?

    while(getline(in, str2)){
        str += str2;
        str += ' ';
    }

All this is doing is reading the whole file into memory (inefficiently) replacing newlines with space. Your main problem with this is going to be the continuous reallocation of the str buffer as it grows. If you know the size you can do this much better with a read().

   std::size_t  size = getFileSize(in);
   std::string  buffer(size);
   in.read(&buffer[0], size);

I would not even do this. It is relatively efficient to read a word at a time and processes that. The standard stream reads a space separated words quite easily with the operator>>.

Here you are manually parsing the input buffer and removing punctuation (or a limited set of it).

    for(i = 0; i < str.length(); i++){
        if(str[i] != ' ' && str[i] != '.' && str[i] != '\t' && str[i] != ','
           && str[i] != ';' && str[i] != ':' && str[i] != '}' && str[i] != '{'){
            tab[k] += tolower(str[i]);
        }else{
            k++;
        }
        if(str[i] == '.' || str[i] == '\t' || str[i] == ',' || str[i] == ';'
        || str[i] == ':' || str[i] == '}' || str[i] == '{') {
            k--;
        }
    }
    tabl = k;

There are a couple of things you can do to make this more efficient and easier to read. First lets make it function to hold the test:

    bool isMyPunct(unsigned char x)
    {
         return str[i] == '.'  || 
                str[i] == '\t' || 
                str[i] == ','  || 
                str[i] == ';'  || 
                str[i] == ':'  || 
                str[i] == '}'  || 
                str[i] == '{';
    }

Notice how much easier that is to read. Now you can modify your code too:

    for(i = 0; i < str.length(); i++){
        if(str[i] != ' ' && !isMyPunct(str[i]){
            tab[k] += tolower(str[i]);
        }else{
            k++;
        }
        if(isMyPunct(str[i]) {
            k--;
        }
    }
    tabl = k;

Back to the isMyPuct(). The best optimization here is we can can convert multiple tests into a single test by using a table lookup.

    bool isMyPunct(unsigned char x)
    {
         static char const punctTestTable[] =
               {
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,  // '\t'
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,  // ',' '.'
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,  // ':' ';'
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0,  // '{' '}'
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
               };
         return punctTestTable[x];
    }

But doing this all manually is a pain. You can get the stream to do it for you by using a specialized local that treats your punctuation like spaces. See How to tokenzie (words) classifying punctuation as space

The rest of the code is incomprehensible.
I could probably sit down and work it out. But the point is that is hard. You want people to be able to read your code at first glance and understand at least the gist of what you are doing.

    k = 0;
    for(i = 0; i < tabl; i++){
        for(j = 0; j < tabl; j++){
            if(tab[i] == tab[j]){
                k++;
            }
        }
        tabs.push_back(k);
        k = 0;
    }
    .....

Prefer "\n" to std::endl.

    cout << "------------------------------------" << endl;

It does not force a flush when you don't need one. Note: you hardly ever need to force a flush it is much more efficient to let the system to flush at appropriate times.

Re-Think

Version 1:

int main()
{

    std::ifstream     inputFile;

    inputFile.imbue(std::locale(std::locale(), new IgnorePuct(std::locale()));
    inputFile.open("file.txt");

    std::map<std::string, std::size_t>   countOfWords;
    TopTenWordsWithCount                 topTen;

    std::string     word;
    while(inputFile >> word)
    {
        std::size_t&  count = countOfWords[word];
        ++count;

        topTen.add(word, count);
    }
    std::cout << topTen;
}

Two things to implement:

\$\endgroup\$
  • \$\begingroup\$ +1 for suggesting to use a facet. I'd be inclined to use ++countOfWords[word]; and then convert the map into a reverse lookup multimap and pick out the top 10 from there. Your version would use less memory, though. \$\endgroup\$ – Edward Oct 13 '14 at 21:26
3
\$\begingroup\$
  • Declare variables as late as possible. int i, k, j, n, l, tabl; What do these variables do? It is quite difficult to figure that out. If you declare and initialize them when needed it would be clear.
  • Keep variables as local as possible. A loop such as for(i = 0; i < str.length(); i++) makes me think the result of i is required later which it is not (I think). Prefer for (int i = 0; i < str.length(); i++).
  • People do not like using namespace std;.
  • tab[10000] and char c = 179; have magic numbers. Why 10000 and 179? Since you know how to use vector it is hard to guess why you thought having 10000 stings twice is a good idea.
  • This seems to be a major performance problem (you are supposed to profile because obvious performance problems can get fixed by the optimizer and the line between what the optimizer thinks is obvious and which is not is very hard to predict):

    while(getline(in, str2)){
        str += str2;
        str += ' ';
    }
    

    This produces a string to hold a single line. Then it adds a line, but it is out of memory, so it allocates new memory for 2 lines, copies 2 lines and throws the memory for 1 string away. Then it allocates memory for 3 lines, copies 3 lines and throws 2 lines of memory away. When you start allocating memory for 100 lines, copy 100 lines and throw 99 lines worth of memory away things get slow. I would suggest counting words one line at a time instead of reading the whole file at once.

  • Use functions. Some people do not allow more than 10 lines per function, otherwise it must be re-factored into multiple functions. 10 lines are a bit strict, but you should separate concerns. One function to get the input, one function to do the word counting, one function to do the output. Maybe some functions will be too complicated and need to be split up further. The point is that if you need to change a part of the program you see from the function names where to change what.
  • I looked at your loops and indexes and I don't even want to try to understand what is going on. You can replace almost all of that with a map<string, int>.

This is what I came up with (it is 4:35 am here). My code kind of deserves a review of its own because it makes me look a bit hypocritical.

    #include <iostream>
    #include <string>
    #include <map>
    #include <algorithm>
    #include <cctype>
    #include <vector>
    #include <sstream>
    #include <fstream>
    #include <iomanip>

    void removeNonAlphabeticalCharacters(std::string &s){
        s.erase(std::remove_if(std::begin(s), std::end(s), [](char c){ return !isalpha(c); }), std::end(s));
    }

    template<class Iterator>
    //constraint: Iterator::value_type == std::pair<std::string, int>
    void displayRanking(Iterator begin, Iterator end, int wordcount){
        int index = 1;
        while (begin != end){
            std::cout << '|' << index << ".\t|" <<
                begin->first << "\t|" << begin->second << "\t|" << 
                std::fixed << std::setprecision(2) << begin->second * 100.f / wordcount << "%\n";
            ++begin;
            index++;
        }
    }

    int main(){
        std::map<std::string, int> wordcounter;
        std::string input;
        int totalwords = 0;
        std::ifstream in("file.txt");
        while (in >> input){
            removeNonAlphabeticalCharacters(input);
            wordcounter[input]++;
            totalwords++;
        }
        if (totalwords == 0){
            std::cout << "failed reading words from file\n";
            return 0;
        }

        //how many words to display in the ranking
        const int top = std::min((size_t)20, wordcounter.size());
        //copy wordcounter to vector for sorting
        std::vector<std::pair<std::string, int>> toplist;
        toplist.reserve(wordcounter.size());
        std::copy(std::begin(wordcounter), std::end(wordcounter), std::back_inserter(toplist));
        auto comparator = [](const std::pair<std::string, int> &lhs, const std::pair<std::string, int> &rhs){return lhs.second > rhs.second; };
        std::partial_sort(std::begin(toplist), std::begin(toplist) + top, std::end(toplist), comparator);

        displayRanking(std::begin(toplist), std::begin(toplist) + top, totalwords);
    }

There are many ways to improve readability and performance still, but let me know how long my code takes with your input file.

\$\endgroup\$
  • \$\begingroup\$ i know that my program is not optimized yes because i did nothing on that but i will try to optimize it in the future i read every character in file and check if it is space that is slow and i use bubble sort it woul be faster with quick sort or something and i should use dinamic tables vectors and so on... \$\endgroup\$ – klemsi123 Oct 13 '14 at 11:46
  • \$\begingroup\$ @nwp actually your program run 200 to 500 times faster maybe more... it goes through 50 MB text file in 16 sec that is pretty good. \$\endgroup\$ – klemsi123 Oct 13 '14 at 12:26
  • \$\begingroup\$ @klemsi123: Your code is very C like. nwp uses more C++ features. Rather than implement everything by hand he has used a map and other standard containers. But there is more work to be done to make it more C++ like \$\endgroup\$ – Martin York Oct 13 '14 at 17:47

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.