Ein Narr lernt Java

[Tzu Iop]

Project Euler ist einfach toll. [...]

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.HashMap;

//How many triangle words does the list of common English words contain?
public class Prb042_sltn {

    /**
     * @param args
     */
    public static void main(String[] args) {
        HashMap<Integer, Integer> trianglenumbers = new HashMap<Integer, Integer>();
        String str = "", line="";
        try {
            BufferedReader input = new BufferedReader(new FileReader("bin/words.txt"));
            line = input.readLine();    
        } 
        catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        String[] words = line.split("\",\"");
        words[0]=words[0].substring(1);
        int count = 0, n=0 ;
        for(int k=1; k <= n; k++){ // Die Schleife tut nichts, da n = 0 und k = 1 und damit direkt k > n.
            trianglenumbers.put(k, k*(k+1)/2);
        }    
        for(int k=0; k < words.length; k++){    
            int value = StringCharMethods.wordvalue(words[k]);
            while(n*(n+1)/2 <= value){
                trianglenumbers.put(n, n*(n+1)/2);
                n++;
            }
            if(trianglenumbers.containsValue(value)){
                count++;
                //System.out.println(words[k]+" is the "+count+". triangle word and it's value is "+value);
            }
        }
        System.out.print(count);
    }
} 

Siehe Kommentar. Ansonsten selbst mehr kommentieren, wenn du Code an andere weiter gibts, sonst ist das etwas schwer verständlich.

[Peregrin_Tooc]

Stimmt, die Schleife tut nichts, die steht da nur noch, weil ich für n mal einen anderen Wert genommen hatte. Ist aus dem Code rausgeflogen, aber nicht aus der Zwischenablage

@Flati: Danke, ich hatte es nachgelesen Die Oracle-API ist ganz gut, auch wenn ich gerade bei den Reader-Unterklassen echt noch nicht durchsteige, da hilft wohl nur Anwendung

[Peregrin_Tooc]

Merke: longs explizit als long deklarieren

final long START=2*3*5*7*11*13*17*23*29; 

ergibt keinen long-Wert
Da kann man sich ja tot debuggen
was so ein "L" für einen Unterschied machen kann...

[Peregrin_Tooc]

