c++ - überhaupt - Sollte ich vermeiden, hier zu gehen? Wenn das so ist, wie?




lohnt sich sparen überhaupt noch 2017 (11)

Darf die Reihenfolge der Elemente in einem Vektor geändert werden? Wenn ja, verwenden Sie einfach einen adjacent_find Algorithmus in einer einzelnen Schleife.

So werden Sie nicht nur goto los, sondern bekommen bessere Leistung (aktuell haben Sie O(N^2) ) und garantierte Korrektheit:

std::sort(hand.begin(), hand.end(), 
    [](const auto &p1, const auto &p2) { return p1.getFace() < p2.getFace(); });
for (auto begin = hand.begin(); begin != hand.end(); )
{
  begin = std::adjacent_find(begin, hand.end(), 
        [](const auto &p1, const auto &p2) { return p1.getFace() == p2.getFace(); });
  if (begin != hand.end())
  {
    auto distance = std::distance(hand.begin(), begin);
    std::erase(begin, begin + 2);  // If more than 2 card may be found, use find to find to find the end of a range
    begin = hand.begin() + distance;
  }
}

Ich schreibe für eine Funktion, die eine Hand nimmt und nach Paaren sucht:

int containsPairs(vector<Card> hand)
{
    int pairs{ 0 };

    loopstart:
    for (int i = 0; i < hand.size(); i++)
    {
        Card c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            Card c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                pairs++;
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                goto loopstart;
            }
        }
    }
    return pairs;
}

Wenn es ein Paar in Zeile 10 findet, möchte ich die Karten in der Hand löschen, in der es das Paar gefunden hat, und dann die gesamte Schleife mit den gelöschten Karten neu starten, um ein zweites Paar zu finden, falls es ein solches gibt. Für mich war goto der intuitivste Weg, dies zu tun, aber in diesem Fall ist das wahr?


Die anderen Antworten beziehen sich bisher auf die grundlegende Umstrukturierung Ihres Codes. Sie weisen darauf hin, dass dein Code anfangs nicht sehr effizient war und bis du das Problem behoben hast, dass du nur aus einer Schleife ausbrechen musst, also brauchst du das goto sowieso nicht.

Aber ich werde die Frage beantworten, wie man goto vermeidet, ohne den Algorithmus grundlegend zu ändern. Die Antwort (wie es oft für die Vermeidung von goto der Fall ist) ist, einen Teil Ihres Codes in eine separate Funktion zu verschieben und eine vorzeitige return :

void containsPairsImpl(vector<Card>& hand, int& pairs)
{
    for (int i = 0; i < hand.size(); i++)
    {
        Card c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            Card c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                pairs++;
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                return;
            }
        }
    }
    hand.clear();
}

int containsPairs(vector<Card> hand)
{
    int pairs{ 0 };
    while (!hand.empty()) {
        containsPairsImpl(hand, pairs);
    }
    return pairs;
}

Beachten Sie, dass ich hand und pairs mit Bezug auf die innere Funktion überlasse, damit sie aktualisiert werden können. Wenn Sie viele dieser lokalen Variablen haben oder die Funktion in mehrere Teile aufteilen müssen, kann dies unhandlich werden. Die Lösung ist dann eine Klasse zu verwenden:

class ContainsPairsTester {
public:
    ContainsPairsTester(): m_hand{}, m_pairs{0} {}

    void computePairs(vector<Card> hand);

    int pairs() const { return m_pairs; }
private:
    vector<Card> m_hand;
    int m_pairs;

    void computePairsImpl(vector<Card> hand);
};

void ContainsPairsTester::computePairsImpl()
{
    for (int i = 0; i < m_hand.size(); i++)
    {
        Card c1 = m_hand[i];
        for (int j = i + 1; j < m_hand.size(); j++)
        {
            Card c2 = m_hand[j];
            if (c1.getFace() == c2.getFace())
            {
                m_pairs++;
                m_hand.erase(m_hand.begin() + i);
                m_hand.erase(m_hand.begin() + (j - 1));
                return;
            }
        }
    }
    m_hand.clear();
}

void ContainsPairsTester::computePairs(vector<Card> hand)
{
    m_hand = hand;
    while (!m_hand.empty()) {
        computePairsImpl();
    }
}

Ich würde diese beiden Schleifen persönlich in ein Lambda setzen, anstatt goto würde von diesem Lambda mit der Angabe zurückkehren, dass die Schleifen neu starten sollten, und würde das Lambda in einer Schleife aufrufen. So ähnlich:

auto iterate = [&hand, &pairs]() {
             {
              ... // your two loops go here, instead of goto return true
             }
             return false;
}

while (iterate());

Kleiner Zusatz : Ich denke nicht, dass dies der beste Algorithmus ist, um Kartenpaare in einem Deck zu finden. Dafür gibt es viel bessere Möglichkeiten. Ich antworte vielmehr auf die allgegenwärtige Frage, wie man die Kontrolle in zwei Schleifen gleichzeitig oder aus diesen heraus übertragen kann.


