[Java] Berechnun in Thread aufteilen

Dieses Thema im Forum "Programmierung & Entwicklung" wurde erstellt von IronSnake, 31. Mai 2010 .

  1. 31. Mai 2010
    Berechnun in Thread aufteilen

    Hallo,
    ich habe folgendes Programm geschrieben, leider dauert die Berechnung bei den befreundeten Zahlen bis 10 000 000 einfach zu lange.

    Wie könnte ich denn das Proramm umstrukturieren damit 10 Threads paralllel laufen

    z.B 1 bis 1 000 000, 1 000 001 bis 2 000 000 ... usw ?

    Code:
    public class zahlen {
     public static void main(String[] args) {
     long gesamt=0;
     for(long i=9000000;i<=10000000;i++){
     long sum = teiler(i);
     if(i<sum){
     long j = teiler(sum);
     if(j==i){
     gesamt = gesamt + i + sum;
     System.out.println("Zwischenwert" + gesamt);
     }
     }
     }
     System.out.println("Gesamtwert" + gesamt);
     }
    
    public static long teiler(long a){
     long summe = 0;
     for(long i = 1; i <= (a/2); i++){
     if ((a % i) == 0){
     summe += i;
     }
     } 
     return summe;
    }
    }
    Ich weiß zwar wie Threads grob funktionieren, aber nicht wie sich zusammen eine variable teilen (gesamt) und evtl noch übergabeparameter haben
     
  2. 31. Mai 2010
    AW: Berechnun in Thread aufteilen

    Ich habe dir mal nen bisschen was geschrieben, kann sein das Feher drin sind, da ich's nicht getestet habe. Weiterhin habe ich das Prinzip deiner Berechnung nicht ganz verstanden, musst daher mal sehen wie du das anpasst:

    Code:
    class TeilerThread extends Thread
    {
    private long start, stop;
    private Queue<Long> resultQueue;
    
    public TeilerThread(long start, long stop, Queue<Long> resultQueue)
    {
     // TODO variablen zuweisen
    }
    
    @Override
    public void run()
    {
     // TODO berechnungen durchführen
     synchronized(resultQueue)
     {
     // ergebnis in resultQueue speichern
     }
    }
    
    public static void main(String[] args) 
    {
     Queue<Long> resultQueue = new LinkedList<Long>();
     List<Thread> threads = new ArrayList<Thread>();
     for(int i=0; i < 10; ++i)
     {
     threads.add(new TeilerThread(/* variablen zuweisen */, resultQueue));
     threads.get(threads.size()).start();
     }
    
     for(Thread t : threads)
     {
     t.join();
     }
    }
    
    }
    
     
  3. 31. Mai 2010
    AW: Berechnun in Thread aufteilen

    also ich habs jetzt so

    Code:
    public class zahlen {
     long gesamt=0;
     public static void main(String[] args) {
     Thread th1, th2, th3, th4, th5, th6, th7, th8, th9, th10;
     th1 = new Thread(0, 1000000);
     th2 = new Thread(1000001, 2000000);
     th3 = new Thread(2000001, 3000000);
     th4 = new Thread(3000001, 4000000);
     th5 = new Thread(4000001, 5000000);
     th6 = new Thread(5000001, 6000000);
     th7 = new Thread(6000001, 7000000);
     th8 = new Thread(7000001, 8000000);
     th9 = new Thread(8000001, 9000000);
     th10 = new Thread(9000001, 10000000);
     th1.run();
     th2.run();
     th3.run();
     th4.run();
     th5.run();
     th6.run();
     th7.run();
     th8.run();
     th9.run();
     th10.run();
     }
    }
    
    
    
    class Thread extends zahlen {
     private long VON=0;
     private long BIS=0;
     
     public Thread(long VON, long BIS) {
     this.VON = VON;
     this.BIS = BIS;
     }
     
     public void run() {
     for(long i=VON;i<=BIS;i++){
     long sum = teiler(i);
     if(i<sum){
     long j = teiler(sum);
     if(j==i){
     gesamt = gesamt + i + sum;
     System.out.println("Zwischenwert" + gesamt + "I: " + i + " " + j);
     }
     }
     }
     }
    
     
     public static long teiler(long a){
     long summe = 0;
     for(long i = 1; i <= (a/2); i++){
     if ((a % i) == 0){
     summe += i;
     }
     } 
     return summe;
     }
    }
    Aber parallel aufrufen tut er nichts dort oder?


    So habs nun so... der rechnet wird zwar stark belasstet, aber wirklich schneller rechnen tut er nicht.

    Code:
     
    
    
    public class zahlen {
    
     public static void main(String[] args) {
     XThread th1, th2, th3, th4, th5, th6, th7, th8, th9, th10;
     th1 = new XThread(0, 1000000);
     th2 = new XThread(1000001, 2000000);
     th3 = new XThread(2000001, 3000000);
     th4 = new XThread(3000001, 4000000);
     th5 = new XThread(4000001, 5000000);
     th6 = new XThread(5000001, 6000000);
     th7 = new XThread(6000001, 7000000);
     th8 = new XThread(7000001, 8000000);
     th9 = new XThread(8000001, 9000000);
     th10 = new XThread(9000001, 10000000);
     th1.start();
     th2.start();
     th3.start();
     th4.start();
     th5.start();
     th6.start();
     th7.start();
     th8.start();
     th9.start();
     th10.start();
     }
    }
    
    
    
    class XThread extends Thread {
     static long gesamt=0;
     private long VON=0;
     private long BIS=0;
     
     public XThread(long VON, long BIS) {
     this.VON = VON;
     this.BIS = BIS;
     }
     
     public void run() {
     for(long i=VON;i<=BIS;i++){
     long sum = teiler(i);
     if(i<sum){
     long j = teiler(sum);
     if(j==i){
     gesamt = gesamt + i + sum;
     System.out.println("Zwischenwert" + gesamt + "I: " + i + " " + j);
     }
     }
     }
     }
    
     
     public static long teiler(long a){
     long summe = 0;
     for(long i = 1; i <= (a/2); i++){
     if ((a % i) == 0){
     summe += i;
     }
     } 
     return summe;
     }
    }
    
     
  4. 31. Mai 2010
    AW: Berechnun in Thread aufteilen

    Wenn es genau so lang dauert, dann werden die 10 Threads trotzdem nur von einem Core berechnet.. nur dass der Scheduler sich immer wieder einen Thread nimmt, einen Teil berechnet, dann einen Anderen usw. im Endeffekt das gleiche wie bei einem Thread nur dass er mit der Berechnung mal dort und mal da ist...

    bzw. schau doch mal im taskmanager ob alle kerne ausgelastet sind wenn das programm läuft
     
  5. 1. Juni 2010
    AW: Berechnun in Thread aufteilen

    Ganz ehrlich, mich wundert's dass dein Programm überhaupt läuft...
    Code:
    class XThread extends Thread {
     [B]static long gesamt=0;[/B]
     private long VON=0;
     private long BIS=0;
     
     public XThread(long VON, long BIS) {
     this.VON = VON;
     this.BIS = BIS;
     }
     
     public void run() {
     for(long i=VON;i<=BIS;i++){
     long sum = teiler(i);
     if(i<sum){
     long j = teiler(sum);
     if(j==i){
     [B]gesamt = gesamt + i + sum;[/B]
     System.out.println("Zwischenwert" + gesamt + "I: " + i + " " + j);
     }
     }
     }
     }
    
     
     [B]public static long teiler(long a)[/B]{
     long summe = 0;
     for(long i = 1; i <= (a/2); i++){
     if ((a % i) == 0){
     summe += i;
     }
     } 
     return summe;
     }
    }
    
    1. Du musst den Zugriff auf gemeinsame Variablen synchronisieren. Da du hier sowieso nur einen Zugriff hast, reicht ein einfacher synchronized-Block:
    Code:
    synchronized(this) {
     gesamt = gesamt + i + sum;
     System.out.println("Zwischenwert" + gesamt + "I: " + i + " " + j);
    
    }
    
    2. Wieso ist denn die teiler-Methode static? Ich weiß zwar nicht wie es sich auf das Laufzeitverhalten auswirkt, aber sie muss es definitiv nicht sein.

    Wie viele Kerne hat dein Prozessor überhaupt?
     
  6. 1. Juni 2010
    AW: Berechnun in Thread aufteilen

    Wenn sie es sein kann sollte sie es auch sein. In Kombination mit final erhält man einen Geschwindigkeitsvorteil.

    Wo erbt eigentlich eine Klasse bei dir von Thread oder implementiert Runnable?

    So kann das ja nichts werden ^^
     
  7. 2. Juni 2010
    AW: Berechnun in Thread aufteilen

    Seine Klasse erbt von Thread,
    Code:
    class XThread extends Thread
    das scheint alles zu funktionieren. Vllt. ist sein PC auch einfach nicht leistungsfähig genug, um die Berechnung schneller auszuführen. In dem Fall sollte man sich dann lieber den Algorithmus mal vornehmen und gucken, was es da zu optimieren gibt.
     
  8. 3. Juni 2010
    AW: Berechnun in Thread aufteilen

    sorry du hast recht.
    ist mir etwas zu kuddel muddel ^^
     
  9. 3. Juni 2010
    AW: Berechnun in Thread aufteilen

    Ach hat sich schon erledigt Für die, die es Interessiert: Es ging um einen kleinen Programmierwettbwerb bei uns in der Uni. Aufgabenstellung war es: Die Summe aller "befreundeten Zahlen" von 2 bis 10 000 000 (10 Millionen) zu errechnen und an den Prof zu senden.

    Beispiel: Die ersten befreundeten Zahlen sind 220 und 284.
    Denn:
    - Teiler von 220 sind: 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110
    - Die Summe davon wäre 284
    - Teiler von 284 sind: 1 + 2 + 4 + 71 + 142
    - Die Summe davon wäre 220


    Also die Summe der Teiler von 220 ergibt 284, und die Summe der Teiler von 284 wiederrum 220. Deswegen sind die Zahlen befreundet.

    Meine Lösung an sich war ja eig. richtig, allerdings würde diese Modulo Geschichte bis 10 000 000 einfach zu viel Zeit beanspruchen.

    Hätte man noch bissel weiter gesucht, wäre man auf eine spezielle Formel von Euler gestoßen, mit der man alle befreundete Zahlen ermitteln kann.

    In meinen Augen voll der Witz, was auch dann eig. nix mehr mit proggen zu tun hat, denn ne Formel in ne Source kloppen kann doch jeder


    Und das mein Source so durcheinander ist, hat damit zu tun, dass es ein Wettbewerb auf Zeit war und die ersten Einsender gewonnen hatten. Threads hatten wir davor noch nicht und ich wollt se einfach mal schnell anlernen und ins programm einhacken, mit der Hoffnung es würde dann schneller klappen. War aber wohl doch nicht der Fall
     
  10. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.