c++ - 此 std::vector 分区性能低下

Question

我已经实现了一个有效的 partition 函数，它的行为类似于 Clojure 中同名的有用工具。但是，我的速度很慢。虽然 Clojure 函数可以在几毫秒内完全划分一百万个元素，但我的函数即使有 50K 个元素也需要几秒钟。 (注意:我没有将我的调用与评论中提到的 Clojure 中可用的惰性函数调用进行比较；我说的是惰性不适用的完整实现)。

它和它的助手是:

template <typename T>
std::vector<T> take(int size, const std::vector<T>& coll){
    if (size<0) return std::vector<T>();
    auto sized = size > coll.size() ? coll.size() : size;
    typename std::vector<T>::const_iterator first = coll.begin();
    typename std::vector<T>::const_iterator last = first + sized;
    return std::vector<T>(first,last);
}

template <typename T>
std::vector<T> drop(int size, const std::vector<T>& coll){
    if (size<0) return std::vector<T>();
    auto sized = size > coll.size() ? coll.size() : size;
    typename std::vector<T>::const_iterator first = coll.begin()+sized;
    typename std::vector<T>::const_iterator last = coll.end();
    return std::vector<T>(first,last);
}

template <typename T>
std::vector<std::vector<T>> partition(int size, int step, const std::vector<T>& coll, bool showPartialEnd=false){
    std::vector<std::vector<T>> ret;
    ret.reserve(coll.size());
    if (size<1||step<1) return ret;
    std::vector<T> temp;
    std::vector<T> remain=coll;
    auto building=true;
        do {
            temp=std::move(take(size, remain));
            building=(showPartialEnd?(temp.size()>0):(temp.size()==size));
            if (building==true){
                ret.push_back(temp);
                remain=std::move(drop(step, remain));
            }
        } while (building==true);
    return ret;
}

我希望得到一些关于我可以在哪里优化它以使其运行得更快的指示。我尝试保留大小，这样 push_back 就不必每次都分配，但这没有什么区别(实际上我已经为大多数用例过度分配了大小)。我还认为也许 showPartialEnd? 条件可能是一个障碍，因为它实际上并不需要在每个循环中都发生，但是分成两个循环，仅通过一次条件迭代来选择循环就没有了区别。

这是一个使用示例:

void examples(){
    auto x=range(30);
    auto y=partition(3, 2, x);
    std::for_each(y.begin(), y.end(), printVector<int>);
}

输出:

0 1 2 
2 3 4 
4 5 6 
6 7 8 
8 9 10 
10 11 12 
12 13 14 
14 15 16 
16 17 18 
18 19 20 
20 21 22 
22 23 24 
24 25 26 
26 27 28 

Answer 1

性能问题的原因是你的 drop 函数把算法变成了 O(n^2) 而不是线性时间，因为它必须不断地做一个新的 remain 容器，其中包含尚未分区的所有元素。

我仍在努力理解代码的用途，以便我可以就如何修复/改进您的版本提供建议。

完全未经测试(现在时间紧)，但我认为这应该很接近:

std::vector<std::vector<T>> partition(int size, int step, const std::vector<T>& coll, bool showPartialEnd=false)
{
    std::vector<std::vector<T>> ret;

    if (size<1||step<1) return ret;

    ret.reserve(coll.size() / step + 1);

    std::vector<T>::const_iterator iter = coll.begin();
    for(; ; iter += step)
    {
        // If you have enough elements left for an entire chunk, push it.
        if((coll.end() - iter) >= size)
        {
            ret.push_back(std::vector<T>(iter, iter + size));
        }
        else if(showPartialEnd)
        {
            ret.push_back(std::vector<T>(iter, coll.end()));
            break;   // Remove if you want *all* partial ends instead of just the first one.
        }
        else break;
    }

    return ret;
}