Ich würde es wahrscheinlich so machen:

Eigenschaften:

  • 3 einer Art ist kein Paar
  • gibt einen Kartenvektor in der Reihenfolge des absteigenden Gesichts zurück und zeigt an, welche Gesichter Paare in der Hand sind.

std::vector<Card> reduceToPair(std::vector<Card> hand)
{
    auto betterFace = [](auto&& cardl, auto&& cardr)
    {
        return cardl.getFace() > cardr.getFace();
    };

    std::sort(begin(hand), end(hand), betterFace);

    auto first = begin(hand);
    while (first != end(hand))
    {
        auto differentFace = [&](auto&& card)
        {
            return card.getFace() != first->getFace();
        };
        auto next = std::find_if(first + 1, end(hand), differentFace);
        auto dist = std::distance(first, next);
        if (dist == 2)
        {
            first = hand.erase(first + 1, next);
        }
        else
        {
            first = hand.erase(first, next);
        }
    }

    return hand;
}

Verwendung:

pairInfo = reduceToPair(myhand);
bool hasPairs = pairInfo.size();
if (hasPairs)
{
  auto highFace = pairInfo[0].getFace();
  if (pairInfo.size() > 1) {
    auto lowFace = pairInfo[1].getFace();
  }
}

Versuche dies:

int containsPairs(vector<int> hand)
{
    int pairs{ 0 };

    for (int i = 0; i < hand.size(); i++)
    {
        int c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            int c2 = hand[j];
            if (c1 == c2)
            {
                pairs++;
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                i--;
                break;
            }
        }
    }
    return pairs;
}

Dies ist fast Ihre Version, der einzige Unterschied ist, dass anstelle von goto, gibt es i--; break; i--; break; . Diese Version ist effizienter als Ihre, da sie nur einmal die Doppelschleife ausführt.

Ist es klarer? Nun, das ist eine persönliche Vorliebe. Ich bin überhaupt nicht gegen goto , ich denke, dass sein aktueller "Nimm es nie" Status sollte überarbeitet werden. Es gibt Situationen, in denen goto die beste Lösung ist.

Hier ist eine andere, noch einfachere Lösung:

int containsPairs(vector<int> hand)
{
    int pairs{ 0 };

    for (int i = 0; i < hand.size(); i++)
    {
        int c1 = hand[i];
        for (int j = i + 1; j < hand.size(); j++)
        {
            int c2 = hand[j];
            if (c1 == c2)
            {
                pairs++;
                hand.erase(hand.begin() + j);
                break;
            }
        }
    }
    return pairs;
}

Wenn es ein Paar findet, entfernt es im Prinzip nur die entferntere Karte und unterbricht die Schleife. Es gibt also keinen Grund, mit i schwierig zu sein.


Während goto ist nicht wirklich so schrecklich, wenn Sie es brauchen, ist es hier nicht notwendig. Da Sie nur auf die Anzahl der Paare achten, ist es auch nicht notwendig, aufzuzeichnen, was diese Paare sind. Sie können einfach die gesamte Liste xor .

Wenn Sie GCC oder Clang verwenden, funktioniert das Folgende. In MSVC können Sie stattdessen __popcnt64() verwenden.

int containsPairs(vector<Card> hand)
{
    size_t counter = 0;
    for ( Card const& card : hand )
        counter ^= 1ul << (unsigned) card.getFace();

    return ( hand.size() - __builtin_popcountll(counter) ) / 2u;
}

Wenn das Sortieren von Karten nach Gesicht möglich ist, können wir Paare mit nur einem einzigen Durchlauf zählen, ohne etwas zu löschen:

bool Compare_ByFace(Card const & left, Card const & right)
{
    return(left.Get_Face() < right.Get_Face());
}

size_t Count_Pairs(vector<Card> hand)
{
    size_t pairs_count{0};
    if(1 < hand.size())
    {
        sort(hand.begin(), hand.end(), &Compare_ByFace);
        auto p_card{hand.begin()};
        auto p_ref_card{p_card};
        for(;;)
        {
           ++p_card;
           if(hand.end() == p_card)
           {          
               pairs_count += static_cast< size_t >((p_card - p_ref_card) / 2);
               break;
           }
           if(p_ref_card->Get_Face() != p_card->Get_Face())
           {
               pairs_count += static_cast< size_t >((p_card - p_ref_card) / 2);
               p_ref_card = p_card;
           }
        }
    }
    return(pairs_count);
}

Wie andere bemerkt haben, sollten Sie nicht nur goto vermeiden, sondern auch vermeiden, Ihren eigenen Code zu schreiben, wo es einen Standardalgorithmus gibt, der diese Aufgabe erfüllen kann. Ich bin überrascht, dass niemand das einzigartige vorgeschlagen hat, das für diesen Zweck entwickelt wurde:

