c++ - 提高 std::sort 性能

Question

我有一个包含大约 10k 个项目的索引，必须按字典顺序对不区分大小写的项目进行排序。

这是我的方法:

bool lowercomp (AbstractServiceProvider::AbstractItem*  i, AbstractServiceProvider::AbstractItem* j)

{
    std::string a,b;

    // lower first string
    a.resize(i->title().length());
    std::transform(i->title().cbegin(), i->title().cend(), a.begin(),
                std::bind2nd(std::ptr_fun(&std::tolower<char>), std::locale("")));

    // lower 2nd string
    b.resize(j->title().length());
    std::transform(j->title().cbegin(), j->title().cend(), b.begin(),
                std::bind2nd(std::ptr_fun(&std::tolower<char>), std::locale("")));

    return 0 > a.compare(b);
}

在我的代码中某处:

t = new boost::timer::auto_cpu_timer;
std::sort(_index.begin(), _index.end(), lowercomp);
delete t;

但这大约需要 4 秒。没有 toLower 部分，大约需要 0.003 秒。有没有办法改善这一点？

Answer 1

直到您看到探查器输出，才能知道 减速是，你不能确定，但​​有很多点 这似乎可能会导致我减速。两个最 重要的是:

• 您的函数在每次调用时创建两个新字符串。这样可以 非常昂贵，并且

• 您使用 std::tolower 的两个操作数形式;这个功能 必须提取 ctype每次它被调用时(你 每次您构建一个新的语言环境临时实例 调用 lowercomp .

我自己的偏好是使用功能对象 比较。对于一些编译器，它更快，但在这种情况下， 它也更干净:

class CaseInsensitiveCompare
{
    std::locale myLocale;   //  To ensure lifetime of the facet.
    std::ctype<char> const& myCType;
public:
    CaseInsensitiveCompare( std::locale const& locale = std::locale( "" ) )
        : myLocale( locale )
        , myCType( std::use_facet<std::ctype<char>>( myLocal ) )
    {
    }
    bool operator()( AbstractItem const* lhs, AbstractItem const* rhs ) const
    {
        return (*this)( lhs->title(), rhs->title() );
    }
    bool operator()( std::string const& lhs, std::string const& rhs ) const
    {
        return std::lexicographical_compare(
            lhs.begin(), lhs.end(),
            rhs.begin(), rhs.end(),
            *this);
    }
    bool operator()( char lhs, char rhs ) const
    {
        return myCType.tolower(lhs) < myCType.tolower(rhs);
    }
};

除此之外，还有其他几点可以改进 性能:

• 如果您确定 locale 的生命周期你正在使用 (你通常可以)，删除 myLocale中的成员 类(class);复制语言环境将是最昂贵的部分 复制此类的实例(以及调用 lexicographical_compare将至少复制一次)。

• 如果您不需要本地化功能，请考虑使用 tolower在 <cctype> 中发挥作用，而不是在 <locale> .这将完全避免任何数据成员的需要 在比较中。

• 最后，虽然我不确定它是否值得 小到 10K 项，您可以考虑使用 字符串的规范形式(已经小写等)， 仅使用 < 对那些进行排序在琴弦上，然后重新排序 原始 vector 。

此外，我非常怀疑`new boost::timer::auto_cpu_timer'。你真的需要动态吗 在这里分配？副手，我怀疑局部变量是 更合适。