Как спроектировать память и ресурсоемкую программу для запуска на Google App Engine - PullRequest
Новая
       4

Как спроектировать память и ресурсоемкую программу для запуска на Google App Engine

2 голосов
/ 28 декабря 2010

У меня проблема с моим кодом, работающим на Google App Engine. Я не знаю, как изменить свой код в соответствии с требованиями GAE. Вот моя проблема 

for j in range(n):
 for d in range(j):
  for d1 in range(d):
   for d2 in range(d1):
    # block which runs in O(n^2)

Фактически весь блок кода равен O (N ^ 6), и он будет работать более 10 минут в зависимости от n. Таким образом, я использую очереди задач. Мне также понадобится 4-мерный массив, который хранится в виде списка (например, A [j] [d] [d1] [d2]) из n x n x n x n, т. Е. Требуется пространство памяти O (N ^ 4)

Поскольку ограничение put () составляет 10 МБ, я не могу сохранить весь массив. Поэтому я попытался нарезать на более мелкие куски и сохранить их, а при получении объединить их. Для этого я использовал функцию json, но она не поддерживает большее n (> 40).

Затем я сохранил всю матрицу как отдельные объекты списков в хранилище данных, т.е. каждый объект A [j] [d] [d1]. Так что нет локальной переменной. Когда я получаю доступ к A [j] [d] [d1] [d2] в моем коде, я вызываю свои собственные функции getitem и putitem для получения и помещения данных из хранилища данных (также используется кэширование). В результате мой код требует больше времени для вычислений. После нескольких итераций я получаю ошибку 203, вызванную GAE, и задача завершается с кодом 500.

Я знаю, что мой код может не подходить для GAE. Но как лучше всего это реализовать на GAE?

Ответы [ 3 ]

1 голос
/ 28 декабря 2010

Могут быть и более эффективные способы хранения ваших данных и их перебора.

Вопросы:

  • Какой тип данных вы храните, list of list ... of int?
  • В каком диапазоне вложенного списка обычно работает ваша часть O (n ^ 2) внутреннего цикла?
  • Когда вы делаете putitem, getitem, сколько значений вы получаете за один разили получите?

Идеи:

  • Вы можете попробовать сжать свой json (и base64 для вырезания и вставки).'myjson'.encode('zlib').encode('base64')
  • Использование «разделяй и властвуй» (уменьшение карты), как предложил @Robert.Вы можете использовать словарь с кортежами для ключей, это может быть меньше поисков, чем A[j][d][d1][d2] во внутреннем цикле.Это также позволит вам редко заполнять вашу структуру.Вам нужно будет отслеживать и знать свои границы того, какие данные вы загрузили другим способом.A[j][d][d1][d2] becomes D[(j,d,d1,d2)] or D[j,d,d1,d2]
0 голосов
/ 22 февраля 2011

Сэм, просто дайте вам идею и укажите, с чего начать.

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

http://appengine -cookbook.appspot.com / recipe / how-to-put-any-python-object-in-а-хранилищу

0 голосов
/ 28 декабря 2010

Вы пропустили важные детали, такие как ожидаемый размер n в вашем вопросе. Кроме того, «# block which runs in O(n^2)» нужен доступ ко всей матрице или вы просто заполняете матрицу на основе значений индекса?

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

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

...