优化处理字形的算法

-1

我正在研究一个项目，并且在某个时间点，我需要接受字母，然后搜索槽中的单词词典，并输出词典中所有单词，我接受的字母可以找到。优化处理字形的算法

例如，如果我接受字母odg 程序会从词典中找到单词dog and god。我面临的问题是，如果我接受更多的信件，程序将永远输出。我有点理解为什么，因为anagrams基本上是给定字母的因式分解，并且这种增长非常快。我想知道是否可以修改我已经编写的用于更快地编写该程序的代码。

我打算在这里发布3个函数，这是可怕的减速发生的地方。请注意，我的字典存储在二叉搜索树中。

//lookup accepts the letters, which will be rearrange and searched in the BST 
//it accepts function pointer callback, but do not worry about it, its just the //way to output the words that I found. 
    void DictionaryImpl::lookup(string letters, void callback(string)) const 
    { 
     if (callback == nullptr) 
      return; 

     removeNonLetters(letters); 
     if (letters.empty()) 
      return; 

     string permutation = letters; 


     string tempString; 

     do 
     { 
      tempString=findValue(root, permutation); 

      if(tempString !="!!!ValueNotFound!!!") 
       callback(tempString); 

      generateNextPermutation(permutation); 
     } while (permutation != letters); 

    } 


//findValue accepts pointer to the root of the tree 
//and it accepts the string that it is searching 
    string DictionaryImpl::findValue(Node* p, string searchValue) const 
    { 
       if(p !=nullptr) 
     { 
      if(p ->data == searchValue) 
       return searchValue; 
      else if(p->data > searchValue) 
       return findValue(p->left,searchValue); 
      else if(p->data < searchValue) 
       return findValue(p->right,searchValue); 
     } 
     return "!!!ValueNotFound!!!"; 
    } 

    //accepts a string that it is going to rearrange 
    void generateNextPermutation(string& permutation) 
    { 
     string::iterator last = permutation.end() - 1; 
     string::iterator p; 

     for (p = last; p != permutation.begin() && *p <= *(p-1); p--) 
      ; 
     if (p != permutation.begin()) 
     { 
      string::iterator q; 
      for (q = p+1; q <= last && *q > *(p-1); q++) 
       ; 
      swap(*(p-1), *(q-1)); 
     } 
     for (; p < last; p++, last--) 
      swap(*p, *last); 
    }

谢谢。

来源

2015-05-30 user1335175

提高代码性能的最佳方法是使用性能分析工具查找瓶颈.. –

当然，处理这个问题的最佳方法是......搜索... ... http://stackoverflow.com/search?q=anagram+algorithm –

C++标准库已经具有您正在实现的结构（例如set或使用lower_bound和vector）和算法（next_permutation）使用这些可能比编写自己的解决方案更有效。

但正如你所说，阶乘增长非常快：你需要的是一个新的算法。这里有一个标准的技巧：两个字符串是彼此的字典，当且仅当它们在排序后相同。例如，排序dog和god都给出dgo。

通过使用排序的版本，您完全避免了遍历排列的需要。（在执行沿这些线的方法，知道大约multimap可以帮助）

（另一种方法是用multiset的人物的工作;再次，多重集{d，邻，克}和{克，邻，d}比较相等，但排序后的字符串效率更高）

来源

2015-05-30 09:27:14 Hurkyl

哦，男人，那个排序词的想法将是平等的很好，这正是我所需要的，非常感谢。 – user1335175

还有一件事，我应该在这里使用哪种排序算法？ – user1335175

内置的一个... –

优化处理字形的算法

回答

相关问题