4. durchsuchen von 2 dim Arrays nach gleichen Wertepaaren

durchsuchen von 2 dim Arrays nach gleichen Wertepaaren

  • ?

    Hallo!

    Ich tapse gerade die ersten Schritte durch C und möchte ein 2D Array von Integerwerten auf gleiche Paare durchsuchen.

    Bsp.:
    3,2
    5,6
    2,5
    2,3
    8,1
    1,2
    3,4
    2,3

    Das Paar 2,3 tritt oben dreifach auf (die Reihenfolge 3,2 oder 2,3 ist egal) und die Mehrfacheinträge möchte ich eliminieren oder kennzeichnen (z.B. in dem ich dort z.B. 0,0 eintrage oder mit -1 multipliziere), so daß am Ende jedes Wertepaar nur einmal auftritt.

    Ich kann davon Ausgehen, daß nie zwei gleiche Werte pro Datensatz auftreten.
    Also der Fall 5,5 oder 6,6 kommt nicht vor.

    Die Wertepaare dürfen ruhig durcheinandergewürfelt werden.

    Der brute force Ansatz wäre jetzt jedes Paar mit jedem anderen zu vergleichen, was aber recht lange dauert.
    Im eigentlichen Programm können leicht 4-6 Mio. Datenpaare auftreten.

    Deshalb glaube ich meine Idee ist etwas geschickter:

    1. Sortieren der Wertepaare, daß der kleinere Wert immer vorne steht
    2. sortieren des Arrays auf- oder absteigend nach der 1. Spalte
    3. prüfen, ob nacheinander 2 gleiche Werte in der 1. Spalte stehen und wenn ja prüfen, ob der Wert der 2. Spalte auch identisch ist.

    Schritt 1 ist ja leicht getan, aber beim sortieren mit qsort scheitere ich.

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

int cmp(void const *A_p, void const *B_p) {
  int column = 0;
  int retval = 0;

  int const *A = (int const *) A_p;
  int const *B = (int const *) B_p;

  if (A[column] < B[column]) retval = -1;
  if (A[column] > B[column]) retval =  1;

  return (retval);
}

int main(void) {
int i;
int Columns = 2;
int Lines  = 8;

int **Values;

  Values = (int**) malloc (Lines * sizeof(int *));
  if (NULL == Values )
  {
    printf("ERROR: Malloc error Values Phase 1!\n" );
    goto Exit;
  }
  for (i=0; i < Lines; i++)
  {
    Values[i] = (int*) malloc (Columns * sizeof(int));
    if (NULL == Values[i] )
    {
    printf("ERROR: Malloc error Values Phase 2!\n" );
    goto Exit;
    }
  }

Values[0][0]=5;
Values[1][0]=2;
Values[2][0]=2;
Values[3][0]=3;
Values[4][0]=2;
Values[5][0]=1;
Values[6][0]=1;
Values[7][0]=3;

Values[0][1]=6;
Values[1][1]=5;
Values[2][1]=3;
Values[3][1]=6;
Values[4][1]=3;
Values[5][1]=2;
Values[6][1]=4;
Values[7][1]=4;

for(i = 0; i < Lines ; ++i) { 
  printf("%i %i\n", Values[i][0], Values[i][1]);
}
  printf("\n");

qsort(Values, Lines, sizeof (int*), cmp); 

  printf("\n");
for(i = 0; i < Lines; ++i) { 
  printf("%i %i\n", Values[i][0], Values[i][1]);
}
  printf("\n");

Exit:

return 0;
}

    Was mache ich da falsch?

    Ciao

    OkkaPapa

    0
  • Mod

    Erstens ein paar allgemeine Fehler:
    1. Kein goto benutzen!
    2. Kein malloc benutzen, wenn es nicht unbedingt nötig ist!
    3. Wenn schon malloc, dann auch wieder richtig freigeben!
    4. 2D-Arrays sind keine Doppelzeiger!
    5. Korollar aus 4.: Für 2D-Arrays kein doppeltes malloc benutzen!

    Du machst dadurch deinen Code nur unnötig unübersichtlich und auch ziemlich krass ineffizient.

    Zum Problem:
    Eine eigentlich bessere Lösung zum Finden von Duplikaten, wäre alle Einträge in eine set-Datenstruktur einzufügen:
    http://en.wikipedia.org/wiki/Set_(computer_science)
    Gerne auch ein Hashset.
    Da du dich für C als Sprache entschieden hast, darfst du dich aber selber damit herumschlagen, komplexe Datenstrukturen zu implementieren. Viel Spaß.

    Falls der Wertebereich deiner Paare bekannt und übersichtlich ist, kannst du statt eines Hashtables auch einfach ein entsprechend großes Array benutzen. Dann bräuchtest du keine komplizierten Datenstrukturen implementieren, sondern könntest einfach die Einträge im Array als schon vorhanden (oder eben nicht) markieren und wärst sofort fertig.

    Die Sortierlösung wäre wesentlich ineffizienter. Sortieren dauert lange. Man sollte nur sortieren, wenn es tatsächlich das Ziel ist, zu sortieren. Aber auch hier könnte man deinen Ansatz wesentlich verbessern (abgesehen von der falschen technischen Umsetzung): Das Vorsortieren der Zeilen ist ebenfalls wahnsinnig ineffizient und ebenfalls vollkommen unnötig. Du hast doch die volle Freiheit bei der Vergleichsfunktion: Vergleiche dort Wertepaare unter Beachtung deiner Regel, dass die Reihenfolge egal ist. Das heißt, du nimmst von jedem Paar den kleineren Wert, vergleichst diesen, und wenn diese gleich sind, vergleichst du noch die beiden größeren Werte. So sortierst du halbwegs effizient* in einem Durchgang.

    *: Abgesehen davon, dass es, wie gesagt, insgesamt furchtbar ineffizient wäre, weil Sortieren hier der falsche Ansatz ist und weil deine Doppelzeigerstruktur ineffizient ist.

    0

  • Es muss heißen:

    int const *A = *(int const **) A_p;
  int const *B = *(int const **) B_p;

    OkkaPapa schrieb:

    2. sortieren des Arrays auf- oder absteigend nach der 1. Spalte

    Das reicht nicht aus. Du musst (bei Gleichheit der 1.Spalte) auch nach der 2.Spalte gleichartig sortieren.

    Die vielen einzelnen malloc sind auch sehr suboptimal, wenn du sie millionenfach anwendest, also besser z.B.

    int cmp(void const *A_p, void const *B_p) {

  int const *A = A_p;
  int const *B = B_p;

  if (A[0] < B[0]) return -1;
  else
  if (A[0] > B[0]) return  1;
  else
  if (A[1] < B[1]) return  -1;
  else
  if (A[1] > B[1]) return  1;

  return 0;
}

