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

B

berndoa

Bekanntes Mitglied
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

mihe7

Top Contributor
Java:
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();
 
mihe7

mihe7

Top Contributor
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.
 
F

fhoffmann

Top Contributor
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.
 
B

berndoa

Bekanntes Mitglied
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 :cool:

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 :)
 
B

berndoa

Bekanntes Mitglied
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 :)
 
mihe7

mihe7

Top Contributor
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 :)
 
B

berndoa

Bekanntes Mitglied
Dann versuche doch erst einmal. das Problem mit einer verschachtelten for-Schleife zu lösen.
I did a thing:

Java:
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.
 
Zuletzt bearbeitet:
mihe7

mihe7

Top Contributor
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):
Java:
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 :)
 
B

berndoa

Bekanntes Mitglied
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):
Java:
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

mihe7

Top Contributor
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.
 
B

berndoa

Bekanntes Mitglied
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 :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
OSchriever Einfach verkettete Liste ändern Allgemeine Java-Themen 26
HarleyDavidson Eigener PropertyChangeListener funktioniert einfach nicht Allgemeine Java-Themen 3
F Login einfach "ausbauen" Allgemeine Java-Themen 10
F BlueJ Java/Bluej Bug oder einfach nur Dummheit?? Allgemeine Java-Themen 5
O Programm wird einfach "gekillt" Allgemeine Java-Themen 3
C Eclipse Startet einfach nicht Allgemeine Java-Themen 6
S Javadoc hört einfach auf Allgemeine Java-Themen 4
N Vererbung Static & private fields - Nicht ganz einfach? Allgemeine Java-Themen 4
V anstatt thread.join() einfach while schleife? Allgemeine Java-Themen 8
L JAR verändern - JAVAC soll einfach nur kompilieren, ohne Prüfungen Allgemeine Java-Themen 16
L RMI Die richtigen Policy-Einstellungen oder einfach Signieren? Allgemeine Java-Themen 3
E Timer class macht einfach garnichts :/ Allgemeine Java-Themen 6
T Thread beendet sich "einfach so"? Allgemeine Java-Themen 13
D Einfach verkettete Liste Allgemeine Java-Themen 3
N HTML2TXT ganz einfach Allgemeine Java-Themen 6
X einfach verkettete Liste und Insertion Sort Allgemeine Java-Themen 3
G Runtime.exec - Prozess "mittendrin" "einfach Allgemeine Java-Themen 4
4 ich steige einfach nicht durch Allgemeine Java-Themen 5
J XML: JDOM + builder.build() hängt einfach Allgemeine Java-Themen 3
J Merkwürdiger Fehler: Applikation hängt einfach, Quartz-bug? Allgemeine Java-Themen 6
E Wie: Eigener Listener, eigenes Event (möglichst einfach) Allgemeine Java-Themen 29
H will einfach nicht sortieren! Allgemeine Java-Themen 23
G Einfach Mathe – Problem. Allgemeine Java-Themen 7
R Bild wird trotz allem einfach nicht angezeigt. - AHHHHH!!!!! Allgemeine Java-Themen 30
G Warum einfach wenns kompliziert auch geht? Allgemeine Java-Themen 12
E Schaffe es einfach nicht daten innerhalb von 2 klassen zu üb Allgemeine Java-Themen 4
JavaJüngling beliebige Collection die Comperable Elemente enthält als Parameter Allgemeine Java-Themen 37
H Elemente aus ArrayList in Array speichern Allgemeine Java-Themen 8
E Elemente innerhalb einer ArrayList vergleichen Allgemeine Java-Themen 33
J In einem Set doppelte Elemente erzeugen Allgemeine Java-Themen 4
GreenTeaYT Elemente eines 2Dim LinkedList von links nach rechts ausgeben? Allgemeine Java-Themen 0
H ArrayList: Leere Elemente finden? Allgemeine Java-Themen 2
Streeber Probleme mit AWT-EventQueue: ArrayList Elemente hinzufügen Allgemeine Java-Themen 1
Z Elemente einer ArrayList von rechts wegnehmen Allgemeine Java-Themen 5
E ArrayList Anzahl der gleichen Elemente Allgemeine Java-Themen 4
K Neue Elemente in JList einfügen Allgemeine Java-Themen 2
A Collections Array-Elemente in ArrayList kopieren ohne Schleife Allgemeine Java-Themen 7
S GUI - Drag & Drop Elemente Allgemeine Java-Themen 10
J Elemente zu einer List hinzufügen? Allgemeine Java-Themen 9
T OpenOffice Interface Elemente Ein/Ausblenden Allgemeine Java-Themen 5
S Aus einer Liste<Oberklasse> alle Elemente die eine bestimmte Unterklasse von Oberklasse haben filter Allgemeine Java-Themen 8
D prüfen, ob Enums bestimmte Elemente enthalten Allgemeine Java-Themen 3
M Elemente aus ArrayList, die in ArrayList ist Allgemeine Java-Themen 2
Z Elemente einer HashTabelle gezielt ansprechen Allgemeine Java-Themen 10
S Alle Elemente von zwei Listen vergleichen Allgemeine Java-Themen 10
C Auf Oberflaechen Elemente zugreifen Allgemeine Java-Themen 8
H GUI: RectangleDrawer - zu viele Elemente im Vector für die paint-Methode Allgemeine Java-Themen 6
Iron Monkey Array-Elemente Allgemeine Java-Themen 9
S Array: Anzahl Elemente mit best. Wert zählen Allgemeine Java-Themen 4
R Elemente eines Vectors [Java 1.4] Allgemeine Java-Themen 5
B Liste auf gleiche Elemente untersuchen? Allgemeine Java-Themen 2
C Auf ArrayList Elemente referenzieren? Allgemeine Java-Themen 17
M Progblem bei Zugriff auf Array Elemente Allgemeine Java-Themen 4
der JoJo [TreeSelection] wie bekomme ich alle Elemente Allgemeine Java-Themen 4
G Alle Möglichkeiten n Elemente Anzuordnen. Allgemeine Java-Themen 13
M Elemente aus Liste entfernen? Allgemeine Java-Themen 7
Z Elemente in Vector nach Häufigkeit sortieren. Allgemeine Java-Themen 13
E Reihenfolge der Elemente einer ArrayList? Allgemeine Java-Themen 4
J Netbeans: wie auf grafische elemente zugreifen, andere Datei Allgemeine Java-Themen 2
B Nach Deserialisieren: Elemente des JFrames ohne Funktion Allgemeine Java-Themen 5
G Umkehrung der Array Elemente Allgemeine Java-Themen 2
K Elemente im ArrayList vergleichen Allgemeine Java-Themen 9
F Elemente überdecken sich! Allgemeine Java-Themen 13
G anzahl "verwendeter" elemente eines arrays ermitte Allgemeine Java-Themen 2
S alle elemente aus hashmap lesen Allgemeine Java-Themen 8
T Elemente eines Arrays mischen Allgemeine Java-Themen 5
C Collection, LinkedList, Elemente Allgemeine Java-Themen 4
S Einzelne Elemente in einer Bild Datei Allgemeine Java-Themen 5
B Kollision zweier Kugeln im R² Allgemeine Java-Themen 2
AssELAss Best Practice Checksumme über jede Spalte zweier Tabellen und vergleichen Allgemeine Java-Themen 3
C Gemeinsame Oberklasse zweier Generics Allgemeine Java-Themen 10
Tausendsassa Input/Output Problem mit der gleichzeitigen Ausgabe zweier Threads Allgemeine Java-Themen 8
T Parallelisierung zweier BigInteger-Funktionen Allgemeine Java-Themen 6
M Zugriff zweier Threads auf diesselbe Methode Allgemeine Java-Themen 16
I Vergleich zweier Felder Allgemeine Java-Themen 3
F Vergleich zweier Listen Allgemeine Java-Themen 4
R Objektsynchronisierung zweier Listen?!?! Allgemeine Java-Themen 2
data89 [Kurze Frage] Ähnlichkeit zweier Strings ermitteln Allgemeine Java-Themen 19
J Endlosschleife durch wechselseitigen Zugriff zweier Klassen? Allgemeine Java-Themen 2
P gegenseitige Methodenaufrufe zweier Klassen Allgemeine Java-Themen 14
MQue Verbindung zweier Klasse Allgemeine Java-Themen 13
D Generalisierungsbeziehung zweier Klassen Allgemeine Java-Themen 5
D Seltsame Ausgabe beim zusammenführen zweier Dateien Allgemeine Java-Themen 14
J vergleich zweier datenstrukturen Allgemeine Java-Themen 6
Z Verknüpfung zweier Klassen! Allgemeine Java-Themen 2
N Vergleich zweier Hashtable / mehrere Enumerations Allgemeine Java-Themen 7
M run()-Code zweier Threads strikt abwechselnd ausführen Allgemeine Java-Themen 7

Ähnliche Java Themen


Oben