0

辞書ファイルと入力ファイルを指定して、文字または文字セットに一致する可能性のあるすべてを検索するオートコンプリート プログラムを作成しています。反復検索よりも二分検索を実装するバージョンを完成させたばかりで、プログラムの全体的なパフォーマンスを向上できると考えました。

つまり、バイナリ検索は反復検索よりもほぼ9 倍遅くなります。何を与える？反復で二分探索を使用することで、パフォーマンスを改善していると思いました。

実行時間(左側のビン検索) [大きい] : 各バージョンの時間をテストする

ここに各バージョンの重要な部分があります。完全なコードは、私の githubで cmakeを使用してビルドおよび実行できます。

二分探索関数(与えられた入力をループしながら呼び出される)

bool search(std::vector<std::string>& dict, std::string in,
        std::queue<std::string>& out)
{
    //tick makes sure the loop found at least one thing. if not then break the function
    bool tick = false;  
    bool running = true;
    while(running) {
        //for each element in the input vector
        //find all possible word matches and push onto the queue
        int first=0, last= dict.size() -1;
        while(first <= last)
        {
            tick = false;
            int middle = (first+last)/2;
            std::string sub = (dict.at(middle)).substr(0,in.length());
            int comp = in.compare(sub);
            //if comp returns 0(found word matching case)
            if(comp == 0) {
                tick = true;
                out.push(dict.at(middle));
                dict.erase(dict.begin() + middle);      
            }
            //if not, take top half
            else if (comp > 0)
                first = middle + 1;
            //else go with the lower half
            else
                last = middle - 1;
        }
        if(tick==false)
            running = false;
    }
    return true;
}

反復検索 (メイン ループに含まれる):

for(int k = 0; k < input.size(); ++k) {
        int len = (input.at(k)).length();
        // truth false variable to end out while loop
        bool found = false;
        // create an iterator pointing to the first element of the dictionary
        vecIter i = dictionary.begin();
        // this while loop is not complete, a condition needs to be made
        while(!found && i != dictionary.end()) {
            // take a substring the dictionary word(the length is dependent on
            // the input value) and compare
            if( (*i).substr(0,len) == input.at(k) ) {
                // so a word is found! push onto the queue
                matchingCase.push(*i);
            }
            // move iterator to next element of data
            ++i;    
        }

    }

入力ファイルの例:

z
be
int
nor
tes
terr
on
4

3 に答える 3

4

ベクターの途中の要素を消去して (これは非常にコストがかかります)、検索をやり直す代わりに、見つかった項目の前後の要素を比較するだけです (それらはすべて互いに隣接している必要があるため)。マッチするアイテム。

またはstd::equal_range、まさにそれを行う を使用します。

于 2013-09-26T23:33:22.107 に答える
2

これが犯人になります：

dict.erase(dict.begin() + middle);

バイナリ検索を単純に使用してすべての有効なプレフィックスを見つけるために、辞書からアイテムを繰り返し削除しています。これは非常に複雑であり、不要です。

代わりに、一致が見つかったら、最初の一致が見つかるまで後退し、次に前進して、すべての一致をキューに追加します。辞書はソートされており、プレフィックスのみを使用しているため、有効な一致がすべて連続して表示されることに注意してください。

于 2013-09-26T23:33:35.577 に答える
1

dict.erase 操作は dict のサイズに比例します: 配列全体を中央から最後まで配列の先頭にコピーします。これにより、O(N^2) の高価なメモリ コピー操作を使用して、「二分探索」アルゴリズムを dict の長さで 2 次にすることができます。

于 2013-09-26T23:38:43.157 に答える