enum {Lines=8,Columns=2};

int main(void) {
int i;
int (*Values)[Columns] = calloc(Lines,sizeof*Values);

Values[0][0]=5;
Values[1][0]=2;
Values[2][0]=2;
Values[3][0]=3;
Values[4][0]=2;
Values[5][0]=1;
Values[6][0]=1;
Values[7][0]=3;

Values[0][1]=6;
Values[1][1]=5;
Values[2][1]=3;
Values[3][1]=6;
Values[4][1]=3;
Values[5][1]=2;
Values[6][1]=4;
Values[7][1]=4;

for(i = 0; i < Lines ; ++i) {
  printf("%i %i\n", Values[i][0], Values[i][1]);
}
  printf("\n");

qsort(Values, Lines, sizeof*Values, cmp);

  printf("\n");
for(i = 0; i < Lines; ++i) {
  printf("%i %i\n", Values[i][0], Values[i][1]);
}
  printf("\n");
free(Values);
return 0;
}
    0
  • Mod

    Hier noch ein Beispiel, wie man das in O(N) machen könnte. Ich habe die Version

    Falls der Wertebereich deiner Paare bekannt und übersichtlich ist, kannst du statt eines Hashtables auch einfach ein entsprechend großes Array benutzen. Dann bräuchtest du keine komplizierten Datenstrukturen implementieren, sondern könntest einfach die Einträge im Array als schon vorhanden (oder eben nicht) markieren und wärst sofort fertig.

    genommen, da mir ein richtiger Hashtable viel zu viel Aufwand wäre, bloß um ein Beispiel im Forum zu bringen. Zur Not tut es auch ein Binärbaum. Das ist zwar in vielen Fällen nicht so gut wie der Table, aber es ist bei einer großen Anzahl von Wertepaaren allemal effizienter als Sortieren. Ganz besonders wenn der Baum nicht sehr tief wird (aka viele Paare sind identisch).

    Der Code:

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

#define MIN -5
#define MAX 1
#define NUM_PAIRS 40

typedef struct 
{
  int *data;
} pseudo_hashtable;

pseudo_hashtable create_hashtable(size_t size)
{
  pseudo_hashtable h={calloc(size, sizeof(*h.data))};
  return h;
}

void delete_hashtable(pseudo_hashtable h)
{
  free(h.data);
}

// True if element already exists
int hashtable_insert(pseudo_hashtable h, size_t coord)
{
  return h.data[coord]++;
}

