Übergabe von Array an Funktion

[Norben]

Wie sieht eure Min/Max-Funktion denn jetzt aus?

Wir haben die Arraylänge mit übergeben. So funktioniert es. Uns hat nur interessiert, ob es eben auch anders geht, da die Aufgabenstellung lautete:

Implementieren und testen Sie folgende C-Funktionen:
int maxValue(int a[]); //liefert das größte Element der Array zurück

int main(int argc, const char * argv[])
{	
    int a[] = {200,5,4,3,2,1};
    int cnt = sizeof(a)/sizeof(int);

    printf("maxValue: %i \n", maxValue(a,cnt));

    return(0);
}

int maxValue(int a[], int cnt)
{
    doSort(a,cnt);
    return a[cnt-1];
}

[SeppJ]

Fällt euch denn keine wesentlich einfachere Möglichkeit ein, das Maximum einer Reihe Zahlen zu finden, als diese zu sortieren? Wenn ich dir in echt ein paar Karten mit Zahlen^* und die gleiche Aufgabe geben würde, wie würdest du vorgehen?

^*: Es sind zu viele Karten, als dass du auf einem Blick das Maximum sehen könntest.

[Norben]

SeppJ schrieb:

Wenn ich dir in echt ein paar Karten mit Zahlen^* und die gleiche Aufgabe geben würde, wie würdest du vorgehen?

Durchblättern und immer die gerade Größte rauslegen, bis eine neue Größere kommt. Also in C die einzelnen Werte in eine Variable legen und immer mit dem nächsten Element vergleichen, falls dieses Größer, die Variable überschreiben?

[SeppJ]

Klingt nach einer guten Idee. Versuch das doch mal. Als leicht fortgeschrittenere Aufgabe kannst du auch noch mal darüber nachdenken, welche der beiden Techniken (Sortieren oder die neue Idee) wohl schneller ist und warum.

[Norben]

Ist wahrscheinlich effizienter, weil beim Sortieren das Array mehrfach durchlaufen werden muss, bis die Reihenfolge passt und hier das Array nur ein mal durchlaufen wird?

int maxValue(int a[], int cnt)
{
    int max;
    for(int i=0 ; i<cnt ; i++)
    {
        if(a[i] > a[i-1])
        {
            max = a[i];
        }
    }
    return max;
}

[SeppJ]

Norben schrieb:

Ist wahrscheinlich effizienter, weil beim Sortieren das Array mehrfach durchlaufen werden muss, bis die Reihenfolge passt und hier das Array nur ein mal durchlaufen wird?

Ja. Wobei beim Sortieren nicht wirklich von vorne nach hinten durchgelaufen wird, aber insgesamt sind beim Sortieren viel mehr Zugriffe nötig als es Elemente im Array gibt. Beim Maximumsucher, so wie hier, braucht es hingegen nur einen Zugriff pro Arrayelement.

int maxValue(int a[], int cnt)
{
    int max;
    for(int i=0 ; i<cnt ; i++)
    {
        if(a[i] > a[i-1])
        {
            max = a[i];
        }
    }
    return max;
}

Das ist so noch nicht richtig. Sieht zwar auf den ersten Blick so aus, ist es aber nicht.

[Norben]

SeppJ schrieb:

Das ist so noch nicht richtig.

Achso, okay, da war ein Fehler drin.

int maxValue(int a[], int cnt)
{
    int max = 0;
    for(int i=0 ; i<cnt ; i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }
    return max;
}

[Nathan]

Was ist, wenn nur negative Zahlen im Array stehen?
Dann ist max die größte Zahl, obwohl sie gar nicht vorkommt.
max muss als Initialisierungswert den kleinst möglichen Wert eines ints haben.
Den bekommst du via INT_MIN aus limits.h.

[SeppJ]

Nathan schrieb:

Was ist, wenn nur negative Zahlen im Array stehen?
Dann ist max die größte Zahl, obwohl sie gar nicht vorkommt.
max muss als Initialisierungswert den kleinst möglichen Wert eines ints haben.
Den bekommst du via INT_MIN aus limits.h.

Und wenn es sich nicht um ints handelt (Mal angenommen wir schreiben eine typunabhängige Funktion)? Oder wenn das Array leer ist(das betrifft auch den aktuellen Code)? Es gibt da eine bessere Idee für den Anfangswert...

[Nathan]

SeppJ schrieb:

Nathan schrieb:

Was ist, wenn nur negative Zahlen im Array stehen?
Dann ist max die größte Zahl, obwohl sie gar nicht vorkommt.
max muss als Initialisierungswert den kleinst möglichen Wert eines ints haben.
Den bekommst du via INT_MIN aus limits.h.

Und wenn es sich nicht um ints handelt (Mal angenommen wir schreiben eine typunabhängige Funktion)? Oder wenn das Array leer ist(das betrifft auch den aktuellen Code)? Es gibt da eine bessere Idee für den Anfangswert...

Stimmt.

[Norben]

Okay stimmt, negative Zahlen gibt es auch noch.

