Suchfunktion optimieren?

BorisDieKlinge

nene, es an strcmp.. ist ja die einzigste funktion welche "was tut" der sind ja nur verschachtelte schleifen..1 Aber das zufrieden bist : Ohne strcmp oder memcmp geht im faktor 20 schneller..

nep

Naja an strcmp an sich liegt es aber nicht. Wenn du halt Strings verlgeichen musst, dann musst du Strings vergleichen, und das dauert eben.
Wie schon gesagt, du könntest über Hashing und dem Vergleichen der Hash-Werte bestimmt noch was rausholen an Performanz. Ansonsten wie auch schon gesagt, evtl. nochmal die ganzen Strukturen irgendwie umändern.

Bei strcmp wäre die einzigste Möglichkeit die ich sehe, dass du dir evtl. deine eigene strcmp-Funktion als Makro schreibst und da halt auf jede Sicherheitsüberprüfung verzichtest. Wobei ich glaube, dass das bei strcmp auch nicht anders ist und das schon hochperformant implementiert ist. Aber ka, ewig lang her, dass ich was mit C Funktionen gemacht hab
Und da bezweifle ich mal stark, dass du überhaupt nen Unterschied wirst messen können.

Badestrand

Als Anreiz, lässt sich ja nach C übertragen, war mir jetzt aber zuviel Arbeit:

char createRandomChar()
{
	// 40 - 125
	return 40 + (rand()%86);
}

string createRandomString()
{
	int len = rand() % 100;
	string s( len, 'a' );
	for ( int i=0; i<len; i++ )
		s[i] = createRandomChar();
	return s;
}

class Container1
{
	public:
		bool hasElem( const string& s ) const
		{
			for ( size_t i=0; i<arr.size(); i++ )
				if ( arr[i] == s )
					return true;
			return false;
		}

		void operator+=( const string& s )
		{
			arr.push_back( s );
		}

	private:
		vector<string> arr;
};

class Container2
{
	public:
		bool hasElem( const string& s ) const
		{
			std::map<unsigned int,vector<string>>::const_iterator i = arr.find( hash(s) );
			if ( i == arr.end() )
				return false;
			for ( size_t j=0; j<i->second.size(); j++ )
				if ( i->second[j] == s )
					return true;
			return false;
		}

		void operator+=( const string& s )
		{
			arr[hash(s)].push_back( s );
		}

	protected:
		static unsigned int hash( const string& s )
		{
			// algo von http://www.cse.yorku.ca/~oz/hash.html
			unsigned long hash = 5381;
			int c;
			const char* str = s.c_str();
			while (c = *str++)
				hash = ((hash << 5) + hash) + c;
			return hash;
		}

	private:
		std::map< unsigned int, vector<string> > arr;
};

int main()
{
	srand( time(NULL) );

	Container1 c1;
	Container2 c2;
    // Beide Container mit 1 Mio strings füllen
	for ( int i=0; i<1000000; i++ )
	{
		string s = createRandomString();
		c1 += s;
		c2 += s;
	}

    // 100 mal linear suchen => 9 sec
	time_t t = time( NULL );
	for ( int i=0; i<100; i++ )
		cout << c1.hasElem( createRandomString() ) << " ";
	cout << endl << time(NULL)-t << endl;

    // 50.000 mal suchen => 3 sec
	t = time( NULL );
	for ( int i=0; i<50000; i++ )
		cout << c2.hasElem( createRandomString() ) << " ";
	cout << endl << time(NULL)-t << endl;

    // edit: das meiste der Zeit geht eins drüber die Ausgabe drauf, deshalb mal ohne viel Ausgabe:
    t = time( NULL );
	int v = 0;
    // edit 2: Mit 5.000.000 Durchläufen 14 sec
	for ( int i=0; i<5000000; i++ )
	{
		if ( c2.hasElem( createRandomString() ) )
			v++;
	}

	cout << v << endl << time(NULL)-t << endl;
}

In "Container2" wird auf jeden vorkommenden hash-Wert ein string-Array gemappt. Zuerst wird der Hashwert vom zu suchenden String ermittelt, dann in dem entsprechenden Container (wo nur Strings mit diesem Hashwert sitzen) gesucht.

edit3: In Container2 wirkt sich die Hashfunktion auch maßgeblich auf den Speicherverbraucht aus, bei mir bei obigen Werten zwischen 100 MB und 250 MB Verbrauch - ist ja auch logisch, sitzt beinahe jeder String einzeln in einem vector, wird eine Ecke mehr Speicher benötigt weil es eben mehr vectoren gibt..

Badestrand schrieb:

std::map<unsigned int,vector<string>>::const_iterator i = arr.find( hash(s) );

igitt, das ist ja gruselig. mach das weg!

Badestrand

fricky schrieb:

Badestrand schrieb:
std::map<unsigned int,vector<string>>::const_iterator i = arr.find( hash(s) );
igitt, das ist ja gruselig. mach das weg!

Joar, schön sieht das nicht aus. Ohne die Zeile funktioniert's aber nicht und ich hatte keine Lust zu typedef'en.

Badestrand schrieb:

fricky schrieb:
Badestrand schrieb:
std::map<unsigned int,vector<string>>::const_iterator i = arr.find( hash(s) );
igitt, das ist ja gruselig. mach das weg!
Joar, schön sieht das nicht aus. Ohne die Zeile funktioniert's aber nicht und ich hatte keine Lust zu typedef'en.

hehe, ich meinte eigentlich das ganze programm. im c++ forum wärst du damit der held, aber hier kann man fast nix mit anfangen. wozu überhaupt lauter 'vectors' in der map? würde es nicht auch mit 'string' gehen?
ansonsten: einfach mal googlen: hashmap filetype:c. da findeste einiges, ganz ohne dieses c++ geraffel, was wahrscheinlich noch schneller ist.

Badestrand

Du hast ja auch Recht. Ich hatte überlegt, ob ich den C++-Quellcode im C-Forum posten soll. Hab mich dann dafür entschieden, weil es um den Algorithmus geht und nicht um die Umsetzung. Ganz davon abgesehen, dass ich weder Lust hab noch es als sinnvoll ansehe, hier noch 200 Zeilen Sourcecode reinzuposten, der map- und vector-Funktionalität beinhaltet. Letztendlich sehen die Funktionsaufrufe auch nicht anders aus, statt "bla.foo" halt "bla( foo )"

fricky schrieb:

wozu überhaupt lauter 'vectors' in der map? würde es nicht auch mit 'string' gehen?

Ist das eine ernst gemeinte Frage von dir?

PS: Ich gucke mal ob ich morgen Lust hab, das irgendwie noch umzuformen oder anders hinzuschreiben. Wenn du magst, kannst du das aber natürlich auch übernehmen, du bist in C wohl um Längen fitter als ich

edit: Und abgesehen davon war es in erster Linie natürlich ein Anreiz für Boris, der des C++ ja durchaus auch mächtig ist.

BorisDieKlinge

danke, es geht ja lediglich darum:

static unsigned int hash( const string& s )
        {
            // algo von http://www.cse.yorku.ca/~oz/hash.html
            unsigned long hash = 5381;
            int c;
            const char* str = s.c_str();
            while (c = *str++)
                hash = ((hash << 5) + hash) + c;
            return hash;
        }

wie ich dan ne map bzp. den lookup table für die string IDS in C anlege muss ich mir überlegen..

P.S.: falls es doch vorkommen würde, das 2 identische ID für unterschiedliche string existieren, müsste ich den string nach gefundener HashID sicherheitshalber nochmal vergleichen denk ich;)

Bitte ein Bit