bool cardCmp(const Card& a, const Card& b) {
    return a.getFace() < b.getFace();
}

size_t containsPairs(vector<Card> hand) {
    size_t init_size = hand.size();

    std::sort(hand.begin(), hand.end(), cardCmp);
    auto it = std::unique(hand.begin(), hand.end(), cardCmp);
    hand.erase(it, hand.end());

    size_t final_size = hand.size();
    return init_size - final_size;
}

(Erste Antwort auf - Entschuldigung für jeden Fauxpas!)


goto ist nur ein Problem. Ein weiteres großes Problem ist, dass Ihre Methode ineffizient ist.

Ihre Methode

Ihre aktuelle Methode betrachtet im Grunde die erste Karte, iteriert den Rest und sucht nach dem gleichen Wert. Es geht dann zurück auf die zweite Karte und vergleicht sie mit dem Rest. Das ist O(n**2) .

Sortierung

Wie würdest du Paare im wirklichen Leben zählen? Du würdest die Karten wahrscheinlich nach Wert sortieren und nach Paaren suchen. Wenn Sie effizient sortieren, wäre es O(n*log n) .

Verteilen

Die schnellste Methode wäre, 13 Plätze auf einem Tisch vorzubereiten und die Karten entsprechend ihrem Nennwert zu verteilen. Nachdem Sie jede Karte verteilt haben, können Sie die Karten in jedem Slot zählen und sehen, ob ein Slot mindestens 2 Karten enthält. Es ist O(n) und es würde auch drei von einer Art oder vier einer Art erkennen.

Sicher, es gibt keinen großen Unterschied zwischen n**2 und n wenn n 5 . Als Bonus wäre die letzte Methode prägnant, einfach zu schreiben und goto free.


Ein (etwas) schnellerer Algorithmus vermeidet auch das goto

Das Löschen von einem std::vector ist niemals schnell und sollte vermieden werden. Dasselbe gilt für das Kopieren eines std::vector . Indem Sie beide vermeiden, vermeiden Sie auch das goto . Beispielsweise

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand
{
    size_t num_pairs = 0;
    std::unordered_set<size_t> in_pair;

    for(size_t i=0; i!=hand.size(); ++i)
    {
        if(in_pair.count(i)) continue;
        auto c1 = hand[i];
        for(size_t j=i+1; j!=hand.size(); ++j)
        {
            if(in_pair.count(j)) continue;
            auto c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                ++num_pairs;
                in_pair.insert(i);
                in_pair.insert(j);
            }
        }
    }
    return num_pairs;
}

Für große Hände ist dieser Algorithmus immer noch langsam, da O (N ^ 2). Schneller wäre das Sortieren, nach dem Paare benachbarte Karten sein müssen, die einen O (N logN) -Algorithmus ergeben.

Noch schneller, O (N) , benutzt ein unordered_set nicht für die Karten in Paaren, sondern für alle anderen Karten:

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand
{
    size_t num_pairs = 0;
    std::unordered_set<Card> not_in_pairs;
    for(auto card:hand)
    {
        auto match = not_in_pairs.find(card));
        if(match == not_in_pairs.end())
        {
            not_in_pairs.insert(card);
        }
        else
        {
            ++num_pairs;
            not_in_pairs.erase(match);
        }   
    }
    return num_pairs;
}

Für eine ausreichend kleine hand.size() ist dies möglicherweise nicht schneller als der obige Code, abhängig von der sizeof(Card) und / oder den Kosten des Konstruktors. Ein ähnlicher Ansatz besteht darin, die Verteilung zu verwenden , wie in der Antwort von Eric Duminil vorgeschlagen:

size_t containsPairs(std::vector<Card> const &hand) // no copy of hand
{
    std::unordered_map<Card,size_t> slots;
    for(auto card:hand)
    {
        slots[card]++;
    }
    size_t num_pairs = 0;
    for(auto slot:slots)
    {
        num_pairs += slot.second >> 1;
    }
    return num_pairs;
}

Natürlich können diese Methoden viel einfacher implementiert werden, wenn Card trivialerweise in eine kleine ganze Zahl abgebildet werden kann, wenn kein Hashing benötigt wird.


#include <vector>
#include <unordered_map>
#include <algorithm>

std::size_t containsPairs(const std::vector<int>& hand)
{
    // boilerplate for more readability
    using card_t = std::decay_t<decltype(hand)>::value_type;
    using map_t = std::unordered_map<card_t, std::size_t>;

    // populate map and count the entrys with 2 occurences
    map_t occurrences;
    for (auto&& c : hand) { ++occurrences[c]; }
    return std::count_if( std::cbegin(occurrences), std::cend(occurrences), [](const map_t::value_type& entry){ return entry.second == 2; });
}




goto