Unterschiedliche Elemente in einem Array zählen

crispin kenton

SeppJ schrieb:

crispin kenton schrieb:

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

Nee, das ist doof. Erst einmal O(N*log(N)) Komplexität für das Sortieren und hinterher müssen wir noch einmal zusätzlich komplett Iterieren.

So doof auch wieder nicht. Sortieren ist idr. in-place, das hat man bei einer Baumvariante nicht. Einfügen in einen balancierten Baum ist auch O(n*log n). Der eine scan über das Array ist doch fast kostenlos, wird sowas überhaupt in O eingerechnet und wenn ja dann mit O(n), oder...

SeppJ

Du nennst hier verschiedene Dinge N. Einmal ist es die Anzahl der Elemente, einmal die Anzahl der unterschiedlichen Elemente.

Speicherplatz ist irrelevant, außer es wird explizit verlangt. Prozessorzeit ist nie irrelevant.

In-Place sortieren: Yay! Das dürfen wir einmal selber implementieren, da qsort nicht in-place arbeitet. Das heißt, wir enden wahrscheinlich mit einer lahmen Heapsortimplementierung.

Wenn wir hinterher die Daten verarbeiten wollen, brauchen wir immer noch die assoziative Datenstruktur und hätten uns das ganze Sortieren gleich sparen können.

Das heißt für den Extremfall, dass wir einen in-place Algorithmus benötigen, der die Ergebnisse direkt verarbeitet, ist Sortieren eine gute Idee. Für alle anderen Fälle bringt es uns in eine schlechtere Komplexitätsklasse (auf der Anzahl der Elemente). Nein, das ist nicht gut .

crispin kenton

SeppJ schrieb:

Du nennst hier verschiedene Dinge N. Einmal ist es die Anzahl der Elemente, einmal die Anzahl der unterschiedlichen Elemente.

Wo hast du das rausgelesen?

SeppJ schrieb:

Speicherplatz ist irrelevant, außer es wird explizit verlangt.

so ein käse... mehr verteilter nicht zusammenhängender speicher führt einfach zu einer hohen cache miss rate.

SeppJ schrieb:

Das heißt für den Extremfall, dass wir einen in-place Algorithmus benötigen, der die Ergebnisse direkt verarbeitet, ist Sortieren eine gute Idee. Für alle anderen Fälle bringt es uns in eine schlechtere Komplexitätsklasse (auf der Anzahl der Elemente).

Komplexitätsklasse ist Theorie(zumindest wenn es sich in dem bereich bewegt), ich bin mir sicher, dass in der Praxis einen Sortiervariante mit hoher wahrscheinlichkeit schneller ist.

mir ist es aber auch egal, soll er doch seinen baum bauen, da braucht er erst mal einene eigene implementation, das wird lustig...

crispin kenton

ich will ja auch kein korinthenkacker sein, aber deine lösung ist langsamer als O(n*log(n))... zumindest in einer std. implementation, da man erst sucht ob ein wert vorkommt und dann entweder erhöht oder einfügt. das heißt nur wenn alle zahlen gleich sind hat deiner O(n*log(n)) :p

knivil

Wat? Kann mir jemand mal eine Loesung in weniger als O(n*log n) nennen oder worum geht es hier? Hashtabellen sind geschummelt und mag ich nicht fuer solch ein einfaches Problem.

crispin kenton

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

aber eig. sollte es ja darüber gehen was für OP das beste ist - ach, egal

SeppJ

crispin kenton schrieb:

SeppJ schrieb:

Du nennst hier verschiedene Dinge N. Einmal ist es die Anzahl der Elemente, einmal die Anzahl der unterschiedlichen Elemente.

Wo hast du das rausgelesen?

Aus deinem Text.

Du tust es wieder:

ich will ja auch kein korinthenkacker sein, aber deine lösung ist langsamer als O(n*log(n))... zumindest in einer std. implementation, da man erst sucht ob ein wert vorkommt und dann entweder erhöht oder einfügt. das heißt nur wenn alle zahlen gleich sind hat deiner O(n*log(n)) :p

Gleicher Fehler. Gerade dann, wenn alle Zahlen gleich sind, ist mein Algorithmus besonders gut, da er von der Komplexität her mit der Anzahl der unterschiedlichen Elemente geht.

Komplexitätsklasse ist Theorie(zumindest wenn es sich in dem bereich bewegt), ich bin mir sicher, dass in der Praxis einen Sortiervariante mit hoher wahrscheinlichkeit schneller ist.

Jaja, die Evolution und die Relativität gibt es nicht. Alles nur Theorien.

knivil

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.

Legt man sich auf Integer fester Laenge fest, so ist Radixsort etc. eine Option. Jedoch wuerde ich nachmessen.

SeppJ

knivil schrieb:

Wat? Kann mir jemand mal eine Loesung in weniger als O(n*log n) nennen oder worum geht es hier? Hashtabellen sind geschummelt und mag ich nicht fuer solch ein einfaches Problem.

Wieso wäre das geschummelt? Das ist doch sogar das, was der TE versucht und auch das, was ich hier nehmen würde. Hier ist hash(x) eben x selber und der Table ein Array. Laufzeit: O(N).

knivil

Weils nur Integer sind. und Hashtabellen nicht wirklich O(1) sind.

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!