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

У меня есть скрипт, который помещает 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;
    }
}

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

пс. нет, я не могу выделить больше 64 МБ


php limit memory dijkstra
person svenkapudija    schedule 01.02.2011    source источник
comment
Получают ли эти 2 запроса к базе данных одинаковые данные? Что делает функция подтверждения()?   -  person Marek Tuchalski    schedule 01.02.2011
comment
Вам нужен весь график в памяти? Являются ли первое и второе целочисленными значениями или что-то еще? Нам нужно больше информации.   -  person Tyler Eaves    schedule 01.02.2011
comment
И как выглядит код функции подтверждения?   -  person profitphp    schedule 01.02.2011
comment
Да, теперь я понял - зачем мне весь график сразу - я поставлю его NULL, затем проверю, если он NULL - установите его, если не NULL, проверьте, меньше ли новое значение, чем старое, и замените, если это так. Ничего :) Моя вина. Но да, первое и второе являются целыми числами, а confrim() просто устанавливает соединение и выполняет действия (с базой данных).   -  person svenkapudija    schedule 01.02.2011
comment
Попробуйте вместо этого некоторые структуры данных SPL   -  person Gordon    schedule 01.02.2011
comment
Нет кода = нет ответа. Делать это так же полезно, как мешок с кошачьей рвотой.   -  person Tyler Eaves    schedule 01.02.2011

Ответы (4)


arrow_upward
3
arrow_downward

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

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

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

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

person Pierre    schedule 01.02.2011

arrow_upward
1
arrow_downward

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

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

$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() может также уменьшить объем памяти (в зависимости от фактического размера набора данных).
person Stefan Gehrig    schedule 02.02.2011

arrow_upward
0
arrow_downward

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

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

person Radoslav Georgiev    schedule 01.02.2011
comment
Это не то, как работают массивы в PHP. Это гораздо больше соответствует хеш-таблице, чем массиву C. - person Tyler Eaves; 01.02.2011

arrow_upward
0
arrow_downward

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

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

person John Cartwright    schedule 01.02.2011