python - 如何设计内存和计算密集型程序以在 Google App Engine 上运行

Question

我的代码在 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)，根据 n 的不同，它会运行超过 10 分钟。因此我正在使用任务队列。我还需要一个 4 维数组，它存储为 n x n x n x n 的列表(例如 A[j][d][d1][d2])，即需要内存空间 O(N^4)

由于 put() 的限制是 10 MB，我无法存储整个数组。因此，我尝试将其切成小块并存储起来，然后在检索时将它们组合起来。我为此使用了 json 函数，但它不支持更大的 n (> 40)。

然后我将整个矩阵作为列表的单个实体存储在数据存储中，即每个 A[j][d][d1] 实体。所以没有局部变量。当我在我的代码中访问 A[j][d][d1][d2] 时，我会调用我自己的函数 getitem 和 putitem 从数据存储中获取和放入数据(也使用缓存)。结果，我的代码需要更多的时间来计算。几次迭代后，我收到 GAE 引发的错误 203，任务失败并显示代码 500。

我知道我的代码可能不是最适合 GAE 的。但是在 GAE 上实现它的最佳方式是什么？

Answer 1

可能有更有效的方法来存储您的数据并对其进行迭代。

问题:

• 您要存储什么数据类型，list of list ... of int？
• 最里面的循环 O(n^2) 部分通常在嵌套列表的哪个范围内运行？
• 当您执行 putitem、getitem 时，您在单个 put 或 get 中检索了多少个值？

想法:

• 您可以尝试压缩您的 json(以及用于剪切和粘贴的 base64)。 'myjson'.encode('zlib').encode('base64')
• 按照@Robert 的建议使用分而治之(map reduce)。您可以使用带有元组键的字典，这可能比内部循环中的 A[j][d][d1][d2] 查找次数少。它还可以让您稀疏地填充您的结构。您需要跟踪并了解您以另一种方式加载的数据的范围。 A[j][d][d1][d2] 变为 D[(j,d,d1,d2)] 或 D[j,d,d1,d2]