0

大文字と小文字を区別せずに辞書式に並べ替える必要がある約 10,000 個のアイテムを含むインデックスがあります。

これが私のアプローチです：

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 秒かかります。これを改善する方法はありますか？

4

3 に答える 3

4

あなたは間違いなくそれをはるかに速くすることができます。解決策は、メモリの割り当てを回避することです。代わりに、比較中に tolower() を使用して一度に 1 文字ずつ変換することにより、大文字と小文字を区別せずに文字列を比較します。比較関数でクラス オブジェクトを作成しないでください。このようなもの：

bool lowercomp(const AbstractItem* lhs, const AbstractItem* rhs)  
{
    size_t size = std::min(lhs->title().size(), rhs->title().size());
    for (size_t pos = 0; pos < size; ++pos) {
        if (tolower(lhs->title()[pos]) < tolower(rhs->title()[pos]) {
            return true;
        } else if (tolower(lhs->title()[pos]) > tolower(rhs->title()[pos]) {
            return false;
        }
    }
    return lhs->title().size() < rhs->title().size();
}

それがどれほど速いか教えてください。:)

于 2014-09-08T12:33:11.213 に答える
4

プロファイラーの出力を見るまでは、速度低下がどこにあるのかはわかりませんが、速度低下の原因と思われるポイントがいくつかあります。最も重要なのは次の 2 つです。

  • 関数は、呼び出しごとに 2 つの新しい文字列を作成します。それは非常に高価になる可能性があり、

  • の 2 つのオペランド形式を使用します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ロケールのコピーは、このクラスのインスタンスのコピーで最もコストがかかる部分です (そして、への呼び出しは lexicographical_compare、少なくとも 1 回コピーします)。

  • ローカリゼーション機能が必要ない場合は、 ではなく のtolower関数を使用することを検討してください。これにより、比較でデータ メンバーがまったく必要なくなります。<cctype><locale>

  • 最後に、10,000 アイテムほどの小さなものに価値があるかどうかはわかりませんが、文字列の標準的な形式 (既に小文字になっているなど) を使用してベクトルを作成し<、文字列だけを使用してそれらを並べ替えてから、それに応じて元のベクトルを並べ替えます。

また、私は「新しいboost::timer::auto_cpu_timer」にも非常に懐疑的です。ここで動的割り当てが本当に必要ですか? 一方で、ローカル変数の方が適切だと思います。

于 2014-09-08T13:10:37.923 に答える
0

あなたの実装は非常に非効率的だと思います。いくつかの問題があります。

ソートコンパレータ内tolowerの両方の文字列に対して a を実行しています。このコンパレーターは順番に呼び出されるため、それぞれ約 40K 回 (?) 2 つの文字列になります。n log ntolowering

文字列をまったく比較したくありません。文字列比較は、他の方法 (整数比較など) よりも桁違いに効率が悪いだけでなく、エラーが発生しやすく、データをスクラブする必要があります。これは、非効率のもう 1 つの原因です。

ただし、文字列を比較する必要がある場合は、ソートを実行する前にスクラブしてください。それにはtolowerそれらが含まれます。理想的には、要素の構築時にデータをスクラブします。それがなければ、 を呼び出す直前にスクラブすることもできますsort。何をするにしても、コンパレーター内でスクラブしないでください。

于 2014-09-08T12:42:19.623 に答える