为什么列表操作比numpy数组操作慢 [英] Why operation on list is slower than operation on numpy array

问题描述

我正在做一个使用RSA算法加密数据的项目，为此，我将 .wav 文件作为输入，并使用<$ c $进行读取c> wavfile ，我可以应用密钥（3，25777），但是当我应用解密密钥（16971,25777）时，输出错误，如下所示：

I am doing a project on encrypting data using RSA algo and for that, I have taken a .wav file as an input and reading it by using wavfile and I can apply the key (3, 25777) but when I am applying the decryption key (16971,25777) it is giving wrong output like this:

我得到的输出：

                    [[     0 -25777]
                    [     0 -25777]
                    [     0 -25777]
                    ...
                    [-25777 -25777]
                    [-15837 -15837]
                    [ -8621      1]]

我想要的输出：

                    [[ 0 -1]
                    [ 2 -1]
                    [ 2 -3]
                    ...
                    [-9 -5]
                    [-2 -2]
                    [-4  1]]

与数组的解密部分，所以我决定将2d数组转换为2d列表。之后，它给了我想要的输出，但是将键应用于列表的所有元素要花费很多时间（16分钟，如果是数组，则为2秒）。我不明白为什么会这样，是否还有其他解决办法？

This was happening only with the decryption part of the array so I decided to convert the 2d array to a 2d list. After that, it is giving me the desired output but it is taking a lot of time to apply the keys to all the elements of the list(16min, in case of array it was 2sec). I don't understand why it is happening and if there is any other solution to this problem ?

这是程序的加密和解密部分：

here is the encryption and decryption part of the program:

    #encryption
    for i in range(0, tup[0]): #tup[0] is the no of rows
        for j in range(0, tup[1]): #tup[1] is the no of cols
            x = data[i][j] 
            x = ((pow(x,3)) % 25777) #applying the keys
            data[i][j] = x #storing back the updated value

    #decryption
    data= data.tolist() #2d array to list of lists 
    for i1 in (range(len(data)):
        for j1 in (range(len(data[i1]))):
            x1 = data[i1][j1] 
            x1 = (pow(x1, 16971)%25777) #applying the keys
            data[i1][j1] = x1 

期待建议。谢谢。

推荐答案

出现类似 pow（ x1，16971）应该会让您暂停一下，几乎所有整数x1都会产生64位int无法容纳的结果。这是numpy给出错误结果的原因，因为numpy在最常见的平台上使用64位或32位整数。这也是纯Python速度慢的原因，因为它虽然可以处理大整数，但代价却很高。

The occurrence of something like pow(x1, 16971) should give you pause. This will for almost any integer x1 yield a result which a 64 bit int cannot hold. Which is the reason numpy gives the wrong result, because numpy uses 64 bit or 32 bit integers on the most common platforms. It is also the reason why plain python is slow, because while it can handle large integers this is costly.

一种解决方法是在乘法之间应用模数，这样数字仍然很小，可以通过64位算术轻松处理。

A way around this is to apply the modulus in between multiplications, that way numbers remain small and can be readily handled by 64 bit arithmetic.

这里是一个简单的实现：

Here is a simple implementation:

def powmod(b, e, m):
    b2 = b                         
    res = 1                        
    while e:                       
        if e & 1:                  
            res = (res * b2) % m   
        b2 = (b2*b2) % m        
        e >>= 1                 
    return res

例如：

>>> powmod(2000, 16971, 25777)
10087
>>> (2000**16971)%25777
10087
>>> timeit(lambda: powmod(2000, 16971, 25777), number=100)
0.00031936285085976124
>>> timeit(lambda: (2000**16971)%25777, number=100)
0.255017823074013

这篇关于为什么列表操作比numpy数组操作慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！