Maximales Tupel-Produkt (benachbarter Zahlen) + Laufzeit

[Mat]

Das neue Codeblock-Plugin muss getestet werden!

Ich hatte ein paar Übungsaufgaben gemacht.. eine davon bestand darin, das maximale Produkt benachbarter Zahlen in einem ungeordneten int-Array zu finden.

Da fiel mir spontan erstmal die Lösung hier ein:

// einfach davon ausgehen dass nur positive int kommen und kein Overflow möglich ist
int[] nums = {1, 2, 3, 10, 5, 2, 9, 3, 10};
int maxTupelProdukt = 0;

// in diesem Beispiel interessieren uns nur benachbarte Zahlen
// nums[0] und nums[nums.length-1] werden nicht als Nachbarn betrachtet
for (int i = 1; i < nums.length; i++) {
    maxTupelProdukt = Math.max(maxTupelProdukt, nums[i - 1] * nums[i]);
}
// maxTupelProdukt = 10 * 5 => 50

Gibts da nicht auch was mit Streams? Wie würde das aussehen? Ist reduce eine Möglichkeit?


Und dann hab ich noch über Optimierung nachgedacht und bin mir nicht sicher bei der Laufzeit:

• Welche Laufzeit hat das? Das steigt nur linear, also \( O( n ) \), ja?
• Was wäre, wenn es ein Array mit sehr vielen Elementen wäre?
  • Überlegung: immer nur linearer Anstieg
  • Optimierungsversuche durch Aussieben bestimmter Kandidaten usw. würden wohl nur die Laufzeit erhöhen, durch mehrere Durchläufe und Zwischenspeichern von Werten oder Indizes?
• Was wäre aber, wenn alle möglichen Tupel betrachtet werden müssten (nicht nur direkte Nachbarn)?
  • Überlegung: exponenzieller Anstieg, also \( O( n^2 ) \), ja?
  • Optimierungsversuch: mit 1x vorab Sortieren könnte man das sogar auf \( O( n ) \) runter bringen, wenn man dann nur die letzten / bzw. ersten beiden Elemente multipliziert (je nachdem, ob man auf- oder absteigend sortiert)

Edit: Mal MathJax statt Inline-Code benutzen

 

[german]

Du weißt, ich nix Java
Aber vielleicht ein paar Anmerkungen.

Da fiel mir spontan erstmal die Lösung hier ein:

Passt. Ich meine, selbst wenn du den Kram noch mal in eine andere Struktur mit anderen Methoden packst - was sollte dort in der Implementierung anderes passieren, als das was du hier machst? Vielleicht sparst du dir 2 Zeilen eigenen Code, aber die stecken dann in der Lib. Natürlich kannst du bei großen Datenmengen mit Multithreading ran um was zu reißen, aber da gibt es einen break even. Denn du musst ja vorher die Daten auf die Threads aufteilen, Threads starten und anschließend die Einzelergebnisse vergleichen. Bei deinen paar Arrayelementen viel zu viel Aufwand. Was tatsächlich sinnvoll ist, lässt sich am Ende nur austesten, weil die menschliche Logik da oft versagt. Insbesondere je abstrahierter die Sprache ist und wenn wie im Fall von Java auch noch Bytecode als Zwischenstepp dabei ist. Aus meiner C-Erfahrung heraus sind solche simplen Schleifen mit wenig Arbeit und wenig (verschachteltem) Branching im Schleifenrumpf hocheffizient. Am Ende wird daraus Code bei dem quasi der Prozessor eine Art Multithreading ausführt. Bspw. Branch Prediction. Für die paar Elemente könnten bspw. einfach alle Produkte schon mal parallel vorabberechnet werden, bevor entschieden wird, welches davon der Maximalwert ist.
Den einzigen Optimierungsansatz den ich sehe ist dein Index i. Auch hier ist es ein Frage der Umsetzung in Maschinencode, ob es den Index am Ende überhaupt noch gibt. Aber grundsätzlich behindert er solche Parallelläufe des Prozessors, weil der Index in jeder Schleifeniteration ein anderer ist und somit die Berechnung der Position der Daten im Speicher jedes mal anders ist. Vereinfachen kann man das mit Pointern die in jeder Iteration immer um den gleichen Betrag (nämlich 1) inkrementiert werden. In Java ist das natürlich abstrahiert und der rohe Pointer ist in einen Iterator gewrappt. Aber das wäre zumindest einen Versuch wert...

Welche Laufzeit hat das? Das steigt nur linear, also O(n), ja?

Klar.

Was wäre, wenn es ein Array mit sehr vielen Elementen wäre?

Genauso. Es bleibt O(n). Selbst bei Multithreading würde man das nach wie vor O(n) nennen, auch wenn das vermutlich ein Benefit bei großen Datenmengen bedeutet. Die Komplexität hat erst mal nichts mit der absoluten Prozesszeit zu tun. Das ist klar auseinander zu halten.

Was wäre aber, wenn alle möglichen Tupel betrachtet werden müssten (nicht nur direkte Nachbarn)?

Sortieren kann einen Vorteil ergeben. Kommt auf den Sortieralgorithmus an und wieder auf die Datenmenge. Auch hier gibt es garantiert ein break even.

 

[lord_haffi]

Was wäre aber, wenn alle möglichen Tupel betrachtet werden müssten (nicht nur direkte Nachbarn)?

Könntest einfach beim Durchlaufen des Arrays die beiden maximalen Zahlen ermittteln und hättest immer noch O(n)

Edit: Whoops, hab gerade bemerkt dass der aus runden Klammern mit n den Daumen-runter-Smiley macht ^^

 

[LimDul79]

Mit Streams geht es, aber ist bei der Aufgabe nicht sinnvoll, da ist der Overhead zu groß und die Lesbarkeit zu gering. Problem mit Streams ist, dass die jedes Element einzeln betrachten. Um bei der Reduce-Operation das maximale Produkt zu berechnen, muss ich den int erstmal in ein komplexes Objekt wandeln, was die Zahl und das bisherige maximale Produkt mitführt:

public class MaxProduktStreamHelper {
    
    private int produkt = 0;
    private int number = 0;
    
    public MaxProduktStreamHelper(int produkt, int number) {
        this.number = number;
        this.produkt = produkt;
    }
    
    public MaxProduktStreamHelper(int number) {
        this(0, number);
    }
    
    public static MaxProduktStreamHelper nextProdukt(MaxProduktStreamHelper left, MaxProduktStreamHelper right) {
        int newProdukt = left.number * right.number;
        if (newProdukt > left.produkt) {
            return new MaxProduktStreamHelper(newProdukt, right.number);
        } else {
            return new MaxProduktStreamHelper(left.produkt, right.number);
        }
    }
    
    public int getProdukt() {
        return produkt;
    }

}

public class MaxProdukt {

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 10, 5, 2, 9, 3, 10 };

        System.out.println(Arrays.stream(nums).mapToObj(MaxProduktStreamHelper::new)
                .reduce(new MaxProduktStreamHelper(0), MaxProduktStreamHelper::nextProdukt).getProdukt());
    }

}

 

[Mat]

Branch Prediction

Uhh, das ist ja cool.. ich dachte, das wäre dieser neue Kram (Neural Net Prediction bei AMD, und irgendwas anderes bei Intel), aber den Oberbegriff gibts ja schon ewig.

Für die paar Elemente könnten bspw. einfach alle Produkte schon mal parallel vorabberechnet werden, bevor entschieden wird, welches davon der Maximalwert ist.

Hmm.. das klingt auf jeden Fall sinvoll für alle Fälle, in denen die Paare erst an eine Funktion übergeben werden müssen, bevor ihr kombinierter Wert bekannt ist. Also wenn es zum Beispiel nicht um ein einfaches Produkt, sondern um irgendetwas komplexeres geht, was am besten noch eine lange Laufzeit hat:

int[] nums = {1, 2, 3, 10, 5, 2, 9, 3, 10};
int maxTupelOutput = 0;

// Bei der Variante mit Nachbarn könnte man Abschnitte parallel berechnen
// und ohne Nachbarn alle möglichen Kombinationen parallel berechnen
for (int i = 1; i < nums.length; i++) {
    maxTupelOutput = Math.max(maxTupelOutput, blackBox(nums[i-1], nums[i]));
}

// Voll komplexe Berechnung hier denken
int blackBox(int x, int y) { /* ... */ return ergebnis; }

Ich glaube, ich hab auch mal was mit Zwischenspeicherung von Ergebnissen in einer Tabelle gesehen. Memoisierung oder so. Das könnte man auch machen. Also der Datentyp wäre dann z. B. Map<Tupel, Integer>, sowas wie (1, 2) => 2483, (5, 11) => 1234, ... und dann würde man immer erst in der Tabelle das Ergebnis suchen, bevor man die intensive Berechnung startet.

Vereinfachen kann man das mit Pointern die in jeder Iteration immer um den gleichen Betrag (nämlich 1) inkrementiert werden. In Java ist das natürlich abstrahiert und der rohe Pointer ist in einen Iterator gewrappt. Aber das wäre zumindest einen Versuch wert...

Also meinst du, zum Beispiel: ich kenne die Breite jedes Elements im int-Array und inkrementiere die Adresse auf den Array anstatt extra noch einen Index zu inkrementieren? Ich glaube da scheitert es dann bei Java (zumindest im Moment.. relative Speicheradressierung kann ja noch kommen). Ich muss mich da einfach darauf verlassen, dass das im Bytecode schon optimiert wird. Aber ist dann immer gut zu wissen, wie man es dem Compiler leichter machen kann, zu optimieren.

Könntest einfach beim Durchlaufen des Arrays die beiden maximalen Zahlen ermittteln und hättest immer noch O(n)

Jo, dafür würde ich die Sortierfunktion missbrauchen. Ich wüsste sonst nicht, wie ich die beiden Maxwerte rausholen soll, ohne es umständlicher zu machen.. also ich dachte an sowas:

int[] nums = {10, 2, 3, 10, 5, 2, 9, 3, 10};
int[] sorted = IntStream.of(nums).sorted().toArray();
System.out.println(sorted[sorted.length - 1] * sorted[sorted.length - 2]); // => 100

Mit Streams geht es, aber ist bei der Aufgabe nicht sinnvoll, da ist der Overhead zu groß und die Lesbarkeit zu gering. Problem mit Streams ist, dass die jedes Element einzeln betrachten. Um bei der Reduce-Operation das maximale Produkt zu berechnen, muss ich den int erstmal in ein komplexes Objekt wandeln, was die Zahl und das bisherige maximale Produkt mitführt:

Hab das grad nochmal irgendwie mit reduce versucht, aber da missbrauche ich im Grunde nur den Akku von Reduce und die Schleife vom Stream und könnte genauso gut eine normale Schleife benutzen:

int[] nums = {10, 2, 3, 10, 5, 2, 9, 3, 10};

final int[] tmp = new int[]{0, nums[0]};
System.out.println(IntStream.of(nums).reduce((max, current) -> {
    tmp[0] = tmp[1];
    tmp[1] = current;
    return Math.max(max, tmp[0] * current);
}).getAsInt());

Dein MaxProdukt-Helper ist für mein kleines Beispiel auf jeden Fall overengineered aber interessant . Das könnte man dann auch für Memoisierung benutzen.. mit einer Lookup-Tabelle für Ergebnisse oder so. Also da könnte man in nextProdukt erstmal die Tabelle abfragen (siehe meinen Memoisierungs-Kommentar an german, weiter oben).



Ich wollte es auch nicht übertreiben mit der Optimierung, aber jetzt bin ich neugierig geworden, was der Compiler aus den Codebeispielen hier macht. Ich teile die in Methoden auf und poste die gleich.

 

[Mat]

package spielkram;

import java.util.Arrays;
import java.util.stream.IntStream;

public class MaxProdukt {

    public static void main(String[] args) {
        int[] nums = {10, 2, 3, 10, 5, 2, 9, 3, 10};

        System.out.println(mitForiSchleife(nums));
        System.out.println(mitMaxProduktHelper(nums));
        System.out.println(mitReduce(nums));
        System.out.println(mitSortieren(nums));
    }

    public static int mitForiSchleife(int[] nums) {
        int maxTupelProdukt = 0;
        for (int i = 1; i < nums.length; i++) {
            maxTupelProdukt = Math.max(maxTupelProdukt, nums[i - 1] * nums[i]);
        }
        return maxTupelProdukt;
    }

    public static int mitMaxProduktHelper(int[] nums) {
        return Arrays.stream(nums).mapToObj(MaxProduktStreamHelper::new)
                .reduce(new MaxProduktStreamHelper(0), MaxProduktStreamHelper::nextProdukt).getProdukt();
    }

