Более 640 000 элементов в массиве - проблема памяти [Dijkstra] - PullRequest
Новая
       12

Более 640 000 элементов в массиве - проблема памяти [Dijkstra]

2 голосов
/ 01 февраля 2011

У меня есть скрипт, который помещает график 803 * 803 (644 809) со значением 1 000 000 внутри каждого.С ~ 500 * 500 все работает нормально - но теперь происходит сбой - он пытается выделить более 64 МБ памяти (чего у меня нет).Какое решение?Каким-то образом «разделить» его или ...? 

$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;
    }
}

* речь идет об алгоритме Дейкстры

ps нет, я не могу выделить более 64 МБ

Ответы [ 4 ]

3 голосов
/ 01 февраля 2011

Попробуйте освободить свой внутренний sql-результат в конце каждого цикла, используя mysql_free_result($result2);, PHP-скрипт может этого не сделать, в зависимости от версии PHP (сборщик мусора может быть не включен или может быть бесполезным из-за слишком старая версия PHP).

Не создавайте экземпляры двух временных переменных внутри цикла, используйте непосредственно результат mysql_fetch_array, например $graph[$rows["something"]][$rows2["something2"]] = 1000000;, вы сэкономите 2 выделения памяти на цикл.

PS: Это микро -оптимизация, поэтому она может помочь вам сэкономить достаточно памяти, чтобы поместиться в ваши 64M памяти. Не забывайте, что с 64 *1024* 1024 байтами памяти у вас есть максимальный размер в 104 байта для каждого из ваших 644 809 элементов, плюс размер самого массива плюс оставшиеся временные данные, которые вы можете выделить для своего алгоритма .

Если он не подходит, рассмотрите возможность разделения вашей матрицы и выполнения пакетных заданий или чего-то подобного, чтобы разделить вашу работу при меньшем потреблении памяти, но при выполнении более одного сценария.

1 голос
/ 02 февраля 2011

Если приведенный выше пример кода действительно соответствует реальному коду, вы получаете один и тот же результат два раза (второй даже в цикле).Если это один и тот же набор данных, выборки из базы данных будет достаточно, и это уменьшит нагрузку на базу данных, время выполнения и объем памяти.

Возможно, следующий подход может работать в среде с ограниченным объемом памяти. 

$result = mysql_unbuffered_query("SELECT * FROM some_table", $connection);
confirm($result);
$rawData    = array();
while ($rows = mysql_fetch_assoc($result)) {
    $rawData[] = array($rows["something"], $rows["something2"]);
}
mysql_free_result($result);

$graph = array();
foreach ($rawData as $r1) {
    foreach ($rawData as $r2) {
        $graph[$r1[0]][$r2[1]] = 1000000;
    }
}
unset($rawData);

Примечания:

  • Я использую mysql_fetch_assoc() вместо mysql_fetch_array(), поскольку последний будет возвращать каждый столбец дважды (один численно проиндексированный и один проиндексированный)по имени столбца)
  • Возможно, использование mysql_unbuffered_query() вместо mysql_query() может также уменьшить объем памяти (в зависимости от фактического размера набора данных)
0 голосов
/ 01 февраля 2011

Если вы настаиваете на использовании PHP для операций с большим объемом памяти (что на самом деле не очень хорошая идея), я бы разбил график на квадранты и использовал GD для объединения квадрантов.Таким образом, вам нужно будет построить график только с 1/4 объема памяти.

Опять же, это не идеально, но вы пытаетесь использовать гвоздь, чтобы вбить молоток: D

0 голосов
/ 01 февраля 2011

Попробуйте использовать http://en.wikipedia.org/wiki/Adjacency_list для представления графика вместо матрицы смежности (я думаю, вы используете матричную причину $graph[$first][$second] = 1000000;

Для разреженного графа требуется меньше памяти.

...