2
\$\begingroup\$

I made a program to attempt to find all palindromes in the danish language. Words.txt contains about 50.000 lines of danish words. Palindromes.txt is empty initially.

Im running the program on a Intel® Core™ m3-7Y30 Processor - which has a base frequency of 1.00 GHz. Seeing as the program - as it currently stands - has to check 50.000 * 50.000 = 2.500.000.000 words, it is really slow. Ive been running it for about 25 minutes now without a result (unsuprisingly). I am fairly new to C++, and so I have no idea how to optimize this.

Thats why im posting here - any tips on how to optimize the speed of the program would be greatly appreciated!

#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <chrono>

std::string read_file(const std::string& path)
{
    std::ifstream file(path);
    if (!file.is_open())
    {
        std::cerr << "Couldent open file!" << std::endl;
    }
    std::string content = std::string(std::istreambuf_iterator<char>(file), std::istreambuf_iterator<char>());
    if (content.empty())
    {
        std::cerr << "Couldent read file content" << std::endl;
    }
    return content;
}

std::vector<std::string> split_words(const std::string& words_string)
{
    std::vector<std::string> words;
    words.reserve(50000);
    std::stringstream ss_word(words_string);
    std::string word;
    while (!ss_word.eof())
    {
        ss_word >> word;
        words.push_back(word);
    }
    return words;
}

std::vector<std::string> find_palinedromes(const std::vector<std::string>& words)
{
    std::vector<std::string> palindromes;
    std::string first_word = std::string();
    std::string second_word = std::string();

    for (int i = 0; i < words.size(); ++i)
    {
        for (int j = 0; j < words.size(); ++j)
        {
            first_word = words[i];
            second_word = words[j];
            std::reverse(first_word.begin(), first_word.end());

            if (first_word == second_word)
            {
                if (std::find(palindromes.begin(), palindromes.end(), first_word) == palindromes.end())
                {
                    palindromes.push_back(first_word);
                }
            }
        }
    }

    return palindromes;
}

void write_to_file(const std::string& path, const std::vector<std::string>& words)
{
    std::ofstream file(path);
    if (!file.is_open())
    {
        std::cerr << "Couldent open file!" << std::endl;
    }
    for (const std::string& word : words)
    {
        file << word + "\n";
    }
}

int main()
{
    auto start = std::chrono::high_resolution_clock::now();
    std::string words_string = read_file("C:/Users/A/source/repos/Bresenhams/Bresenhams/src/Words.txt");
    std::vector<std::string> words = split_words(words_string);
    std::vector<std::string> palindromes = find_palinedromes(words);
    write_to_file("C:/Users/A/source/repos/Bresenhams/Bresenhams/src/Palindromes.txt", palindromes);
    auto stop = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::seconds>(stop - start);
    std::cout << "Found all palindromes in: " << duration.count() << std::endl;
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

You are doing a double loop checking against all other words to determine if something is a palindrome. This is unnecessary. You can look at a single word and determine if it is a palindrome, by reversing it. This should reduce the number of checks by a factor of n.

You should also prefer using a range for to a raw for-loop.

find_palindromes can then become something like this:

std::vector<std::string> find_palindromes(const std::vector<std::string>& words)
{
    for (const std::string& word : words )
    {
        std::string reverseWord(word);
        std::reverse(reverseWord.begin(), reverseWord.end());

        if (word == reverseWord)
        {
            if (std::find(palindromes.begin(), palindromes.end(), first_word) == palindromes.end())
            {
                palindromes.push_back(first_word);
            }
        }
     }

    return palindromes;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Waw, no idea why I thought I needed two words.. This is optimal, thank you! \$\endgroup\$ – Cortex Oct 31 '19 at 15:15

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.