python - 基于 numpy 提高脚本的时间和内存

Question

我需要在 Python 中实现图像中的公式。集合 B 是一组实数 -1 <= t <= 1。此外，F_2 是包含元素 0 和 1 的集合。y_i 是 $y$ 的第 i 个元素。这个公式是我的程序迭代部分的一部分。迭代次数约为 10K（超过 x），n 为 32。我尝试了一种预计算方法。也就是说，我预先计算了所有 f(y) 并将其放入一个 numpy 数组中，我还计算了 (-1**y_i) 并将其放入了一个 numpy 数组中。请参阅下面的代码。但即便如此，非预计算的计算时间约为 3 秒，n=24。当我尝试 n=32 时，由于大数组，我遇到了一些内存问题。我的问题是。你能帮我在内存和时间方面改进这段代码吗？

import time
from multiprocessing import Pool
import multiprocessing
import numpy as np
import numexpr as ne
import galois


def precomputation_part(linear_layer_matrix, dim):
    y_shift = np.fromfunction(lambda i,j: (i)>>j, ((2**dim), dim), dtype=np.uint32)
    um=np.ones(((2**dim), dim), dtype=np.uint8);
    and_list = np.bitwise_and(y_shift,um, dtype=np.uint8)
    minus1_power_x_t = np.power(-1,and_list, dtype=np.int8)
    fy_matrix = evaluated_f_bool_matrix(and_list, np.array(linear_layer_matrix,dtype=np.uint8))
    boolean_function_0 = fy_matrix[0]
    return boolean_function_0, minus1_power_x_t

def evaluated_f_bool_matrix(and_components, input_matrix):
    t1 = time.time()
    mc = and_components.transpose()
    mal = input_matrix
    return np.matmul(mal,mc,dtype=np.uint8)%2

def create_ext_component_function(dim, boolean_function, input_lst, minus1_power_x_t):
    um_minus_minus1_power = ne.evaluate('1-minus1_power_x_t*input_lst')
    um_minus_minus1_power_prod = um_minus_minus1_power.prod(axis=1)
    boolean_function_times_prod = np.dot(boolean_function, um_minus_minus1_power_prod)

    return boolean_function_times_prod*(1/((2**dim)-1))-1


if __name__ == '__main__':
    dim = 24
    f_matrix = [[0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1], [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1], [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1], [1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0], [1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1], [0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0], [0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1], [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1], [0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1], [0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0], [0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1], [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1], [0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1], [0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0], [1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1], [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1], [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]]
    boolean_function_0, minus1_power_x_t = precomputation_part(f_matrix, dim)
    ########The below two lines are executed several times
    x = np.array([i+1 for i in range(dim)], dtype=float)
    print(create_ext_component_function(dim, boolean_function_0, x, minus1_power_x_t))

标签： pythonnumpy

Answer 1

这不是一个完整的答案，但这里有一些优化的想法。

1. f(y) 只返回 0 或 1，对吗？如果是这样，只计算 f(y)=1 的乘积。当 f(y)=0 时，乘积计算被浪费了。如果 f(y)=1 的概率很低，则这一点变得非常重要，否则就不太重要了。

2. 总和是 2^n-1 中的所有整数，对吗？如果每个位都存储为一个字节，尤其是当 n 甚至大于 32 时，那将是一个非常大的矩阵。我不认为预计算是实用的，除非它被分块。由于您有一个总和，因此有一种合乎逻辑的方法可以跨 y 分块。

3. 您可能可以在计算 y 的高位时重复计算 y 的低位，因为 x 在总和上是恒定的，作为分而治之（对第 2 项有帮助）。

   我真的希望我们在这里有乳胶，但是：

   

   此优化与优化项 1 不兼容。

import numpy as np
n = 32
x = np.random.uniform(-1,1,n).astype(np.float16)

prods = np.array([1-x[0],1+x[0]]).astype(np.float16)
a = np.array([-1, 1]).astype(np.float16)

for i in range(1, n):
  prods = np.kron(
      1+a*x[i],
      prods
  )

4. 还可以考虑使用不同的浮点精度来节省内存。

5. 不是速度的事情，但看起来你正在乘以很多可能下溢或溢出的数字。不是计算乘积，而是对元素乘积的对数求和，然后对对数的总和求幂。

防止数值下溢的 Log-Sum-Exp 技巧