flertrådet programmering

Hej Emilie.

I dit eksempel har du hvordan du tester om et tal er en primtal.
Det må kunne gøres mere effektivt, men det handler din opgave jo ikke om.

Der er sikker mange måder at dele opgaven ud i flere tråde, men hvis du gerne vil have at primtallene kommer nogenlunde ud til brugeren i rækkefølge, så kunne du have et object som indeholder tal som skal testes og som test-trådene trækker numre fra - vel og mærke i nummer-orden.

Dvs. du laver en klasse som kan danne en kø struktur fra et start-tal til et slut-tal.
Denne klasse skal have en metode til at trække et tal fra køen og en metode til at melde tilbage med et tal som er fundet som primtal.

Disse 2 metoder skal trådsikres, så du kan have et vilkårligt antal objecter i hver sin tråd til at kalde 'simultant'.

Hvis ikke din kø klasse skal være singleton eller statisk, så skal du give udregnings objecterne kø objectet som reference - enten ved injection gennem en metode eller på anden vis.

Ved kørsel tænker jeg at du først laver et kø-object og sætter det til at have tallene fra x til y.
Så starter du et antal test-objecter op som hver sin tråd.
Hver test-object vil så mens dens tråd afvikles spørge kø-objectet om et tal der skal testes - derefter vil talles blive testet og hvis det er et primtal meldes det tilbage til kø-objectet (som står for at sende besked til brugeren) og så trækkes der et nyt tal.

Så skal du bare have fundet ud af hvordan du stopper dine test-object tråde - og der kan det hjælpe hvis du beholder en reference til dem der hvor du starter dem op - f.eks. ved at putte dem i en liste af en slags - Vector eller noget andet - som du så kan løbe igennem og bede om at stoppe,

Håber det giver bare en smule ide om hvordan du kommer videre.

Hvis du bare vil have noget Java kode kan jeg godt skrive det til dig, men det ville du ikke lære ret meget af er jeg bange for.

Hej Jonathan.

Tusind tak for dit meget grundige og hurtige svar.

Jeg er med på din idé med at starte med at lave en kø-klasse med et kø-objekt, men jeg forstår ikke hvordan jeg skal implementere et kø som går fra start-tal til slut-tal. Ville det være en idé at oprette en integer med et start-tal og en integer med et slut-tal eller hvordan skal jeg danne denne kø-struktur?

Derefter skal jeg have to metoder i min kø-klasse. En metode som looper igennem min kø-struktur og en metode som looper igennem den samme kø-struktur, men som KUN sender primtal tilbage?

Det er her jeg er i tvivl om hvad jeg skal stille op da jeg ikke ved hvordan jeg skal lave disse to metoder som tråde der kører simultant/samtidigt. Forstår ikke hvad du mener med at de skal trådsikres.

Jeg er også usikker på hvordan jeg skal definere udregningsobjekterne og give dem en reference til kø-objektet som metode.

Ved kørsel forstår jeg lidt af den idé men igen har jeg svært ved at se hvordan jeg skal konstruere de forskellige dele du nævner. Jeg skal altså lave et antal test-objekter som starter og tester deres tråd hente et tal fra kø-objektet. Når tallet så er testet sendes det tilbage til kø-objektet hvis det altså er et primtal.

Jeg er også i tvivl om hvordan jeg skal lave en liste.


Jeg forstår godt hvad du mener mht at forstå komponenter og jeg lærer selvfølgelig mere hvis jeg selv prøver, men jeg er meget lost omkring hvordan jeg kan fange problemet an og har siddet i flere dage uden at finde en løsning. Da jeg er lidt i tidspres og skal aflevere i morgen, vil jeg derfor blive meget meget taknemlig hvis du kan vise mig kode.

Kærlig hilsen Emilie

Hej Emilie.

Jeg tænker at du laver en klasse primeque.
Den klasse har en metode som tager imod long fra og long til.
Denne metode fylder en intern attribut med alle numrene fra 'fra' til 'til'.
Klassen har også en anden attribut som er tom fra start, og som under kørslen fyldes med de tal som meldes tilbage som værende primtil fra den tråd som nu har testet det.

Yderligere har klassen disse to public synchronized metoder: nextnumber og logprime(long prime).

1) din hoved klasse starter din kø klasse op som object og giver den fra og til som danner dens interne liste af numre.
2) din hoved klasse starter x antal arbejder tråde op, med kø klasse objectet som argument/arameter til deres contructor (eller hvordan du nu vil give hver tråd adgang til kø-objectet)
3) nu kører hver tråd afsted, trækker et nummer fra køen - tester om det er et primtal og melder tilbage til køen med tallet hvis det var et primtal - og så om igen - træk nyt osv. - indtil tråden lukkes ned.

