PHP中可伸缩Trie的实现
在本教程之后，我遇到了Trie数据结构。因为最近我一直在用PHP编程，所以我试图用它来解决讲座中的问题。我能够获得正确的答案，但只适用于较小的输入（输入#10是一个2,82 MB的文件）。显然，我的算法缩放不好。它还超过了PHP默认的128 MB内存限制。
Trie中存储了一个根节点。每个节点都有一个“子”成员。我使用标准PHP数组来存储子对象。子键表示一个字符（目前我正在为每个字符创建一个新节点，A-z小写，映射到0-25），子值是对另一个节点的引用。
由于该问题，每个节点都有一个“权重”成员。我想优化我的代码（或者甚至用另一种方法从stratch重写代码），这样它就可以通过大输入测试。
我对一个解决方案感兴趣，如果可能的话，它可以使这个数据结构在PHP中使用大输入。
三节点类存储树层次结构。
class TrieNode {
// weight is needed for the given problem
public $weight;
/* TrieNode children,
* e.g. [0 => (TrieNode object1), 2 => (TrieNode object2)]
* where 0 stands for 'a', 1 for 'c'
* and TrieNode objects are references to other TrieNodes.
*/
private $children;
function __construct($weight, $children) {
$this->weight = $weight;
$this->children = $children;
}
/** map lower case english letters to 0-25 */
static function getAsciiValue($char) {
return intval(ord($char)) - intval(ord('a'));
}
function addChild($char, $node) {
if (!isset($this->children)) {
$this->children = [];
}
$this->children[self::getAsciiValue($char)] = $node;
}
function isChild($char) {
return isset($this->children[self::getAsciiValue($char)]);
}
function getChild($char) {
return $this->children[self::getAsciiValue($char)];
}
function isLeaf() {
return empty($this->children);
}
}
Trie类存储根TrieNode。它可以插入和查询节点。
class Trie {
/* root TrieNode stores the first characters */
private $root;
function __construct() {
$this->root = new TrieNode(-1, []);
}
function insert($string, $weight) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = $string[$i];
if(!$currentNode->isChild($char)) {
$n = new TrieNode($weight, null);
$currentNode->addChild($char, $n);
}
$currentNode->weight = max($weight, $currentNode->weight);
$currentNode = $currentNode->getChild($char);
}
}
function getNode($string) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = $string[$i];
if ($currentNode->isLeaf() || !$currentNode->isChild($char)) {
return null;
}
$currentNode = $currentNode->getChild($char);
}
return $currentNode;
}
function getWeight($string) {
$node = $this->getNode($string);
return is_null($node) ? -1 : $node->weight;
}
}
测试代码。解析输入并调用Trie对象。
//MAIN / TEST
/*
In case the problem page is down:
e.g.
INPUT
2 1
hackerearth 10
hackerrank 9
hacker
OUTPUT
10
where 2 is the number of inserts, 1 is the number of queries
"string number" is the string to insert and its "weight"
"hacker" is the string to query
10 is maximum the weight of the queried string (hacker -> 10)
*/
$trie = new Trie();
$handle = fopen('test.txt', 'r');
//$handle = STDIN; // <- this is for the online judge
list($n, $q) = fscanf($handle, "%d %d");
for ($i = 0; $i < $n; $i++) { // insert data
list($s, $weight) = fscanf($handle, "%s %d");
$trie->insert($s, $weight);
}
for ($i = 0; $i < $q; $i++) { // query data
$query = trim(strval(fgets($handle)));
echo $trie->getWeight($query) . PHP_EOL;
}
fclose($handle);
共有2个答案
下面是经过以下优化的代码-
删除了所有不必要的条件检查，如
- 不需要检查节点是否是叶子，因为如果节点没有指定的子字符，那么它是否是叶子并不重要。
- 无需在每次添加子节点时检查是否初始化了{子节点。删除此检查初始化{子}为空数组在构造函数本身。
删除了{getAsciiValue}的函数，而不是使用一个简单的关联数组。还将{char}更改为ascii值已从TrieNode移动到Trie类，因此我们不需要多次转换它
经过这些优化后，我提出了以下最小解决方案，但这也无法通过测试#10。在阅读了PHP中的数组之后，我了解到PHP并不像其他编译语言那样实现数组，相反，PHP中的任何数组都只是一个有序的哈希映射，因为这个数组不支持常量时间操作。https://stackoverflow.com/a/4904071/8203131
也使用SplFixedArray，但没有帮助，因为它是一个对象，并且有实例化的成本。如果尝试使用大型数组来存储整个Trie，可能会有所帮助。您可以尝试实现一个解决方案，使用SplFixedArray存储整个Trie，并检查它是否能够通过测试#10。
<?php
/*
* Read input from stdin and provide input before running code
fscanf(STDIN, "%s\n", $name);
echo "Hi, ".$name;
*/
class TrieNode {
// weight is needed for the given problem
public $weight;
/* TrieNode children,
* e.g. [0 => (TrieNode object1), 2 => (TrieNode object2)]
* where 0 stands for 'a', 2 for 'c'
* and TrieNode objects are references to other TrieNodes.
*/
private $children;
function __construct($weight) {
$this->weight = $weight;
$this->children = [];
}
function addChild($char, $node) {
$this->children[$char] = $node;
}
function isChild($char) {
return isset($this->children[$char]);
}
function getChild($char) {
return $this->children[$char];
}
}
class Trie {
/* root TrieNode stores the first characters */
private $root;
function __construct() {
$this->root = new TrieNode(-1);
}
static $asciiValues = array(
"a" => 0,
"b" => 1,
"c" => 2,
"d" => 3,
"e" => 4,
"f" => 5,
"g" => 6,
"h" => 7,
"i" => 8,
"j" => 9,
"k" => 10,
"l" => 11,
"m" => 12,
"n" => 13,
"o" => 14,
"p" => 15,
"q" => 16,
"r" => 17,
"s" => 18,
"t" => 19,
"u" => 20,
"v" => 21,
"w" => 22,
"x" => 23,
"y" => 24,
"z" => 25
);
function insert($string, $weight) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = self::$asciiValues[$string[$i]];
$currentNode->weight = max($weight, $currentNode->weight);
if($currentNode->isChild($char)) {
$childNode = $currentNode->getChild($char);
} else {
$childNode = new TrieNode($weight);
$currentNode->addChild($char, $childNode);
}
$currentNode = $childNode;
}
}
function getNodeWeight($string) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = self::$asciiValues[$string[$i]];
if (!$currentNode->isChild($char)) {
return -1;
}
$currentNode = $currentNode->getChild($char);
}
return $currentNode->weight;
}
}
$trie = new Trie();
//$handle = fopen('test.txt', 'r');
$handle = STDIN; // <- this is for the online judge
list($n, $q) = fscanf($handle, "%d %d");
for ($i = 0; $i < $n; $i++) { // insert data
list($s, $weight) = fscanf($handle, "%s %d");
$trie->insert($s, $weight);
}
for ($i = 0; $i < $q; $i++) { // query data
//$query = trim(strval(fgets($handle)));
$query = trim(strval(fgets($handle)));
echo $trie->getNodeWeight($query) . PHP_EOL;
}
fclose($handle);
?>
在做了一些调整和修改后，我已经能够让这个东西为所有的测试用例工作，除了一个测试用例正在计时，
下面是除了测试用例10之外的所有测试用例都将成功运行的整个代码。
class TrieNode {
// weight is needed for the given problem
public $weight;
/* TrieNode children,
* e.g. [0 => (TrieNode object1), 2 => (TrieNode object2)]
* where 0 stands for 'a', 1 for 'c'
* and TrieNode objects are references to other TrieNodes.
*/
private $children;
function __construct($weight, $children) {
$this->weight = $weight;
$this->children = $children;
}
/** map lower case english letters to 0-25 */
static function getAsciiValue($char) {
return intval(ord($char)) - intval(ord('a'));
}
function addChild($char, $node) {
if (!isset($this->children)) {
$this->children = [];
}
$this->children[self::getAsciiValue($char)] = $node;
}
function isChild($char) {
return isset($this->children[self::getAsciiValue($char)]);
}
function getChild($char) {
return $this->children[self::getAsciiValue($char)];
}
function isLeaf() {
return empty($this->children);
}
}
class Trie {
/* root TrieNode stores the first characters */
private $root;
function __construct() {
$this->root = new TrieNode(-1, []);
}
function insert($string, $weight) {
$currentNode = $this->root;
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = $string[$i];
if(!$currentNode->isChild($char)) {
$n = new TrieNode($weight, null);
$currentNode->addChild($char, $n);
}
$currentNode->weight = max($weight, $currentNode->weight);
$currentNode = $currentNode->getChild($char);
}
}
function getNode($string) {
$currentNode = $this->root;
if (empty($currentNode) || !isset($currentNode)) {
return null;
}
$l = strlen($string);
for ($i = 0; $i < $l; $i++) {
$char = $string[$i];
if (empty($currentNode) || $currentNode->isLeaf() || !$currentNode->isChild($char)) {
return null;
}
$currentNode = $currentNode->getChild($char);
if (empty($currentNode)) {
return null;
}
}
return $currentNode;
}
function getWeight($string) {
$node = $this->getNode($string);
return is_null($node) ? -1 : $node->weight;
}
}
$trie = new Trie();
//$handle = fopen('test.txt', 'r');
$handle = STDIN; // <- this is for the online judge
list($n, $q) = fscanf($handle, "%d %d");
for ($i = 0; $i < $n; $i++) { // insert data
list($s, $weight) = fscanf($handle, "%s %d");
$trie->insert($s, $weight);
}
for ($i = 0; $i < $q; $i++) { // query data
$query = trim(strval(fgets($handle)));
echo $trie->getWeight($query) . PHP_EOL;
}
fclose($handle);
我将尝试添加更多的检查，以便减少此程序所占用的计算周期。
-
我有500MB的数据要推送到云搜索。 以下是我尝试过的选项： 直接从控制台上传： 试图上传文件时，有5 MB的限制。 然后将文件上传到S3并选择S3选项， 上传到S3并在控制台中给出S3 url： 失败并要求尝试命令行。 尝试使用命令行 aws cloudsearchdomain上载文档--endpointurlhttp://endpoint--内容类型application/json--文档s3
-
实现效果 点击任意一张图片，图片展开，同时从图片上下两方分别移入文字。点击已经展开的图片后，图片被压缩，同时该图片上下两端的文字被挤走。若图片加载不出来，请点链接看更完整的演示图片，在线效果请点这里。 初始文档的 DOM 结构：以 .panels 为父 div 之下，有 5 个类名为 .panel 的 div，这 5 个各含有 3 个子 p 标签。而相应的 CSS 样式中，动画时间等特性已经设定好
-
假设某个负载均衡器（希望将来不会出现一个故障点，但我不知道如何实现这一点，或者可能只是转移到AWS）正在将SocketIO连接从终端客户机分配到聊天服务器。不同的用户连接到不同的服务器可能在同一个房间，因此需要将消息发送到其他服务器。 我如何可行地实现这样的东西？希望不要太复杂。 问题：（1）如果所有服务器都需要处理所有的消息，因为用户可以通过任何服务器登录，这是否可以扩展？（2）服务器之间是否需
-
伸缩是对该应用所启动的pods数量进行一个控制。 同样进入应用的详情页页，在右上角找到“伸缩”按钮并点开。 在弹出来的对话框中选择启动的POD数量，如下图： 提交之后若数量大于之前的数量，则会启动缺少的POD数量，若小于之前的值，将会逐步减少应用的POD。 目前给的最大值是8个pod，资源可使用的内存是16G，若您的应用超过我们所设定的最大值。想办法优化吧，64核128G内存都不够用，这种级别的应
-
我用JBossas7创建了一个新的可伸缩应用程序。创建之后，添加MySql墨盒。但是当我使用SSH登录到gear时，我无法看到mysql目录。同样，当尝试使用sqlplus时，会引发command not found错误。 我还尝试使用JDBC使用一个简单的Java应用程序连接到数据库。在Openshift环境中使用了Valuse变量。出现连接超时异常。 我是不是漏掉了一些基本的东西？
-
本文向大家介绍可伸缩的textview详解(推荐)，包括了可伸缩的textview详解(推荐)的使用技巧和注意事项，需要的朋友参考一下 在Android原生的TextView的基础上，可收缩/扩展的TextView：PhilExpandableTextView。 实现原理：核心是控制TextView的max lines。在TextView的初始化阶段但尚未绘制出View的时候，使用ViewTree