C++Guns – RoboBlog blogging the bot

How do I sort two vectors containing relative entries, using STL? [1]

Da ich mir kein Account auf stackoverflow machen konnte, (ka. warum es passierte einfach nichts), gibt es jetzt hier die richtige Antwort.
Der Ansatz von Nikos Athanasiou war schon richtig, leider total krank programmiert und mit zu vielen Schleifen. So hat der Algo. quatratische Laufzeit und ist unbrauchbar fuer grosse Datenmengen.
Ich uebernehme seinen Ansatz und tausche nur die Funktion rearrange_vector() aus. So ergibt sich eine linear-logaritmische Laufzeit dominiert durch die Sortierung. Und einen linearen Speicherverbrauch. Da aber nur integer indices gespeichert werden, ist der Zusatzverbraucht sehr gering. Gerade einmal 4byte pro Namen. Also ca. 4MB pro eine Millionen Namen. Das sollte nun wirklich niemand stören.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

using namespace std;

void rearrange_vector(const vector<int> indices, vector<string> &v) {
    for(int idx1=0; idx1 < v.size(); ++idx1) {
        int idx2 = indices[idx1];
        // nur dann tauschen, wenn nicht schonmal getauscht wurde,
        // und wenn ein tausch ueberhaupt notwenig ist
        if(idx2 > idx1) {
            swap(v[idx1], v[idx2]);
        }
    }
}

int main() {
    // 1. Problem space
    vector<string> firstnames = {"Dennis",  "Alexander", "Bjarne",      "James",   "James" };
    vector<string> lastnames  = {"Ritchie", "Stepanov",  "Stroustrup",  "Coplien", "Gosling" };

    // 2. vector of indices - sorted according to the order of firstnames
    vector<int> indices(firstnames.size());
    // create sequenz 0,1,2,3,...
    iota(begin(indices), end(indices), 0);

    sort(begin(indices), end(indices), [&](int i1, int i2) {
        return firstnames[i1] < firstnames[i2];
    });

    // debug
    cout << "Sorted indices\n";
    for(auto i : indices) {
        cout << i << " ";
    }
    cout << "\n";

    // 3. rearrangement according to the sorted indices
    rearrange_vector(indices, firstnames);
    rearrange_vector(indices, lastnames);

    // 4. print results
    for (size_t i=0; i < indices.size(); ++i) {
        cout << firstnames[i] << " " << lastnames[i] << endl;
    }

    return 0;
}

[1] http://stackoverflow.com/questions/25085015/how-do-i-sort-two-vectors-containing-relative-entries-using-stl

According to N3337

3.9.1 Fundamental types [basic.fundamental]
2
There are five standard signed integer types : “signed char”, “short int”, “int”, “long int”, and “long
long int”. In this list, each type provides at least as much storage as those preceding it in the list.
There may also be implementation-defined extended signed integer types. The standard and extended signed
integer types are collectively called signed integer types. Plain ints have the natural size suggested by the
architecture of the execution environment 44; the other signed integer types are provided to meet special
needs.

44) ) that is, large enough to contain any value in the range of INT_MIN and INT_MAX, as defined in the header .

Thus
sizeof(short) <= sizeof(int) <= sizeof(long) Thx 2 m$ 4 <= instead of < ;)

Mir ist aufgefallen dass die Implementierung von Algorithmen in verschiedene
Kategorien passen. Es geht also nicht um das, was der Algorithmus macht, sondenr
wie er programmiert ist. Die Kategorien sind auch meist Sprach uebergreifend.

Beispiel: segmentTools vertex-collapse

In der derzeitigen Version faellt der Algorithmus in die Kategorie
"korret, aber nicht vollstaendig".
Das bedeutet, das Programm bearbeitet die Probleme richtig, aber nicht fuer alle
Faelle. Es fehlen also einige Sonderfallbehandlungen.

Die Kategorie "Datenabhaenigkeit" ist sehr komplex und oft untergliedert. Fuer den vertex-collaps
Algorithmus gilt, dass ein Segment mit mehreren anderen Segmenten zusammen fallen kann. Also
eine 1-n Beziehung. Momentan wird immernur eine 1-1 Beziehung bearbeitet.
Daher ist die derzeitige Version auch in der Kategorie "nicht vollstaenig". (Gluecklicherweise
kann durch wiederholte Aufrufe des Programms das Problem umgangen werden).

Auch trifft die Kategorie "langsam - quadratisch Laufzeit" zu. Das bedeutet einfach,
dass die Berechnung statt Sekunden (mehrere) Tage dauert.
Dementsprechend gibt es noch die Kategorie "schnell - linear logarithmische Laufzeit".

Um nun den Algorithmen in die Kategorie "schnell" zu heben, gibt es einige schon ausgearbeitet
Techniken. Darum den Sweepline Algorithmus. Dieser steuert, auf einer intelligentere Art und Weise,
welche Segmente der vertex-collapse Algo in welcher Reihenfolge bearbeiten wird. Der Sweepline Algorithmen
bedient sich eines weiteren Algorithmus zum Sortieren von Daten.

Der vertex-collapse Algorithmus faellt also in weitere Kategorien.
Einmal "Datenabhaenigkeit - Reihenfolge". Dadurch entstehen weitere Sonderfaelle welche die 1-n Beziehnung noch
verkomplizieren.

Und es gibt zusaetzliche die Kategoie "Daten Redundanzen/Kopien".
Hier gibt es zwei aehnliche Faelle.

