sắp xếp bảng ở vị trí sử dụng STL loại

Question

Tôi có một bảng HUGE (khoảng 50GB) ở định dạng (i, j, k) (từ một ma trận thưa thớt) được lưu trữ như

uint32_t * idx1, * idx2; 
float * vals; 
uint32_t tablesize; 

và tôi muốn sắp xếp nó phù hợp với một hàm so sánh đã cho, đó là hàm của idx1 và idx2. Điều này có thể được thực hiện bằng cách sử dụng std :: sort?

Cụ thể, mỗi mục nhập không đồng phân (i, j) với giá trị v trong ma trận thưa thớt được lưu trữ bằng cách đặt i vào idx1, j trong idx2 và v trong mục nhập tương ứng trong vals. Tôi muốn sau đó sắp xếp những mục theo (i1, j1, v1) < = (i2, j2, v2) nếu

(i1 < i2) || (i1==i2 && j1 <= j2) 

Các ví dụ tôi đã có thể ăn trộm lên của việc sử dụng std :: sắp xếp trên các kiểu dữ liệu không chuẩn cho rằng mỗi mục được so sánh là một cá thể đơn của một lớp; ở đây mỗi mục được đại diện bởi ba giá trị trong các mảng khác nhau.

Answer 1

Nếu bạn phải tiếp tục sử dụng cấu trúc dữ liệu hiện tại của bạn, mà chủ yếu là một std::tuple ba std::vector s, sử dụng boost::zip_iterator sẽ vẻ là con đường để đi. Một zip_iterator xử lý ba trình lặp (hai đến chỉ mục và một đến một giá trị) dưới dạng một bộ đơn và bạn có thể sử dụng đối tượng hàm so sánh tùy chỉnh để sắp xếp dữ liệu của bạn tại chỗ. Không thể sử dụng, boost::zip_iterator với std::sort, như được giải thích trong this Q&A, vì không thể viết được.

Điều này có nghĩa là bạn sẽ phải viết lớp zip_iterator của riêng bạn có thể được sử dụng với std::sort. Lưu ý rằng đây không phải là bài tập tầm thường, xem this Q&A và/hoặc paper này.

Việc sắp xếp một số std::vector của số std::tuple dễ dàng hơn rất nhiều. Nỗ lực của tôi dưới đây sử dụng một số std::tuple của hai chỉ mục và giá trị, đồng thời lưu trữ các mục đó vào một số std::vector. Để sắp xếp, tôi sử dụng lambda chung C++ 14 để chuyển tiếp hai chỉ mục vào một bộ nhỏ hơn và so sánh các từ đó theo thứ tự từ điển (ví dụ: đầu tiên trên chỉ mục hàng, sau đó trên cột chỉ mục) bằng cách sử dụng thư viện operator< của std::tuple.

#include <algorithm> 
#include <iostream> 
#include <tuple> 
#include <vector> 

using index = uint32_t; 
using value = float; 
using sparse_entry = std::tuple<index, index, value>; 
using sparse_matrix = std::vector<sparse_entry>; 

int main() 
{ 
    // sparse 3x3 matrix 
    auto m = sparse_matrix { 
     std::make_tuple(1, 1, -2.2), 
     std::make_tuple(1, 0, 42 ), 
     std::make_tuple(0, 2, 3.4), 
     std::make_tuple(0, 1, 1.7) 
    };  

    // sort by row-index, then column-index 
    std::sort(begin(m), end(m), [](auto const& L, auto const& R) { 
     return 
      std::forward_as_tuple(std::get<0>(L), std::get<1>(L)) < 
      std::forward_as_tuple(std::get<0>(R), std::get<1>(R)) 
     ; 
    }); 

    for (auto const& elem : m) 
     std::cout << "{ " << std::get<0>(elem) << ", " << std::get<1>(elem) << ", " << std::get<2>(elem) << "}, \n"; 
} 

Live Example.

Nếu ứng dụng của bạn có thể sử dụng bố cục dữ liệu được chuyển đổi này (và có thể có lý do hiệu suất bộ nhớ cache tại sao nó không thể), thì mã trên sẽ thực hiện sắp xếp theo ý bạn.

LƯU Ý: như @ Casey đề cập, bạn cũng có thể sử dụng std::tie thay vì std::forward_as_tuple, nhưng điều đó có thể cắn bạn khi bạn thay đổi sparse_entry vào một lớp người dùng định nghĩa chính thức với thu khí trở bởi giá trị.

Answer 2

Rất tiếc, rất khó thuyết phục std::sort hoặc bất kỳ thư viện chuẩn nào để làm việc với dữ liệu sọc. Nó được thiết kế để giả định rằng dữ liệu có thể được sao chép thông qua một đơn =, được di chuyển qua một move hoặc hoán đổi qua một swap.

Đặt cược tốt nhất của bạn là sử dụng boost::iterator_facade để viết một lớp biến lặp tùy chỉnh kết thúc dữ liệu và ẩn định dạng dữ liệu sọc từ std::sort. Tôi đã từng muốn làm điều tương tự trong quá khứ nhưng không gian làm việc của tôi không cho phép chúng tôi sử dụng boost. EDIT: khi mặt tiền của bạn bị dereferenced, nó có lẽ sẽ cần phải tạo ra một số loại đối tượng proxy có thể được chỉ định/di chuyển/hoán đổi và sẽ làm điều đúng cho mỗi mảng sọc. Nó không tầm thường.

Đặt cược tốt nhất tiếp theo là tạo một mảng int s từ 0 đến N, mỗi một đại diện cho một chỉ mục vào mảng dữ liệu sọc của bạn. Viết một functor tùy chỉnh để std::sort mà sắp xếp mảng này để phù hợp với tiêu chí của bạn. Nó rõ ràng là xa lý tưởng khi bạn có một tập dữ liệu lớn như vậy.