Unterschiedliche Elemente in einem Array zählen

paddy_bo

Hallo Liebe Community,
Ich muss für mein Studium ein Programm schreiben, welches die unterschiedlichen Elemente in einem Array zählt. Wie gesagt es sollen nur die UNTERSCHIEDLICHEN Elemente im Feld gezählt werden. Und da liegt genau mein Problem. Ich habe einmal versucht, mit Hilfe eines zweiten Feldes nur die nicht wiederholten Elemente zu übernehmen und dann diese auszugeben aber so richtig funktioniert das nicht. Ich hoffe ihr könnt mir helfen

int tag[4]={3,6,3,9,2}

neutag[0]=tag[0];
 for(j=0;j<4;j++)
 {
  for(k=1;k<4;k++)
  {
   if(tag[k]!=neutag[j])
   {
    neutag[j+1]=tag[k];
   }
   else
    break;
  }
 }
   for (z = 0; z < 4; z++) 
    if (neutag[z] != 0) 
      printf ("Element: %i\n", neutag[z]);
    else  
      break;
  }

crispin kenton

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

Swordfish

...

paddy_bo

Ja selbst verständlich, ich war nur gerad ein wenig im Stress.

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

int main(int argc, char *argv[])
{
  int u=0;
  int i=0;
  int j=0;
  int k=0;
  int z=0;
  int tag[u];
  int neutag[u];

  printf("Wie viele Unfälle sind diesen Monat passiert? ");
  scanf("%i",&u);
  for(i=0;i<u;i++)
  {
   printf("Geben Sie den Tag des %i. Unfalls an: ",i+1);
   scanf("%i",&tag[i]);
  }
 neutag[0]=tag[0];
 for(j=0;j<u;j++)
 {
  for(k=1;k<u;k++)
  {
   if(tag[k]!=neutag[j])
   {
    neutag[j+1]=tag[k];
   }
   else
    break;
  }
 }
   for (z = 0; z < u; z++)
  {
    if (neutag[z] != 0) 
      printf ("Element: %i\n", neutag[z]);
    else  
      break;
  }
  system("PAUSE");	
  return 0;
}

Wenn man nun nur unterschiedliche Elemente im Feld "tag" eingibt, übernimmt er diese ohne probleme auch in "neutag". Wenn sich in "tag" nun jedoch ein Element wiederholt, kommen bei der Ausgabe utopische Zahlen heraus.

Swordfish

...

paddy_bo

/* Egal. Ein Array der Groesze 0 !? */

Ich definiere die Größe des Arrays ja dadurch, dass ich die Anzahl der Unfälle(u) angebe.

Du schreibst auch über Arraygrenzen ...

Inwiefern überschreib ich das denn?
Tut mir Leid ich bin in C noch relativ unerfahren, da ich bisher erst seit gut einem Monat damit programmiere.

Swordfish

...

gary1195

paddy_bo schrieb:

/* Egal. Ein Array der Groesze 0 !? */

Ich definiere die Größe des Arrays ja dadurch, dass ich die Anzahl der Unfälle(u) angebe.

Du schreibst auch über Arraygrenzen ...

Inwiefern überschreib ich das denn?
Tut mir Leid ich bin in C noch relativ unerfahren, da ich bisher erst seit gut einem Monat damit programmiere.

zum Zeitpunkt der Definition der Arrays (in Zeilen 11,12) hat u den Wert 0 also haben die arrays die Größe 0. Somit schreibst du über die Grenzen des Arrays hinaus(hier obere Grenze: 0 und untere Grenze: 0)

SeppJ

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. Wenn wir das Ergebnis hinterher noch in eine Datenstruktur schrieben (weil wir damit weiterarbeiten wollen), anstatt es direkt auszugeben, dann hätten wir das alles umsonst getan, denn das Schreiben in eine Datenstruktur ist schon die Lösung: Wir brauchen irgendeine Art assoziative Struktur Element->Anzahl. Damit iterieren wir bloß einmal über das Array und zählen für jeden Element mit.

So eine Struktur kann je nach Art und Anzahl der Elemente anders aus sehen. Allgemeine Lösungen sind Binärbäume (C++: map) und Hashtables (C++ unordered_map), die uns allgemeine Assoziationen bieten für alle möglichen Arten von (sortierbaren) Elementen. Oder hier, für überschaubar viele Elemente, einfach ein Array, in dem der Index selber das Element darstellt.

paddy_bo schrieb:

/* Egal. Ein Array der Groesze 0 !? */

Ich definiere die Größe des Arrays ja dadurch, dass ich die Anzahl der Unfälle(u) angebe.

Nein. C ist eine imperative Sprache mit eager evaluation:

int a,b;
a = 5;
b = a;
a = 7;

printf("%d", b); // 5, nicht 7

Das ist ganz, ganz elementar, um überhaupt Programme in C schreiben zu können. Bitte nochmal die absoluten Grundlagen aus einem guten Buch (z.B. K&R) reinziehen.

Du schreibst auch über Arraygrenzen ...

Inwiefern überschreib ich das denn?

Weil du in etwas schreibst, was 0 Elemente hat, siehe oben.

Tut mir Leid ich bin in C noch relativ unerfahren, da ich bisher erst seit gut einem Monat damit programmiere

Bevor du dich jetzt in Arrays und andere kompliziertere Probleme vertiefst, wiederhole noch einmal das Gelernte gründlich.

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.