Frage zur Verbesserung der Performance von bestimmtem Algorithmus

Hallo, ich habe folgendes Problem:
Ich lese Daten aus einer Database aus. Diese Daten werden dann in Objekte einer Klasse eingelesen und in einem std::vector gespeichert. Eine Eigenschaft der Klasse ist eine id. Nun darf in dem vector jede id nur einmal vorkommen. Das klingt jetzt sehr nach dem Aufgabenfeld für std::set oder std::map, allerdings ist die Vorgabe, dass std::vector benutzt werden soll. Hier ein Minimalbeispiel:

class Klasse
{
    std::string id;
    //...
};

std::vector<KLASSE> vec;

int main()
{
    vec.reserve(20000);
    std::ifstream lesen("Database");
    while(!lesen.eof())
    {
        Klasse objekt;
        lesen>>objekt;
        for(size_t a(0), b(vec.size()); a!=b; ++a)
        {
            if(objekt.id == vec[a].id)
                break;
        }
    }
}

Die Laufzeit deses Algorithmus steigt natürlich mit zunehmender Database größe exponentiell. In meinem Fall hat die Database ca. 15.000 Einträge und der Einlesevorgang benötigt ca. 5 Sekunden.
Hat jemand eine Idee, wie man das einlesen performanter gestalten könnte? Ich hatte schon die Idee, den vector nach jedem neu eingelesenem Objekt zu sortieren, um bei der suche nach objekten den Suchbereich eingrenzen zu können. Was haltet ihr davon? Der Code ist relativ komplex, daher habe ich diese Änderung noch nicht probiert. Was haltet ihr davon? Gibt es andere Möglichkeiten?

*edit:
Natürlich fehlt das "vec.push_back(objekt);" nach der inneren for-schleife

@ hah: komischer Vorschlag Oo

Dravere

1. Deine Schleife funktioniert nicht richtig. Das eofbit Flag wird erst gesetzt, wenn über das Ende hinaus gelesen wurde. Du wirst dadurch einen Eintrag zu viel lesen, bzw. wahrscheinlich einfach doppelt eintragen. Frag nach dem Einlesen ab, ob das Einlesen korrekt verlaufen ist, bzw. ob der Stream noch gültig ist. Nutze dazu den Rückgabewert von operator >> aus
2. Ich würde alle Einträg einfach einlesen. Danach mit std::sort Soriteren und am Ende mit std::unique doppelte Einträge rauslöschen.

Grüssli

Ok, Dravere's Problemlösung ist gut, allerdings in meinem Fall nicht anwendbar. Dazu muss ich etwas ausholen:
Die Klasse hat neben id weitere Eigenschaften. Unter andem eine... nenn wir sie version. Wenn ein eingelesenes Objekt eine id besitzt, die es schon im Vector gibt, dann wird die version der schon vorhandenen id hinzugefügt:

class Klasse
{
    std::string id;
    std::vector<int> version;
    //...
};

std::vector<Klasse> vec;

int main()
{
    vec.reserve(20000);
    std::ifstream lesen("Database");
    bool gefunden = false;
    while(!lesen.eof())
    {
        Klasse objekt;
        lesen>>objekt;
        for(size_t a(0), b(vec.size()); a!=b; ++a)
        {
            if(objekt.id == vec[a].id)
            {
                vec[a].version.push_back(objekt.version[0]);
                gefunden=true;
                break;
            }
        }
        if(gefunden)
        {
            gefunden=false;
            continue;
        }
        vec.push_back(objekt);
    }
}

pumuckl

Muss die Klasse so sein wie sie ist mit dem Version-vector? Was du da fabrizierst ist nämlich reichlich umständlich und sieht ein wenig nach suboptimalem Design aus. Was genau ist denn die Aufgabenstellung/was genau willst du erreichen?

Dravere

Abgesehen von dem was pumuckl gesagt hat, könntest du deinen eigenen unique Algorithmus einbauen. Es gibt sogar bereits andere Algorithmen, welche dir dabei behilflich sein könnten. Zum Beispiel:
http://www.cplusplus.com/reference/algorithm/adjacent_find/

So kompliziert ist der Algorithmus ja wirklich nicht.

Grüssli

Michael E.

[Edit] Was übersehen...

Genauso wie es Draveres Vorschlag tut. Lies alle Werte ein, sortier und füll dann erst den Versionsvektor auf mit den doppelten Elementen, die folgen. Zum Schluss die doppelten Objekte entfernen.

Die idee mit adjacent_find und dann die doppelten Elemente über unique löschen find ich gut! Werd die gleich mal implementieren!

adjacent_find hat sich als nicht so gut herausgestellt, da von einer id durchaus mehr als 2 vorkommen können. Ich habe jetzt versucht das selbst zu implementieren. Allerdings habe ich am ende statt ca. 15000 Objekten nur ca. 5000 im vector. Sieht jemand den Denkfehler?

class Klasse
{
    std::string id;
    std::vectir<int> version;
    //...
}

inline bool sort_all ( const Klasse& a, const Klasse& b){ return (a.id < b.id); }
inline bool operator==(const Klasse& a, const Klasse& b){ return (a.id == b.id); }

std::vector<Klasse> vec;

int main()
{
    vec.reserve(20000);
    while(!lesen.eof())
    {
        Klasse objekt;          //
        lesen>>objekt;          // alle einlesen
        vec.push_back(objekt);  //
    }
    lesen.close()

    std::vector<Klasse>::iterator it=vec.begin(), end=vec.end(), at, unique_it;

    sort(it, et, sort_all); //vec sortieren

    at = it;
    ++it;

    while(at != end)
    {
        if(*it == *at)
        { 
            (*it).version.push_back( (*at).version[0] );
            ++at;
            continue;
        }
        it = at;
        ++at;
    }

    unique_it = unique(vec.begin(), end);
    vec.resize(end-unique_it);
}

*edit: ++it in Zeile 29 sollte ++at heißen

Michael E.

Was hast du denn gegen adjacent_find()=

typedef vector<Klasse>::iterator Iter;

Iter pos1 = vec.begin();
Iter pos2;

while((pos1 = adjacent_find(pos1, vec.end())) != vec.end())
{
	pos2 = pos1 + 1;
	while(*pos2 == *pos1)
	{
		pos1->version.push_back(pos2->version[0]);
		++pos2;
		if(pos2 == vec.end())
			return;	// aus beiden Schleifen raus
	}
	pos1 = pos2 + 1;
}

Wie immer ungetestet.

[Edit] OK, hier kann man sich adjacent_find() wirklich sparen

Offensichtlich hast du meinen "falschen" Code 1:1 mit adjacent_find umgesetzt Mit deinem und meinem Ansatz bekomme ich genau 5697 Elemente in den vector, obwohl am ende ca. 15000 drin sein sollten

Michael E.'s code funktioniert wunderbar. Hatte mich mit unique() vertan. Jetzt geht das einlesen in unter einer sekunde. Danke!