Tôi đang làm việc với một cấu trúc cây không nhỏ (đó là một Burkhard-Keller-Tree,> 100 MB trong bộ nhớ) được thực hiện trong C + +. Các con trỏ đến con của mỗi nút được lưu trữ trong một QHash.Cách nhanh nhất để deserialize một cây trong C++
Mỗi nút x có n con y [1] ... y [n], các cạnh của trẻ được gắn nhãn với khoảng cách chỉnh sửa d (x, y [i]), do đó, sử dụng băm để lưu trữ nút là một giải pháp rõ ràng.
class Node {
int value;
QHash<int, Node*> children;
/* ... */
};
Tôi cũng muốn tuần tự hóa và deserialize nó thành một tệp (Tôi hiện đang sử dụng QDataStream). Cây chỉ được xây dựng một lần và không thay đổi sau đó.
Xây dựng cây và deserializing nó là khá chậm. Tôi đang tải cây theo cách hiển nhiên: Xây dựng đệ quy từng nút. Tôi nghĩ rằng điều này là tối ưu do nhiều nút được tạo riêng biệt với toán tử new. Tôi đọc ở đâu đó rằng new là khá chậm. Việc xây dựng ban đầu không phải là một vấn đề lớn bởi vì cây khá ổn định và không cần phải xây dựng lại thường xuyên. Nhưng tải cây từ một tập tin nên càng nhanh càng tốt.
Cách tốt nhất để thực hiện việc này là gì?
Nó phải tốt hơn nhiều để lưu toàn bộ cây trong một khối bộ nhớ duy nhất với các nút lân cận. Tuần tự hóa và deserializing sau đó sẽ được giảm xuống để tiết kiệm và tải toàn bộ khối, mà tôi phải phân bổ chỉ một lần.
Nhưng để thực hiện điều này, tôi sẽ phải triển khai lại QHash, AFAIK.
Bạn sẽ làm gì để tăng tốc độ deserialization?
Phụ Lục
Cảm ơn bạn đã gợi ý của bạn để làm một số hồ sơ. Dưới đây là kết quả:
Trong khi xây dựng lại cây từ một tập tin
1 % of the time is consumed by my own new calls
65 % is consumed by loading the QHash objects (this is implemented by the
Qt Library) of each node
12 % is consumed by inserting the nodes into the existing tree
20 % is everything else
Vì vậy, nó chắc chắn là không cuộc gọi mới của tôi mà gây ra sự chậm trễ nhưng xây dựng lại của QHash đối tượng tại mỗi nút. Điều này về cơ bản được thực hiện với:
QDataStream in(&infile);
in >> node.hash;
Tôi có phải tìm hiểu về QHash và xem điều gì đang xảy ra dưới mui xe ở đó không? Tôi nghĩ rằng giải pháp tốt nhất sẽ là một đối tượng băm có thể được nối tiếp với một hoạt động đọc và ghi mà không cần phải xây dựng lại cấu trúc dữ liệu nội bộ.
Bạn có cần truy cập nhanh vào các nút cụ thể y [i] không? Hãy thử sử dụng một QList thay vì QHash, nó sẽ nhanh hơn để làm việc với khi nói đến I/O. – rpg
Có. Tra cứu phải nhanh. – WolfgangA