size_t hashfunction(int x, int y)
{
  int min = (x < y) ? x : y;
  int max = (x < y) ? y : x;
  return (min - MIN) * (MAX - MIN) + (max - MIN);
}

int main()
{
  int (*data)[2] = malloc(NUM_PAIRS * sizeof(*data));
  puts("Alle Paare:");
  for (size_t i = 0; i < NUM_PAIRS; ++i)
    {
      data[i][0] = rand() % (MAX - MIN) + MIN;
      data[i][1] = rand() % (MAX - MIN) + MIN;
    }

  pseudo_hashtable ht = create_hashtable((MAX-MIN)*(MAX-MIN));
  for (size_t i = 0; i < NUM_PAIRS; ++i)
    {
      if (hashtable_insert(ht, hashfunction(data[i][0], data[i][1])))
        {
          printf("%i, %i gibt es bereits\n",  data[i][0], data[i][1]);
        }
      else
        {
          printf("%i, %i gibt es noch nicht\n",  data[i][0], data[i][1]);
        }
    }

  delete_hashtable(ht);
  free(data);
}
    0
  • O

    Hallo SeppJ!

    Erstmal vielen Dank für die Kritik am Code...

    SeppJ schrieb:

    Erstens ein paar allgemeine Fehler:
    1. Kein goto benutzen!
    2. Kein malloc benutzen, wenn es nicht unbedingt nötig ist!
    3. Wenn schon malloc, dann auch wieder richtig freigeben!
    4. 2D-Arrays sind keine Doppelzeiger!
    5. Korollar aus 4.: Für 2D-Arrays kein doppeltes malloc benutzen!

    Du machst dadurch deinen Code nur unnötig unübersichtlich und auch ziemlich krass ineffizient.

    zu 1: Ich weiß, daß wird allgemein als schlechter Stil gesehen, da aber im source zur ein einziges "Exit:" steht, wars das einfachste.

    zu 2, 4 und 5: Ist notwendig, weil ich erst zur Laufzeit weiß wie viele Wertepaare der Anwender erzeugt hat.
    Mit statischen Arrays tut der source nämlich, daher meinte ich das mit den Pointer verstanden zu haben...

    Gibt es da elegantere Möglichkeiten mehrdim. Arrays zur Laufzeit zu allokieren außer malloc und calloc??
    Mir wurde das so gezeigt und bislang hats auch gut funktioniert.

    zu 3: Ist klar, war aber für das Problem nicht wichtig, daher weggelassen.

    Ciao

    OkkaPapa

    0
  • Mod

    1. Ja, das sagen sie alle. Erst ist es bloß ein Exit. Später kommt noch ein Begin dazu, da es mit dem Exit ja schon so gut geklappt hat. Später dann noch 15 weitere Labels, weil man nie gelernt hat, wie es richtig geht. Meinst du, es gäbe keinen Grund, wieso alle erfahrenen Programmierer davor warnen?
    2. Ja, dann ist es hier eben nötig.
    3. Siehe Punkt 1. Erst lässt man es weg, weil unnötig, später lässt man es weg, weil man es nie richtig gelernt hat an den einfachen Fällen.
    4. Nein, das ist schlichtweg falsch. Siehe meinen oder Wutz Code, wie man dynamische 2D-Arrays macht.
    5. Siehe 4. Das gilt auch, wenn die innere Dimension erst zur Laufzeit feststeht. Dann allokiert man eben ein einziges großes Array und rechnet die Indizes selber aus, ungefähr so wie meine Hashfunktion das für das eine große Array des (Pseudo-)Hashtables tut.

    Ein 2D-Array am Stück und ein Array von Pointern auf Arrays sind technisch ein riesiger Unterschied. Letzteres brauchst du nur, wenn die "Zeilen" unterschiedlich lang sind. Die Laufzeitkosten dieser Möglichkeit sind hoch! Also benutze es nicht, wenn du es nicht brauchst.

    0
  • O

    Hi SeppJ!

    SeppJ schrieb:

    1. Ja, das sagen sie alle. Erst ist es bloß ein Exit. Später kommt noch ein Begin dazu, da es mit dem Exit ja schon so gut geklappt hat. Später dann noch 15 weitere Labels, weil man nie gelernt hat, wie es richtig geht. Meinst du, es gäbe keinen Grund, wieso alle erfahrenen Programmierer davor warnen?
    2. Ja, dann ist es hier eben nötig.
    3. Siehe Punkt 1. Erst lässt man es weg, weil unnötig, später lässt man es weg, weil man es nie richtig gelernt hat an den einfachen Fällen.
    4. Nein, das ist schlichtweg falsch. Siehe meinen oder Wutz Code, wie man dynamische 2D-Arrays macht.
    5. Siehe 4. Das gilt auch, wenn die innere Dimension erst zur Laufzeit feststeht. Dann allokiert man eben ein einziges großes Array und rechnet die Indizes selber aus, ungefähr so wie meine Hashfunktion das für das eine große Array des (Pseudo-)Hashtables tut.

    Ein 2D-Array am Stück und ein Array von Pointern auf Arrays sind technisch ein riesiger Unterschied. Letzteres brauchst du nur, wenn die "Zeilen" unterschiedlich lang sind. Die Laufzeitkosten dieser Möglichkeit sind hoch! Also benutze es nicht, wenn du es nicht brauchst.

    Ich habe schon diverse Basic und Fortran77 Programme geschrieben, daher keine Angst mit den gotos 🙂

    Was die dyn. Speicherallokierung angeht werde ich mir mal Eure Lösungen angucken und einen entsprchende Rückmeldung an meinen C-Kursleiter machen...

    Ciao

    OkkaPapa

    0
  • ?

    OkkaPapa schrieb:

    Ich habe schon diverse Basic und Fortran77 Programme geschrieben, daher keine Angst mit den gotos 🙂

    Das ist auch in Basic und Fortran extrem schlechter Stil.

    0
  • O

    Hi!

    seldon schrieb:

    OkkaPapa schrieb:

    Ich habe schon diverse Basic und Fortran77 Programme geschrieben, daher keine Angst mit den gotos 🙂

    Das ist auch in Basic und Fortran extrem schlechter Stil.

    Eigentlich wollte ich keinen thread über meinen Programmierstil lostreten.

    Den halte ich (wie wohl jeder andere seinen eigenen Stil) nicht für "extrem schlecht".

    Bitte jetzt keine Diksussion nach dem Motto "aber es gibt aus gutem Grunde anerkannte Programmierregeln".
    Darüber müssen wir nicht diskutieren: da ich programmiertechnisch Autodidakt bin, habe ich leider auf die harte Tour lernen müssen, dass es sinnvoll ist diese einzuhalten.
    Allerdings nehme ich mir auch das Recht diese Regeln nicht als Dogma aufzufassen, um mir das Leben nicht zu kompliziert zu machen.

    Die Tipps und Anmerkungen zur Speicherallokierung und zur der Sortierproblematik nehme ich gerne mit.

    Danke dafür an die Autoren!!

    Aber bitte nicht einen fix ausgeschnittenen und lauffähig gemachten Codeschnipsel als repräsentativen Programmierstil ansehen. Das ist IMHO unfair und führt vom eigentlichen Problem weg.

    Mein Stil ist (wie ein guter Whisky) über die Jahre gereift und mir "schmeckt" er. 🙂

    Ciao

    OkkaPapa

    0
  • ?

    OkkaPapa schrieb:

    Eigentlich wollte ich keinen thread über meinen Programmierstil lostreten.

    Das hast du gerade eben gemachtt. 😃

    OkkaPapa schrieb:

    Mein Stil ist (wie ein guter Whisky) über die Jahre gereift und mir "schmeckt" er. 🙂

    Dann sei nicht enttäuscht, wenn du ihn alleine trinken musst; äh, sich keiner deinen Code mehr ansieht (auch nicht in Ulan-Bator).

    0
  • Mod

    Das ist keine Frage des Stils, sondern vor allem der Produktivität. Tausende Programmierer haben jeweils tausende Stunden verschwendet, weil so programmiert wurde, bis man sich entschloss, es gemeinsam anders anzugehen. Wenn du selber tausende Stunden deines Lebens mit unnötiger Fehlersuche verschwenden möchtest anstatt 10 Stunden mit Umlernen, dann tu das. Sag aber hinterher nicht, dass man dich nicht gewarnt hätte, falls es bei großen Projekten mal gar nicht mehr geht oder wenn du dich wunderst, wieso andere in 2 Stunden das schaffen, wofür du zwei Tage benötigst.

    0
  • ?

    Ich gebe auch zu bedenken, dass Programmierung idR Teamarbeit ist -- wenn du mit so einem unwartbaren Durcheinander ankommst, behinderst du nicht nur deine eigene Arbeit. Und zwar auch lange nachdem du aus dem Team geworfen wurdest, weil in deinem Teil noch Jahre später mühsam Fehler behoben werden müssen.

    Um es deutlich zu sagen: Dein Stil ist nicht über Jahre "gereift," sondern gewuchert. Jäten ist dringend notwendig.

    0
Anmelden zum Antworten