Unterschiedliche Elemente in einem Array zählen

SeppJ

knivil schrieb:

es geht darum, ob sortieren und dann die unterschiede zählen schneller ist als einen baum aufbauen.

Beides O(n*log n), deswegen verstehe ich die Argumentation mit der O-Notation nicht.

Unterschiedliche Ns:

Sei N die Zahl der Elemente in der Basismenge, M die Anzahl der unterschiedlichen Elemente:

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)

Zusätzlich kommt bei der Sortiervariante hinterher noch ein Zählalgorithmus hinzu (den haben Baum und Table gleich mit erschlagen). Dieser wird exakt der gleiche Table oder Binärbaum sein, je nachdem, wie das Ergebnis aussehen soll (irgendwie muss das Ergebnis schließlich weiterverarbeitet werden, die Daten müssen irgendwo gespeichert werden^*). Das verändert zwar die Komplexitätsklasse des Sortierens nicht mehr, aber im Endeffekt heißt es, dass das Sortieren reine Zeitverschwendung war, denn um den Baum/Table zu bauen, brauchen die werte nicht vorsortiert zu sein. Für den Baum ist das sogar eher hinderlich!

knivil schrieb:

Hashtabellen nicht wirklich O(1) sind.

Nahe genug dran, um aus diesem Grund benutzt zu werden. Gerade hier hauen sie richtig gut rein.

^*: Die eine Ausnahme habe ich oben genannt: Wir können sofort verarbeiten, zum Beispiel weil die Verarbeitung eine Ausgabe ist, und wir nichts speichern müssen.

crispin kenton

SeppJ schrieb:

Für den Baum ist das sogar eher hinderlich!

Aha, und warum?

SeppJ schrieb:

Sei N die Zahl der Elemente in der Basismenge, M die Anzahl der unterschiedlichen Elemente:

Sortieren (reines Sortieren, noch ohne Zählen): O(Nlog(N))
Binärbaum aufbauen (komplett, mit Zählen): O(Nlog(M))

okay, seh ich ein.

@edit:
Sortieren: O(N*(log(N)+1))
Binärbaum: O(N*log(M))

darum mach ich mir nicht in die hose... wie gesagt, sortieren und ein scan geht in 10 zeilen.

crispin kenton

SeppJ schrieb:

knivil schrieb:

Hashtabellen nicht wirklich O(1) sind.

Nahe genug dran, um aus diesem Grund benutzt zu werden. Gerade hier hauen sie richtig gut rein.

ich bring mal noch einen vorgeschalteten blöömfilter für dein bäumchen ins gespräch. der ist zumindest im gegensatz zum hash für sowas gedacht. aber der ist in der theorie sicher auch wieder langsamer

SeppJ

crispin kenton schrieb:

SeppJ schrieb:

Für den Baum ist das sogar eher hinderlich!

Aha, und warum?

Weil du im Durchschnitt mehr ausgleichen musst (außer du weißt schon im Voraus, dass die Daten sortiert sein werden und passt den Baumalgorithmus entsprechend an.

Sortieren: O(N*(log(N)+1))

O-Notation funktioniert anders.

darum mach ich mir nicht in die hose... wie gesagt, sortieren und ein scan geht in 10 zeilen.

Aber wozu müssen die Daten sortiert sein? Du kannst doch auch einfach so scannen!

crispin kenton

SeppJ schrieb:

Sortieren: O(N*(log(N)+1))

O-Notation funktioniert anders.

Wie soll das sonst ausgedrückt werden

So? O((N*log(N))+N)

camper

crispin kenton schrieb:

SeppJ schrieb:

Sortieren: O(N*(log(N)+1))

O-Notation funktioniert anders.

Wie soll das sonst ausgedrückt werden

So? O((N*log(N))+N)

Das kann man zwar so aufschreiben, Kleinheiten höherer Ordnung sind bei Grenzwertbetrachtungen aber irrelevant.
O((N*log(N))+N) == O(N*log(N))

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
)