首页 / PHP / php-优化Trie实现
php-优化Trie实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了php-优化Trie实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2632字,纯文字阅读大概需要4分钟。
内容图文
![php-优化Trie实现](/upload/InfoBanner/zyjiaocheng/671/50c505ff9fff463c8ac332a454eb354b.jpg)
除了乐趣之外,我今天没有实现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实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。