时间戳

首页 > 解决方案 > 优化方法

c++ - 优化方法

问题描述

我想优化以下方法：

int getRowWithMinConflicts(int cols)
{
    int minConflicts = MAX;
    int rowWithMinCOnflicts[MAX];
 

    for (int rows = 0; rows < N; rows++)
    {
        rowWithMinCOnflicts[rows] = getConfilictsCount(rows, cols);

        int tempMin = rowWithMinCOnflicts[rows];
        if (tempMin < minConflicts)
        {

             minConflicts = tempMin;
        }
    }


    vector<int> currentRow;


    for (int rows = 0; rows < N; rows++)
    {
        if (rowWithMinCOnflicts[rows] == minConflicts)
        {
            currentRow.push_back(rows);
        }
    }

    return currentRow[rand() % currentRow.size()];
}

首先，我正在对 N 运行一个循环以保存数组 rowWithMinCOnflicts 值并跟踪最小值

我再次运行循环到 N 以在数组 rowWithMinCONflicts 中检查哪些条目的值 =“minConflicts”，然后我将它们添加到向量中，因为我只需要它们最后的大小。如何同时优化两个循环？

标签： c++optimization

解决方案

要仅使用一个循环而不是 2 个，您可能会这样做（但我认为它不会更快）：

int getRowWithMinConflicts(int cols)
{
    int minConflicts = MAX;
    std::vector<int> candidateRows;
 
    for (int rows = 0; rows < N; rows++)
    {
        int tempMin = getConfilictsCount(rows, cols);

        if (tempMin < minConflicts) {
             candidateRows.clear();
             candidateRows.push_back(row);
             minConflicts = tempMin;
        } else if (tempMin == minConflicts) {
             candidateRows.push_back(row);
        }
    }
    return currentRow[rand() % currentRow.size()];
}

还有一个没有额外内存的版本（但有额外的rand调用）：

int getRowWithMinConflicts(int cols)
{
    int minConflicts = MAX;
    int bestRow = -1;
    std::size_t minCount = 0;

    for (int rows = 0; rows < N; rows++)
    {
        int tempMin = getConfilictsCount(rows, cols);

        if (tempMin < minConflicts) {
             bestRow = row;
             minCount = 1;
             minConflicts = tempMin;
        } else if (tempMin == minConflicts) {
             ++minCount;
             if (rand() % minCount == 0) {
                 bestRow = row;
             }
        }
    }
    return bestRow;
}

推荐阅读