smistamento in posizione utilizzando stl sorta

Question

Ho una tabella enorme (circa 50GB) in formato (i, j, k) (da una matrice sparsa) memorizzato come

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

e desidero ordinare è in atto con una data funzione di confronto che è una funzione di idx1 e idx2. Questo può essere fatto usando std :: sort?

In particolare, ciascuna voce diversa da zero (i, j) con valore v nella matrice sparsa viene memorizzata inserendo i in idx1, j in idx2 e v nella voce corrispondente in vals. Mi piacerebbe quindi ordinare queste voci in base alle (i1, J1, V1) < = (i2, J2, v2) se

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

Gli esempi sono stato in grado di scroccare up di usare std :: ordinare su tipi di dati non standard presuppone che ogni elemento da confrontare sia una singola istanza di una classe; qui ogni elemento è rappresentato da tre valori in diversi array.

Answer 1

Se si deve continuare a utilizzare la struttura dati esistenti, che è essenzialmente un std::tuple di tre std::vector s, utilizzando boost::zip_iterator sarebbe sembrano essere la strada da percorrere. A zip_iterator tratta tre iteratori (da due a indici e uno a un valore) come una singola tupla ed è possibile utilizzare un oggetto funzione di confronto personalizzato per ordinare i dati sul posto. Purtroppo, boost::zip_iterator non può essere utilizzato con std::sort, come spiegato in this Q&A, perché non può essere scritto.

Ciò significa che è necessario scrivere la propria classe zip_iterator che può essere utilizzata con std::sort. Si noti che non si tratta di un esercizio banale, vedere this Q&A e/o questo paper.

È molto più facile ordinare uno di un std::tuple. Il mio tentativo qui sotto utilizza uno std::tuple di due indici e un valore e memorizza tali voci in un std::vector. Per l'ordinamento, utilizzo un lambda generico C++ 14 che inoltra i due indici in una tupla più piccola e li confronta lessicograficamente (vale a dire prima sull'indice di riga, quindi sull'indice di colonna) utilizzando la libreria operator< di 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.

Se l'applicazione può utilizzare questo layout di dati trasformato (e potrebbero esserci motivi di prestazioni della cache per cui non può farlo), il codice precedente eseguirà l'ordinamento come desiderato.

NOTA: come cita @Casey, è anche possibile utilizzare al posto di std::tiestd::forward_as_tuple, ma che possono fare molto quando si cambia sparse_entry in una classe a tutti gli effetti definito dall'utente con getter ritorno per valore.

Answer 2

È purtroppo piuttosto difficile convincere std::sort o una qualsiasi delle librerie standard a lavorare con i dati a strisce. È progettato per presupporre che i dati possano essere copiati tramite un singolo =, spostati tramite uno move o scambiati tramite uno swap.

La soluzione migliore è utilizzare boost::iterator_facade per scrivere una classe di iterazione personalizzata che avvolge i dati e nasconde il formato dei dati a strisce da std::sort. Ho voluto fare qualcosa di simile in passato, ma il mio spazio di lavoro non ci consente di utilizzare boost. EDIT: quando la facciata è dereferenziata, sarà probabilmente necessario creare una sorta di oggetto proxy che può essere assegnato/spostato/scambiato e farà la cosa giusta per ciascuno degli array di stripe. Non è banale.

La soluzione migliore consiste nel creare un array di int da zero a N, ognuno dei quali rappresenta un indice nella matrice di dati a strisce. Scrivi un functor personalizzato su std::sort che ordina questa matrice in modo che corrisponda ai tuoi criteri. Ovviamente è lontano dall'ideale quando si dispone di un set di dati così ampio.