Fall 1:
Um nicht den orignal Datensatz zu veraendern, macht man in der Regel eine Kopie davon und sortiert ihn dann
mit Sweepline. Das funktioniert bei großen Datensatzen nicht mehr, da hier der RAM oft zu klein ist. (Der
Ergebnisdatensatz sollte auch noch in den RAM passen).

Eine gängige Methode um das zu umgehen ist, statt das eigentliche Datenobjekt zu sortieren (das Segment)
werden nur die IDs sortiert. Aber nicht die ID als Nummer, sondern der (speziell hierfuer angepasster) Sortier Algoritmus greift beim
sortieren ueber die ID auf das Segmente Objekt zurueck und erstellt dementsprechend eine Sortierung der IDs.

Das hat Vorteile und auch viele Nachteile.

Vorteile:
* Der Speicherverbrauch sink. Nehmen wir z.B. ein Segment mit zwei 3D Punkten und doppelter Zahlengenauigkeit.
2*3*8byte = 48byte pro Segment. Werden stattdessen nur IDs kopiert und sortiert, fallen nur 4byte pro Segment
zusaetzlich an.
* Die Geschwindigkeit steigt. Im jeder Sortieriteration werden Daten bewegt. Statt 48byte muessen nur 4byte im Ram
bewegt werden.

Nachteile:
* Nicht jeder Datencontainer kann ueber eine integer ID effizient angesprochen werden. Das funktioniert nur effizent
bei Vector Containern. Deque, Hash und Sorted Maps sind auch noch moeglich. Bei Listen funktioniert es nicht mehr.

* Nicht jeder Datencontainer kann ueberhaupt ueber eine integer ID angesprochen werden. Oft werden auch andere Typen
als ID benutzt. Zum Beispiel kurze Strings. Ein Mapping String ID -> Integer ID ist zwar moeglich, kostet aber wieder
Speicherplat und Geschwindigkeit.

* Die ID Variable enthaelt keine Informationen ueber den Datentype auf den sie verweist. Arbeitet man mit mehreren Datensaetze
z.B. Segmente und Punkte, so ist es moeglich mit einer Segment ID Variable auf den Punkt Datensatz zuzugreifen ohne
dass dieser Programmierfehler sofort bemerkt wird.

Fall 2:
Der zweite Fall bezieht sich auf Daten die der Sweepline Algoritmus zwischenspeichert. Auch hier muss wie beim Sortieren
auf die Datenobjekte zugegriffen werden und es entstehen die selben Vor und Nachteile.

Weiterhin muss auch der Sortier Algorithmus darauf hin ausgelegt sein, nicht die eigentlichen Daten zu sortieren, sondern ihre
IDs.
Dies fuehrt zu dem Problem, dass der Programmierer des Sort und auch Sweeplines mit einem unbekannten, benutzer definierten,
Datentype arbeiten muss.
Dies wurde in C und Fortran dadurch geloest, dass der Benutzer definierte Datentype nur als Pointer von Type void (also
keine Type Information), oder noch schlimmer: als Typ double, der Sortier Routine uebergeben wurde. Der Algorithmus arbeitet
also blind aus den Daten und es liegt in der Hoffnung des Programmiers, dass es auch immer funktioniert.

Noch dazu gibt es von C std lib keine Sortierfunktion die zusaetzlich auch IDs beruecksichtigt. Die Routine muss also immer
neu geschrieben werden mit allen Fehlern und Sonderfaelle. Insbesondere bei Fortran. Da es hier nicht mal eine Sortierfunktion
von der Standardlib selbst gibt.

Das Problem mit den benutzer definierten Datentypen wurde mit der Einfuehrung von C++ im Jahre 1984, und die integierte Template
Sprache, geloest.
Es koennen nun abstrakt geschrieben werden und zur Compilierzeit wird der benutzer definierten Datentype eingebaut und entsprechende
Fehler vom Compiler weise auf Probleme hin.

Um die Probleme mit den IDs anzugehen kann man als erstes Versuchen satt einer Integer ID, einen Pointer auf das Datenobjeckt zu speichern
und zu sortieren.

Vorteile:
* Es funktionieren nun alle Containertypen.
* Kein Problem mehr mit string IDs, da auf das Datenobjekt selbst zugegriffen wird.
* Keine extra Mapping sortierte ID -> container -> Datenobjekt mehr noetig
* Weiterhin Platzersparnig als wenn eine Kopie des Objekt sortiert wird

Nachteile:
* Pointer verbrauchen auf 64bit Systemen 8byte, also doppelt so viel wie integer IDs
* Pointer koennen invalid sein. Immer ein Check noetig.
* Pointer muessen immer explizit dereferenziert werden um an das Objekt zu gelanden auf das sie zeigen.

Weiterhin muss der Sortierfunktion eine Funktion uebergeben werden, die besagt, wie zwei Pointer Objeckte auf kleiner "<" verglichen werden konnen. Das ist aber schon immer in C und C++ moeglich. Nur eine Frage der kryptischen Syntax. Um auch die Nachteile der Pointer zu kompensieren, können Referenzen genutzt werden. Vorteil: * Referenzen sind immer valid. * Refreenzen muessen nicht extrea dereferenziert werden. Nachteil: * Referenzen brauchen wie Pointer 8byte. Seit C++ 2011 ist es moeglich auch Referenzen in einem Container zu speichern. Weiterhin gibt es mit Lambdas eine elegante Moeglichkeit die relations Funktion zweite Datenobjekte zu formulieren. Kein kryptischer Code mehr. Somit bietet C++ seit 2011 die fehlerfreiste und performanteste Moeglichkeit einen Algorithmus schneller durch Sortierung zu machen. Viele Worte, wenig Code. So siehts aus: