php-优化Trie实现

大佬教程收集整理的这篇文章主要介绍了php-优化Trie实现，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

除了乐趣之外,我今天没有实现Trie.目前它支持add()和search(),remove()也应实现,但我认为这很简单.

它具有完整的功能,但是按照我的喜好,用数据填充Trie会花费太多.我使用此列表作为数据源：http://www.isc.ro/lists/twl06.zip(在SO上的其他地方找到).加载大约需要11秒.我最初的实现花费了大约15秒,所以我已经给它带来了不错的性能提升,但是我仍然不满意:)

我的问题是：还有什么可以使我获得(实质性的)性能提升？我不受此设计的束缚,可以接受全面的大修.

class Trie
{
    private $trie;
    public function __construct(TrieNode $trie = null)
    {
        if($trie !== null) $this->trie = $trie;
        else $this->trie = new TrieNode();
        $this->counter = 0;
    }
    public function add($value, $val = null)
    {
        $str = '';
        $trie_ref = $this->trie;
        foreach(str_split($value) as $char)
        {
            $str .= $char;
            $trie_ref = $trie_ref->addNode($str);
        }
        $trie_ref->value = $val;
        return true;
    }
    public function search($value, $only_words = falsE)
    {
        if($value === '') return $this->trie;
        $trie_ref = $this->trie;
        $str = '';
        foreach(str_split($value) as $char)
        {
            $str .= $char;
            if($trie_ref = $trie_ref->getNode($str))
            {
                if($str === $value) return ($only_words ? $this->extractWords($trie_ref) : new self($trie_ref));
                conTinue;
            }
            return false;
        }
        return false;
    }
    public function extractWords(TrieNode $triE)
    {
        $res = array();
        foreach($trie->getChildren() as $child)
        {
            if($child->value !== null) $res[] = $child->value;
            if($child->hasChildren()) $res = array_merge($res, $this->extractWords($child));
        }
        return $res;
    }
}
class TrieNode
{
    public $value;
    protected $children = array();
    public function addNode($indeX)
    {
        if(isset($this->children[$index])) return $this->children[$index];
        return $this->children[$index] = new self();
    }
    public function getNode($indeX)
    {
        return (isset($this->children[$index]) ? $this->children[$index] : falsE);
    }
    public function getChildren()
    {
        return $this->children;
    }
    public function hasChildren()
    {
        return count($this->children)>0;
    }
}

解决方法:

不知道PHP,但是,

通过以下方法：

   public function add($value, $val = null) 
    { 
        $str = ''; 
        $trie_ref = $this->trie; 
        foreach(str_split($value) as $char) 
        { 
            $str .= $char; 
            $trie_ref = $trie_ref->addNode($str); 
        } 
        $trie_ref->value = $val; 
        return true; 
    } 
    public function search($value, $only_words = falsE) 
    { 
        if($value === '') return $this->trie; 
        $trie_ref = $this->trie; 
        $str = ''; 
        foreach(str_split($value) as $char) 
        { 
            $str .= $char; 
            if($trie_ref = $trie_ref->getNode($str)) 
            { 
                if($str === $value) return ($only_words ? $this->extractWords($trie_ref) : new self($trie_ref)); 
                conTinue; 
            } 
            return false; 
        } 
        return false; 
    } 

为什么甚至需要$str.= $char(我想是追加)？这本身会将您的O(n)时间加法/搜索更改为Omega(n ^ 2)(n是$value的长度),而不是O(n).

在特里树中,通常会在遍历字符串时遍历树头,即根据当前字符而不是当前前缀找到下一个节点.

大佬总结

以上是大佬教程为你收集整理的php-优化Trie实现全部内容，希望文章能够帮你解决php-优化Trie实现所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。