四方密码加解密程序优化：二维数组非嵌套循环遍历方案咨询

Hey there! Great question about optimizing your foursquare cipher implementation—let’s dive into how you can ditch those nested loops and speed things up dramatically.

The root issue with your current nested loop approach is that you’re repeatedly scanning the 5x5 matrices to find the position of each character, which adds unnecessary O(25) overhead per character. The fix is to precompute a character-to-coordinate lookup table that lets you jump directly to a character’s (row, column) position in constant time (O(1)), eliminating the need for nested loops entirely.

Here’s the step-by-step optimization plan: #

1. Prebuild Character-to-Coordinate Maps

First, create a dictionary (or array-based map, since we’re dealing with a fixed set of 25 letters) for each of your four foursquare matrices. This map will map every character to its (row, column) index in the matrix. You only need to build these maps once at the start of your program, not per encryption/decryption.

Example (using Python for clarity, but this translates to any language):

def build_char_coordinate_map(matrix):
    char_map = {}
    for row_idx, row in enumerate(matrix):
        for col_idx, char in enumerate(row):
            char_map[char] = (row_idx, col_idx)
    return char_map

# Example standard 5x5 matrix (I/J combined)
standard_matrix = [
    ['A','B','C','D','E'],
    ['F','G','H','I','K'],
    ['L','M','N','O','P'],
    ['Q','R','S','T','U'],
    ['V','W','X','Y','Z']
]

# Build maps for all four foursquare matrices
left_top_map = build_char_coordinate_map(left_top_matrix)
right_top_map = build_char_coordinate_map(right_top_matrix)
left_bottom_map = build_char_coordinate_map(left_bottom_matrix)
right_bottom_map = build_char_coordinate_map(right_bottom_matrix)

2. Replace Nested Loop Lookups with Direct Lookups

Once you have these maps, processing each bigram becomes a series of O(1) operations—no loops needed to find character positions. For each bigram (p1, p2):

• Look up p1’s coordinates in the left-top matrix using left_top_map[p1]
• Look up p2’s coordinates in the right-bottom matrix using right_bottom_map[p2]
• Fetch the encrypted characters from the right-top matrix (using p1’s row and p2’s column) and left-bottom matrix (using p2’s row and p1’s column)

3. Use a Single Loop to Process Bigrams

The only loop you’ll need is a single pass over your list of bigrams to apply the above logic. No nested loops anywhere in the critical encryption path.

Example encryption function:

def encrypt_bigram(p1, p2, right_top_matrix, left_bottom_matrix, left_top_map, right_bottom_map):
    # Get coordinates in constant time
    r1, c1 = left_top_map[p1]
    r2, c2 = right_bottom_map[p2]
    # Apply foursquare cipher rule
    c1_char = right_top_matrix[r1][c2]
    c2_char = left_bottom_matrix[r2][c1]
    return (c1_char, c2_char)

def encrypt_content(content, right_top_matrix, left_bottom_matrix, left_top_map, right_bottom_map):
    # Preprocess content: uppercase, filter non-letters, pad if odd length
    processed = [c.upper() for c in content if c.isalpha()]
    if len(processed) % 2 != 0:
        processed.append('X')  # Standard padding character
    
    cipher_chars = []
    # Single loop to process all bigrams
    for i in range(0, len(processed), 2):
        p1, p2 = processed[i], processed[i+1]
        cipher_b1, cipher_b2 = encrypt_bigram(p1, p2, right_top_matrix, left_bottom_matrix, left_top_map, right_bottom_map)
        cipher_chars.extend([cipher_b1, cipher_b2])
    
    return ''.join(cipher_chars)

Why This Works So Much Better #

• Eliminates redundant work: Instead of scanning the entire 5x5 matrix for every character, you look up coordinates in O(1) time. For large files, this cuts down runtime drastically.
• Simplifies code: The logic becomes more readable, with clear separation between preprocessing and encryption.
• Scales better: Even if you were to use larger matrices (though foursquare uses 5x5 by design), this approach remains efficient.

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