Miniprog: Wer liefert schnellstes snippet :) -> anzahl gleicher zahlen in folge

[Badestrand]

Das kürzeste was ich vom Code her hinbekomme, sieht so aus:

void lala(int const* in, size_t size, int* out)
{
    std::map<int,int> vals;
    for ( size_t i=0; i<size; i++ )
        ++ vals[ in[i] ];
    for ( map<int,int>::iterator iter=vals.begin(); iter!=vals.end(); iter++ )
        *(out++) = iter->second;
}

[gast_xy]

also die version von hustbaer hat halt am ende des arrays ein problem weil er ja dann zu wenig zählt...ohne jetzt vorlaut sein zu wollen...

Ich danke euch allen - aber ich wollte eigentlich nicht die Kürzeste version - sonder die schnellste

aber scheint wohl einher zu gehen....

[gast_xy]

@badestrand...du sortierst vorher nicht nicht wahr?

ich revidiere gerade die aussage von vorhin dass das von hustbaer nicht stimmt....mein hirn nimmts als korrekt an - nur mein eingabe array zählt am ende zu wenig....ich muss noch mal drüberschauen

[Badestrand]

gast_xy schrieb:

@badestrand...du sortierst vorher nicht nicht wahr?

std::map sortiert automatisch, hab ich mir einfach zu eigen gemacht ...

btw, hier meine "schnelle, aber lange" Version:

void lala( int const* in, size_t in_size, int* out, size_t out_size )
{
	struct Duo
	{
		int key;
		int value;

		static void SwapElements( Duo* list, int first, int second )
		{
			Duo tmp = list[first];
			list[first] = list[second];
			list[second] = tmp;
		}

		static void Quicksort( int low, int high, Duo* list )
		{
			int top = low;
			int bottom = high - 1;
			int iPartitionIndex = 0;
			int iPartitionValue = 0;
			if ( low < high )
			{
				if ( high == (low+1) )
				{
					if ( list[low].key >= list[high].key )
						SwapElements( list, high, low );
				}
				else
				{
					iPartitionIndex = static_cast<int>((low + high) / 2);
					iPartitionValue = list[iPartitionIndex].key;
					SwapElements( list, high, iPartitionIndex );
					do
					{
						while ( (list[top].key<iPartitionValue) && (top<=bottom) )
							++top;
						while ( (list[bottom].key>=iPartitionValue) && (top <= bottom))
							--bottom;
						if ( top < bottom )
							SwapElements( list, top, bottom );
					} while ( top < bottom );
					SwapElements( list, top, high );
					Quicksort( low, top-1, list );
					Quicksort( top+1, high, list );
				}
			}
		}
	};

	int n = 0;
	Duo* m = new Duo [ out_size ];

	for ( size_t i=0; i<in_size; ++i )
	{
		bool found = false;
		for ( int j=0; j<n; j++ )
		{
			if ( m[j].key == in[i] )
			{
				++m[j].value;
				found = true;
				break;
			}
		}
		if ( ! found )
		{
			m[n].key = in[i];
			m[n].value = 1;
			++n;
		}
	}

	Duo::Quicksort( 0, n-1, m );

	for ( int i=0; i<n; ++i )
		out[i] = m[i].value;

	delete[] m;
}

[Gast]

KasF schrieb:

Liefert *__first kein pair<int,int> zurück ?

Nein, ein pair<const int,int>

So funktioniert das dann aber auch nicht:

map<int, int> mappo;
std::vector< pair<const int,int> > ergebnis;

mappo.insert(make_pair(4,5));

pair<const int,int> eraser(4,5);
remove_copy(mappo.begin(),mappo.end(),ergebnis.begin(),eraser);

Kann jemand mit remove und ner map ein funkionierendes Beispiel posten.

[Gast]

@finix: Ich habs mal mit deinem select2nd probiert.

template<class T>
struct select2nd
{
    typename T::second_type operator()( const T& val )
    {
        return val.second;
    }
};

int main()
{

    map<int, int> mappo;

    mappo.insert(make_pair(4,5));

    std::vector<int> result;
    transform(mappo.begin(), mappo.end(), result.begin(), select2nd<map<int, int>::value_type>() );

    copy(result.begin(),result.end(),ostream_iterator<int>(cout));

}