Altså - din test klasse som skal køre som en tråd for hvert object kan implementere runnable eller på anden måde gøre sig klar til at blive en tråd.

Hjalp det lidt?

En rudimentær, men vigtig forbedring er at lave:

 while (numberToBeLookedAt % factor > 0)

om til:

 while (numberToBeLookedAt % factor > 0 && factor < Math.sqrt(numberToBeLookedAt))

Da en primfaktor selvfølgelig ikke kan være større end kvadratruden af tallet.

Og en endnu mere vigtig forbedring.
Lav:

 while (numberToBeLookedAt % factor > 0 && factor < Math.sqrt(numberToBeLookedAt))

..om til:

 double sqrt = Math.sqrt(numberToBeLookedAt);
 while (numberToBeLookedAt % factor > 0 && factor < sqrt)

Ingen grund til at beregne kvadratroden for hvert loop.

Pinligt - Tak Robert. (Fanger compileren egentlig ikke det?)

I C/C++ gør den, for der kan man markere, at input ikke bliver ændret, og at funktionen ikke har side effekter. Det kan man ikke i Java.
Compileren kan derfor ikke vide, om resultatet altid er det samme, eller om funktionen ændrer på en global variabel for hvert kald. Den er nødt til at gøre, hvad du beder den om.

Hey Emillie.
Hvis du ønsker at optimere din løsning vil jeg gerne fraråde dig at bruge tid på tråde. Paralellisme er først og fremmest skide svært, men vigtigst af alt, bruger du en naiv og meget langsom algoritme...

En langt bedre (og kode-mæssig simplel) løsning er Miller Rabins Primtals Test. Tjek: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Jeg har lavet en implementering her:

 import java.util.Random;
 
 
 public class MillerRabin {
     private static int countPrim = 0;
     
     public static void main(String[] args) {
         CalcPrim(10, 37870);
     }
 
     /**
      * Repeats the Miller Rabin test
      * @param start
      * @param end
      */
     private static void CalcPrim(int start, int end) {
         if(start % 2 == 0) //even then get next odd
             start++;
         
     
         for(int i = start; i < end; i=i+2){
             MillerRabinTest(i, 2);
         }
         
         System.out.println("Number of prims "+countPrim);
     }
 
     /**
      * Calc s and t and calc calculator
      * @param test-number
      * @param times we will test
      */
     private static void MillerRabinTest(int m, int repeat) {
         Random b = new Random();
         
         //find s and t
         int t = m-1;
         int s = 0;
         while(t%2 == 0){
             t = t/2;
             s++;
         }
         
         boolean aPrime = true;
         for(int i = 0; i < repeat; i++){
             if(!makeTest(s,t,b.nextInt(m-1)+1, m)){
                 aPrime = false;
             }
         }
         if(aPrime == true){
             //System.out.println(m+" is a prim");
             countPrim++;
         }
         
     }
     
     private static long pow(int b, int t, int m){
         long res = 1;
         String binaryT = Integer.toBinaryString(t);
         for(int i = 0; i < binaryT.length(); i++){
             res = (res*res)%m;
             res = (res*(binaryT.substring(i,i+1).equals("1") ? b:1))%m;
         }
         return res%m;
     }
 
 
     private static boolean makeTest(int s, int t, int b, int m) {
         long y = (long) pow(b, t, m);
         if(y == 1){
             return true;
         }
         for(int i = 0; i<=s-1; i++){
             if(y == m-1){
                 return true;
             }    
             y = (long) pow((int) y, 2, m);
         }
         return false;
     }
     
 }

Derudover vil jeg også lige informerer dig. Flere tråde vil bare gøre din implementation concurrent. Du vil ikke bruge alle processorer ved at bruge den.

Derudover vil jeg også lige informerer dig. Flere tråde vil bare gøre din implementation concurrent. Du vil ikke bruge alle processorer ved at bruge den.

Det kommer vel an på om der bliver lavet nok tråde og hvordan operativsystemet vælger at fordele trådene, så det er ikke et helt utænkeligt scenarie.

Passs... Jeg ved ikke om der er nogen OS eller sprog der gør det anderledes.
Men som udgangspunkt snakker man altid tråde som concurrency...
Og det er hvert fald især tilfældet for tåde i java