Unterschiedliche Elemente in einem Array zählen

knivil

Sortieren (reines Sortieren, noch ohne Zählen): O(Nlog(N))
Binärbaum aufbauen (komplett, mit Zählen): O(Nlog(M))
Table aufbauen (komplett, mit Zählen): O(N) (außer wir haben wirklich viele Kollisionen)

Guter Punkt O(n log m). Leider bin ich negativ gebrandmarkt bei Hashtabellen. Gegenueber std::set hatten sie erst bei Elementanzahl groesser als 100000 was gebracht.

crispin kenton

// map::insert (C++98)
#include <iostream>
#include <map>
#include <random>

#include <stdio.h>
#include <stdlib.h>

#include <sys/time.h>

int cmp_int(const void *a,const void *b){
	return *((int*)a)-*((int*)b);
}

double getTime(){
	struct timeval tp;

	gettimeofday(&tp,0);
	return tp.tv_usec / 1000000.00 + tp.tv_sec;
}

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

	size_t len = 1024 * 1024;
	size_t l = len;
	int *data = (int*)malloc(sizeof(int) * len);
	std::map<int,int> mymap;
	double start;

	if(data){
		l = len;
		while(l--){
			data[l] = rand() % 1000;
		}

		l = len;
		/*while(l--){
			printf("[%zu] => %d\n",l,data[l]);
		}*/

		l = len;
		start = getTime();
		while(l--){
			std::map<int,int>::iterator it = mymap.find(data[l]);
			if(it != mymap.end()){
				it->second++;
			}else{
				mymap.insert(std::pair<int,int>(data[l],1));
			}
		}
		printf("Tree: %f\n",getTime() - start);

		start = getTime();
		qsort(data,len,sizeof(int),cmp_int);
		printf("Sort: %f\n",getTime() - start);

		free(data);
	}
	return 0;
}

panda@white:~/Desktop/childs$ g++ test.cpp -std=c++0x && ./a.out
Tree: 0.505556
Sort: 0.310263

ich wollt jetzt erst mal nicht weitermachen, ehe wir nicht sicher sind, dass da kein fehler drin ist, da ich kein c++ programmierer bin

@nachtrag: die sort in c++ ist schneller, da hatte volkard mal ein benchmark...

crispin kenton

weitermachen mit dem durchzählen in der c-version natürlich :p

SeppJ

Ähh, du hast da eine Kleinigkeit vergessen bei deinem Benchmark. Das Zählen. Also das, worum es geht. Nur die Map hat mitgezählt, beim sort ist das immer noch auf der Todo-Liste.

Außerdem benutzt du die map falsch. Einfach ++mymapp[data[l]]. Oder wenigstens insert mit Hint, wenn man schon vorher gesucht und gefunden hat (ist aber immer noch doppelt so umständlich wie der erste Vorschlag). So wie du es derzeit machst, suchst du 2x.

Mit dieser Änderung bekomme ich:

Tree: 0.087345
Sort: 0.214867

Wohlgemerkt: Das Sort hat hier noch nicht einmal gezählt!

Wenn wir das C++-Sort nehmen:

Tree: 0.087050
Sort: 0.066687

Also:
1. Das Sort muss immer noch bitte einmal zählen (@crispin: Wie?)
2. C++-Templates FTW!

crispin kenton

SeppJ schrieb:

Wohlgemerkt: Das Sort hat hier noch nicht einmal gezählt!

du mit ++mymapp[data[l]] auch nicht...

aber zählen geht wenn ich mich nicht grob täusche in 0.001s.

SeppJ schrieb:

2. C++-Templates FTW!

es dreht sich hier noch immer um C89, C99 und C11.

crispin kenton

noch dazu sollte man nicht vergessen, dass ich extra um dir raum zu geben ein % 1000 an die rand() angehängt hab. aber selbst da tust du dich mit deiner c++ version schwer! ...

crispin kenton

bei mir kommt selbst mit ++mymap[data[l]];

also

// map::insert (C++98)
#include <iostream>
#include <map>
#include <random>

#include <stdio.h>
#include <stdlib.h>

#include <sys/time.h>

int cmp_int(const void *a,const void *b){
	return *((int*)a)-*((int*)b);
}