    public static int mitReduce(int[] nums) {
        final int[] tmp = new int[]{0, nums[0]};
        return IntStream.of(nums).reduce((max, current) -> {
            tmp[0] = tmp[1];
            tmp[1] = current;
            return Math.max(max, tmp[0] * current);
        }).getAsInt();
    }

    public static int mitSortieren(int[] nums) {
        int[] sorted = IntStream.of(nums).sorted().toArray();
        return sorted[sorted.length - 1] * sorted[sorted.length - 2];
    }


    static class MaxProduktStreamHelper {

        private int produkt = 0;
        private int number = 0;

        public MaxProduktStreamHelper(int produkt, int number) {
            this.number = number;
            this.produkt = produkt;
        }

        public MaxProduktStreamHelper(int number) {
            this(0, number);
        }

        public static MaxProduktStreamHelper nextProdukt(MaxProduktStreamHelper left, MaxProduktStreamHelper right) {
            int newProdukt = left.number * right.number;
            if (newProdukt > left.produkt) {
                return new MaxProduktStreamHelper(newProdukt, right.number);
            } else {
                return new MaxProduktStreamHelper(left.produkt, right.number);
            }
        }

        public int getProdukt() {
            return produkt;
        }

    }
}

// class version 57.0 (57)
// access flags 0x21
public class spielkram/MaxProdukt {

  // compiled from: MaxProdukt.java
  NESTMEMBER spielkram/MaxProdukt$MaxProduktStreamHelper
  // access flags 0x8
  static INNERCLASS spielkram/MaxProdukt$MaxProduktStreamHelper spielkram/MaxProdukt MaxProduktStreamHelper
  // access flags 0x19
  public final static INNERCLASS java/lang/invoke/MethodHandles$Lookup java/lang/invoke/MethodHandles Lookup

  // access flags 0x1
  public <init>()V
   L0
    LINENUMBER 6 L0
    ALOAD 0
    INVOKESPECIAL java/lang/Object.<init> ()V
    RETURN
   L1
    LOCALVARIABLE this Lspielkram/MaxProdukt; L0 L1 0
    MAXSTACK = 1
    MAXLOCALS = 1

