ترانهاده‌ی سریع ماتریس خلوت

ماتریس خلوت را به‌صورت سه‌تایی‌های (سطر، ستون، مقدار) نگه می‌دارد و ترانهاده‌اش را بدون مرتب‌سازی، با شمردن جمله‌های هر ستون، در O(ستون‌ها + جمله‌ها) می‌سازد.

ماتریسی که بیشتر خانه‌هایش صفر است (خلوت) را بهتر است فقط با جمله‌های ناصفرش نگه داشت: فهرستی از سه‌تایی‌های (سطر، ستون، مقدار) که سطر به سطر مرتب‌اند.

ادامه‌ی توضیح ↓

زمان: O(cols + terms)
حافظه: O(cols + terms)
هوروویتز–ساهنی، فصل ۲

ورودی:

A 6×6خروجی PDF

ماتریس ۶×۶ با ۸ جمله‌ی ناصفر؛ ترانهاده با دو گذر روی جمله‌ها ساخته می‌شود.

def fast_transpose(A):
rows, cols = len(A), len(A[0])
# The sparse form: one (row, column, value) triple per non-zero, row by row.
terms = [(i, j, A[i][j]) for i in range(rows) for j in range(cols) if A[i][j] != 0]
# 1. How many terms each column has, and where its block starts in the result.
row_terms = [0] * cols
for _, j, _ in terms:
row_terms[j] = row_terms[j] + 1
start = [0] * cols
for j in range(1, cols):
start[j] = start[j - 1] + row_terms[j - 1]
# 2. Drop each term straight into its place, swapping row and column.
b = [None] * len(terms)
for i, j, v in terms:
b[start[j]] = (j, i, v)
start[j] = start[j] + 1
return b

ناوردا: start[j] همیشه اولین جای خالی بلوک ستون j در b است؛ چون سه‌تایی‌ها سطر به سطر می‌آیند، هر بلوک مرتب پر می‌شود.

شروع اجرا

row_terms—

start—

terms

جدول هنوز خالی است.

متغیرهای محلی

نارنجی = در همین گام عوض شد

`A` list

[15, 0, 0, 22, 0, -15][0, 11, 3, 0, 0, 0][0, 0, 0, -6, 0, 0][0, 0, 0, 0, 0, 0][91, 0, 0, 0, 0, 0][0, 0, 28, 0, 0, 0]

Call stack

fast_transpose()خط 1

گام ۱ از ۶۰

توضیح

ایده