"..hat ein Problem festgestellt und muss beendet werden" ???
Wo ist mein Fehler ?

Edit: Oh man, ich schreibe in irgendeinen Speicher.

back_inserter(result);
//oder
std::vector<int> result(mappo.size());

schafft natürlich Abhilfe.

[blogg]

int main(int argc, char* argv[])
{
   int a[] = { 1,1,2,2,2,3,3,5,5,5,5,5 };
   const int num = sizeof(a)/sizeof(int);
   set <int> nr;
   for(int i=0;i<num;i++) nr.insert(a[i]);
   for(set <int>::iterator it=nr.begin();it!=nr.end();it++) cout << count(a,a+num,*it);
   return 0;
}

[Gast]

Normales remove sollte also überhaupt nicht funktionieren mit ner map:

http://www.sgi.com/tech/stl/Map.html schrieb:

[1] Map::iterator is not a mutable iterator, because map::value_type is not Assignable. That is, if i is of type map::iterator and p is of type map::value_type, then *i = p is not a valid expression. However, map::iterator isn't a constant iterator either, because it can be used to modify the object that it points to. Using the same notation as above, (*i).second = p.second is a valid expression. The same point applies to map::reverse_iterator.

Eine remove_copy müsste dennoch irgendwie funktionieren, da die map ( bzw. dessen Iterator ) ja nicht modifiziert wird.

[hustbaer]

gast_xy schrieb:

also die version von hustbaer hat halt am ende des arrays ein problem weil er ja dann zu wenig zählt...ohne jetzt vorlaut sein zu wollen...

Ja, du hast Recht. Doofer Fehler aber auch. So müsste passen:

void lala(int const* in, size_t size, int* out) 
{ 
    (*out)++; 
    for (size_t i = 1; i < size; i++) 
    { 
        if (in[i] != in[i-1]) 
            out++; 
        (*out)++; 
    } 
}

Die schnellste Version von "dem Anderen" (-> 522 statt 2232) wäre IMHO über eine hash-map zu erreichen. Damit kommst du auch auf O(N), vorausgesetzt die Map ist gross genug. Wenn die hash-map allerdings ZU gross wird wird das Anlegen/Auslesen/Freigeben wieder grob aufwändig, womit sich der tolle O(N) Vorteil wieder atomisiert. Könnte also leicht sein dass eine O(N log N) Lösung absolut gesehen (für realistische N) besser ist als die O(N) Lösung namens "hash-map".

Macht übrigens denke ich auch einen Unterschied ob du für 992299333 als Output 423 (erstes Vorkommen zuerst) oder 234 (niedrigstes Element zuerst) brauchst (oder ob beides akzeptabel ist).

[gast_xy]

Danke Hustbaer,

interessant mit den Komplexitätsmaßen...also der input kann wirklich sehr stark variieren , von 20 bis 20000 z.B.
Also erreichen wir ja dann wohl so nur O(nlogn).

Leider lese ich jetzt in den posts immer wieder das die ein oder andere version nicht funktioniert....welche könnte denn jetzt passen - die von blogg? Aber braucht die auch wirklich nur O(nlogn) ?

[Gast]

Funktionieren tut hier eigentlich alles, dass was ich hier dauernd gepostet habe, hat ja nichts wirklich was damit zu tun.

Meine funktionierende Variante von Seite 1 war ja die hier:

int a[] = { 1,1,2,2,2,3,3,5,5,5,5,5 };
const int num = sizeof(a)/sizeof(int);

map<int,int> mappo;

for(int i=0; i<num; ++i)
        ++mappo[a[i]];

[Badestrand]

Meins müsste auch funktionieren (nimm wenn dann die zweite Version)
Hat außerdem erst die Laufzeit O(n) fürs zählen und anschließend O(nlogn) fürs sortieren, also insgesamt auch O(n) (edit: natürlich n*logn!)
Wenn dir die Laufzeit so wichtig ist, prüf doch erst alle Algorithmen auf Korrektheit durch und benchmarke sie dann..

[hustbaer]

Badestrand schrieb:

Meins müsste auch funktionieren (nimm wenn dann die zweite Version)
Hat außerdem erst die Laufzeit O(n) fürs zählen und anschließend O(nlogn) fürs sortieren, also insgesamt auch O(n)
Wenn dir die Laufzeit so wichtig ist, prüf doch erst alle Algorithmen auf Korrektheit durch und benchmarke sie dann..

