Chuyển tiếp mảng 2D

Question

Làm thế nào để bạn chuyển đổi hiệu quả ma trận? Có thư viện cho việc này hay bạn sẽ sử dụng thuật toán nào?

Ví dụ:

short src[W*H] = { 
    {1,2,3}, 
    {4,5,6} 
}; 
short dest[W*H]; 


rotate_90_clockwise(dest,src,W,H); //<-- magic in here, no need for in-place 

//dest is now: 

{ 
    {4, 1}, 
    {5, 2}, 
    {6, 3} 
}; 

(Trong trường hợp cụ thể của tôi mảng src của nó là dữ liệu hình ảnh thô, và điểm đến là một bộ đệm khung, và tôi nhúng trên ARM trên toolchain mà không hỗ trợ lắp ráp)

Answer 1

Có một số thư viện cho điều này, trong một số trường hợp. Và, đáng chú ý, có những thủ thuật bạn có thể chơi với dữ liệu vectơ (ví dụ, bốn phần tử 32 bit trong vectơ 128 bit, nhưng điều này cũng áp dụng cho bốn byte 8 bit trong thanh ghi 32 bit) để đi nhanh hơn cá nhân truy cập -element.

Để chuyển vị trí, ý tưởng tiêu chuẩn là bạn sử dụng hướng dẫn "trộn", cho phép bạn tạo một vectơ dữ liệu mới trong số hai vectơ hiện có, theo thứ tự bất kỳ. Bạn làm việc với các khối 4x4 của mảng đầu vào. Vì vậy, bắt đầu, bạn có:

v0 = 1 2 3 4 
v1 = 5 6 7 8 
v2 = 9 A B C 
v3 = D E F 0 

Sau đó, bạn áp dụng hướng dẫn ngẫu nhiên vào hai vectơ đầu tiên (đan xen các yếu tố kỳ quặc của họ, A0B0 c0d0 -> ABCD, và đan xen thậm chí yếu tố của họ, 0A0B 0C0D -> ABCD) , và hai cuối cùng, để tạo ra một bộ mới của vectơ với mỗi khối 2x2 hoán:

1 5 3 7 
2 6 4 8 
9 D B F 
A E C 0 

cuối cùng, bạn áp dụng hướng dẫn ngẫu nhiên để cặp lẻ và cặp thậm chí (kết hợp cặp đầu tiên của các yếu tố, AB00 CD00 -> ABCD và các cặp cuối cùng của chúng, 00AB 00CD -> ABCD), để nhận được:

1 5 9 D 
2 6 A E 
3 7 B F 
4 8 C 0 

Và ở đó, 16 phần tử được chia thành tám hướng dẫn! Bây giờ, đối với các byte 8 bit trong thanh ghi 32 bit, ARM không có chỉ dẫn trộn chính xác, nhưng bạn có thể tổng hợp những gì bạn cần với ca và lệnh SEL (chọn) và tập hợp ngẫu nhiên thứ hai của bạn có thể làm trong một hướng dẫn với các lệnh PKHBT (gói nửa đầu dưới cùng) và hướng dẫn PKHTB (đóng nửa đầu từ trên).

Cuối cùng, nếu bạn đang sử dụng một bộ xử lý ARM lớn với véc tơ NEON, bạn có thể làm điều gì đó như thế này với vectơ 16 phần tử trên khối 16x16.

Answer 2

Một giải pháp rất đơn giản hoạt động trong O (1) là tiết kiệm một boolean bổ sung cho ma trận, cho biết liệu nó có 'transposed' hay không. Sau đó truy cập vào mảng sẽ được thực hiện theo boolean này (hàng/col hoặc col/hàng).

Tất nhiên, nó sẽ cản trở việc sử dụng bộ nhớ cache của bạn. Vì vậy, nếu bạn có nhiều thao tác chuyển đổi, và một vài "traversals hoàn chỉnh" (trong đó, btw, cũng có thể được sắp xếp lại theo giá trị của boolean), đây là lựa chọn tốt nhất của bạn.

Answer 3

• Nếu ma trận là hình vuông hoặc nếu bạn không tìm kiếm một chuyển vị inplace nó thực sự dễ dàng:

Về cơ bản bạn lặp trên dây chuyền và trao đổi tất cả các mục có phù hợp với mục cột. Bạn nhận được mục phù hợp bằng cách trao đổi các chỉ mục hàng và cột. Khi bạn đã xử lý tất cả các chuyển vị cột được hoàn thành. Bạn cũng có thể đi theo cách khác xung quanh và lặp lại trên cột.

Nếu bạn muốn tăng hiệu suất, bạn có thể sao chép toàn bộ dòng vào một mảng tạm thời và cột khớp hoàn toàn thành một cột khác, sau đó sao chép chúng trở lại. Nó sẽ nhanh hơn một chút (ngay cả khi chiến lược này liên quan đến một nhiệm vụ thay đổi nhiều hơn) nếu bạn sử dụng một memcopy cho chuyển giao liên quan đến yếu tố trong cùng.