Mit der limits.h Variante würde ich min einfach INT_MIN zuweisen? (min = INT_MIN;)? Und dahinter verbirgt sich quasi -32768?

Und wenn es sich nicht um ints handelt (Mal angenommen wir schreiben eine typunabhängige Funktion)? Oder wenn das Array leer ist(das betrifft auch den aktuellen Code)? Es gibt da eine bessere Idee für den Anfangswert...

Bekomme ich leider nicht heraus. Der restliche Code stimmt aber soweit, es geht nur noch um den Anfangswert?

[SeppJ]

Norben schrieb:

Okay stimmt, negative Zahlen gibt es auch noch.

Mit der limits.h Variante würde ich min einfach INT_MIN zuweisen? (min = INT_MIN;)? Und dahinter verbirgt sich quasi -32768?

Ja. Wobei INT_MIN aber in der Regel wesentlich kleiner sein wird, eher so etwas wie -2 hoch 31.

Und wenn es sich nicht um ints handelt (Mal angenommen wir schreiben eine typunabhängige Funktion)? Oder wenn das Array leer ist(das betrifft auch den aktuellen Code)? Es gibt da eine bessere Idee für den Anfangswert...

Bekomme ich leider nicht heraus. Der restliche Code stimmt aber soweit, es geht nur noch um den Anfangswert?

Letzter Tipp bevor ich es verrate (ja, es ist schwer da drauf zu kommen): Der Anfangswert muss ja nicht der kleinstmögliche Wert überhaupt sein, es muss bloß irgendein Wert sein, von dem du weißt, dass er höchstens so groß ist wie das Maximum in der Menge. Aus welcher Wertemenge könnte solch ein Wert kommen?

Ansonsten ist der Code soweit richtig. Wenn du drauf kommst, was ein besserer Startwert wäre, ergeben sich ein paar Änderungen von ganz alleine.

[Norben]

int max = minValue(a, cnt);

Wobei das ja weniger effizent wäre. Ich komm echt nicht drauf. :p

[SeppJ]

Einfach irgendein Wert aus dem Feld, zum Beispiel der erste.

Wenn man es weiß, ist es ganz einfach, aber man kommt einfach nicht drauf. :p

[Bashar]

SeppJ schrieb:

Einfach irgendein Wert aus dem Feld, zum Beispiel der erste.

Und wie löst du damit das Problem eines leeren Arrays? Das war immerhin einer deiner Einwände gegen INT_MIN (und eigentlich auch der einzige, weil es typunabhängige Funktionen in C nicht gibt). Ich warte schon die ganze Zeit auf deinen Vorschlag...

[Norben]

Achso, danke. Da wäre ich nicht drauf gekommen.^^

[...]typunabhängige Funktionen in C nicht gib

Mit generischen Pointern ist das aber möglich oder?

[SeppJ]

Bashar schrieb:

SeppJ schrieb:

Einfach irgendein Wert aus dem Feld, zum Beispiel der erste.

Und wie löst du damit das Problem eines leeren Arrays?

Indem man es entweder abfängt oder ignoriert. Der Fehler liegt im Aufruf der Funktion mit ungültigen Argumenten. Das Ergebnis ist also entweder ein Fehler/Exception oder undefiniertes Verhalten. Hier einfach INT_MIN zurück zu geben, wäre eine Lüge. Das Minimum einer leeren Menge ist einfach undefiniert. Punkt.

Dieses Vorgehen löst auf jeden Fall aber alle anderen Probleme zufriedenstellend, die man sich mit einem Minimal-/Maximalstartwert einhandelt. Zum Beispiel bei der Suche des alphabetischen Minimums einer Menge von Zeichenketten. Mit welchem Wert sollte man da anfangen?

und eigentlich auch der einzige, weil es typunabhängige Funktionen in C nicht gibt

qsort ruft gerade an und fragt, warum du dich nie meldest. Und das Präprozessormakro ist ebenfalls traurig.

edit: Hier ein einfaches Beispiel:

#include <stddef.h>

const void *min_element(void *ptr, size_t cnt, size_t size, int (*comp)(const void *, const void *))
{
  const void *min;
  size_t i;

  if (!cnt) return NULL;

  min = ptr;
  for(i = 1; i < cnt; ++i)
    if (comp(min, (const char*)ptr + size * i) > 0)
      min = (const char*)ptr + size * i;

  return min;
}

#include <stdio.h>
#include <string.h>

int compare_ints(const void* a, const void* b)  
{
  int arg1 = *(const int*)a;
  int arg2 = *(const int*)b;
  if(arg1 < arg2) return -1;
  if(arg1 > arg2) return 1;
  return 0;
}

int compare_strings(const void* a, const void* b)  
{
  return strcmp(*((char**) a), *((char**) b));
}

