title: increase performances of CPU-intensive PHP scripts
body: <p>I have a PHP script which takes hours (maybe days) to execute. It is quite simple but very CPU-intensive, most of the execution time is spent into (I can tell after having profiled the script):</p>
  
  <ol>
  <li><p><code>$array = explode(',', $a[$i]);</code>
  where <code>$a[$i]</code> is a very long string which represents a vector of 30k elements separated by comma</p></li>
  <li><p><code>foreach($array as $key =&gt; $value)</code> loops; where for each loop some in_array() and comparison and assignment operations are performed</p></li>
  </ol>
  
  <p><code>$a</code> is actually a very large and sparse matrix (30k * 30k) but I can't keep it in memory (8GB seems to be not enough RAM) so I keep just a "sparse representation" (basically each row is a string) and use <code>explode()</code> any time I need to work on a row.</p>
  
  <p>I know that rewriting everything in C (or other languages) would improve performances (how much?) but, before doing that I would like to know if I can do anything to improve the execution time in PHP.</p>
  
  <p>EDIT after answers.</p>
  
  <p>I tried several of your advises and here is my report:</p>
  
  <p>1) str_getcsv is in most of the case slower than explode</p>
  
  <p>2) SPLFixedArray decrease the memory requested to store the matrix but still, 8GB was not enough for a 30k x 30k matrix so I don't think it can help much; the real problem here is the lack of a sparse representation for matrix in PHP I think</p>
  
  <p>3) I can't store all the results of the explode operations because, still, that would mean keeping the whole matrix in memory (not enough RAM)</p>
  
  <p>4) I've tried the database approach even if I was sure it would have been slower: I've stored triples (i,j,value) to represent each matrix element; even deleting the less important values (I can sacrifice values less than a threshold and get a less precise result, but still useful) and storing just 18 millions tuples, the approach with mysql myisam is much slower than my array approach in memory.</p>
  
  <p>5) I've tried the database approach using the MEMORY engine (a mysql table in RAM) and storing all the matrix elements except the ones having value zero; having 42 millions records this time...it is faster, not an order of magnitude but 2-4 times faster...I think I can finish the job in 5 days instead of 15-20...it is still too much (I would like to finish in 24 hours), if you have any other suggestions you are very welcome</p>
  
  <p>EDIT 2: I explain the problem</p>
  
  <p>I'll give some details about the problem, I really need to simplify everything otherwise it would be too long to explain but I think it is enough to understand better the situation.</p>
  
  <p>I have a matrix representing distances among nodes; the distance in an integer and could also be infinite.</p>
  
  <p>I have a memory table representing each distance with triples: node_1, node_2, distance (just the non infinite distances are represented).</p>
  
  <p>I have this sort of greedy algorithm that I did not write and I should optimize to execute it in a feasible time (let's say less than one day) on a laptop having 8GB of RAM.</p>
  
  <p>The algo basically gets in input two nodes and designs a path between a starting node and an ending node step by step according to the following two properties that must be verified at each step:</p>
  
  <ul>
  <li>the new intermediate node must be chosen among the set of nodes that are closer to the ending node respect to the current node</li>
  <li>among those nodes, the one which is the closer to the current node is chosen</li>
  </ul>
  
  <p>Please consider that
  1) The triangle inequality is NOT satisfied.
  2) It is NOT a shortest path problem</p>
  
  <p>Here is some pseudo code for the function I call several times until I'm close enough to the ending node:</p>
  
  <pre><code>get_next_node($node_1, $node_2){
  
      $dist = select distance from distances_table where node_2 = $node_2 and node_1 = $node_1
  
      $candidates_ar = select node_1 from distances_table where node_2 = $node_2 and distance &lt; $dist
  
      $distances_ar = select distance from distances_table where node_1 = $node_1 and node_2 in ($candidates_ar) // e.g. $distances_ar[12] contains distance between node 12 and $node_1
  
      $min = 1000;
      foreach ($candidates_ar as $value){
          if ($distances_ar[$value] &lt; $min){
              $min = $distances_ar[$value]
              $next_node = $value
          }
      }
  
  }
  </code></pre>
  
  <p>I have omitted a lot of checks and additional complexity, but this is the basic and this is where the algo spends most of time.</p>
  
  <p>I guess it can be solved with an implementation of A* but I would like to avoid it if it is possible to increase the performances so that I can execute it in hours (not days).</p>
  
  <p>Thanks.</p>