Unterschiedliche Elemente in einem Array zählen

[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!

[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)