Einfach Elemente zweier Arraylisten kreuz und quer vergleichen, min und max Problem?

[berndoa]

Hallo, ich habe eine konzeptuelle Frage wie man das möglichst effizient hinkriegt:
In meinem Beispiel habe ich 2 ArrayList<ArrayList<Long>> , nenne wir sie A und B.
könnte auch einfache ArrayList<Long> sind, ist für die Frage grundsätzlich egal.

Und ich habe eine selbst geschriebene Methode , die als Input ein Element der Lsite A und ein Element der Liste B nimmt und als Ergebnis eine normale int zahl rauswirft. nennen wir sie f(Ai,Bi).
wie die methode intern diese zahl bestimmt, ist egal.

zuerst bestimme zu jedem b aus B das Maximum der Werte f(a,b) mit a aus A.
Heißt, man nimmt ein bestimmtes Element aus B, gleicht es mit allen Werten aus b ab (indem man f(a,b) bildet jeweils).
von all diesen gefundenen Werten sucht man das maximum und merkt es sich.

gleiches tut man für die anderen Elemente aus b sodass man eine Liste mit Werten hat.
von diesen wiederum bildet man dieses mal das Minimum.

Ich machs mal an einem beispiel damit mans kapiert was ich meine:
Seien die Arraylist A={1,2,3} und B={9,3,7}
sei f(a,b)=a+b

Sei C auch ein Array.
wir bestimmen zuerst
C[0]:=min(f(1,9),f(2,9),f(3,9))=min(10,11,12)=10
analog finden wir C[1]=min(f(1,3),f(2,3,),f(3,3))=f(4,5,6)=4
C[2]=...=8

demnach ist also C={10,4,8}
von den elementen bilden wir nun noch das maximum:
max(10,4,8)=10

das heißt für A={1,2,3} und B={9,3,7} (und f wie oben definiert) ist das gesuchte ergebnis 10.

so auf die art will ich auch bei meinem problem sozusagen das max von einer menge an minima finden.

natürlich könnte ich wie hier (aktuell machen ich es auch so) die bestimmten minima alle in einen array speichern und die arraelemente danach noch durchsuchen welches davon nun wiederum das maximum ist.

nur würde ich mir dieses bilden von so zwischenarrays gerne ersparen und kluge rechnereien und so einfach direkt das ergebnis finden lassen.

gibts da irgendwie eine kluge vorgehensweise?

 

[mihe7]

List<Long> a = List.of(1L, 2L, 3L);
List<Long> b = List.of(9L, 3L, 7L);
BiFunction<Long, Long, Long> f = (a,b) -> a+b;

long maxOfMin = b.stream().mapToLong(x ->
        a.stream().mapToLong(y -> f.apply(x,y)).min().getAsLong()
    ).max().getAsLong();

 

[berndoa]

puh, also ich kapiere noch nicht so ganz was da steht

 

[mihe7]

Wir bilden jedes x aus b auf ein Minimum der Werte ab, die sich ergeben, wenn man zusammen mit jedem y aus a die Funktion f(x,y) aufruft. Von den so ermittelten Minima bilden wir abschließend das Maximum.

 

[fhoffmann]

Die Stream-Lösung von @mihe7 ist sicherlich sehr elegant.
Wenn du sie aber nicht verstehst, kannst du das Problem auch mit zwei geschachtelten for-Schleifen lösen:
In der inneren for-Schleife berechnest du das Minimum und in der äußeren for-Schleife berechnest du das Maximum dieser Minima.

 

[mihe7]

Ach so, ich hatte es so verstanden, dass eine kurze Lösung gesucht ist

 

[fhoffmann]

Ach so, ich hatte es so verstanden, dass eine kurze Lösung gesucht ist

Ich habe ja nichts gegen deine Lösung. Aber zunächst war die Frage ja, ob man das Maximum berechnen kann, ohne die Minima (in einem Array) zwischenzuspeichern.

 