public static boolean prime(long n){ /**tests if a given long is prime */
        if(n == 1|n<0){
            return false; 
        }
        
        for(long i=2L; i*i<=n; i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
    
    public static ArrayList<Long> oddPrimeList(long n){ /**returns a list of all primes below n */
        ArrayList<Long> L = new ArrayList<Long>();
        if(n <2){
            return L;
        }
        L.add(2L);
        for(long i=3L; i<=n; i++){
                boolean prime = true;
                for(Long p: L){
                    if(i%p==0){
                        prime=false;
                        break;
                    }
                }
                if(prime){
                    L.add(i);
                }
            }
        return L;
    }
    public static ArrayList<Long> primeList(long n){ /**returns a list of all primes below n */
        ArrayList<Long> L = new ArrayList<Long>();
        for(long i=2L; i<=n; i++){
            if(prime(i)){
                L.add(i);
            }
        
        }
    return L;
    } 

Ich bin etwas verwirrt.
Die erste Methode testet naiv, ob eine Zahl prim ist.
Die dritte Methode gibt ne Primzahlliste aus, wo für jede Zahl naiv geprüft wird, ob sie prim ist.
Die zweite Methode sollte, so dachte ich, viel schneller sein, da nur für jede kleinere Primzahl geprüft wird, ob sie die zu untersuchende Zahl teilt. Ist aber vieeeeel langsamer. Liegt das daran, dass der Zugriff auf die Liste so langsam ist? Kann man das schneller machen?

[Tzu Iop]

[...]
Ich bin etwas verwirrt.
Die erste Methode testet naiv, ob eine Zahl prim ist.
Die dritte Methode gibt ne Primzahlliste aus, wo für jede Zahl naiv geprüft wird, ob sie prim ist.
Die zweite Methode sollte, so dachte ich, viel schneller sein, da nur für jede kleinere Primzahl geprüft wird, ob sie die zu untersuchende Zahl teilt. Ist aber vieeeeel langsamer. Liegt das daran, dass der Zugriff auf die Liste so langsam ist? Kann man das schneller machen?

ArrayList benutzt unten drunter einen Array, d.h. da muss eventuell häufiger kopiert werden, wenn das Array zu klein ist. Ich hätte deswegen folgende Verbesserungsvorschläge, die man testen könnte:
- LinkedList stattdessen benutzen (Kein Kopieren beim Einfügen)
- Beim Erzeugen der Liste, die Länge auf n/log n setzen, dann wird weniger oft vergrößert. (int-Argument im Listen Konstruktor)
- Vector probieren und dort auch die Länge beim Erzeugen auf n/log n setzen.

edit:
Zur genaueren Erklärung ArrayList verhält sich in etwa wie ein Unbounded Array, d.h. es wird für das Einfügen nur armotisiert konstante Zeit erwartet.

[Peregrin_Tooc]

Aber das Problem des "Addierens" hat man ja bei beiden Methoden, da kann der Zeitunterschied nicht herkommen.
Um alle Primzahlen unter 100.000 aufzulisten, brauch ich mit der schnellen Methode 116ms, mit der langsamen 3.655 ms.
Bei 200.000 sinds 252 bzw 14.901; bei 300.000 sinds 474 bzw. 31950

Will sagen, die schnelle geht linear, die langsame quadratisch. Das kann ja nur am Zugriff liegen?

[Tzu Iop]

Aber das Problem des "Addierens" hat man ja bei beiden Methoden, da kann der Zeitunterschied nicht herkommen.
Um alle Primzahlen unter 100.000 aufzulisten, brauch ich mit der schnellen Methode 116ms, mit der langsamen 3.655 ms.
Bei 200.000 sinds 252 bzw 14.901; bei 300.000 sinds 474 bzw. 31950

Will sagen, die schnelle geht linear, die langsame quadratisch. Das kann ja nur am Zugriff liegen?

Ich sehe gerade, dass du einen kleinen aber feinen Fehler gemacht hast:

if(n == 1||n<0) 

Muss es heißen, denn | ist bitweises Oder und || logisches. Dein Ausdruck wertet immer zu True aus und damit ist auch die Methode immer sofort zu Ende. Linearzeit kann bei dem Primzahlentest nämlich niemals eintreten.

[Shakka]

[Tzu Iop]

Ändert übrigens nichts daran, dass Java anscheinend die Schleifen aus der ersten Methode recht gut optimiert. Ich bekomme da nämlich auch ordentlich Laufzeitunterschiede.

[goethe]

da gibt es eine Funktion und eine boolsche Variable, die beide "prime" heißen. Die boolesche Variable wird mit jedem Schleifendurchlauf erzeugt (boolean prime = true; Speichallokierung) und wieder zerstört --> habe ich das richtig verstanden? Ein Compiler würde das sicher optimieren, aber was macht java dann?

[Quietsch]

Wo ich gerade damit rumspiele: Wenn man

for(Long p: L){ 
                    if(i%p==0){ 
                        prime=false; 
                        break; 
                    } 
                }

zu

for(Long p: L){
                	if(p*p > i){
                		break;
                	}
                    if(i%p==0){ 
                        prime=false; 
                        break; 
                    } 
                }

ändert, macht es ein klein wenig aus.

[Peregrin_Tooc]

Ich sehe gerade, dass du einen kleinen aber feinen Fehler gemacht hast:

if(n == 1||n<0) 

Muss es heißen, denn | ist bitweises Oder und || logisches. Dein Ausdruck wertet immer zu True aus und damit ist auch die Methode immer sofort zu Ende. Linearzeit kann bei dem Primzahlentest nämlich niemals eintreten.

Nein, das stimmt nicht (aber du hast Recht, || wäre besser), der Primzahltest gibt für 0 und 1 durchaus false aus. Und (nur) für Primzahlen true. "|" ist das nicht-Kurzschluss-oder und erzwingt, das beide Ausdrücke ausgewertet werden. Ersetzt habe ich es aber nun eh durch

if(n<2) 

[Peregrin_Tooc]

da gibt es eine Funktion und eine boolsche Variable, die beide "prime" heißen. Die boolesche Variable wird mit jedem Schleifendurchlauf erzeugt (boolean prime = true; Speichallokierung) und wieder zerstört --> habe ich das richtig verstanden? Ein Compiler würde das sicher optimieren, aber was macht java dann?

Das ist eine gute Frage. An und für sich müsste der Garbage-Collector nach jedem Durchlauf die Variable killen. Vielleicht kann man an der Stelle was drehen.

Wo ich gerade damit rumspiele: Wenn man

for(Long p: L){ 
                    if(i%p==0){ 
                        prime=false; 
                        break; 
                    } 
                }

zu

for(Long p: L){
                	if(p*p > i){
                		break;
                	}
                    if(i%p==0){ 
                        prime=false; 
                        break; 
                    } 
                }

ändert, macht es ein klein wenig aus.

Stimmt, das hilft natürlich, aber sollte nicht soo viel ausmachen.

[Quietsch]

Stimmt, das hilft natürlich, aber sollte nicht soo viel ausmachen.

Bei mir hat's den Unterschied zwischen ~10s und ~0,8s ausgemacht. Du sparst dir dadurch, vor allem bei den größeren Zahlen, unheimlich viele Listenzugriffe.

[Tzu Iop]

Das ist eine gute Frage. An und für sich müsste der Garbage-Collector nach jedem Durchlauf die Variable killen. Vielleicht kann man an der Stelle was drehen.

Macht quasi nichts aus. Da das auf dem Stack landet wie jede lokale Variable. Man spart sich vielleicht einen Maschinenbefehl pro Schleifendurchlauf.

Stimmt, das hilft natürlich, aber sollte nicht soo viel ausmachen.

Oh, doch macht es. War selbst etwas überrascht.