giảm yêu cầu bộ nhớ cho danh sách kề

Question

Tôi đang sử dụng adjacency_list < vecS, vecS, bidirectionalS ...> rộng rãi. Tôi có quá nhiều đồ thị được tải cùng một lúc khiến bộ nhớ trở thành sự cố. Tôi đang thực hiện phân tích chương trình tĩnh và lưu trữ các đồ thị và đồ thị đồ họa của các phân tách nhị phân trong đồ thị tăng cường. Vì vậy, tôi có thể có hàng chục nghìn chức năng == biểu đồ và một đồ họa khổng lồ. Tôi thực sự muốn giảm mức sử dụng bộ nhớ cho các đồ thị của mình trong khi vẫn sử dụng BGL.

Vì đồ thị của tôi là tĩnh sau khi tải và cạnh và số lượng đỉnh được biết trước, tôi thấy tiềm năng lớn để tối ưu hóa. Đối với ví dụ , tôi muốn phân bổ một bộ đệm duy nhất cho tất cả các đỉnh/cạnh của một biểu đồ và để đồ thị chỉ lưu trữ các chỉ mục vào bộ đệm đó.

câu hỏi khác:
1) chi phí bộ nhớ của việc sử dụng thuộc tính đỉnh và cạnh là gì? Tôi có khá nhiều người trong số họ.
2) có thể thuyết phục BGL sử dụng thu nhỏ để phù hợp với thành ngữ không? Theo tôi hiểu, danh sách kề nhau sử dụng push_back để thêm cạnh. Có thể giảm sử dụng bộ nhớ bằng cách hoán đổi véc tơ kết quả với bản sao của chính nó không? Có thể bằng cách sao chép toàn bộ đồ thị ?
3) Có thể sử dụng bộ phân bổ tăng cường pool với BGL không? Theo như như tôi có thể nói với BGL hiện đang thực hiện rất nhiều phân bổ nhỏ - Tôi thực sự muốn tránh điều đó vì lý do không gian và hiệu suất thời gian chạy.

Có ai đã xây dựng phiên bản BGL được tối ưu hóa để sử dụng bộ nhớ không? Tôi có nên thử sử dụng cấu trúc đồ thị hiện có và tăng thêm phân bổ tùy chỉnh hoặc somesuch hoặc thực hiện việc thực hiện của riêng mình và cố gắng giữ giao diện tương thích với BGL để Tôi có thể tiếp tục sử dụng thuật toán của nó?

Trân trọng,

Sören 

Answer 1

Có một loại biểu đồ ít được biết đến được gọi là biểu đồ "hàng thưa thớt" trong BGL. Nó có vẻ khá mới và không được liên kết từ các trang chỉ mục. Tuy nhiên nó sử dụng một mẹo nhỏ đẹp để có được biểu diễn đồ thị càng nhỏ càng tốt. http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

Sử dụng điều này cho một số biểu đồ của chúng tôi Tôi đã có thể giảm tổng mức sử dụng bộ nhớ xuống 20% ​​- do đó, đây thực sự là một tối ưu hóa rất đáng giá.

Nó cũng lưu trữ các thuộc tính đỉnh/cạnh trong vectơ, do đó, cung cấp chi phí nhỏ nhất có thể cho những người đó.

Lưu ý rằng vận chuyển phiên bản có mức tăng mới nhất 1.40 chỉ hỗ trợ đồ thị định hướng (trái ngược với hai hướng). Nếu bạn cần để có thể hiệu quả lặp qua một đỉnh của các cạnh và trong các cạnh (như tôi đã làm), bạn cần phải kiểm tra các thân cây tăng từ lật đổ. Jeremiah rất hữu ích khi thêm tính năng đó vào yêu cầu của tôi.

Answer 2

Kể từ BGL được thiết kế để interoperate with legacy or custom graphs, có lẽ bạn đang giảm giá tốt nhất bằng văn bản đồ của riêng bạn.

Answer 3

1. Chi phí phụ thuộc vào phiên bản bạn đang sử dụng và liệu bạn có đi đến các thuộc tính "được nhóm" hay không. Tôi đã chỉ sử dụng các thuộc tính đi kèm và đọc mã tôi mong đợi mỗi gói thuộc tính chi phí cho bạn 2 con trỏ + kích thước của loại bó bạn đang sử dụng + sizeof của mỗi thuộc tính được đính kèm. Không có công cụ kiểm tra khái niệm nào được để lại trong phần tử nhị phân. Vì bạn có mã mặc dù, tại sao không chỉ đo lường chi phí? Nếu bạn không có bất kỳ công cụ nào để giúp thử chỉ tạo biểu đồ có kích thước đã biết trong bộ đệm có kích thước đã biết. Một cái gì đó sẽ thất bại cuối cùng và vào thời điểm đó bạn nên có đếm.

2. Bạn đã thử gọi adjacency_list<blah>.swap(adjacency_list& x) chưa? Tôi hy vọng rằng sẽ thu nhỏ các thùng chứa một cách thích hợp.

3. ???

Tôi bắt đầu viết một cái gì đó giống như hệ thống bạn mô tả, nhưng cuối cùng đã bỏ BGL và chuyển sang mã hóa thuật toán của riêng tôi để chạy trên cơ sở dữ liệu sqlite của tất cả các ký hiệu liên kết.

Answer 4

Là một câu trả lời cho:

3) Có thể sử dụng allocators tăng hồ bơi với các BGL? Theo như tôi có thể nói BGL hiện đang thực hiện rất nhiều phân bổ nhỏ - tôi thực sự muốn tránh điều đó vì không gian và lý do hiệu quả thời gian chạy.

Mã sao chép từ here:

template <class Allocator> 
    struct list_with_allocatorS { }; 

    namespace boost { 
    template <class Alloc, class ValueType> 
    struct container_gen<list_with_allocatorS<Alloc>, ValueType> 
    { 
     typedef typename Alloc::template rebind<ValueType>::other Allocator; 
     typedef std::list<ValueType, Allocator> type; 
    }; 
    } 

    // now you can define a graph using std::list 
    // and a specific allocator 
    typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;