An Badestrand:
Gelle die STL ist doch schön ? Da sind so viele Dinge / Datenstrukturen drin welche man in vielen Fällen gut gebrauchen kann. Und wenn man sich die interne Datenstrukturen von Sets (ich vermute auch mal die Maps) anschaut, kommt man schnell zu Bäumen.

Da das Ganze aber leider für C++ programmiert wurde, muss man das Ganze wohl oder übel in C nachprogrammieren. Oder kennt jemand ein STL-Pendant (ohne Templates), welche die gängigen Container-Klassen implementiert ?

Bitte ein Bit schrieb:

Oder kennt jemand ein STL-Pendant (ohne Templates), welche die gängigen Container-Klassen implementiert ?

z.b. das: http://home.gna.org/gdsl/

Tachyon

fricky schrieb:

Bitte ein Bit schrieb:

Oder kennt jemand ein STL-Pendant (ohne Templates), welche die gängigen Container-Klassen implementiert ?

z.b. das: http://home.gna.org/gdsl/

Boa, was für ein unsicherer Frickelhaufen...

Tachyon schrieb:

Boa, was für ein unsicherer Frickelhaufen...

was speziell meinst du? sind doch überall asserts drin.

Tachyon

Die Typsicherheit...

Tachyon schrieb:

Die Typsicherheit...

was gefällt dir nicht? vielleicht gdsl_element_t, der ein void* ist? was würdest du besser machen?

Tachyon

fricky schrieb:

Tachyon schrieb:

Die Typsicherheit...

was gefällt dir nicht? vielleicht gdsl_element_t, der ein void* ist? was würdest du besser machen?

C++ Templates benutzen.
Wenn ich mich auf einer derart hohe Abstraktionsebene begebe, dass ich generische Container benötige, würde ich eine andere Sprache wählen.

wenn ich mich nicht irre, wurde hier die binäre suche, bzw. die halbierungssuche noch nicht erwähnt. das bringt auch schon ernome laufzeitverkürzungen.

Tachyon schrieb:

C++ Templates benutzen.

geht nicht in C. ausserdem blasen templates, wenn man nicht aufpasst, das executable ganz schön auf.

Tachyon schrieb:

Wenn ich mich auf einer derart hohe Abstraktionsebene begebe, dass ich generische Container benötige, würde ich eine andere Sprache wählen.

du kannst ja ein grafisches tool nehmen, dass dir aus abstrakten modellen den C-code generiert. aber in C braucht man eigentlich selten was generisches und wenn man's doch braucht, dann ist so 'ne lib da oben^^ doch nicht schlecht.

Badestrand

BorisDieKlinge schrieb:

falls es doch vorkommen würde, das 2 identische ID für unterschiedliche string existieren, müsste ich den string nach gefundener HashID sicherheitshalber nochmal vergleichen denk ich;)

Genau deshalb habe ich die map einen int-Wert auf einen String-Array abbilden lassen - ich hatte auch mal geschaut, zu einem Hashwert gab's sogar immer ~10000 Strings.

ljlöjlk schrieb:

wenn ich mich nicht irre, wurde hier die binäre suche, bzw. die halbierungssuche noch nicht erwähnt. das bringt auch schon ernome laufzeitverkürzungen.

Bitte ein Bit schrieb:

An Badestrand:
Gelle die STL ist doch schön ? Da sind so viele Dinge / Datenstrukturen drin welche man in vielen Fällen gut gebrauchen kann. Und wenn man sich die interne Datenstrukturen von Sets (ich vermute auch mal die Maps) anschaut, kommt man schnell zu Bäumen.

Oh ja, ich merke auch immer wieder (voller Freude), wie bequem doch so einiges ist

BorisDieKlinge

"binäre halbierungssuche" ERKÄRUNG BITTE bin wissenhunrig;)

Badestrand

http://de.wikipedia.org/wiki/Binäre_Suche schrieb:

Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.

Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.

Die Länge des Suchbereiches wird von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf 1 Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.