Problem definition

Find the longest word that doesn't contain any of the following characters:

gkmqvwxz

Input comes from a file named words.txt and contains one word per line. A word is anything that is not a whitespace.


The twist

My C++ implementation posted below is surprisingly slow, taking 1.7 seconds to run, whereas my javascript implementation (link, will obviously be slower because it's online) takes only 55ms. Is it possible to somehow optimize my C++ implementation?

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdint>

#include "TimeUtil.h"

int main()
{
    uint64_t begin_time = currentTimeNanoseconds();

    std::string longestAcceptableWord; // Variable to contain the longest word

    std::string currentLine;
    const char badLetters[] = { 'g', 'k', 'm', 'q', 'v', 'w', 'x', 'z' };

    std::ifstream in;
    in.open("words.txt");
    while (!in.eof()) // Loop through the entire file (466 544 lines, 4 749 kB).
    {
        getline(in, currentLine);

        if (currentLine.length() <= longestAcceptableWord.length())
        {
            continue;
        }

        // If the word contains one of the bad letters, don't accept it.
        for (unsigned int i = 0; i < sizeof(badLetters); i++)
        {
            if (currentLine.find(badLetters[i]) != std::string::npos)
            {
                continue;
            }
        }

        // If the word is longer than the current longest word found, 
        // and doesn't have any bad letters, make it the new longest 
        // word found.
        longestAcceptableWord = currentLine;
    }
    in.close();

    std::cout << "[" << (double) ((currentTimeNanoseconds() - begin_time) / 1000) / 1000.0f << "ms] " << longestAcceptableWord << std::endl;

    return 0;
}
  • are you sure it is 55ms and not 550ms? I'm getting 90-100ms on my computer with my C++ implementation. – Incomputable Oct 10 at 16:12
  • 1
    Are you sure you enabled all optimizations in your compiler? Because something like a debug mode, or even no optimization could jeopardize performance. – papagaga Oct 10 at 16:20
  • @Xydez, after testing on the computer of my friend, he got 90ms for javascript version and ~47ms for C++ version with -O3, which I expected. I believe there is some other variable in the benchmark, not only performance of the two implementations. – Incomputable Oct 10 at 17:07
  • 1
    Your JavaScript solution is broken. It should be letter of badLetters, not letter in badLetters. – xehpuk Oct 11 at 9:16
  • 1
    Folks, don't forget that comments are not the place to make insightful observations about the code. The answer box is right there, use it :). If you want to banter, Code Review Chat is much more suited to that. I've removed a slew of comments in accordance to the site rules. Thanks! – Vogel612 Oct 11 at 9:37

I see a number of things that may help you improve your program.

Fix the bug

There is a subtle bug in the original implementation. It contains these lines:

// If the word contains one of the bad letters, don't accept it.
for (unsigned int i = 0; i < sizeof(badLetters); i++) {
    if (currentLine.find(badLetters[i]) != std::string::npos) {
        continue;
    }
}

The intent is, of course, to escape the for loop and go on if a bad letter is found in a candidate word. However, what actually happens is that first letter is checked, and the loop continues no matter if the letter was found or not. That's a bug and one reason I don't much like continue. It's too easy to make this kind of error.

Don't loop on eof()

It's almost always incorrect to loop on eof() while reading a file. The reason is that the eof indication is only set when an attempt is made to read something from the file when we're already at the end. So instead of this:

while (!in.eof()) {
    getline(in, currentLine); 
    // ...
}

write this:

while (getline(in, currentLine)) { 
    // ...
}

See this question for more details on why using eof is usually wrong.

Initialize variables on declaration

The best practice is to initialize variables as soon as they're created. In C++, this most often means initializing them in the same line as the declaration. So instead of this:

std::ifstream in;
in.open("words.txt");

write this:

std::ifstream file2{wordsFile};

Note, too, that I use the C++11 uniform initializer syntax (with the {}) to make it clear to both the compiler and the reader that this is an initialization and not a function call. See Stroustrup's description for more details on that.

Allow the user to specify input files

The words file name is currently hardcoded which certainly greatly restricts the usefulness of the program. Consider using argc and argv to allow the user to specify file names on the command line.

Prefer newer structures to plain arrays

Instead of a plain array as with badLetters, one could instead use an std::array or std::string. If your compiler has C++17 support, std::string_vew might be an even better choice.

const std::array<char, 8> badLetters = { 'g', 'k', 'm', 'q', 'v', 'w', 'x', 'z' };

Use standard algorithms

Instead of searching with a for loop for all badLetters, we can use std::find_first_of() instead. The result would look like this:

while (getline(in, currentLine)) {
    if (currentLine.length() > longestAcceptableWord.length()
        && (std::find_first_of(currentLine.begin(),
                            currentLine.end(),
                            badLetters.begin(),
                            badLetters.end()) == currentLine.end())
    ) {
        longestAcceptableWord = currentLine;
    }
}

Note that I prefer to avoid continue and instead rely on the short-circuit evaluation of the if clauses to cause the same effect.

Don't use std::endl if you don't really need it

The difference between std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

  • The only time I have had to use std::endl was in a utility which needed to write to the console during the building of a Docker image, without it the progress would have been displayed all at once at the end of the utility, which usually ran for a couple of minutes. – Tommaso Thea Cioni Oct 10 at 20:12
  • 1
    Applying Edward recommendations, here is how it may look like on repl: repl.it/@Coeur/LongestWordWithoutDisallowedCharacter – Cœur Oct 11 at 6:14

The code is reasonably good. There are some inefficiencies and small bug that doesn't affect the result.

Bug

!in.eof(), .eof() is never true until its read. It should be the getline instead.

Inefficiencies

  • reading line by line

It is in general better to just read into string variable, it is clearer and probably more efficient.

  • Manually closing the file

Standard file streams close themselves when they get out of scope, which end of main in this case.

Alternative implementation

Now, lets eliminate the main culprit, string validity check:

bool is_valid_word(std::string_view word) {
    for (char letter: word) {
        switch (letter) {
            case 'g':
            case 'k':
            case 'm':
            case 'q':
            case 'v':
            case 'w':
            case 'x':
            case 'z':
                return false;
            default:
                ; //silence warnings
        }
    }

    return true;
}

The main change is to use jump table (switch statement) with fallthrough. The other change is to use std::string_view, immutable non owning view into string.

The next thing to care about is iteration through the file. My personal preference is to use a pair of iterators:

std::ifstream file("words.txt");
auto first = std::istream_iterator<std::string>(file);
auto last = std::istream_iterator<std::string>();

And the algorithm itself:

template <typename InputIterator>
std::string longest_valid_word(InputIterator first, InputIterator last) {
    std::string longest_word;
    while (first != last) {
        if (first->size() > longest_word.size() && is_valid_word(*first)) {
            longest_word = *first;
        }
        ++first;
    }

    return longest_word;
}

Note that the above algorithm can run on anything that provides a pair of iterators, e.g. std::vector, std::list, etc.


Full code

No demo for this post, as I don't want to put the weight onto wandbox:

#include <string_view>
#include <utility>
#include <string>
#include <fstream>
#include <iterator>
#include <chrono>
#include <atomic>
#include <iostream>

bool is_valid_word(std::string_view word) {
    for (char letter: word) {
        switch (letter) {
            case 'g':
            case 'k':
            case 'm':
            case 'q':
            case 'v':
            case 'w':
            case 'x':
            case 'z':
                return false;
            default:
                ; //silence warnings
        }
    }

    return true;
}

template <typename InputIterator>
std::string longest_valid_word(InputIterator first, InputIterator last) {
    std::string longest_word;
    while (first != last) {
        if (first->size() > longest_word.size() && is_valid_word(*first)) {
            longest_word = *first;
        }
        ++first;
    }

    return longest_word;
}

int main() {
    std::ifstream file("words.txt");

    using namespace std::chrono;
    auto start_time = system_clock::now();
    //std::atomic_thread_fence(std::memory_order_seq_cst);
    auto found_word = longest_valid_word(std::istream_iterator<std::string>(file), {});
    //std::atomic_thread_fence(std::memory_order_seq_cst);
    auto end_time = system_clock::now();

    auto duration = duration_cast<milliseconds>(end_time - start_time);

    std::cout << "[" << duration.count() << "ms] "
              << found_word << std::endl;
}

The atomic thread fences can be uncommented, but they don't really change much in this case. It is probably bottlenecked by performance of my SSD and of std::ifstream.


Conclusion

Well, I got around 90-100 milliseconds on my machine. I've got no idea why it runs so slowly, but I've exhausted my sane ideas. The other one would be to do some manual parsing of the file, which is much harder.

Of course it didn't go as I expected :) this is what happens when optimizations are done in a rush. Let me break down why the code above is slower than what Toby and Edward (my speculations from results, of course):

  • std::getline is faster than using std::istream_iterator<std::string>

  • using jump table or just using array of bad letters make no difference whatsoever on my timings

Different version of alternative approach (uses std::getline)

std::string longest_valid_word(std::ifstream& is) {
    std::string buffer;
    std::string longest_word;
    while (std::getline(is, buffer)) {
        if (buffer.size() > longest_word.size() && is_valid_word(buffer)) {
            longest_word = buffer;
        }
    }

    return longest_word;
}

Just paste the function into the code and call it with the file stream, instead of calling the one with iterators.

  • @Xydez, feel free to ask questions about the post. Although templates and iterators might be a little bit alien to you, I recommend getting accustomed to them if you're planning to be library developer, as they serve as a great tools for algorithm and data structure abstractions. – Incomputable Oct 10 at 16:46

I'm not sure what "TimeUtil.h" contains, but the standard facilities (in std::chrono) are to be preferred for portable code:

#include <chrono>

int main()
{
    auto begin_time = std::chrono::high_resolution_clock::now();

    // ...

    auto end_time = std::chrono::high_resolution_clock::now();
    auto duration
        = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-begin_time);

    std::cout << "[" << duration.count() << "ms] "
              << longestAcceptableWord << std::endl;
}

