Cấu trúc dữ liệu nào sẽ sử dụng?

Question

Tôi cần một cấu trúc dữ liệu với các thuộc tính sau:

• Tiếp cận các yếu tố cần phải hết sức nhanh
• Elements, mà không được thêm vào, không nên mất trí nhớ (như lý tưởng, kích thước của cấu trúc rỗng gần zero)
• Mỗi phần tử có hai tọa độ số nguyên (x, y) (truy cập đến các yếu tố duy nhất của họ)
• đếm tối đa yếu tố được biết đến vào thời gian tạo (hơn 10^3)
• phần tử chứa vài phao đánh giá cao

Sẽ tốt nếu bạn cũng hướng đến việc triển khai cấu trúc này trong C hoặc C++.

Answer 1

Kiểm tra điều này - bạn có thể thay đổi loại thành phần thành float nếu điều này làm mọi thứ bạn muốn.

Concise Sparse Matrix Package in C

Đối với C++ bạn có thể sử dụng Boost.uBLAS - chi tiết sparse_matrix here.

Answer 2

Bạn đang tìm kiếm sparse matrix?

Answer 3

Nếu X và Y của bạn tương đối nhỏ thì mảng con trỏ hai chiều sẽ hoạt động. 10000 con trỏ sẽ là 40K trong mã 32 bit.

Answer 4

 

typdef ElementAccessor std::pair<int, int>; 

struct Element 
{ 
    float f1; 
    float f2; 
    //etc. 

}; 

std::map< ElementAccessor, Element > myElementMap; 

Bây giờ bạn có thể sử dụng bản đồ này như một ma trận. ElementAccessor đề cập đến x, y. Chỉ cần đảm bảo xem liệu phần tử có tồn tại trong bản đồ hay không trước khi bạn cố gắng truy cập nó hoặc một phần tử được tạo theo mặc định.

http://www.cplusplus.com/reference/std/utility/pair/ http://www.cplusplus.com/reference/stl/map/find/

chỉnh sửa: khung mẫu được hiển thị cho bản đồ. loại khóa bản đồ là ElementAccessor, giá trị là Element. Ngoài ra, đối với các cặp, templating là int, int.