0

我正在编写一个自动完成程序，该程序查找给定字典文件和输入文件的字母或字符集的所有可能匹配项。我刚刚完成了一个通过迭代搜索实现二进制搜索的版本，并认为我可以提高程序的整体性能。

问题是，二分搜索几乎比迭代搜索慢 9 倍。是什么赋予了？我以为我通过使用二分搜索而不是迭代来提高性能。

运行时间（向左搜索 bin）[大]： 测试每个版本的时间

这是每个版本的重要部分，完整的代码可以在我的 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 的大小上是线性的：它将整个数组从中间到末尾复制到数组的开头。这使得“二分搜索”算法在 dict 的长度上可能是二次的，具有 O(N^2) 昂贵的内存复制操作。

于 2013-09-26T23:38:43.157 回答