[Løst] Primtallutregning ved hjelp av tråder

[Teknolog-1]

Hei!

 

Jeg holder for tiden på med en oppgave og den går ut på å regne ut primtall i et visst intervall (mellom to gitte tall). Det skal gjøres i et gitt antall tråder. Dette skal lagres i en liste og sorteres (de minste primtallene ut først).

 

I den forbindelse har jeg støtt på noen problemer da jeg er relativt fersk når det kommer til trådprogrammering. Her er klassen Tråd (som jeg kjører flere av i klienten):

public class Tråd extends Thread {
    private ArrayList<Integer> primliste = new ArrayList<Integer>();
    private static int fra;
    private static int til;

    public Tråd(int fra, int til) {
        this.fra = fra;
        this.til = til;
    }

    public ArrayList<Integer> getPrimliste() {
        return primliste;
    }

    public static boolean erPrimtall(int n) {
        return !new String(new char[n]).matches(".?|(..+?)\\1+");
    }

    public static ArrayList<Integer> primtall(int f, int t) {
        ArrayList<Integer> tall = new ArrayList<Integer>();
        System.out.println("F: " + f + " T: " + t);
        for (int i = f; i < t; i++) {
            if (erPrimtall(i)) {
                tall.add(i);
            }
        }
        return tall;
    }

    public void run() {
        synchronized (primliste){
            primliste = primtall(fra, til);
        }
        try{
            Thread.sleep(1000);
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Jeg er usikker på om dette er rett bruk av run(). Det pga at jeg får ikke ut den utskriften jeg vil ha. Her er klienten:

public class Øving1 {

    public static void main(String[]args) {
        ArrayList<ArrayList<Integer>> sum = new ArrayList<ArrayList<Integer>>();

        //Oppretter tråder og starter de
        Tråd tr = new Tråd(0, 10);
        tr.start();
        Tråd tr2 = new Tråd(11, 20);
        tr2.start();
        Tråd tr3 = new Tråd(21, 30);
        tr3.start();
        try{
            tr.join();
            tr2.join();
            tr3.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        //Legger til primtallene i en ArrayList
        sum.add(tr.getPrimliste());
        sum.add(tr2.getPrimliste());
        sum.add(tr3.getPrimliste());

        //Sorterer primtallene
        for(ArrayList<Integer> l : sum) {
            Collections.sort(l);
        }
        sort(sum, new Comparator<ArrayList<Integer>>() {
            public int compare(ArrayList<Integer> en, ArrayList<Integer> to) {
                return en.get(0).compareTo(to.get(0));
            }
        });

        for(ArrayList<Integer> ai : sum) {
            for(Integer i : ai) {
                System.out.print(i + " ");
            }
        }
    }
}

Utskriften jeg får er: 23 29 23 29 23 29. 23 og 29 er rett for den tredje tråden (altså primtallene mellom 21 og 30). Problemet er at den blir kjørt tre ganger. Det virker som om det er noe synkroniseringsproblemer ettersom hvor jeg hadde diverse out.println gjorde at jeg fikk ut resultatet av tråd to i tillegg.

 

Jeg vil med andre ord få hver sin tråd til å håndtere hvert sitt intervall, for så å hente ut verdiene og legge de i en liste for så å sortere de og eventuelt skrive ut.

 

Jeg har også forstått det slik at man helst skal bruke implements runnable fremfor extends thread? Jeg har prøvd begge (da det tok få sekunder å skrive om) og jeg får samme resultat.

 

Er det noen som kan fortelle meg hva jeg gjør feil?

[quantum]

Problemet ditt er at til og fra-variablene er static, alle tråd-instansene deler dermed samme intervall.

 

Trådinstansene deler derimot ikke primliste, så denne trenger du ikke synkronisere på, trådene kan bare rase ivei uten å løpe i beina på hverandre.

 

Det er også som du sier korrekt å implementere Runnable, men det hjelper - som du har funnet ut - ikke på resultatet her.

 

Til slutt putter du de tre resultatlistene i en ny liste-liste, det er unødvendig komplisert. Her er en lettere modda variant ... tillot meg å endre klassenavnene også, en tråd som heter Tråd sier oss fint lite...

package primecalculation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class PrimeCalculation {

    private static class PrimeCalculationThread implements Runnable {

        private ArrayList<Integer> primliste = new ArrayList<>();
        private int fra;
        private int til;

        public PrimeCalculationThread(int fra, int til) {
            this.fra = fra;
            this.til = til;
        }

        public ArrayList<Integer> getPrimliste() {
            return primliste;
        }

        public static boolean erPrimtall(int n) {
            return !new String(new char[n]).matches(".?|(..+?)\\1+");
        }

        public static ArrayList<Integer> primtall(int f, int t) {
            ArrayList<Integer> tall = new ArrayList<Integer>();
            System.out.println("F: " + f + " T: " + t);
            for (int i = f; i < t; i++) {
                if (erPrimtall(i)) {
                    tall.add(i);
                }
            }
            return tall;
        }

        public void run() {

            primliste = primtall(fra, til);

            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ArrayList<Integer> sum = new ArrayList<Integer>();

        //Oppretter tråder og starter de
        PrimeCalculationThread pct1 = new PrimeCalculationThread(0, 10);
        PrimeCalculationThread pct2 = new PrimeCalculationThread(11, 20);
        PrimeCalculationThread pct3 = new PrimeCalculationThread(21, 30);
        Thread tr1 = new Thread(pct1);
        tr1.start();
        Thread tr2 = new Thread(pct2);
        tr2.start();
        Thread tr3 = new Thread(pct3);
        tr3.start();
        try {
            tr1.join();
            tr2.join();
            tr3.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        //Legger til primtallene i en ArrayList
        sum.addAll(pct1.getPrimliste());
        sum.addAll(pct2.getPrimliste());
        sum.addAll(pct3.getPrimliste());

        Collections.sort(sum);

        for (Integer ai : sum) {
            System.out.print(ai + " ");
        }
    }
}

Utskrift:

F: 11 T: 20
F: 21 T: 30
F: 0 T: 10
2 3 5 7 11 13 17 19 23 29

Legg merke til at utskriften av de tre intervallene kommer i "tilfeldig" rekkefølge.

Endret 28. januar 2014 av quantum

[Teknolog-1]

Ah det visste jeg ikke (om static). Grunnen til at jeg la de i en liste-liste var at jeg ikke fikk til å legge til uten å gjøre det på den måten. Jeg visste ikke om metoden addAll(), burde bli bedre til å sjekke Java API'et. Tråd fulgte nok ikke akkurat navnekonvensjonene i java nei, det er sant. Tusen takk for hjelpen og forklaringen.

[quantum]

Få deg et IDE så blir det meste enklere. Ctrl-space så får du (som regel) se alle tilgjengelige metoder osv.