It's better to separate the actual logic into its own function, separate from the timing and file opening housework.

badLetters can have static duration.

We don't need to separately construct and open the input file (and we'd be more flexible if we didn't hard-code that input - why not just read from standard input?). Also, no need to explicitly close it if we're not using the return value of close() - just let the destructor do its job!

while (!eof()) is an anti-pattern: we should while (getline()) instead. The latter actually attempts a read, whereas the former only determines whether the previous read hit end of file.

std::string has find_first_of which tests for all the characters in a set concurrently. The set does need to be passed as a null-terminated string (or as a std::string or std::string_view), but that's not hard to arrange.

Modified code

Applying the advice above, we get:

#include <iostream>
#include <fstream>
#include <string>

#include <chrono>

std::string findLongestLineNotContaining(std::istream& in,
                                         const char *badLetters)
{
    std::string longestAcceptableWord;
    std::string currentLine;
    while (getline(in, currentLine))
    {
        if (currentLine.length() > longestAcceptableWord.length() &&
            currentLine.find_first_of(badLetters) == currentLine.npos)
        {
            // Word is longer than the current longest word found,
            // and doesn't have any bad letters, so make it the new
            // longest word found.
            longestAcceptableWord = currentLine;
        }
    }
    return longestAcceptableWord;
}


