数组中超过64万个元素 - 内存问题[Dijkstra]

Question

I have a script which puts 803*803 (644 809) graph with 1 000 000 value inside each. With ~500*500 everything works fine - but now it crashes - it tries to allocate more than 64MB of memory (which I haven't). What's the solution? Somehow "split" it or...?

$result=mysql_query("SELECT * FROM some_table", $connection);
confirm($result);
while($rows = mysql_fetch_array($result)){
    $result2=mysql_query("SELECT * FROM some_table", $connection);
    confirm($result2);
    while($rows2 = mysql_fetch_array($result2)){
        $first = $rows["something"];
        $second = $rows2["something2"];

        $graph[$first][$second] = 1000000;
    }
}

*it's about Dijkstra algorithm

p.s. no, I can't allocate more than 64MB

Answer 1

Try freeing your inside sql result at the end of each loop, using mysql_free_result($result2);, the PHP script may not do it for you, depending on the PHP version (the garbage collector may not be enabled or may be useless due to a too old PHP version).

Do not instanciate the two temporary variables inside the loop, use the mysql_fetch_array result directly such as $graph[$rows["something"]][$rows2["something2"]] = 1000000; , you will save 2 memory allocations per loop..

PS: This is micro-optimization, therefore it may help you to save enough memory to fit into your 64M of memory. Don't forget that with 64 * 1024 * 1024 bytes of memory, you have an average 104 bytes maximum size for each of your 644 809 elements, plus the array size itself, plus the rest of the temporary data you may allocate for your algorithm.

If it doesn't fit, consider splitting your matrix and doing batched jobs or such to split your work in lesser memory consuming but more than one script run.