时间戳

首页 > 解决方案 > 当输入有大量数据时，for循环进行了超长时间（20+分钟）迭代

c++ - 当输入有大量数据时，for循环进行了超长时间（20+分钟）迭代

问题描述

我在这里有两个功能：

int getHighestVal(int n, vector<double> arr) {
    int highest = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > arr[highest])
            highest = i;
    }

    return highest;
}

vector<int> getRank(int n, vector<double> arr) {
    vector<int> rank(n);
    vector<bool> used(n);
    for (int i = 0; i < n; i++)
        used[i] = false;
    int lowestVal = getHighestVal(n, arr);
    cout << "Pass waypoint lowestVal" << endl;

    for (int i = 1; i <= n; i++) { //LOOP HERE WENT INFINITE ITERATION
        for (int j = 0; j < n; j++) {
            if (used[j] == false && arr[lowestVal] > arr[j])
                lowestVal = j;
        }

        rank[lowestVal] = i;
        used[lowestVal] = true;
        lowestVal = getHighestVal(n, arr);
        cout << "\rPass waypoint RANKING Loop2: " << n;
    }
    cout << "Pass waypoint RANKING" << endl;

    return rank;
}

我正在使用它来实现我的程序，但是当我尝试输入包含 16200 个双精度数的 a 时，for 循环getRank会表现得很挑剔（花了将近 20 分钟才能完成） 。vector<double>arr

为什么？这对于 16200 双打来说太长了。

注意：使用@bruno 的解决方案，在 Release 模式下运行它可以将时间从 1.5 秒缩短到 0.3 秒。巨大的改进。

标签： c++for-loop

解决方案

假设您希望始终为整个数组创建排名，那么第一个参数n是多余的——您可以从arr.size(). 冗余可能是错误的来源，所以在这种情况下，宁愿删除参数：

std::vector<size_t> getRank(std::vector<double> const& arr);

另外两个变化：

  • 看起来好像排名永远不会变成负数。那么无符号类型是更好的选择。size_t适合容纳任何数量的元素，您可以将其打包到 astd::vector中，因此它是一种很好的类型。只有当这消耗太多内存时，我才会回退到更小的类型......
  • 通过 const 引用接受可避免复制向量。无论如何您都不会修改它，因此无需创建副本。这与您的 -function 尤其相关getHighestVal，它会一次又一次地被调用。

然而，没有必要重新发明轮子，已经有std::max_element同样的事情了……

std::vector<size_t> getRank(std::vector<double> const& arr)
{
    vector<size_t> rank(arr.size());
    vector<bool> used(arr.size(), false);
    // Noticed second argument? It makes the subsequent loop obsolete...
    //for (int i = 0; i < n; i++)
    //    used[i] = false;

    // using std:max_element instead
    auto lowestVal = std::max_element(arr.begin(), arr.end()) - arr.begin();
    // std::max_element returns an iterator, though – for getting an index,
    // we need to calculate the difference to first element

    std::cout << "Pass waypoint lowestVal" << std::endl;

    // now avoid calling std::max_element again and again!
    auto lowestValConst = lowestVal;

    for (size_t i = 1; i <= arr.size(); i++)
    {
        for (size_t j = 0; j < arr.size(); j++)
        {
            if (!used[j] && arr[lowestVal] > arr[j])
                lowestVal = j;
        }

        rank[lowestVal] = i;
        used[lowestVal] = true;

        // avoid re-calculation:
        lowestVal = lowestValConst; //getHighestVal(n, arr);

        std::cout << "\rPass waypoint RANKING Loop2: " << arr.size();
    }
    std::cout << "Pass waypoint RANKING" << std::endl;
}

不过，这仍然是一个 O(n²) 算法。不过，您可以更好地使用 O(n*log(n))：

std::vector<size_t> getRank(std::vector<double> const& arr)
{
    std::vector<std::pair<double, size_t>> values;
    values.reserve(arr.size()); // avoid re-allocations
    size_t index = 0;
    for(auto d : arr)
        values.emplace_back(d, index++);

    // copying the array into a second one with indices paired: O(n)

    std::sort
    (
        values.begin(), values.end(),
        std::greater<std::pair<double, size_t>>
    );
    // std::pair has already a lexicographical operator<, so we can use that one
    // – but because of lexicographical comparison it is important to use the
    // double value as first element; the index as second element then, as a
    // bonus assures stable sorting...
    // still we want to get descending order, so we need to compare with
    // greater instead of default of less

    // sorting has complexity of O(n*log(n))

    // we need to copy the indices into the ranks:
    std::vector<size_t> rank(arr.size());
    index = 0;
    for(auto& v : values)
        //ranks[v.second] = index++;
        // pre-increment: you seem to need 1-based rank...
        ranks[v.second] = ++index;

    // copying back: O(n)
}

现在总计是 O(n) + O(n*log(n) + O(n)，总共是 O(n*log(n))。

请注意，上面是未经测试的代码 - 如果您遇到错误，请自行修复...

推荐阅读