PHP太慢了，有没有办法让它变得更快？

Question

给定一组电话号码，判断它们是否一致，即没有一个号码是另一个的前缀。假设电话目录列出了以下号码：

紧急电话 911 爱丽丝 97 625 999 鲍勃 91 12 54 26

在这种情况下，你不能拨打鲍勃的电话，因为只要你拨打了鲍勃电话号码的前三个数字，中央就会将您的电话转接到紧急电话。因此，此列表不一致。

输入

输入的第一行包含一个整数t，表示测试用例的数量，1≤t≤40。每个测试用例都以单独的一行n（1≤n≤10000）开始，表示电话号码的数量。然后是n行，每行一个唯一的电话号码。电话号码是最多十个数字的序列。

输出

对于每个测试用例，如果列表一致，则输出“YES”，否则输出“NO”。

---

程序应该从标准输入读取，然后写入标准输出。我们也可以假设输入将遵守规范。这是我的代码：

<?php

    fscanf(STDIN, "%d", $numOfTestCases);

    for ($i = 0; $i < $numOfTestCases; $i++) { //Loop for reading test cases
        fscanf(STDIN, "%d", $numOfPhoneNumbers);

        $phoneNumbers = array();
        $isConsistent = true;

        for ($j = 0; $j < $numOfPhoneNumbers; $j++) { //Loop for reading phone numbers of each test case
            fscanf(STDIN, "%d", $newNumber);

            if ($isConsistent != false) { //If list already inconsistent, we dont need to check further input
                if (empty($phoneNumbers)) { // If the array of phone numbers is empty, we just add the new one
                    $phoneNumbers[$j] = $newNumber;
                } else {
                    foreach ($phoneNumbers as $k => $testNumber) { //Loop for checking if new number is consistent or not
                        $newNumLen = strlen($newNumber);
                        $testNumlen = strlen($testNumber);

                        $newBeginning = substr($newNumber, 0, $testNumlen);
                        $testBeginning = substr($testNumber, 0, $newNumLen);

                        if ($newNumber == $testBeginning || $testNumber == $newBeginning) {
                            $isConsistent = false;
                            break;
                        }
                    }

                    if ($isConsistent == true) $phoneNumbers[$j] = $newNumber;
                }                   
            } 
        }

        $newAnswer = ($isConsistent) ? "YES" : "NO";
        $ansString = ($i == 0) ? $newAnswer : $ansString."\n".$newAnswer;
    }

    fwrite(STDOUT, $ansString);

    exit(0);
?>

我的问题是有一个测试程序正在运行此代码，并且其超时时间为4秒。第二个测试文件总是超时。我无法访问测试程序或文件，但我认为该文件非常长，甚至可能包含40个测试用例，每个用例有10000个电话号码。

有人能否看出如何使这段代码以任何方式更快地运行？

以下是示例运行：

Sample Input:

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output:

NO
YES

- BluePrint

---

使用性能分析工具。Xdebug非常好用，可以看到程序执行中大部分时间都花费在哪里。 - exussum

我会采用完全不同的方法：目前，您基本上是将每个数字与其他数字进行比较，这会产生O(n^2)的复杂度。相反，您可以使用每个层级上的数字构建已知数字的树形结构。当您向树中输入新数字并在其中途遇到已知数字时，请拒绝它。这将导致几乎线性的复杂度。 - Sirko

也许慢的部分是一个缓慢、阻塞、等待输入的STDIN读取。 - hanshenrik

[php]和[performance]从来不是一个有效的组合。 ;) - Qix - MONICA WAS MISTREATED

@Qix，你说的部分正确，但是使用像HHVM这样的JIT编译器，会让你的代码运行更快。 - YyYo

Answer 1

如众所周知，树是你的解决方案。创建一棵树，每个节点代表数字中的一个数字。每个数字中的最后一个数字将标记为isNumber=true，其余数字将标记为isNumber=false。

当您将数字添加到树中时，请遍历树的节点并检查是否遍历到isNumber=true的节点。如果是，则返回false/打印某些内容。

例如：请参见下面的说明

添加数字21：迭代数字。创建新节点=1，新节点=2（isNumber=true）

添加数字911：迭代数字。创建新节点=9，新节点=1，新节点=1（isNumber=true） 添加数字9125：迭代数字。创建新节点=9，新节点=1，新节点=2，新节点=5（isNumber=true）

添加数字9112：迭代数字。创建新节点=9，新节点=1，新节点=1（错误：因为isNumber=true而失败） 希望这有点帮助。

编辑：

好吧，既然它让我感兴趣，我尝试实现了这个解决方案，我离你的解决方案相当接近。

我编写了一个简单的脚本来创建一个包含10000个数字（1≤n≤10000）的testcase.txt文件。

我编写了一个简单的unittest.php脚本，它在同一个文件上运行40次（1≤t≤40）。

<?php 

// create_testcase.php
$handle = fopen("testcase.txt",'w');

for($i=0 ; $i < 10000 ; $i++){
    $number = rand(1,9999999999);
    fwrite($handle,$number."\n");
}
fclose($handle);

// unittest.php
class Node{
    private $digit;
    private $leaf = false;
    private $children = array();
    function __construct($digit,$leaf = false){
        $this->digit = $digit;
        $this->leaf = $leaf;
    }

    function isLeaf(){
        return $this->leaf;
    }

    function hasChild($digit){
        return array_key_exists($digit,$this->children);

    }

    function hasChildren(){
        return count($this->children);
    }

    function addChild($digit,$isLeaf){
        $this->children[$digit] = new Node($digit,$isLeaf);
        return $this->children[$digit];
    }

    function getChild($digit){
        return $this->children[$digit];
    }

}


for($i=0 ; $i < 40 ; $i++){

    $anchor = new Node(0,false);
    $isConsistent = true;
    $handle = fopen("testcase.txt",'r');

    while(($number = fgets($handle)) != false){
        $node = $anchor;
        $number = rtrim($number);
        $number_length = strlen($number);
        foreach(str_split($number) as $index => $digit){
            if($node->hasChild($digit)){
                $node = $node->getChild($digit);
                if($node->isLeaf()){
                    $isConsistent = false;
                    break;
                }
            }
            else{
                (($index+1) == $number_length) ? ($isLeaf = true) : ($isLeaf = false);
                $node = $node->addChild($digit,$isLeaf);
            }   
        }

        if($node->hasChildren()){
            $isConsistent = false;      
        }

        if(!$isConsistent){
            break;                  // don't continue to next number in test case
        }
    }
    if($isConsistent){
        print "Consist list\n";

    }
    else{
        print "Not Consist list\n";
    }
    fclose($handle);

}

对于我的旧款仍在使用的core2duo，2GB内存电脑来说，结果如下：

40x10000=400,000个数字的情况下：

单个测试用例所需时间为：

真实时间0m0.554s

用户时间0m0.544s

系统时间0m0.008s

- YyYo

---

非常感谢，这是最好的解决方案。现在我只需要想出编写此代码的方法了。 - BluePrint

我尝试使用以上方法来解决问题，但是我的代码在测试程序的4秒超时限制下仍然太慢了。我新写的代码在这里：http://pastebin.com/wSzxCu05 ，你能看出我可能做错了什么吗？ - BluePrint

@YyYo 很棒的回答。 :) - Qix - MONICA WAS MISTREATED