我应该避免在这里使用goto吗？如果是这样,怎么样？

Question

我正在编写一个函数,它需要一只手并检查对:

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

当它在第10行找到对时,我想删除它找到该对的手牌,然后用已删除的卡重新启动整个循环以找到第二对,如果有的话.对我来说,goto是最直观的方式,但在这种情况下,是真的吗？

Answer 1

试试这个:

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

这几乎是你的版本,唯一的区别是,而不是goto,有i--; break;.这个版本比你的更高效,因为它只进行一次双循环.

它更清楚了吗？嗯,这是个人偏好.我根本不反对goto,我认为应该修改其目前的"永不使用"状态.有时候goto最好的解决方案.

这是另一个,甚至更简单的解决方案:

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

基本上,当它找到一对时,它只会移除更远的卡,并打破循环.所以没有必要狡猾i.

Answer 2

(稍微)更快的算法也避免了 goto

从a中删除std::vector永远不会很快,应该避免.同样适用于复制a std::vector.通过避免两者,你也避免了goto.例如

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

对于大手,这个算法仍然很慢,因为O(N ^ 2).更快的是排序,之后对必须是相邻的卡,给出O(N logN)算法.

然而,更快,O(N),是unordered_set成对使用非卡,但对于所有其他卡:

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

对于足够小hand.size(),这可能不比上面的代码快,这取决于sizeof(Card)其构造函数和/或成本.类似的方法是使用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;
}

当然,如果Card不需要散列,可以简单地映射到一个小整数,这些方法可以更简单地实现.

Answer 3

为了好玩,这里还有两种方法,我提出了一种稍微更有效的方法,没有休息或转到.然后我提出一种效率较低的方法,首先进行排序.

这两种方法都易于阅读和理解.

这些只是为了显示其他答案的替代方案.我要求的第一个containsPairs方法要求卡值在0到13的范围内,如果不是这样,它将会中断,但是比我见过的任何其他答案的效率都要高一些.

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

注意:其他几个答案会将3对类似的卡片视为2对.上面的两种方法考虑到了这一点,而只计算了3对的3对.如果有4张类似的牌,他们会把它当作2对.

Answer 4

goto只是一个问题.另一个大问题是你的方法效率低下.

你的方法

您当前的方法基本上查看第一张卡,迭代其余卡并查找相同的值.然后它返回第二张卡并将其与其余卡进行比较.这是O(n**2).

排序

你怎么算现实生活中的对子？您可能会按价值对卡片进行排序并寻找配对.如果你有效排序,那就是O(n*log n).

分发

最快的方法是在桌子上准备13个插槽,并根据他们的面值分配卡片.分发每张卡后,您可以统计每个插槽上的卡,看看是否有任何插槽至少有2张卡.它O(n)也可以检测到三种或四种.

当然,n n**2和nn 之间没有太大区别5.作为奖励,最后一种方法将是简洁,易于编写和goto免费的.