如何加速从文件读取矩阵并执行矩阵乘法运算？

Hey there! Let's break down how to solve this problem efficiently—focusing on both fast file parsing and optimized matrix computation, since you mentioned wanting to speed things up.

Understanding the Input Format #

First, let's recap the input structure to make sure we're on the same page:

Example input string: 3 2 1 2 1 2 3 4 4 2 1 3 1 2 2 1

• First two values: Number of matrices (≤130) and order of square matrices (≤130)
• Next two values: 1-based indices (i,j) for the element we need from the final product matrix
• Remaining values: Flattened row-wise elements for each matrix in sequence

Key Optimizations for Speed #

The biggest win here is avoiding full matrix multiplication. Since we only need a single element from the final product, we don't have to compute every entry of the intermediate or final matrices. Here's why that matters:

• A full product of k n×n matrices takes O(k*n³) time.
• Calculating just the target element takes O(k*n²) time—way faster as n grows.

Other speed tweaks:

• Batch file reading: Read the entire file at once instead of line-by-line to minimize slow I/O operations.
• Use optimized libraries: For Python, leveraging NumPy's C-backed operations will outperform pure Python loops for large matrices.

Implementation #

Step 1: Fast Input Parsing #

First, we'll read and parse the input file efficiently:

def read_input(file_path):
    with open(file_path, 'r') as f:
        # Read entire file at once, split into integers
        data = list(map(int, f.read().split()))
    
    ptr = 0
    matrix_count = data[ptr]
    ptr += 1
    n = data[ptr]
    ptr += 1
    # Convert 1-based indices to 0-based for easier array access
    target_i = data[ptr] - 1
    ptr += 1
    target_j = data[ptr] - 1
    ptr += 1
    
    # Parse each matrix (row-wise)
    matrices = []
    for _ in range(matrix_count):
        matrix = []
        for _ in range(n):
            row = data[ptr:ptr + n]
            matrix.append(row)
            ptr += n
        matrices.append(matrix)
    
    return matrices, target_i, target_j

Step 2: Compute Target Element (Pure Python) #

This implementation tracks only the row relevant to our target element, updating it as we multiply with each subsequent matrix:

def compute_target_element(matrices, target_i, target_j):
    n = len(matrices[0])
    # Start with the target row from the first matrix
    current_row = matrices[0][target_i].copy()
    
    for mat in matrices[1:]:
        new_row = [0] * n
        # Transpose the matrix to access columns as rows (faster dot product)
        mat_transposed = list(zip(*mat))
        for col_idx in range(n):
            # Dot product of current row and matrix column
            new_row[col_idx] = sum(a * b for a, b in zip(current_row, mat_transposed[col_idx]))
        current_row = new_row
    
    return current_row[target_j]

Step 3: Faster NumPy Version #

For large matrices, NumPy's optimized operations will be significantly faster. Here's the equivalent implementation:

import numpy as np

def compute_target_element_numpy(matrices, target_i, target_j):
    # Convert matrices to NumPy arrays (use int64 to avoid overflow)
    np_matrices = [np.array(mat, dtype=np.int64) for mat in matrices]
    # Start with the target row from the first matrix
    current_vector = np_matrices[0][target_i, :]
    
    # Multiply the row vector with each subsequent matrix
    for mat in np_matrices[1:]:
        current_vector = current_vector @ mat
    
    return current_vector[target_j]

Step 4: Main Execution #

Put it all together:

if __name__ == "__main__":
    matrices, ti, tj = read_input("input.txt")
    # Use pure Python version or NumPy version for speed
    result = compute_target_element(matrices, ti, tj)
    # result = compute_target_element_numpy(matrices, ti, tj)
    print(result)

Testing with the Example Input #

For the example input:

• The product matrix is [[22, 20], [52, 50]]
• The target element at (1,2) (0-based (0,1)) is 20, which the code will output correctly.

内容的提问来源于stack exchange，提问作者pazukdev