[berndoa]

Ich habe auch nix gegen seine Lösung, mittlerweile kapiere ich sie auch.
Nur habe ich mich mit Streams, maps und so noch nie beschäftigt, musste mich also kurz etwas einlesen.

Im Prinzip ist mir jede möglichst simple Lösung des Problems recht, ich bin da recht offen für Alles
Ja, so mein Stil wäre das mit den for Schleifen und so,
aber kürzer und eleganter ist sichelrich die Streamsache.

Ich bin nur programmirtechnishc noch nicht arg so hoch, insofern benutze ich zu 99% immer nur Arrays oder maximal Arraylists.

Einfach und doppelt verkettete Listen kenne ich vom Konzept her auch, habe aber noch nie eine Situation oder einen grund gehabt sie zu verwenden

Alles Kompliziertere sind einfach Sachen und Datentypen die sicherlich sinnvoll und praktisch sind, wo aber meine Problem meist einfach zu einfach gestrickt waren als dass ich hätte auf einen komplizierteren Datentyp hätte zugreifen müssen.

Nach einigem Einlesen käme ich damit sicherlich auch klar, nur für meinen Kleinkram den ich selten mal Programmiere, tun es die Grundlegenden Sachen.

Aber wie gesagt, ich bin offen für Alles (bei mir besteht ein Dreier aber aus 2 Frauen und einem Mann)
und lerne da gerne dazu was Alles geht.

Bin nur der Typ der, wenn ich nicht ein Problem habe, das es erfordert, mich nicht unnötig mit Neuen Sachen beschäftige.

Weil ich durch reines Auswendiglernen nur schlecht lerne, learning by doing ist da die Devise

 

[berndoa]

Die Stream-Lösung von @mihe7 ist sicherlich sehr elegant.
Wenn du sie aber nicht verstehst, kannst du das Problem auch mit zwei geschachtelten for-Schleifen lösen:
In der inneren for-Schleife berechnest du das Minimum und in der äußeren for-Schleife berechnest du das Maximum dieser Minima.

Das Prinzip ist schon klar.
Nur die Reihenfolge wie man es hinschreibt verwirrt mich etwas.

Man bildet erst die x werte aus a irgendwie auf etwas ab, was die y werte aus b auf etwas abbildet was irgendwie (x,y) auf f(x,y) abbildet.

Dieses nacheinanderschreiben verwirrt mich etwas, dass das so geht.
Weil klammermässig wird das ja von innen nahc aussen ausgewertet. und wenn da y dann auf eine funktion (x,y)->f(x,y) abgebildet wird, ohne dass y überhaupt definiert ist bisher (wird ja erst im nächstäusseren teil vorgegeben) verwirrt mich das etwas .

Nichtdass ich nicht glaube dass es so funktioniert, habe nur so meine probleme das "warum funktioniert es" zu verstehen

 

[fhoffmann]

Dann versuche doch erst einmal. das Problem mit einer verschachtelten for-Schleife zu lösen.

 

[mihe7]

Dieses nacheinanderschreiben verwirrt mich etwas, dass das so geht.
Weil klammermässig wird das ja von innen nahc aussen ausgewertet. und wenn da y dann auf eine funktion (x,y)->f(x,y) abgebildet wird, ohne dass y überhaupt definiert ist bisher (wird ja erst im nächstäusseren teil vorgegeben) verwirrt mich das etwas .

Oh, das sind Lamda-Ausdrücke. In Java kannst Du damit funktionale Interfaces implementieren.

Aber bleiben wir doch bei den Schleifen. Das ist nämlich gar nicht so einfach wie es auf den ersten Blick vielleicht scheint

 

[berndoa]

Dann versuche doch erst einmal. das Problem mit einer verschachtelten for-Schleife zu lösen.

I did a thing:

public static long calculatewithoutj(ArrayList<ArrayList<Long>> sixtuples, ArrayList<ArrayList<Long>> input, long ignoreindex){
    //anzahl richtige für jedes tupel in input finden 
    long minimum=999999999;
    for(ArrayList<Long> sixtuple:sixtuples){
        long maximum=0;
        //setze maximum gleich dem maximum, also den größtmöglichen richtigen die mit irgendeiner inputreihe getroffen werden
        for(long inputindex=0;inputindex<input.size();inputindex++){
            if(inputindex!=ignoreindex){
                long inttemp=equalnum(sixtuple,input.get((int)inputindex));
                if(inttemp>maximum){
                    maximum=inttemp;
                }
            }
        }
        //hier ist nun maximum bestimmt, abgleich ob kleiner als das bisherige minimum
        if(minimum>maximum){
            minimum=maximum;
        }
    }
    return minimum;
}

Das soll das machen was wir hier bisher gesagt haben, wobei hier zusätzlich das ignoreindex'te Element von input ignoriert wird.

Das geht vermutlich viel schöner, schätze ich

Achja,
public static long equalnum(ArrayList<Long> a, ArrayList<Long> b)
gibt einfach nur die Anzahl an Long zahlen an, die zugleich in a und b vorkommen.

Findet also die anzahl an gmeeinsamen zahlen, wenn man so will.

 

[berndoa]

Und ja, ich weiß, meine Namensgebungen sind ziemlich schlecht

 

[mihe7]

Indexvariablen -> in der Regel int verwenden, nie long.

Du berechnest jetzt das Minimum der Maxima?


In Zeile 3 sieht man gleich warum ich oben geschrieben habe, dass das gar nicht so einfach ist. Das Minimum mit irgendeinen angenommenen Maximalwert zu belegen kann funktionieren (wenn der Wertebereich wirklich fix ist), im Allgemeinen ist es aber falsch oder drückt zumindest nicht das aus, worum es geht.

Nehmen wir mal an, man soll das Minimum aus einer Liste bestimmen. D. h. gesucht ist das kleinste Element. Wieso sollte man das Minimum mit irgendeinem Wert vorbelegen? Das Minimum muss, sofern es überhaupt existiert, zwangsweise aus der Liste stammen. Ein Minimum existiert, wenn die Liste wenigstens ein Element besitzt.

Was, wenn die Liste leer ist? Dann gibt es kein Minimum. Darauf kann man unterschiedlich reagieren, z. B. mit einer Exception.

Beispiel (eine Möglichkeit von vielen):

public long min(List<Long> values) {
    if (values.isEmpty()) {
        throw new NoSuchElementException("no minimum in empty list");
    }

    long minSoFar = values.get(0);
    for (int i = 1, n = values.size(); i < n; i++) {
        long value = values.get(i);
        if (value < minSoFar) {
            minSoFar = value;
        }
    }

    return minSoFar;
}

In Deinem Fall wird das noch etwas komplizierter, weil Du ja nicht einfach Werte aus einer Liste hast. Das Prinzip ist das Gleiche, aber da lass ich Dich mal selbst versuchen

 

[berndoa]

Indexvariablen -> in der Regel int verwenden, nie long.

Du berechnest jetzt das Minimum der Maxima?


In Zeile 3 sieht man gleich warum ich oben geschrieben habe, dass das gar nicht so einfach ist. Das Minimum mit irgendeinen angenommenen Maximalwert zu belegen kann funktionieren (wenn der Wertebereich wirklich fix ist), im Allgemeinen ist es aber falsch oder drückt zumindest nicht das aus, worum es geht.

Nehmen wir mal an, man soll das Minimum aus einer Liste bestimmen. D. h. gesucht ist das kleinste Element. Wieso sollte man das Minimum mit irgendeinem Wert vorbelegen? Das Minimum muss, sofern es überhaupt existiert, zwangsweise aus der Liste stammen. Ein Minimum existiert, wenn die Liste wenigstens ein Element besitzt.