int main()
{
    namespace chr = std::chrono;
    auto begin_time = chr::high_resolution_clock::now();

    static const char *badLetters = "gkmqvwxz";
    std::ifstream in("words.txt");
    std::string longestAcceptableWord
        = findLongestLineNotContaining(in, badLetters);

    auto end_time = chr::high_resolution_clock::now();
    auto duration = chr::duration_cast<chr::milliseconds>(end_time - begin_time);

    std::cout << "[" << duration.count() << "ms] "
              << longestAcceptableWord << std::endl;
}
  • 1
    I like the clean interface for findLongestLineNotContaining, but I'd suggest making badLetters a better container such as a std::string_view or const std::array. – Edward Oct 10 at 18:06
  • Yes, that's more idiomatic modern C++; std::string_view works better, as that's directly accepted by std::string::find_first_of(); an array would need conversion (admittedly not hard). – Toby Speight Oct 10 at 19:07
  • Actually, there is a standalone std::find_first_of that I showed in my answer that accepts any kind of container. (Frankly, I'd just forgotten about the string version until I saw your answer!) – Edward Oct 10 at 19:09
  • This is good advice but it doesn’t explain why OP’s C++ code is substantially slower than their JavaScript code. The logic in both implementations is essentially the same (modulo a JS bug pointed out in the comments, and a C++ bug which means that every string, not just a candidate, is copied; both bugs barely affect timing). The C++ code should be a lot faster (and on my machine it’s ~ 10x as fast as the JS code). – Konrad Rudolph Oct 11 at 9:49

The problem's definition doesn't specify that the answer should be in C++. You can get the answer in less than a second with the following Unix shell pipeline one-liner.

$ time grep -v '[gkmqvwxz]' words.txt | awk '{print length($1), $1}' | sort -rn | head -1

31 dichlorodiphenyltrichloroethane

real    0m0.960s

Here are the commands explained one-by-one. The commands are connected into a pipeline so that the output of each command is filtered by the next one.

# Remove lines containing any of the disallowed characters
grep -v '[gkmqvwxz]' words.txt |
# Prefix each word by its length
awk '{print length($1), $1}' |
# Order the output numerically in reverse order
sort -rn |
# Output first line
head -1

Alternatively, you might want to write this in a scripting language, which, compared to the C++ implementation, is almost as concise and also executes faster.

awk

$ time awk '!/[gkmqvwxz]/ && length($1) > max_length {result = $1; max_length = length($1); } END {print result}' words.txt
dichlorodiphenyltrichloroethane

real    0m0.180s

Perl

$ time perl -ne ' if (!/[gkmqvwxz]/ && length($_) > $max_length) {$result = $_; $max_length = length($_); } END {print $result}' words.txt
dichlorodiphenyltrichloroethane

real    0m0.371s

Less code means fewer possibilities for bugs and significantly less effort from your part. Nowadays in most cases it's better to optimize for readability and developer effort rather than for CPU efficiency.

  • 2
    These are great solutions but this is a code review site and I’m not sure how much use they’d be to the OP. That said, I actually think highlighting alternative solutions isn’t a bad idea here. – Konrad Rudolph Oct 11 at 10:38
  • 1
    @DiomidisSpinellis As Konrad said, this isn't of use to me. However I appreciate the answer. Thanks! – Xydez Oct 11 at 10:58
  • 3
    @KonradRudolph It could possibly be useful for others though in this case. I'm normally against "alternative solution"-answers but I consider this as a quite insightful one. – Simon Forsberg Oct 11 at 13:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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