• Nếu ma trận không vuông (như trong ví dụ của bạn) thì thật là khó để làm điều đó tại chỗ. Vì transposing không thay đổi bộ nhớ nên nó vẫn có thể làm điều đó tại chỗ, nhưng nếu bạn làm điều đó bất cẩn, bạn sẽ kết thúc việc ghi đè lên các phần tử của một dòng hoặc cột khác.

Nếu bộ nhớ không phải là nút cổ chai, tôi khuyên dùng ma trận tạm thời. Nó thực sự dễ dàng hơn và nó có lẽ sẽ nhanh hơn.

• Phương pháp tốt nhất không chuyển vị chút nào nhưng chỉ đặt cờ ở đâu đó nêu rõ nếu bạn truy cập dữ liệu hàng đầu tiên hoặc cột đầu tiên. Trong hầu hết các trường hợp, các thuật toán cần chuyển đổi có thể được viết lại để truy cập vào ma trận không được chuyển đổi như thể nó. Để đạt được điều này, bạn chỉ cần phải viết lại một số hoạt động cơ bản như các sản phẩm ma trận để chấp nhận ma trận với một định hướng hoặc một định hướng khác.

Nhưng trong một số trường hợp, tôi hiểu điều này sẽ không thể thực hiện được, thông thường nếu dữ liệu đang được chuẩn bị để một số phần cứng hoặc thư viện hiện có truy cập.

Answer 4

Wikipedia có entire article trên chuyển vị ma trận tại chỗ. Đối với ma trận không vuông, đó là một vấn đề không nhỏ, khá thú vị (trong khi sử dụng ít hơn O (N x M) bộ nhớ, đó là). Bài viết có liên kết đến một vài bài báo với các thuật toán, cũng như một số mã nguồn.

Xem xét mặc dù - như tôi đã nói trong nhận xét cho câu hỏi của bạn, minh họa của bạn là không phải của chuyển vị tiêu chuẩn, tất cả các thuật toán sẽ được viết.

(Một chức năng chuyển vị tiêu chuẩn sẽ cho kết quả này cho dữ liệu ví dụ của bạn :)

{ 
    {1, 4}, 
    {2, 5}, 
    {3, 6} 
}; 

Nếu bạn chỉ làm điều này để hiển thị một hình ảnh trên một màn hình, bạn có thể giảm giá tốt nhất chỉ làm chuyển vị khi bạn sao chép hình ảnh vào bộ đệm phía sau, thay vì chuyển đổi tại chỗ và sau đó nhấp nháy.

Answer 5

Chỉ cần một bản sao đơn giản để tạm thời và sao chép lại, transposing khi bạn đi, sử dụng con trỏ bước để tránh nhân trong tính toán địa chỉ, và vòng lặp bên trong trải ra:

char temp[W*H]; 
char* ptemp = temp; 
memcpy(temp, array, sizeof(char)*W*H); 
for (i = 0; i < H; i++){ 
    char* parray = &array[i]; 
    for (j = 0; j+8 <= W; j += 8, ptemp += 8){ 
     *parray = ptemp[0]; parray += H; 
     *parray = ptemp[1]; parray += H; 
     *parray = ptemp[2]; parray += H; 
     *parray = ptemp[3]; parray += H; 
     *parray = ptemp[4]; parray += H; 
     *parray = ptemp[5]; parray += H; 
     *parray = ptemp[6]; parray += H; 
     *parray = ptemp[7]; parray += H; 
    } 
    for (; j < W; j++, parray += H){ 
     *parray = *ptemp++; 
    } 
} 

Tôi không biết làm thế nào để tránh các vấn đề địa phương bộ nhớ cache vì bản chất của vấn đề.

Answer 6

Giải pháp hiệu quả nhất ở đây là xoay dữ liệu khi dữ liệu được sao chép từ RAM sang bộ đệm khung. Xoay nguồn trong RAM và sau đó sao chép kết quả vào bộ đệm khung, sẽ tốt nhất, bằng một nửa tốc độ của phiên bản sao chép và xoay. Vì vậy, câu hỏi là, là nó hiệu quả hơn để đọc tuần tự và viết ngẫu nhiên hoặc đọc ngẫu nhiên và viết tuần tự.Trong mã, đây sẽ là sự lựa chọn giữa:

// read sequential 
src = { image data } 
dest = framebuffer 
for (y = 0 ; y < H ; ++y) 
{ 
    for (x = 0 ; x < W ; ++x) 
    { 
    pixel = *src++ 
    dest [y,x] = pixel 
    } 
} 

hay:

// write sequential 
src = { image data } 
dest = framebuffer 
for (x = 0 ; x < W ; ++x) 
{ 
    for (y = 0 ; y < H ; ++y) 
    { 
    pixel = src [x,y] 
    *dest++ = pixel 
    } 
} 

Câu trả lời cho điều này chỉ có thể được xác định bởi profiling mã. Bây giờ, nó có thể là bạn có một GPU trong trường hợp nó chắc chắn sẽ có khả năng làm quay và nó sẽ hiệu quả hơn nhiều để cho GPU làm xoay khi blitting hình ảnh vào màn hình.