Was, wenn die Liste leer ist? Dann gibt es kein Minimum. Darauf kann man unterschiedlich reagieren, z. B. mit einer Exception.

Beispiel (eine Möglichkeit von vielen):

public long min(List<Long> values) {
    if (values.isEmpty()) {
        throw new NoSuchElementException("no minimum in empty list");
    }

    long minSoFar = values.get(0);
    for (int i = 1, n = values.size(); i < n; i++) {
        long value = values.get(i);
        if (value < minSoFar) {
            minSoFar = value;
        }
    }

    return minSoFar;
}

In Deinem Fall wird das noch etwas komplizierter, weil Du ja nicht einfach Werte aus einer Liste hast. Das Prinzip ist das Gleiche, aber da lass ich Dich mal selbst versuchen

So Sonderfälle wie ne leere Liste und Ähnliches habe ich generell nicht behandelt.
Habe es beim Vorbelegen halt auch gedanklich ausgenutzt dass ich ziemlich gut absehen kann was so vorkommen wird an Zahlen, dass die inneren Arraylists alle gleich lang sein werden, etc.

Geht im meinem Beispiel ja um ein Lottospiel, da werden ich wohl eher nicht über was wie "Lotto 56 aus493234" stoßen

Aber gut, von mir aus kann man am Anfang auch stattdessen ein
long minimum=arraylist.get(0).get(0); nehmen.

Das mit den long habe ich mehr oder minder durchgängig genommen.
Einfach aus dem Grund weil mir 49*48*47*46*45*44/(6!), die Anzahl an Möglichkeiten für 6 Zahlen beim 6aus40 lotto, doch etwas ZU bedrohlich nahe an den Grenzen des Intbereichs scharbt. Da wollte ich auf Nummer sicher gehen

Aber leere Listen und Co. werde ich vermutlich nciht abfangen, da müsste ich ja dauernd Alles prüfen ob es nicht gleich null ist, ob die länge >0 ist, etc.

Ansonsten finde ich die Arraylisten auch nicht viel schwierger als Arrays.
aus .length wird eben .size() und aus wird .get(i)

 

[mihe7]

Wenn es so speziell ist, kannst Du Dir die Überlegungen für den allgemeinen Fall natürlich schenken. Ein Lotto mit negativen Zahlen ist wohl eher nicht zu erwarten, also sollte 0 als Initialwert für maximum passen. Für das minimum nimm als Initialwert aber bitte Long.MAX_VALUE, man weiß ja nie, was noch kommt

Nur der Vollständigkeit halber:

Aber gut, von mir aus kann man am Anfang auch stattdessen ein
long minimum=arraylist.get(0).get(0); nehmen.

Du bräuchtest das Maximum, das sich für das erste Sechstupel ergibt.

Ansonsten finde ich die Arraylisten auch nicht viel schwierger als Arrays.
aus .length wird eben .size() und aus wird .get(i)

Ja, das gilt für alle List-Implementierungen. Man könnte sogar sagen, dass Listen einfacher sind, weil sie sich selbst um den benötigten Speicher kümmern.

 

[berndoa]

Wenn es so speziell ist, kannst Du Dir die Überlegungen für den allgemeinen Fall natürlich schenken. Ein Lotto mit negativen Zahlen ist wohl eher nicht zu erwarten, also sollte 0 als Initialwert für maximum passen. Für das minimum nimm als Initialwert aber bitte Long.MAX_VALUE, man weiß ja nie, was noch kommt

Nur der Vollständigkeit halber:

Du bräuchtest das Maximum, das sich für das erste Sechstupel ergibt.


Ja, das gilt für alle List-Implementierungen. Man könnte sogar sagen, dass Listen einfacher sind, weil sie sich selbst um den benötigten Speicher kümmern.

Definitiv, bei Arrays muss ich abschätzen wie groß es wohl maximal werden wird.
Bei ArrayLists kann ich fleissig drauf los adden, java kümmert sich dann shcon drum dass es passt