Tôi đang làm việc trên một ứng dụng Java cần làm việc trên các ma trận rất lớn. Ví dụ nhân hai ma trận 10 triệu * 10 triệu! Tất nhiên, vùng heap Java không có đủ dung lượng ngay cả khi lưu trữ một trong các ma trận này. Tôi nên làm gì? Tôi có nên sử dụng cơ sở dữ liệu để lưu trữ ma trận của mình và mang đến bộ nhớ mọi phần cần thiết và nhân nó lại với nhau không?Xử lý cấu trúc dữ liệu lớn trong Java
xem xét sử dụng một db nhớ như http://hsqldb.org/
Đây là một RDB. Bạn có nghĩa là tôi có thể sử dụng bất kỳ RDB cho điều này có nghĩa là ... ví dụ như MySQL? Có hiệu quả khi sử dụng DB không? Tôi có nghĩa là có bất kỳ giải pháp tốt hơn (sử dụng không gian đĩa hoặc ...). – user78564
Tôi muốn nói "nhúng" DB, vì HSQLDB có thể làm nhiều hơn các cơ sở dữ liệu trong bộ nhớ thuần túy. –
@unknown: có, một RDB có lẽ là một ý tưởng tốt cho điều này, vì nó được thiết kế để xử lý một lượng lớn dữ liệu. Tùy thuộc vào nhu cầu chính xác của bạn, bạn có thể cần phần mềm chuyên biệt hơn, nhưng từ những gì bạn đã viết, tôi đề nghị một cơ sở dữ liệu quan hệ. –
Vâng, nếu bạn buộc phải sử dụng Java và không thể viết mã mà những giao dịch với điều này phương pháp như mẹ đẻ (có nghĩa là, bằng cách nói với Java để gọi một số mã C thay vì) thì điều hiệu quả nhất để làm đúng là sử dụng một tệp nhị phân đơn giản. Tôi sẽ tránh xa cơ sở dữ liệu trong trường hợp này vì chúng chậm hơn truy cập tệp trực tiếp và bạn không cần các tính năng mà chúng cung cấp.
Độ phức tạp của phép nhân ma trận, nếu được thực hiện một cách ngây thơ, là O (n^3), nhưng các thuật toán hiệu quả hơn vẫn tồn tại. Dù sao cho một ma trận 10 triệu * 10 triệu, việc này sẽ mất một thời gian rất dài và bạn có thể sẽ phải đối mặt với cùng một vùng thám hiểm heap nhưng với đệ quy.
Nếu bạn vào toán học phức tạp, bạn có thể tìm thấy công cụ trợ giúp bạn trong this article.
Hãy xem hadoop.
Vì đây là một tính toán rất lớn, tôi nghĩ bạn sẽ gặp sự cố về hiệu suất cùng với sự cố lưu trữ của mình. Vì vậy, tôi sẽ xem xét song song vấn đề này, và nhận mutliple máy/lõi để xử lý một tập con của dữ liệu.
May mắn là giải pháp nhân ma trận sẽ phân hủy tự nhiên. Nhưng tôi sẽ xem xét một số dạng lưới hoặc giải pháp tính toán phân tán.
Sử dụng bất kỳ thuật toán ma trận thưa thớt nào áp dụng cho dữ liệu của bạn. (trên giả định rằng bạn không có 2.4 PB dung lượng đĩa để lưu 3 ma trận không vuông góc 10^8 vuông, hãy để một mình RAM nhiều cho cơ sở dữ liệu trong bộ nhớ - Blue Gene/Q 'only' có 1.6 PB.)
có một cái nhìn tại CGL-MapReduce http://www.cs.indiana.edu/~jekanaya/cglmr.html#Matrix_Multiplication
Hãy thử sử dụng Memory Mapped File bằng cách lưu trữ tất cả dữ liệu của bạn trong một tập tin bên ngoài và truy cập nó thông qua đối tượng FileChannel.
Khám phá this article để biết giới thiệu ngắn gọn về MMF.
Trước hết, một ma trận 10 triệu x 10 triệu chỉ đơn giản là rất lớn. Giả sử tăng gấp đôi cho mỗi tế bào và không có lưu trữ đại tu, mỗi một trong những điều này sẽ là 800 terabyte. Chỉ cần đọc từng tế bào một lần từ bộ nhớ chính (nếu nó bằng cách nào đó kỳ diệu phù hợp với đó, rõ ràng là không xảy ra), sẽ mất vài ngày. Làm điều đó từ bất kỳ loại SAN hợp lý nào (chúng tôi sẽ đặt nó trên 10GbE) có nhiều khả năng là tháng. Và không có ma trận nhân có O (n) phức tạp - phương pháp tiếp cận bình thường là O (n^3). Vì vậy ... bạn không làm điều này với bộ nhớ ánh xạ tập tin, cơ sở dữ liệu phổ biến, hoặc bất cứ điều gì của loại đó.
Mã làm việc như thế này sẽ hoạt động hoặc chết trên hiệu suất bộ nhớ cache, nơi "bộ nhớ cache" bao gồm việc sử dụng tốt bộ nhớ chính, ổ đĩa cục bộ. Vì bất kỳ giao diện lưu giữ nào chứa hơn 800 terabyte ma trận đều bị ràng buộc là một SAN của một số loại, bạn gần như chắc chắn liên quan đến nhiều máy chủ đọc và làm việc trên các phần khác nhau của nó, quá.
Có rất nhiều cách nổi tiếng để nhân đôi ma trận nhân (chủ yếu nhân các ma trận phụ có kích thước khác nhau và sau đó kết hợp các kết quả) và bố cục thay đổi để các mẫu truy cập có vị trí bộ nhớ cache hợp lý bằng cách sắp xếp dữ liệu xung quanh space-filling curves thay vì sắp xếp hàng/cột. Bạn chắc chắn sẽ muốn xem xét giao diện và thiết kế LAPACK cổ điển, Intel's MKL, GotoBLAS khi triển khai các chức năng BLAS được điều chỉnh theo phần cứng hiện đại cụ thể và sau đó bạn có thể mạo hiểm vào lãnh thổ chưa được khám phá :-)
ma trận thưa thớt bởi bất kỳ cơ hội? – TrayMan
yea. nó có thể trong rất nhiều trường hợp. nhưng chúng tôi không thể chắc chắn. – user78564
Bạn đang cố gắng đạt được điều gì? Nhiều khả năng đây không phải là cách đúng để làm điều đó. – starblue