Cách hiệu quả nhất để xác định ma trận mạng rất thưa thớt ở Julia là gì?

Question

Tôi có dữ liệu cho một mạng rất lớn khá thưa thớt. Tôi đã tự hỏi những gì sẽ là cách hiệu quả nhất bộ nhớ để lưu trữ và dễ dàng nhất để truy cập cho dù hai nút được kết nối.

Rõ ràng với N nút, việc giữ ma trận N * N không hiệu quả về mặt không gian tôi lưu trữ. Vì vậy, tôi nghĩ có lẽ giữ danh sách kề như dưới đây:

Array(Vector{Int64}, N_tmp) 

đâu N_tmp < = N, như nhiều nút có thể không có bất kỳ kết nối.

Bạn có thể giúp tôi xem có cách nào tốt hơn hoặc có thể gói tốt hơn về bộ nhớ và quyền truy cập không?

Answer 1

Trong LightGraphs.jl, chúng tôi sử dụng danh sách kề (về cơ bản, một vec tơ vectơ) để lưu trữ hàng xóm cho mỗi nút. Điều này cung cấp việc sử dụng bộ nhớ rất tốt cho các đồ thị thưa thớt lớn, cho phép chúng ta mở rộng tới hàng trăm triệu nút trên phần cứng hàng hóa, trong khi cung cấp truy cập nhanh để đánh bại cấu trúc dữ liệu ma trận thưa thớt nguyên bản cho hầu hết các hoạt động biểu đồ.

Bạn có thể xem xét liệu LightGraphs có đáp ứng nhu cầu của bạn trực tiếp hay không.

Chỉnh sửa với thông tin bổ sung: chúng tôi lưu trữ danh sách hàng xóm được sắp xếp - điều này mang lại cho chúng tôi hiệu suất khi tạo cạnh, nhưng sẽ nhanh hơn để thực hiện các lần tra cứu tiếp theo.