int main()
{
  int foo[] = {75, 72, 98, -84, 63};
  const char *bar[] = {"Blah", "Blupp", "Aachen", "Zeppelin", "Foobar"};

  printf("Integerminimum ist: %d\n", *(int*) min_element(foo, sizeof(foo)/sizeof(*foo), sizeof(*foo), compare_ints));
  printf("Stringminimum ist: %s\n", *(const char**) min_element(bar, sizeof(bar)/sizeof(*bar), sizeof(*bar), compare_strings));
  return 0;
}

https://ideone.com/Hk304U

[Bashar]

SeppJ schrieb:

Bashar schrieb:

SeppJ schrieb:

Einfach irgendein Wert aus dem Feld, zum Beispiel der erste.

Und wie löst du damit das Problem eines leeren Arrays?

Indem man es entweder abfängt oder ignoriert.

Also gar nicht, OK, das hab ich erwartet.

qsort ruft gerade an und fragt, warum du dich nie meldest.

OK, wenn ich mal meinen Dreisternetag habe und ein void-Pointer-basiertes minElement programmiere, werde ich an dich denken, damit ich auf keinen Fall aus versehen INT_MIN hinschreibe. Oder einfach deine Funktion kopieren. Naja, oder nicht, weil dieser Tag nicht kommen wird.

[SeppJ]

Bashar schrieb:

SeppJ schrieb:

Bashar schrieb:

SeppJ schrieb:

Einfach irgendein Wert aus dem Feld, zum Beispiel der erste.

Und wie löst du damit das Problem eines leeren Arrays?

Indem man es entweder abfängt oder ignoriert.

Also gar nicht, OK, das hab ich erwartet.

Doch, das ist die Lösung. Guck mal oben in meinem Beispiel (hat etwas gedauert zu programmieren, daher später edit, während du schon geantwortet hast). Der Nullzeiger ist da auf jeden Fall besser als eine diffuse Lüge.

Das Maximum einer leeren Menge ist mathematisch nicht definiert, es kann kein Ergebnis geben. Also gibt es drei Möglichkeiten:
1. Fehler. (siehe oben; kein Ergebnis)
2. Bewusst so tun als wäre nichts. (undefiniertes Verhalten; undefiniertes Ergebnis)
3. Gar nicht erst erkennen, dass es ein Problem geben könnte. (definiertes, aber falsches Verhalten; es gibt ein Ergebnis)
Du schlägst hier offenbar 3. vor. Was zwar effektiv dem 2. gleicht, aber "moralisch" schlechter ist. Es spiegelt nicht die mathematische Definition des Maximums einer leeren Menge wieder. Das ist nämlich nicht INT_MIN.

OK, wenn ich mal meinen Dreisternetag habe und ein void-Pointer-basiertes minElement programmiere, werde ich an dich denken, damit ich auf keinen Fall aus versehen INT_MIN hinschreibe. Oder einfach deine Funktion kopieren. Naja, oder nicht, weil dieser Tag nicht kommen wird.

Weil du kein C programmierst. Guck mal wie std::min_element in C++ programmiert ist. Bestimmt nicht mit std::numeric_limits.

P.S.:

template < class ForwardIterator , class Compare >
ForwardIterator min_element ( ForwardIterator first , ForwardIterator last ,
Compare comp );

Returns: The first iterator i in the range [first ,last ) such that for any iterator j in the range [first ,last
) the following corresponding conditions hold: !(*j < *i) or comp (*j, *i) == false. Returns last if
first == last .

Complexity: Exactly max((last - first ) - 1, 0) applications of the corresponding comparisons.

[Bashar]

SeppJ schrieb:

Bashar schrieb:

SeppJ schrieb:

Bashar schrieb:

SeppJ schrieb:

Einfach irgendein Wert aus dem Feld, zum Beispiel der erste.

Und wie löst du damit das Problem eines leeren Arrays?

Indem man es entweder abfängt oder ignoriert.

Also gar nicht, OK, das hab ich erwartet.

Doch, das ist die Lösung. Guck mal oben in meinem Beispiel (hat etwas gedauert zu programmieren, daher später edit, während du schon geantwortet hast). Der Nullzeiger ist da auf jeden Fall besser als eine diffuse Lüge.

Du kannst aus einer int-Funktion keinen Nullzeiger zurückgeben. Ausschließlich darauf war die Aussage bezogen.

Dass es bei deiner void-Pointer-Geschichte geht ist klar. (Aber das ist dann ja auch nicht das erste Element des Arrays). Überhaupt streiten wir hier gerade ausschließlich über Trivialitäten, ich versteh gar nicht, woher du die Energie nimmst, das auch auszuprogrammieren.

Das Maximum einer leeren Menge ist mathematisch nicht definiert

Ich weiß, was ein Maximum ist (wäre schon peinlich, als Mathematiker), und würde auch nie auf die Idee kommen, die INT_MIN-Lösung tatsächlich zu propagieren.

Ich denke lediglich, dass deine Behauptung, das erste Element des Arrays zu verwenden würde das Problem des leeren Arrays tatsächlich lösen, absurd ist.

Das ist auf einer Meta-Ebene eine Lösung, weil ein Problem manchmal am besten gelöst wird, indem man es ignoriert.