Ich habe eine riesige Tabelle (etwa 50 GB) im Format (i, j, k) (aus einer dünnen Matrix), die als
gespeichert ist %Vor%und ich möchte es mit einer gegebenen Vergleichsfunktion an Ort und Stelle sortieren, die eine Funktion von idx1 und idx2 ist. Kann dies mit std :: sort gemacht werden?
Insbesondere wird jeder von Null verschiedene Eintrag (i, j) mit dem Wert v in der Sparse-Matrix gespeichert, indem i in idx1, j in idx2 und v in dem entsprechenden Eintrag in vals platziert wird. Ich würde dann gerne diese Einträge nach (i1, j1, v1) & lt; = (i2, j2, v2) wenn
sortieren %Vor%Die Beispiele, die ich verwenden konnte, um std :: sort bei nichtstandardisierten Datentypen zu verwenden, setzen voraus, dass jedes verglichene Element eine einzelne Instanz einer Klasse ist; hier wird jedes Element durch drei Werte in verschiedenen Arrays dargestellt.
Wenn Sie Ihre bestehende Datenstruktur weiterverwenden müssen, was im Wesentlichen ein std::tuple von drei std::vector s ist, dann wäre boost::zip_iterator scheinen , um der richtige Weg zu sein. A zip_iterator behandelt drei Iteratoren (zwei zu Indizes und eins zu einem Wert) als einzelnes Tupel, und Sie können ein benutzerdefiniertes Vergleichsfunktionsobjekt verwenden, um Ihre Daten direkt zu sortieren. Leider kann boost::zip_iterator nicht mit std::sort verwendet werden, wie in diesem Q & A
Dies bedeutet, dass Sie Ihre eigene zip_iterator-Klasse schreiben müssen, die mit std::sort verwendet werden kann. Beachten Sie, dass es keine triviale Übung ist, siehe dieses Q & A und / oder dieses Papier .
Es ist viel einfacher, ein std::vector eines std::tuple zu sortieren. Mein Versuch unten verwendet ein std::tuple von zwei Indizes und einen Wert und speichert diese Einträge in einem std::vector . Für die Sortierung verwende ich ein C ++ 14 generisches Lambda, das die beiden Indizes in ein kleineres Tupel weiterleitet und diese lexikografisch (dh zuerst am Zeilenindex, dann am Spaltenindex) mit der Bibliothek operator< von std::tuple vergleicht .
Wenn Ihre Anwendung dieses transformierte Datenlayout verwenden kann (und möglicherweise aus Gründen der Cache-Performance, warum dies nicht möglich ist), führt der obige Code die Sortierung aus, wie Sie es wollen.
HINWEIS : Wie @Casey erwähnt, können Sie auch std::tie anstelle von std::forward_as_tuple verwenden, aber das kann Sie beißen, wenn Sie sparse_entry in eine vollwertige benutzerdefinierte Klasse ändern mit Gettern, die als Wert zurückkommen.
Es ist leider ziemlich schwierig, std::sort oder irgendeine der Standardbibliotheken davon zu überzeugen, mit Striped-Daten zu arbeiten. Es ist davon auszugehen, dass Daten über eine einzige = kopiert, über eine move verschoben oder über eine swap ausgetauscht werden können.
Am besten verwenden Sie boost::iterator_facade , um eine benutzerdefinierte Iterator-Klasse zu schreiben, die die Daten umschließt, und verbirgt das Format der gestreiften Daten von std::sort . Ich wollte in der Vergangenheit etwas Ähnliches machen, aber mein Arbeitsbereich erlaubt uns nicht, boost zu verwenden. BEARBEITEN: Wenn Ihre Fassade dereferenziert wird, muss wahrscheinlich eine Art Proxy-Objekt erstellt werden, das zugewiesen / verschoben / vertauscht werden kann und das Richtige für jedes der Stripe-Arrays tut. Es ist nicht trivial.
Die nächstbeste Wette besteht darin, ein Array von int s von Null bis N zu erstellen, von denen jedes einen Index in Ihr Striped-Daten-Array darstellt. Schreiben Sie einen benutzerdefinierten Funktor nach std::sort , der dieses Array nach Ihren Kriterien sortiert. Es ist offensichtlich bei weitem nicht ideal, wenn Sie einen so großen Datensatz haben.