Scară de cuvinte implementată folosind stivă și coadă (Revizuirea codului, C++, Performanță)

user142301 a intrebat.

Funcția mea outputLadder function preia practic un șir de început și de sfârșit și generează cea mai scurtă scară de cuvinte din aceasta.

Este iterația printr-o listă std::list care conține peste 3600 de cuvinte citite în ea dintr-un fișier text și pare să dureze foarte mult timp.

Ce pot face pentru ca funcția mea să fie mai rapidă, păstrând în același timp o implementare a stivei și a cozii pentru scara de cuvinte?

Iată linkul către ceea ce conține fișierul text: http://textuploader.com/dkacm

Iată un video: a rezultatului care arată cât timp durează.

Măsurând cu clock(), durează aproximativ 8 secunde pentru a găsi cea mai scurtă scară de cuvinte pentru style și crazy.

void WordLadder::outputLadder(const string &start, const string &end)
{
    stack<string> words;
    words.push(start);

    queue<stack<string>> ladder;
    ladder.push(words);

    while (!ladder.empty())
    {
        for (list<string>::iterator i = dictionary.begin(); i != dictionary.end(); ++i)
        {
            if (oneDiff(*i, ladder.front().top()))
            {
                if (*i == end)
                {
                    stack<string> output;

                    while (!ladder.front().empty())
                    {
                        output.push(ladder.front().top());
                        ladder.front().pop();
                    }

                    while (!output.empty())
                    {
                        cout << output.top() << " ";
                        output.pop();
                    }

                    cout << *i << endl;

                    return;
                }
                else
                {
                    stack<string> temp = ladder.front();
                    temp.push(*i);
                    ladder.push(temp);
                    i = dictionary.erase(i);
                }
            }
        }

        ladder.pop();
    }

    cout << "No word ladder exists for this word." << endl;
}

bool WordLadder::oneDiff(const string &dictWord, const string &stackWord)
{
    int count = 0;

    for (int i = 0; i < stackWord.size(); ++i)
    {
        if (dictWord.at(i) != stackWord.at(i))
        {
            ++count;
        }
    }

    if (count <= 1)
    {
        return true;
    }

    return false;
}

Comentarii

  • Ați făcut de fapt și dumneavoastră măsurători de performanță? Ar trebui să faceți asta și măcar să ne spuneți ce parte a codului dumneavoastră consumă cel mai mult.  > Por Ben Steffan.
1 răspunsuri
Ben Steffan

Câteva mici îmbunătățiri:

  1. Nu folosiți std::endl deoarece forțează întotdeauna o spălare în plus față de o nouă linie, ceea ce poate degrada performanța de ieșire.
  2. Preferați operator[] în loc de at[] ori de câte ori este posibil. De exemplu, în oneDiff se utilizează dictWord.at(i) în loc de dictWord[i]. Motivul pentru care acest lucru este dăunător este că at() efectuează o verificare a limitelor (și, eventual, aruncă o excepție dacă limitele sunt încălcate), în timp ce operator[] nu o face. Deoarece i ia întotdeauna doar valori mai mici decât stackWord.size(), , nu aveți nevoie de at().
  3. Preferați std::size_t pentru variabilele de iterație. int poate fi prea mică pentru a conține toți indicii pentru șiruri foarte mari.
  4. Nu utilizați ... < something.somemethod() în capul unei bucle, deoarece something.somemethod() poate fi executat la fiecare iterație. Dacă știți că valoarea sa nu se schimbă pe parcursul buclei, stocați valoarea sa înainte de buclă într-o variabilă.
  5. oneDiff poate fi optimizat. Deoarece returnați doar dacă diferența dintre caractere este sau nu mai mică sau egală cu unu, puteți returna false imediat ce ați găsit mai multe neconcordanțe.
  6. Cu toate că nu ați dat definiția lui dictionary, se poate presupune că este de tip std::list<std::string> din cauza iteratorului pe care îl utilizați. Aș recomanda înlocuirea acestuia cu un std::vector dacă nu efectuați multe inserții și ștergeri în poziții aleatorii, deoarece std::vector beneficiază de coerența cache-ului.