double getTime(){
	struct timeval tp;

	gettimeofday(&tp,0);
	return tp.tv_usec / 1000000.00 + tp.tv_sec;
}

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

	size_t len = 1024*1024;
	size_t l = len;
	int *data = (int*)malloc(sizeof(int) * len);
	std::map<int,int> mymap;
	double start;

	if(data){
		l = len;
		while(l--){
			data[l] = rand() % 1000;
		}

		l = len;
		/*while(l--){
			printf("[%zu] => %d\n",l,data[l]);
		}*/

		l = len;
		start = getTime();
		while(l--){
			++mymap[data[l]];
		}
		printf("Tree: %f\n",getTime() - start);

		start = getTime();
		qsort(data,len,sizeof(int),cmp_int);
		printf("Sort: %f\n",getTime() - start);

		free(data);
	}
	return 0;
}

panda@white:~/Desktop/childs$ g++ test.cpp -std=c++0x && ./a.out
Tree: 0.487014
Sort: 0.310705

raus

SeppJ

crispin kenton schrieb:

SeppJ schrieb:

Wohlgemerkt: Das Sort hat hier noch nicht einmal gezählt!

du mit ++mymapp[data[l]] auch nicht...

Doch?

crispin kenton schrieb:

SeppJ schrieb:

2. C++-Templates FTW!

es dreht sich hier noch immer um C89, C99 und C11.

Um so schlimmer für deine Lösung, da bricht das sort um Faktor 4 ein. Ich glaube, du hast nicht verstanden, worauf sich meine Bemerkung bezog. Es ging darum, dass das C++-Sort so viel schneller ist als C-Sort.

crispin kenton schrieb:

panda@white:~/Desktop/childs$ g++ test.cpp -std=c++0x && ./a.out

Au weia! Lass das mit Performancmessungen mal lieber die Erwachsenen machen und halt dich in Zukunft da raus. Wenn du so misst, dann ist das kein Wunder, dass du so verquere Vorstellungen von einfachen Dingen hast. Fällt dir denn hier kein Anfängerfehler auf?

Nochmal zwei Bemerkungen, eine alt, eine neu:
1. Liefer doch mal ein Zählergebnis nach dem Sortieren. In welcher Form würdest du überhaupt das Ergebnis liefern? Wie erhältst du es?
2. Der Elefant im Raum, den noch niemand angesprochen hat, weil er sich hinter der Mammutherde versteckt hat:

void zaehle_elemente(datentyp *elemente, size_t size, ergebnistyp *ergebnis);
// vs.
void zaehle_elemente(const datentyp *elemente, size_t size, ergebnistyp *ergebnis);

Ojeh, ein weiteres dickes Problem für die Sortieridee.

Nebenbemerkung dazu: Du hattest auch mal was von in-place als Vorteil gesagt, das hat sich damit wohl auch erledigt (wei gehst du da eingetnlich mit dem Ergebnis um?). Nicht dass das schnelle Quicksort in-place wäre. Ein in-place Algorithmus kann zwar auch O(N*log(N)) sein, aber hätte weitaus größere Konstanten.

P.S.: Und noch eine dritte Bemerkung:
Die Hashmap habe wir noch gar nicht rausgeholt:

l = len;
        start = getTime();
        while(l--){
          ++mymap[data[l]];
        }
        printf("Tree (komplett gezählt): %f\n",getTime() - start);

        std::unordered_map<int,int> my_hash_map;
        l = len;
        start = getTime();
        while(l--){
          ++my_hash_map[data[l]];
        }
        printf("Hashmap (komplett gezählt): %f\n",getTime() - start);

        int my_poor_hash_map[1000] ={0};
        l = len;
        start = getTime();
        while(l--){
          ++my_poor_hash_map[data[l]];
        }
        printf("Hashmap für Arme (komplett gezählt): %f\n",getTime() - start);
        printf("Anti Optimierung: %d\n", my_poor_hash_map[500]);

        start = getTime();
        std::sort(data, data+len);
        printf("C++-Sort (Ohne Zählen): %f\n",getTime() - start);

Damit:

Tree (komplett gezählt): 0.088626
Hashmap (komplett gezählt): 0.017943
Hashmap für Arme (komplett gezählt): 0.002230
C++-Sort (Ohne Zählen): 0.078775

Oh, weh, nicht einmal das C++-Sort kommt da mit. Erst recht nicht gegen die allereinfachste Lösung (die der TE ohnehin vor hatte), die (erwartungsgemäß) selbst die Hashmap weit abhängt.

Folgerung:

SeppJ schrieb:

crispin kenton schrieb:

ich würde erst mal sortieren, aber wart mal auf die cracks

Nee, das ist doof.

QFT!