  // access flags 0x9
  public static main([Ljava/lang/String;)V
   L0
    LINENUMBER 9 L0
    BIPUSH 9
    NEWARRAY T_INT
    DUP
    ICONST_0
    BIPUSH 10
    IASTORE
    DUP
    ICONST_1
    ICONST_2
    IASTORE
    DUP
    ICONST_2
    ICONST_3
    IASTORE
    DUP
    ICONST_3
    BIPUSH 10
    IASTORE
    DUP
    ICONST_4
    ICONST_5
    IASTORE
    DUP
    ICONST_5
    ICONST_2
    IASTORE
    DUP
    BIPUSH 6
    BIPUSH 9
    IASTORE
    DUP
    BIPUSH 7
    ICONST_3
    IASTORE
    DUP
    BIPUSH 8
    BIPUSH 10
    IASTORE
    ASTORE 1
   L1
    LINENUMBER 11 L1
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 1
    INVOKESTATIC spielkram/MaxProdukt.mitForiSchleife ([I)I
    INVOKEVIRTUAL java/io/PrintStream.println (I)V
   L2
    LINENUMBER 12 L2
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 1
    INVOKESTATIC spielkram/MaxProdukt.mitMaxProduktHelper ([I)I
    INVOKEVIRTUAL java/io/PrintStream.println (I)V
   L3
    LINENUMBER 13 L3
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 1
    INVOKESTATIC spielkram/MaxProdukt.mitReduce ([I)I
    INVOKEVIRTUAL java/io/PrintStream.println (I)V
   L4
    LINENUMBER 14 L4
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 1
    INVOKESTATIC spielkram/MaxProdukt.mitSortieren ([I)I
    INVOKEVIRTUAL java/io/PrintStream.println (I)V
   L5
    LINENUMBER 15 L5
    RETURN
   L6
    LOCALVARIABLE args [Ljava/lang/String; L0 L6 0
    LOCALVARIABLE nums [I L1 L6 1
    MAXSTACK = 4
    MAXLOCALS = 2

  // access flags 0x9
  public static mitForiSchleife([I)I
   L0
    LINENUMBER 18 L0
    ICONST_0
    ISTORE 1
   L1
    LINENUMBER 19 L1
    ICONST_1
    ISTORE 2
   L2
   FRAME APPEND [I I]
    ILOAD 2
    ALOAD 0
    ARRAYLENGTH
    IF_ICMPGE L3
   L4
    LINENUMBER 20 L4
    ILOAD 1
    ALOAD 0
    ILOAD 2
    ICONST_1
    ISUB
    IALOAD
    ALOAD 0
    ILOAD 2
    IALOAD
    IMUL
    INVOKESTATIC java/lang/Math.max (II)I
    ISTORE 1
   L5
    LINENUMBER 19 L5
    IINC 2 1
    GOTO L2
   L3
    LINENUMBER 22 L3
   FRAME CHOP 1
    ILOAD 1
    IRETURN
   L6
    LOCALVARIABLE i I L2 L3 2
    LOCALVARIABLE nums [I L0 L6 0
    LOCALVARIABLE maxTupelProdukt I L1 L6 1
    MAXSTACK = 4
    MAXLOCALS = 3

  // access flags 0x9
  public static mitMaxProduktHelper([I)I
   L0
    LINENUMBER 26 L0
    ALOAD 0
    INVOKESTATIC java/util/Arrays.stream ([I)Ljava/util/stream/IntStream;
    INVOKEDYNAMIC apply()Ljava/util/function/IntFunction; [
      // handle kind 0x6 : INVOKESTATIC
      java/lang/invoke/LambdaMetafactory.metafactory(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
      // arguments:
      (I)Ljava/lang/Object;,
      // handle kind 0x8 : NEWINVOKESPECIAL
      spielkram/MaxProdukt$MaxProduktStreamHelper.<init>(I)V,
      (I)Lspielkram/MaxProdukt$MaxProduktStreamHelper;
    ]
    INVOKEINTERFACE java/util/stream/IntStream.mapToObj (Ljava/util/function/IntFunction;)Ljava/util/stream/Stream; (itf)
    NEW spielkram/MaxProdukt$MaxProduktStreamHelper
    DUP
    ICONST_0
    INVOKESPECIAL spielkram/MaxProdukt$MaxProduktStreamHelper.<init> (I)V
    INVOKEDYNAMIC apply()Ljava/util/function/BinaryOperator; [
      // handle kind 0x6 : INVOKESTATIC
      java/lang/invoke/LambdaMetafactory.metafactory(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
      // arguments:
      (Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;,
      // handle kind 0x6 : INVOKESTATIC
      spielkram/MaxProdukt$MaxProduktStreamHelper.nextProdukt(Lspielkram/MaxProdukt$MaxProduktStreamHelper;Lspielkram/MaxProdukt$MaxProduktStreamHelper;)Lspielkram/MaxProdukt$MaxProduktStreamHelper;,
      (Lspielkram/MaxProdukt$MaxProduktStreamHelper;Lspielkram/MaxProdukt$MaxProduktStreamHelper;)Lspielkram/MaxProdukt$MaxProduktStreamHelper;
    ]
   L1
    LINENUMBER 27 L1
    INVOKEINTERFACE java/util/stream/Stream.reduce (Ljava/lang/Object;Ljava/util/function/BinaryOperator;)Ljava/lang/Object; (itf)
    CHECKCAST spielkram/MaxProdukt$MaxProduktStreamHelper
    INVOKEVIRTUAL spielkram/MaxProdukt$MaxProduktStreamHelper.getProdukt ()I
   L2
    LINENUMBER 26 L2
    IRETURN
   L3
    LOCALVARIABLE nums [I L0 L3 0
    MAXSTACK = 4
    MAXLOCALS = 1

  // access flags 0x9
  public static mitReduce([I)I
   L0
    LINENUMBER 31 L0
    ICONST_2
    NEWARRAY T_INT
    DUP
    ICONST_0
    ICONST_0
    IASTORE
    DUP
    ICONST_1
    ALOAD 0
    ICONST_0
    IALOAD
    IASTORE
    ASTORE 1
   L1
    LINENUMBER 32 L1
    ALOAD 0
    INVOKESTATIC java/util/stream/IntStream.of ([I)Ljava/util/stream/IntStream; (itf)
    ALOAD 1
    INVOKEDYNAMIC applyAsInt([I)Ljava/util/function/IntBinaryOperator; [
      // handle kind 0x6 : INVOKESTATIC
      java/lang/invoke/LambdaMetafactory.metafactory(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite;
      // arguments:
      (II)I,
      // handle kind 0x6 : INVOKESTATIC
      spielkram/MaxProdukt.lambda$mitReduce$0([III)I,
      (II)I
    ]
    INVOKEINTERFACE java/util/stream/IntStream.reduce (Ljava/util/function/IntBinaryOperator;)Ljava/util/OptionalInt; (itf)
   L2
    LINENUMBER 36 L2
    INVOKEVIRTUAL java/util/OptionalInt.getAsInt ()I
   L3
    LINENUMBER 32 L3
    IRETURN
   L4
    LOCALVARIABLE nums [I L0 L4 0
    LOCALVARIABLE tmp [I L1 L4 1
    MAXSTACK = 5
    MAXLOCALS = 2

  // access flags 0x9
  public static mitSortieren([I)I
   L0
    LINENUMBER 40 L0
    ALOAD 0
    INVOKESTATIC java/util/stream/IntStream.of ([I)Ljava/util/stream/IntStream; (itf)
    INVOKEINTERFACE java/util/stream/IntStream.sorted ()Ljava/util/stream/IntStream; (itf)
    INVOKEINTERFACE java/util/stream/IntStream.toArray ()[I (itf)
    ASTORE 1
   L1
    LINENUMBER 41 L1
    ALOAD 1
    ALOAD 1
    ARRAYLENGTH
    ICONST_1
    ISUB
    IALOAD
    ALOAD 1
    ALOAD 1
    ARRAYLENGTH
    ICONST_2
    ISUB
    IALOAD
    IMUL
    IRETURN
   L2
    LOCALVARIABLE nums [I L0 L2 0
    LOCALVARIABLE sorted [I L1 L2 1
    MAXSTACK = 4
    MAXLOCALS = 2

  // access flags 0x100A
  private static synthetic lambda$mitReduce$0([III)I
   L0
    LINENUMBER 33 L0
    ALOAD 0
    ICONST_0
    ALOAD 0
    ICONST_1
    IALOAD
    IASTORE
   L1
    LINENUMBER 34 L1
    ALOAD 0
    ICONST_1
    ILOAD 2
    IASTORE
   L2
    LINENUMBER 35 L2
    ILOAD 1
    ALOAD 0
    ICONST_0
    IALOAD
    ILOAD 2
    IMUL
    INVOKESTATIC java/lang/Math.max (II)I
    IRETURN
   L3
    LOCALVARIABLE tmp [I L0 L3 0
    LOCALVARIABLE max I L0 L3 1
    LOCALVARIABLE current I L0 L3 2
    MAXSTACK = 4
    MAXLOCALS = 3
}

Sieht interessant aus, wie er die anonyme Funktion aus mitReduce nochmal auslagert.

 

[german]

Das könnte man auch machen.

Es macht aber einen Unterschied auf welchem Level das passiert. Ich meine wirklich die Optimierung die die CPU an der Stelle vornimmt. Die temporären Werte liegen dann in Registern und die Zugriffszeiten tendieren gegen Null. Selbst implementieren erzeugt schon wieder Overhead weil du einmal über die Werte iterierst um die Produkte zu berechnen und dann noch mal über die Produkte. Die CPU macht ersteres ggf. asynchron.

Also meinst du, zum Beispiel: ich kenne die Breite jedes Elements im int-Array und inkrementiere die Adresse auf den Array anstatt extra noch einen Index zu inkrementieren?

Das wäre was Pointer automatisch machen wenn sie inkrementiert werden. Die Adresse rückt um die Typbreite weiter.

Ich hab gerade mal Google bemüht um was zusammen zu basteln was etwa dem entspricht was ich meine.

    public static void main(String[] args) {
        int[] numbs = {1, 2, 3, 10, 5, 2, 9, 3, 10};
        if (numbs.length > 1) {
            java.util.PrimitiveIterator.OfInt it = java.util.stream.IntStream.of(numbs).iterator();
            int previous = it.nextInt();
            int current = it.nextInt();
            int maxTupleProduct = previous * current;
            while (it.hasNext()) {
                previous = current;
                current = it.nextInt();
                maxTupleProduct = Math.max(maxTupleProduct, previous * current);
            }
            System.out.println(maxTupleProduct);
        }
    }

Das scheint also in Java tatsächlich komplizierter zu sein als gedacht. .nextInt() gibt dir also den derzeitig referenzierten Wert und rückt anschließend die Referenz auf das nächste int. (Referenzen sind üblicherweise über Pointer implementiert, da schließt sich der Kreis wieder.) Es ist aber offenbar nicht möglich diese beiden Aktionen unabhängig voneinander auszuführen. Somit ist man gezwungen die zurückgegebenen Werte temporär zwischen zu speichern. Wie viel Sinn das dann noch macht, kann ich nicht sagen.

 

[LimDul79]

Wobei - meiner persönlichen Meinung nach - sowas zwar als Spielerei interessant ist, aber im Endeffekt es zu 99% wichtiger ist, lesbaren Code zu schreiben, als so eine - böse formuliert - Pseudo-Optimierung zu betreiben. Denn zwischen Java Code und Ausführung auf dem Prozessor liegen so viele Schichten, die Dinge tun, dass es schwer bis unmöglich ist auf den tatsächlich durchgeführten Code zu schließen.

Gut, ich komme aus der Java EE Welt, wo es um Enterprise Anwendungen geht, die in der Regel immer Kommunikation mit anderen System etc. drin haben - da ist eine Performance Optimierung an so einer Stelle in der Regel sinnlos, weil alles was man da an Gewinn rausholt bezogen auf die Gesamtlaufzeit in den Bereich der Messungenauigkeit fällt. Und wenn man mit Datenmengen hantiert, wo es relevant wird, würde ich persönlich eher Hinterfragen ob Java da die geeignete Technologie ist oder ob das nicht eher eine Datenbank oder ähnliches machen soll.

 

[german]

Ja, das denke ich auch.
BTW: Hast du eine Ahnung wie Streams implementiert sind? Ich hatte keine Möglichkeit gefunden direkt einen Iterator auf das Array zu holen. Wenn in Streams, genauer gesagt im darunterliegenden Streambuffer, nicht das Array mit den Daten in einem konsekutiven Speicherbereich liegt, dann bleibt man wohl besser bei den Indices. Wenn Daten erst kopiert werden und womöglich eine Linked List oder so etwas gebaut wird, dann wäre das Unsinn. Ist halt tatsächlich das Problem bei hochgradig abstrahierten Sprachen. Du kannst zwar als Entwickler kaum noch was grundsätzlich falsch machen weil alles doppelt und dreifach abgesichert ist. Die Klassen mit ihren Methoden sind bequem, aber da steckt auch das Problem. Du siehst nur dein Interface und weißt nicht was in der Implementierung passiert. Wenn du Pech hast kopierst du Daten 50x von a nach b ohne es zu wissen und wunderst dich anschließend warum die Performance in den Keller rutscht.

 

[LimDul79]

Muss ich passen, das ist der Fluch und Segen der Enterprise Entwicklung. Man muss sich nicht mehr mit diesen Details unter Haube beschäftigen. Nachteil ist, man verliert leicht den Blick wie du geschrieben hast. Bei Streams sehe ich da noch nicht das Problem, aber JPA ist da ein schöner Fallstrick. Man schreibt schön bequem Java-Code und sieht dem Code nicht auf den ersten Anblick an, dass der zig DB-Queries absetzen wird. Und dann wundert man sich, warum sich der DBA über die Last beschwert

 

[german]

Kein Ding Wie du schon geschrieben hast, sind solche Mikrooptimierungen bei Sprachen wie Java vergebliche Liebesmühe. Dessen bin ich mir schon bewusst. Aber da wir einmal beim Spielen waren ...
Und bloß nicht missverstehen. Nur weil ich aus der C Ecke komme halte ich C nicht für das Nonplusultra. Im Gegenteil, C ist für Masochisten. Wer seine Brötchen mit Programmierung verdienen will (was bei mir nicht der Fall ist), ist mit Java besser dran. Irgendwann besteht der Kunde auch mal darauf, dass abgeliefert wird. Und man will seine Zeit auch nicht damit verbringen, die zehnfache Menge Code zu schreiben und noch Monde mit Debugging zu verbringen, was bei C Code ziemlich wahrscheinlich wäre. In der Zeit hat man schon wieder die nächsten Projekte abzuliefern...
Kommt eben immer auf die Aufgabe an. Java ist sicher geil für Frontend. Für Backend und selbst für das API muss das aber schon nicht mehr zutreffen wie du ja auch angemerkt hattest.