PHP troppo lento, qualcuno può vedere un modo per renderlo più veloce?

Dato un elenco di numbers di telefono, determinare se è coerente nel senso che nessun numero è il prefisso di un altro. Supponiamo che il catalogo telefonico abbia elencato questi numbers:

Emergenza 911 Alice 97 625 999 Bob 91 12 54 26

In questo caso, non è ansible call Bob, perché la centrale indirizza la chiamata alla linea di emergenza non appena sono state composte le prime tre cifre del numero di telefono di Bob. Quindi questa list non sarebbe coerente.

Ingresso

La prima row di input fornisce un singolo numero integer, 1≤t≤40, il numero di casi di test. Ogni test case inizia con n, il numero di numbers di telefono, su una row separata, 1≤n≤10000. Quindi segue n linee con un unico numero di telefono su ciascuna linea. Un numero di telefono è una sequenza di al massimo dieci cifre.

Produzione

Per each caso di test, emettere "SÌ" se l'elenco è coerente, o "NO" in caso contrario.


Il programma dovrebbe leggere lo standard in e scrivere allo standard. Possiamo anche presumere che l'input rispetterà le specifiche. Questo è il mio codice:

<?php fscanf(STDIN, "%d", $numOfTestCases); for ($i = 0; $i < $numOfTestCases; $i++) { //Loop for reading test cases fscanf(STDIN, "%d", $numOfPhoneNumbers); $phoneNumbers = arrays(); $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 arrays 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); ?> 

Il mio problema è che c'è un programma di test che sta eseguendo questo, che ha un timeout di 4 secondi. Il secondo file di test scade sempre. Non ho accesso al programma o ai file di test, ma presumo che il file sia molto lungo, forse anche 40 casi di test con 10000 numbers di telefono in ciascun caso.

Qualcuno può vedere come posso far funzionare questo codice più velocemente in qualsiasi modo?

Ecco un esempio di esecuzione:

 Sample Input: 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 Sample Output: NO YES 

Come tutti citano, l'tree è la tua soluzione. crea un tree che each nodo rappresenta una cifra in un numero. L'ultima cifra in each numero segnerà isNumber = true, e il resto delle cifre segnerà come isNumber = false.

Quando aggiungi un numero all'tree, attraversa il nodo dell'tree e verifica se attraversi un nodo con isNumber = true. in tal caso, restituire false / printingre qualcosa.

Es: vedi il disegno qui sotto

aggiungi un numero 21: iterare sulle cifre. crea un nuovo nodo = 1, nuovo nodo = 2 (isNumber = true)

aggiungi il numero 911: itera su cifre. crea un nuovo nodo = 9, nuovo nodo = 1, nuovo nodo = 1 (isNumber = true) aggiungi il numero 9125: iterare sulle cifre. crea un nuovo nodo = 9, nuovo nodo = 1, nuovo nodo = 2, nuovo nodo = 5 (isNumber = true)

aggiungi il numero 91 1 2: itera su cifre. crea un nuovo nodo = 9, nuovo nodo = 1, nuovo nodo = 1 ( ERRORE: non riuscito poiché isNumber = true ) inserisci la descrizione dell'immagine qui

spero che aiuti un po '

MODIFICARE:

Ok, dal momento che mi interessa, ho cercato di implementare la soluzione, e sono arrivato molto vicino al tuo.

Ho creato uno script semplice per creare un file testcase.txt contenente 10000 numbers (1≤n≤10000).

Ho creato un semplice script unittest.php che esegue 40 volte (1≤ t≤40), sullo stesso file.

 <?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 = arrays(); function __construct($digit,$leaf = false){ $this->digit = $digit; $this->leaf = $leaf; } function isLeaf(){ return $this->leaf; } function hasChild($digit){ return arrays_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); } 

Il risultato ha richiesto, per il mio vecchio e ancora funzionante, core2duo, memory da 2 GB:
vero utente 0m26.123s 0m26.064 sys 0m0.048s

per: 40×10000 = 400.000 numbers.

per un singolo testcase ci sono voluti: vero utente 0m0.554s 0m0.544 sys 0m0.008s