switch - loop c++ example program

¿Debería evitar usar goto aquí? ¿Si es así, cómo?

Question

Estoy codificando una función que toma una mano y busca pares:

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;
}

Cuando encuentre el par en la línea 10, quiero eliminar las cartas en la mano con la que encontró el par y luego reiniciar todo el ciclo con las tarjetas eliminadas para encontrar un segundo par, si es que hay uno. Para mí, goto fue la forma más intuitiva de hacerlo, pero en este caso, ¿es cierto?

Answer 1

¿Se te permite cambiar el orden de los elementos en un vector? Si es así, simplemente use un algoritmo de búsqueda adjacent_find en un solo bucle.

Por lo tanto, no solo eliminará goto , sino que obtendrá un mejor rendimiento (actualmente tiene O(N^2) ) y una corrección garantizada:

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;
  }
}

Answer 2

Como han comentado otros, no solo debe evitar ir, sino también evitar escribir su propio código donde hay un algoritmo estándar que puede hacer el trabajo. Me sorprende que nadie haya sugerido que sea único, que está diseñado para este propósito:

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;
}

(Primera respuesta en - ¡disculpas por cualquier paso de falsa!)

Answer 3

Las otras respuestas hasta ahora abordan cómo reestructurar fundamentalmente su código. Señalan que su código no era muy eficiente para empezar, y para el momento en que lo arregló solo necesita salir de un bucle, por lo que no necesita el goto todos modos.

Pero voy a responder la pregunta de cómo evitar goto sin cambiar fundamentalmente el algoritmo. La respuesta (como suele ser el caso para evitar goto ) es mover parte de su código a una función separada y usar un return anticipado:

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;
}

Tenga en cuenta que paso hand y pairs por referencia a la función interna para que puedan actualizarse. Si tiene muchas de estas variables locales, o tiene que dividir la función en varias partes, esto puede volverse difícil de manejar. La solución entonces es usar una clase:

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();
    }
}

Answer 4

Para divertirse aquí hay dos formas más, presento un método un poco más eficiente sin interrupciones o goto. Luego presento un método menos eficiente que se ordena primero.

Ambos métodos son simples de leer y entender.

Estos solo tienen la intención de mostrar alternativas a las otras respuestas. El primer método containsPairs que tengo requiere que los valores de las tarjetas estén en el rango de 0 a 13 y se romperán si eso no es cierto, pero es un poco más eficiente que cualquiera de las otras respuestas que he visto.

int containsPairs(const vector<int> &hand)
{
    int pairs{ 0 };
    std::vector<int> counts(14); //note requires 13 possible card values
    for (auto card : hand){
        if(++counts[card] == 2){
            ++pairs;
            counts[card] = 0;
        }
    }
    return pairs;
}

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

    std::sort(hand.begin(), hand.end());
    for (size_t i = 1;i < hand.size();++i){
        if(hand[i] == hand[i - 1]){
            ++i;
            ++pairs;
        }
    }
    return pairs;
}

Nota: varias de las otras respuestas tratarán 3 cartas similares en una mano como 2 pares. Los dos métodos anteriores tienen esto en cuenta y en su lugar solo contarán 1 par por 3 de un tipo. Lo tratarán como 2 pares si hay 4 cartas similares.

Answer 5

Personalmente pondría esos dos bucles en una lambda, en lugar de goto volvería de esta lambda con indicación de que los bucles deberían reiniciarse, y llamaría a la lambda en un bucle. Algo como eso:

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

while (iterate());

Pequeña adición : no creo que este sea el mejor algoritmo para encontrar pares de cartas en un mazo. Hay opciones mucho mejores para eso. Prefiero responder la pregunta omnipresente de cómo transferir el control dentro o fuera de dos bucles a la vez.

Answer 6

Probablemente lo haría de esta manera:

caracteristicas:

• 3 de una clase no es un par
• devuelve un vector de cartas en orden de cara descendente que indica qué caras son pares en la mano.

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;
}

uso:

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

Answer 7

Prueba esto:

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;
}

Esta es casi su versión, la única diferencia es que en lugar de goto, hay i--; break; i--; break; . Esta versión es más eficiente que la tuya, ya que solo hace doble bucle una vez.

¿Está más claro? Bueno, esa es una preferencia personal. No estoy en contra de goto , creo que su estado actual de "nunca lo use" debería ser revisado. Hay ocasiones en que goto es la mejor solución.

Aquí hay otra, incluso una solución más simple:

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;
}

Básicamente, cuando encuentra un par, solo elimina la carta más lejana y rompe el ciclo. Entonces no hay necesidad de ser tramposo con i .

Answer 8

Si bien goto no es tan horrible si lo necesitas, no es necesario aquí. Como solo te importa el número de pares, tampoco es necesario registrar qué son esos pares. Puede simplemente recorrer toda la lista.

Si está utilizando GCC o clang, lo siguiente funcionará. En MSVC, puede usar __popcnt64() lugar.

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;
}

Answer 9

Si la clasificación de las cartas por persona es posible y está permitida, podemos contar pares usando solo una pasada sin borrar nada:

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);
}

Answer 10

Si realmente quiere evitar goto, puede llamar a la función recursivamente, donde estaría la línea goto [label], pasando cualquier variable cuyo estado desee guardar como parámetros. Sin embargo, recomendaría seguir con el goto.

Answer 11

Su implementación no está funcionando ya que cuenta tres de una clase como un par, cuatro de una clase como dos.

Aquí hay una implementación que sugeriría:

int containsPairs(std::vector<Card> hand)
{
    std::array<int, 14> face_count = {0};
    for (const auto& card : hand) {
        ++face_count[card.getFace()]; // the Face type must be implicitly convertible to an integral. You might need to provide this conversion or use an std::map instead of std::array.
    }
    return std::count(begin(face_count), end(face_count), 2);
}

( demo en coliru )

Se puede generalizar para contar no solo pares sino también n de un tipo ajustando el 2 .

Answer 12

Un problema con goto es que las etiquetas tienden a funcionar como walkies en refactorizaciones erróneas. Eso es fundamentalmente por lo que no me gustan. Personalmente, en su caso, si necesita mantener el algoritmo tal como está, goto el goto en una llamada recursiva:

int containsPairs(vector<Card>&/*Deliberate change to pass by reference*/hand)
{
    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())
            {
                hand.erase(hand.begin() + i);
                hand.erase(hand.begin() + (j - 1));
                return 1 + containsPairs(hand); 
            }
        }
    }
    return 0;
}

La sobrecarga en la creación del marco de pila es despreciable, cf. las manipulaciones std::vector . Esto puede ser poco práctico según el sitio de llamadas: ya no puede llamar a la función con un temporal anónimo, por ejemplo. Pero realmente hay mejores alternativas para la identificación de pares: ¿por qué no pedir la mano de manera más óptima?

Answer 13

goto es solo un problema. Otro gran problema es que su método es ineficiente.

Tu método

Su método actual básicamente mira la primera carta, itera sobre el resto y busca el mismo valor. Luego vuelve a la segunda carta y la compara con el resto. Esto es O(n**2) .

Clasificación

¿Cómo contarías los pares en la vida real? Probablemente clasifique las cartas por valor y busque pares. Si ordena de manera eficiente, sería O(n*log n) .

Distribuido

El método más rápido sería preparar 13 ranuras en una mesa y distribuir las tarjetas de acuerdo con su valor nominal. Después de distribuir cada carta, puedes contar las cartas en cada casilla y ver si alguna ranura contiene al menos 2 cartas. Es O(n) y también detectaría tres de una clase o cuatro de una clase.

Claro, no hay mucha diferencia entre n**2 y n cuando n es 5 . Como beneficio adicional, el último método sería conciso, fácil de escribir y libre de goto .

Answer 14

Sí, debes evitar usar goto aquí.

Es un uso innecesario de goto específicamente porque el algoritmo no lo necesita. Por otro lado, tiendo a no utilizar goto , pero no me opongo firmemente como a muchos. goto es una gran herramienta para romper bucles anidados o para salir de una función limpiamente cuando una interfaz no es compatible con RAII.

Hay algunas ineficiencias con su enfoque actual:

• No hay ninguna razón para volver a buscar en la lista desde el principio cuando encuentre un par coincidente. Ya ha buscado todas las combinaciones anteriores. La eliminación de tarjetas no cambia el orden relativo de las tarjetas no eliminadas y, además, no le proporciona más pares.
• No es necesario quitar elementos del centro de la hand . Para este problema, eliminar desde el medio de un std::vector presumiblemente representa una mano de 5 cartas no es un problema. Sin embargo, si el número de cartas es grande, esto puede ser ineficiente. En problemas como este, debería preguntarse, ¿importa el orden de los elementos? La respuesta es no, no importa. Podemos mezclar cualquier carta que no haya sido emparejada y aún así obtener la misma respuesta.

Aquí hay una versión modificada de tu código:

int countPairs(std::vector<Card> hand)
{
    int pairs{ 0 };

    for (decltype(hand.size()) i = 0; i < hand.size(); ++i)
    {
        // I assume getFace() has no side-effects and is a const
        // method of Card.  If getFace() does have side-effects
        // then this whole answer is flawed.
        const Card& c1 = hand[i];
        for (auto j = i + 1; j < hand.size(); ++j)
        {
            const Card& c2 = hand[j];
            if (c1.getFace() == c2.getFace())
            {
                // We found a matching card for card i however we
                // do not need to remove card i since we are
                // searching forward.  Swap the matching card
                // (card j) with the last card and pop it from the
                // back.  Even if card j is the last card, this
                // approach works fine.  Finally, break so we can
                // move on to the next card.
                pairs++;
                std::swap(c2, hand.back());
                hand.pop_back(); // Alternatively decrement a size variable
                break;
            }
        }
    }
    return pairs;
}

Puede retocar el enfoque anterior para usar iteradores si lo desea. También puede utilizar un std::vector referencia constante y usar std::reference_wrapper para volver a ordenar el contenedor.

Para un mejor algoritmo general construya una tabla de frecuencias de cada valor nominal y su conteo correspondiente.

Answer 15

Un algoritmo (ligeramente) más rápido también evita el goto

Borrar de un std::vector nunca es rápido y debe evitarse. Lo mismo vale para copiar un std::vector . Al evitar ambos, también evitas el goto . Por ejemplo

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;
}

Para manos grandes, este algoritmo aún es lento, ya que O (N ^ 2). Más rápido sería ordenar, después de lo cual los pares deben ser tarjetas adyacentes, dando un algoritmo O (N logN).

Sin embargo , más rápido, O (N) , es usar un conjunto no unordered_set no para las cartas en pares, sino para todas las demás cartas:

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;
}

Para hand.size() suficientemente pequeño, esto puede no ser más rápido que el código anterior, dependiendo del sizeof(Card) y / o el costo de su constructor. Un enfoque similar es usar la distribución como se sugiere en la respuesta de Eric Duminil :

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;
}

Por supuesto, estos métodos se pueden implementar mucho más simplemente si la Card se puede mapear trivialmente en un entero pequeño, cuando no se requiere hash.

Answer 16

#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; });
}