cách hiệu quả để biểu diễn ma trận tam giác dưới/trên

Question

Tôi đang làm việc trên dữ liệu của mình trong chương trình C/C++, là 2 chiều. Ở đây giá trị của tôi được tính cho giá trị khôn ngoan và giá trị ở đây sẽ giống nhau cho foo[i][j] và foo[j][i].

Vì vậy, nếu tôi thực hiện nó bằng cách sử dụng mảng 2 chiều đơn giản, một nửa không gian của tôi sẽ bị lãng phí. Vì vậy, những gì sẽ là cấu trúc dữ liệu tốt nhất để đại diện cho ma trận tam giác dưới/trên này.

Kính trọng,

Answer 1

Thực sự, tốt nhất bạn nên sử dụng ma trận hai chiều thông thường. RAM khá rẻ. Nếu bạn thực sự không muốn làm điều đó, thì bạn có thể xây dựng một mảng một chiều với số lượng phần tử phù hợp và sau đó tìm ra cách truy cập từng phần tử. Ví dụ, nếu mảng được cấu trúc như thế này:

j 
    1234 
i 1 A 
    2 BC 
    3 DEF 
    4 GHIJ 

và bạn có nó được lưu trữ như một mảng chiều, trái sang phải, bạn sẽ truy cập vào yếu tố C(2, 2) với array[3]. Bạn có thể làm việc ra một chức năng để đi từ [i][j] đến [n] nhưng tôi sẽ không làm hỏng niềm vui của bạn. Nhưng bạn không phải làm điều này trừ khi mảng hình tam giác được đề cập thực sự rất lớn hoặc bạn rất quan tâm đến không gian.

Answer 2

Sử dụng một mảng lởm chởm:

int N; 
// populate N with size 

int **Array = new Array[N]; 
for(int i = 0; i < N; i++) 
{ 
    Array[i] = new Array[N - i]; 
} 

nó sẽ tạo ra mảng như

0 1 2 3 4 5 
0 [   ] 
1 [   ] 
2 [  ] 
3 [  ] 
4 [ ] 
5 [ ] 

Answer 3

Nếu bạn có N mặt hàng sau đó một mảng tam giác thấp hơn mà không có đường chéo chính sẽ có (N - 1) * N/2 phần tử, hoặc (N + 1) * N/2 phần tử với đường chéo chính. Không có đường chéo chính, (I, J) (I, J ∈ 0..N-1, I> J) ⇒ (I * (I - 1)/2 + J). Với đường chéo chính, (I, J ∈ 0..N-1, I ≥ J) ⇒ ((I + 1) * I/2 + J).

(Và vâng, khi bạn đang phân bổ 4 gigabyte trên một máy 2,5 gigabyte, cắt nó một nửa không tạo sự khác biệt rất lớn.)

Answer 4

Số lượng các yếu tố độc đáo, m, cần thiết để được đại diện trong một n của ma trận n đối xứng:

với chính chéo

m = (n*(n + 1))/2

Nếu không có đường chéo (đối với ma trận đối xứng như OP mô tả, chính đường chéo là cần thiết, nhưng chỉ để đo tốt ...)

m = (n*(n - 1))/2.

Không chia cho 2 cho đến khi thao tác cuối cùng là quan trọng nếu số học số nguyên với cắt ngắn được sử dụng.

Bạn cũng cần thực hiện một số phép tính để tìm chỉ mục, i, trong bộ nhớ được phân bổ tương ứng với hàng x và cột y trong ma trận đường chéo.

Index trong bộ nhớ được phân bổ, i, của hàng x và cột y trong trên ma trận đường chéo:

Với đường chéo

i = (y*(2*n - y + 1))/2 + (x - y - 1) 

Nếu không có đường chéo

i = (y*(2*n - y - 1))/2 + (x - y -1) 

Đối với một ma trận đường chéo thấp hơn x và y trong các phương trình. Đối với ma trận đối xứng, chỉ cần chọn x> = y hoặc y> = x nội bộ và có chức năng thành viên khi cần.

Answer 5

Riffing về câu trả lời của Dani ...

Thay vì bố trí nhiều mảng của các kích cỡ khác nhau, có thể dẫn đến phân mảnh bộ nhớ hoặc truy cập bộ nhớ cache lạ mô hình, bạn có thể phân bổ một mảng để chứa các dữ liệu và một mảng nhỏ để giữ con trỏ đến các hàng trong phân bổ đầu tiên.

const int side = ...; 
T *backing_data = new T[side * (side + 1)/2]; // watch for overflow 
T **table = new T*[side]; 
auto p = backing_data; 
for (int row = 0; row < side; ++row) { 
    table[row] = p; 
    p += side - row; 
} 

Bây giờ bạn có thể sử dụng table như thể nó là một mảng lởm chởm như trong Dani của câu trả lời:

table[row][col] = foo; 

Nhưng tất cả các dữ liệu trong một khối duy nhất, mà nó có thể không nếu không được tùy thuộc vào chiến lược của người cấp phát của bạn.

Sử dụng bảng con trỏ hàng có thể hoặc không thể nhanh hơn tính toán bù trừ bằng cách sử dụng công thức của Praxeolitic.

Answer 6

Trong câu trả lời Adrian McCarthy, thay thế

p += side - row; 

với

p += row + 1; 

cho một ma trận tam giác thấp hơn thay vì một người trên.

Answer 7

Vì Dan và Praxeolitic đề xuất ma trận hình tam giác thấp hơn với đường chéo nhưng với quy tắc chuyển đổi được sửa.

Đối với ma trận n theo n, bạn cần mảng (n+1)*n/2 độ dài và quy tắc chuyển đổi là Matrix[i][j] = Array[i*(i+1)/2+j].

#include<iostream> 
#include<cstring> 

struct lowerMatrix { 
    double* matArray; 
    int sizeArray; 
    int matDim; 

    lowerMatrix(int matDim) { 
    this->matDim = matDim; 
    sizeArray = (matDim + 1)*matDim/2; 
    matArray = new double[sizeArray]; 
    memset(matArray, .0, sizeArray*sizeof(double)); 
    }; 

    double &operator()(int i, int j) { 
    int position = i*(i+1)/2+j; 
    return matArray[position]; 
    }; 
}; 

Tôi đã làm điều đó với double nhưng bạn có thể làm điều đó là template. Đây chỉ là bộ xương cơ bản nên đừng quên triển khai destructor.