Badestrand... deine Version hat im besten Fall O(N log N) und im schlechtesten Fall O(N^2).

[Badestrand]

hustbaer schrieb:

Badestrand... deine Version hat im besten Fall O(N log N) und im schlechtesten Fall O(N^2).

Oh, ich meinte eigentlich auch O(n*log(n)).. Und er kann ja auch den Introsort implementieren, der hat auch nlogn als Worst-Case... *brummel*

edit: Habs mal ausprobiert, die map-Methode von KasF steckt mein Quicksort und das set locker in die Tasche Je mehr verschiedene Elemente gegeben sind, desto mehr setzt sich map ab (Faktor > 50), bei wenigen verschiedenen Elementen (bis~100) gewinnt wenigstens noch mein Quicksort.
Gebenchmarkt mit MSVC++ 2003.

[gast_xy]

@badestrand:
Ich weiß es gehört jetzt überhaupt nicht hierher....aber wie misst du deinen code eigentlich? Also könntest du vielleicht deine Zeitmess-Methodik posten?
Merci

[hustbaer]

Badestrand... deine Version hat auch ohne den Sort im besten Fall O(N*M) und im schlechtesten Fall ist eben N=M -> O(N^2).

Guck dir mal deine verschachtelte Schleife näher an...

[Badestrand]

hustbaer schrieb:

Badestrand... deine Version hat auch ohne den Sort im besten Fall O(N*M) und im schlechtesten Fall ist eben N=M -> O(N^2).

Guck dir mal deine verschachtelte Schleife näher an...

Ja ich weiß... Für eine hohe Anzahl an out-Werten ist meine Methode ziemlich ziemlich schlecht Ich sag ja gar nix mehr dagegen

gast_xy schrieb:

@badestrand:
Ich weiß es gehört jetzt überhaupt nicht hierher....aber wie misst du deinen code eigentlich? Also könntest du vielleicht deine Zeitmess-Methodik posten?
Merci

// Die beiden Parameter bestimmen die Laufzeit des Programms
	size_t in_size = 1000000,              // Wieviele Zahlen sind im Array
		   max_in_value = 1000;        // Wie groß ist die Streuung der Zahlen

	// "in" mit Zufallswerten füllen
	int* in = new int [ in_size ];
	srand( GetTickCount() );
	for ( size_t i=0; i<in_size; i++ )
		in[i] = rand() % max_in_value;

	// "out"-Größe ermitteln und 
	std::map<int,int> vals;
    for ( size_t i=0; i<in_size; i++ )
        ++ vals[ in[i] ];
	size_t out_size = vals.size();
	int* out = new int [ out_size ];

	typedef void(*lala)(const int*,size_t,int*,size_t);
	lala funcs[3] = { lala1, lala2, lala3 }; // Das sind die verwendeten Funktionen

	for ( size_t i=0; i<sizeof(funcs)/sizeof(funcs[0]); ++i )
	{
		memset( out, 0, out_size*sizeof(int) );
		time_t start = GetTickCount();
		cout << "Beginning..." << endl;
		funcs[i]( in, in_size, out, out_size );
		cout << "Finished...: " << GetTickCount()-start << " ms" << endl;
		for ( size_t j=0, k=0; j<out_size; j++ )
			k += j*out[j];
		cout << "Checksum: " << j << endl << endl;
	}

	delete[] in;
	delete[] out;

// Die verwendeten Funktionen müssen diesen Kopf haben:
// void lala3( int const* in, size_t in_size, int* out, size_t out_size )

[thordk]

die verwurstete bucketsort variante kam doch bereits und die rennt in verdammt linearer zeit. glaub kaum, dass man ne lösung findet, die nicht wenigstens alle elemente einmal angucken muss.

[jipio]

Wenn wir schon so dabei sind:
BucketSort kann man eigentlich nicht mit den anderen Verfahren vergleichen weil es zusätzliche Annahmen trifft die für die "gewöhnlichen" Sortierverfahren nicht gelten. Z.B Gleichverteilung des inputs. Außerdem ist es kein in-place verfahren - braucht also zusätzlichen Speicher (was u.U. doch ein Argument sein kann).
Außerdem gilt die Unterbietung der unteren schranke von O(nlogn) nur für den average case....