crispin kenton

SeppJ schrieb:

P.S.: Und noch eine dritte Bemerkung:
Die Hashmap habe wir noch gar nicht rausgeholt:

WIR? Den anderen mir inklusive ist die diskussion doch schon längst zu blöd. du brichst dir einen ab, um iwie das sort zu dissen, was als antwort für einen c anfänger _mehr_ als OK und mit absoluter sicherheit nicht doof ist.

SeppJ schrieb:

SeppJ schrieb:

crispin kenton schrieb:

ich würde erst mal sortieren, aber wart mal auf die cracks

Nee, das ist doof.

QFT!

sowas dann am ende zu bringen ist nach der diskussion eig. nur peinlich, sry

SeppJ

crispin kenton schrieb:

du brichst dir einen ab, um iwie das sort zu dissen, was als antwort für einen c anfänger _mehr_ als OK und mit absoluter sicherheit nicht doof ist.

Nein, es ist eben nicht ok. Der TE hatte eine einfachere und bessere Lösung, du hast ihm diesen Unsinn nahegelegt. Das muss gerade gerückt werden. Das Sort bringt gar nichts zur Lösung der Problemstellung, nur sinnlose Zusatzarbeit.

sowas dann am ende zu bringen ist nach der diskussion eig. nur peinlich, sry

Geh auf meine vielen Argumente ein, greif nicht meine Ausdrucksweise an. Oder hast du keine Argumente? Dachte ich mir, schließlich habe ich alles was du gesagt hast, in dem riesigen Beitrag widerlegt, um so zu zeigen, dass das was ich auf Seite 1 gesagt habe, absolut richtig war, du nur nicht hören wolltest.

Nochmal zusammengefasst:
1. Sort zählt nicht, Zählen fehlt noch. Deine Erwiderung?
2. Sort zählt nicht, irgendwie muss das Ergebnis noch rausgegeben werden. Wie?
3. Sort verändert die Daten. Kopie machen? Einfach schlucken? Was, wenn die Daten unveränderlich sind (also der Normalfall in const-korrekten Programmen)?
4. Sort ist (in C) langsamer als alle anderen Methoden, dabei zählt es noch nicht einmal und hat die Daten verändert. Gezeigt durch deinen eigenen Benchmark (wenn man ihn richtig benutzt).
5. Sort ist in C++ langsamer als alle anderen Methoden und ungefähr gleich schnell wie die map, dabei zählt es noch nicht einmal und hat die Daten verändert. Gezeigt durch deinen eigenen Benchmark (wenn man ihn richtig benutzt).

Dann habe ich noch einen Angriff auf deine persönliche Kompetenz bezüglich Performancemessungen gemacht. Dieser ist gut begründet, denn du hast unoptimierte Programme verglichen. Peinlicher Anfängerfehler. Deine Erwiderung?

Und noch ältere Argumente von der 1.-2. Seite:
Sort ist eine Aktion in O(N*log(N)), die Tabellenlösung ist O(N). Und das Sort hat immer noch nicht gezählt und hat immer noch die Daten verändert. Erwiderung?

Also: Wieso möchtest du die Daten sortieren? (Außer dass dies deine erste flotte Idee war, die du nun zwanghaft verteidigst)

crispin kenton

SeppJ schrieb:

crispin kenton schrieb:

du brichst dir einen ab, um iwie das sort zu dissen, was als antwort für einen c anfänger _mehr_ als OK und mit absoluter sicherheit nicht doof ist.

Nein, es ist eben nicht ok. Der TE hatte eine einfachere und bessere Lösung, du hast ihm diesen Unsinn nahegelegt. Das muss gerade gerückt werden. Das Sort bringt gar nichts zur Lösung der Problemstellung, nur sinnlose Zusatzarbeit.

er muss doch nicht zählen wie oft jedes unterschiedliche element im array vorkommt, sondern wie viele unterschiedliche elemente es enhält.

paddy_bo schrieb:

Ich muss für mein Studium ein Programm schreiben, welches die unterschiedlichen Elemente in einem Array zählt.

SeppJ schrieb:

Geh auf meine vielen Argumente ein

wir reden schon viel zu lang aneinander vorbei als dass es etwas bringen würde. festhalten würde ich:

* es gibt für unterschiedliche werte unterschiedliche optimale lösungen.
* sort ist das einfachste für einen c anfänger
* das problem ist gelöst!

SeppJ

crispin kenton schrieb:

