PHP слишком медленный, может ли кто-нибудь увидеть способ сделать это быстрее?

Учитывая список телефонных номеров, определите, является ли он последовательным в том смысле, что число не является префиксом другого. Скажем, в телефонном каталоге перечислены эти номера:

Авария 911 Алиса 97 625 999 Боб 91 12 54 26

В этом случае нельзя позвонить Бобу, потому что центральный будет направлять ваш вызов на аварийную линию, как только вы набрали первые три цифры номера телефона Боба. Таким образом, этот список не будет последовательным.

вход

Первая строка ввода дает одно целое число, 1≤t≤40, количество тестовых примеров. Каждый тестовый пример начинается с n, количества телефонных номеров на отдельной строке, 1≤n≤10000. Затем следует n строк с одним уникальным номером телефона на каждой строке. Номер телефона – это последовательность из десяти цифр.

Вывод

Для каждого тестового примера выведите «ДА», если список согласован, или «НЕТ» в противном случае.

Предполагается, что программа должна читать стандарт fron, и писать стандартно. Мы также можем предположить, что вход будет соответствовать спецификации. Это мой код:

<?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

Как и все упоминание, дерево – это ваше решение. создайте дерево, каждое из которых представляет цифру в числе. Последняя цифра в каждом номере будет отмечена как 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)

добавьте номер 91 1 2: итерация по цифрам. создать новый узел = 9, новый узел = 1, новый узел = 1 ( ERROR: сбой с isNumber = true ) введите описание изображения здесь

надеюсь, что это поможет.

РЕДАКТИРОВАТЬ:

Хорошо, так как это меня интересует, я попытался реализовать решение, и я подошел довольно близко к твоему.

Я создал простой скрипт для создания файла testcase.txt, содержащего 10000 номеров (1≤n≤10000).

Я сделал простой скрипт 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, 2 ГБ памяти:
real 0m26.123s пользователь 0m26.064s sys 0m0.048s

для: 40×10000 = 400 000 номеров.

для одного тестового теста потребовалось: real 0m0.554s пользователь 0m0.544s sys 0m0.008s