由2驱动的非常大的方阵 [英] A very large square matrix powered by 2

问题描述

我有一个大约为570,000 x 570,000的非常大的方阵，我想将其乘以2.

I have a very large square matrix of order around 570,000 x 570,000 and I want to power it by 2.

数据以json格式转换为数组中的关联数组(python中的dict中的dict)形式

The data is in json format casting to associative array in array (dict inside dict in python) form

假设我要代表这个矩阵:

Let's say I want to represent this matrix:

[ [0, 0, 0],
  [1, 0, 5],
  [2, 0, 0] ]

在json中，其存储方式为:

In json it's stored like:

{"3": {"1": 2}, "2": {"1": 1, "3": 5}}

例如，"3": {"1": 2}表示第3行和第1列中的数字是2.

Which for example "3": {"1": 2} means the number in 3rd row and 1st column is 2.

我希望输出与json相同，但由2(矩阵乘法)支持

I want the output to be the same as json, but powered by 2 (matrix multiplication)

编程语言并不重要.我想以最快的方式进行计算(如果可能，请少于2天)

The programming language isn't important. I want to calculate it the fastest way (less than 2 days, if possible)

所以我尝试在python(numpy.linalg.matrix_power)中使用Numpy，但似乎不适用于我嵌套的未排序dict格式.

So I tried to use Numpy in python (numpy.linalg.matrix_power), but it seems that it doesn't work with my nested unsorted dict format.

我写了一个简单的python代码来做到这一点，但我估计需要18天才能完成:

I wrote a simple python code to do that but I estimated that it would take 18 days to accomplish:

jsonFileName = "file.json"
def matrix_power(arr):
    result = {}
    for x1,subarray in arr.items():
        print("doing item:",x1)
        for y1,value1 in subarray.items():
            for x2,subarray2 in arr.items():
                if(y1 != x2):
                    continue
                for y2,value2 in subarray2.items():
                    partSum = value1 * value2
                    result[x1][y2] = result.setdefault(x1,{}).setdefault(y2,0) + partSum

    return result

import json
with open(jsonFileName, 'r') as reader: 
    jsonFile = reader.read()
    print("reading is succesful")
    jsonArr = json.loads(jsonFile)
    print("matrix is in array form")
    matrix = matrix_power(jsonArr)
    print("Well Done! matrix is powered by 2 now")
    output = json.dumps(matrix)
    print("result is in json format")
    writer = open("output.json", 'w+')
    writer.write(output)
    writer.close()
print("Task is done! you can close this window now")

这里，X1，Y1是第一个矩阵的行和列，然后乘以第二个矩阵的相应元素(X2，Y2).

Here, X1,Y1 is the row and col of the first matrix which then is multiplied by the corresponding element of the second matrix (X2,Y2).

推荐答案

Numpy并不是问题，您需要以numpy可以理解的格式输入它，但是由于您的矩阵很大，因此可能不适合在内存中，因此使用稀疏矩阵(scipy.sparse.csr_matrix)可能是一个好主意:

Numpy is not the problem, you need to input it on a format that numpy can understand, but since your matrix is really big, it probably won't fit in memory, so it's probably a good idea to use a sparse matrix (scipy.sparse.csr_matrix):

m = scipy.sparse.csr_matrix((
    [v for row in data.values() for v in row.values()], (
        [int(row_n) for row_n, row in data.items() for v in row],
        [int(column) for row in data.values() for column in row]
    )
))

那只是做一件事情:

m**2

这篇关于由2驱动的非常大的方阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！