er muss doch nicht zählen wie oft jedes unterschiedliche element im array vorkommt, sondern wie viele unterschiedliche elemente es enhält.

Dabei hilft dir sort wie? Was macht das, was eine Tabelle nicht besser kann?

* es gibt für unterschiedliche werte unterschiedliche optimale lösungen.
* sort ist das einfachste für einen c anfänger
* das problem ist gelöst!

Deine Argumentation ist bloß Behauptung. Oben sind (möglicherweise vor deiner Antwort) noch einmal alle Argumente gegen Sort sauber aufgeführt in meinen Beitrag reineditiert.

* es gibt für unterschiedliche werte unterschiedliche optimale lösungen.

Diplomatisches Blabla. Man kann alles so verwässern, dass jede Aussage irgendwie irgendwo irgendwann richtig ist.

* sort ist das einfachste für einen c anfänger

Das möchte ich sehen. Der TE kann gerade mal Arrays. Zufällig ist ein Array, alles was er bräuchte. Ganz ohne void*-Abstraktion und Funktionszeiger auf Vergleichsfunktionen.

* das problem ist gelöst!

Ehrlich gesagt: Nein! Zumindest habe ich von dir immer noch keine Liste der unterschiedlichen Elemente nach dem Sort erhalten. In der Map/Hashtable/Array stehen die Elemente alle drin. Sogar mit Anzahl! Bisher hat dein Algorithmus bloß Strom verbraucht, um Daten zu sortieren, es gibt noch kein Ergebnis.

crispin kenton

SeppJ schrieb:

* das problem ist gelöst!

Ehrlich gesagt: Nein! Zumindest habe ich von dir immer noch keine Liste der unterschiedlichen Elemente nach dem Sort erhalten. In der Map/Hashtable/Array stehen die Elemente alle drin. Sogar mit Anzahl!

dafür hast du sicher während deines studiums ein fleißsternchen bekommen - ich muss jetzt kuchen holen, sonst machen meine eltern ärger

SeppJ

Dann mal guten Hunger . Wenn dir noch was einfällt, kannst du dich ja melden. Ansonsten steht erst einmal, dass die naive Idee mehr als nur das gesuchte Ergebnis liefert und das auch noch schneller als das Sort, das nach wie vor die Aufgabe überhaupt nicht erfüllt hat. In der Schule wäre das eine knappe 4- für den Ansatz. Ansonsten ist das ein Forum zum Lernen, nicht zum Recht haben. Ich hoffe, du lernst wenigstens, das man zum Zählen nicht Sortieren braucht und benutzt das später selber; anstatt aus diesem Thread mitzunehmen, dass irgendein Blödmann die Genialität deiner Idee nicht erkannt hat.

(Weitere versteckte Lektionen:
-Aufpassen bei Komplexitätsargumenten, dass man nicht mittendrin sein N verändert
-Niemanden interessiert es, wie schnell unoptimierter Code läuft
-Niemanden interessiert es, wie schnell ein Code ein falsches (hier: unvollständiges) Ergebnis liefert
)

crispin kenton

SeppJ schrieb:

Ansonsten ist das ein Forum zum Lernen, nicht zum Recht haben. Ich hoffe, du lernst wenigstens, das man zum Zählen nicht Sortieren braucht und benutzt das später selber;

ich hab zumindest in teilen an der gefro* suchfunzel mitgewirkt. da wird öfter gezählt und sortiert. ich denk davon kann sich in sachen performance ein großteil eine große scheibe abschneiden.

SeppJ schrieb:

(Weitere versteckte Lektionen:
-Aufpassen bei Komplexitätsargumenten, dass man nicht mittendrin sein N verändert
-Niemanden interessiert es, wie schnell unoptimierter Code läuft
-Niemanden interessiert es, wie schnell ein Code ein falsches (hier: unvollständiges) Ergebnis liefert
)

du tust gerade so, als hätte deine baum-lösung 'gewonnen'

SeppJ

crispin kenton schrieb:

du tust gerade so, als hätte deine baum-lösung 'gewonnen'

Die funktionierende, naive Arraylösung gewinnt kampflos gegen deine Sortier-Nichtlösung. Die Benchmarks waren auch mehr als eindeutig. Und das Komplexitätsargument ist auch noch da.

crispin kenton

ach, ist doch egal. belassen wir es dabei, ich muss nicht recht haben und wir müssen uns auch wegen so einem unsinn nicht zerfleischen.

ich komm auch auf dem holzweg nach rom