java - 并行程序 Java 中的埃拉托斯特尼筛法

Question

我想制作一个使用 Erastotones Sieve 计算素数的程序。在本期中，我想使用信号量在线程之间进行通信，以对带有数字的表进行计算。 到目前为止我已经编写过这样的代码。

public static void main( String[] args ) throws InterruptedException {
        System.out.println("Podaj gorny zakres\n");
        Scanner scanner = new Scanner(System.in);
        Erastotenes erastotenes = new Erastotenes(Integer.parseInt(scanner.nextLine()));
        erastotenes.initializeTable();


        long start = System.nanoTime();

        List<SingleProcess.MyThread> list = new ArrayList<>();

        List<Integer> numbers = Dollar.$(2,erastotenes.getMaximumNumber()+1).toList();

        for(int i=0;i<2;i++)
        {
            list.add(new SingleProcess.MyThread(erastotenes,numbers.subList((numbers.size()/2)*i,(numbers.size()/2)*i+numbers.size()/2)));
            list.get(list.size()-1).start();
            list.get(list.size()-1).join();
        }

        System.out.println(System.nanoTime() - start);

        //System.out.println("Liczba elementów: "+erastotenes.countPrimeElements());
    }

Erastotenes 类。

public class Erastotenes {

    private int upperRange;
    private int maximumNumber;
    private int table[];

    public Erastotenes(int upperRange) {
        this.upperRange = upperRange;
        this.maximumNumber = (int)(Math.floor(Math.sqrt(upperRange)));
        this.table = new int[upperRange+1];
    }


    public int getMaximumNumber() {
        return maximumNumber;
    }

    public int getUpperRange() {
        return upperRange;
    }

    public void initializeTable()
    {
        for(int i=1;i<=upperRange;i++) {
            table[i] = i;
        }

    }

    public void makeSelectionOfGivenNumber(int number)
    {
        if (table[number] != 0) {
            int multiple;
            multiple = number+number;
            while (multiple<=upperRange) {
                table[multiple] = 0;
                multiple += number;
            }
        }
    }

    public List<Integer> getList()
    {
        List<Integer> list = Ints.asList(table);
        return  list.stream().filter(item->item.intValue()!=0 && item.intValue()!=1).collect(Collectors.toList());
    }
}

描述单个线程使用静态信号量进行计算的类如下所示。

public class SingleProcess {

    static Semaphore semaphore = new Semaphore(1);

    static class MyThread extends Thread {

        Erastotenes erastotenes;
        List<Integer> numbers;

        MyThread(Erastotenes erastotenes,List<Integer> numbers) {
            this.erastotenes = erastotenes;
            this.numbers=numbers;
        }


        public void run() {
            for(int number:numbers) {
                try {
                    semaphore.acquire();
                    //1System.out.println(number + " : got the permit!");
                    erastotenes.makeSelectionOfGivenNumber(number);

                } catch (InterruptedException e) {

                    e.printStackTrace();
                } finally {
                    semaphore.release();
                }
            }

        }

    }
}

我认为，像这两个线程的erastotrenes算法一样，将半个表的数字从2到最大数字作为平方根进行分割会提高计算量，但将upperRange设置为100000000时，并行和序列之间的差异并不那么大。我怎样才能在另一个方面实现并行编程Erastonenes Sieve的这个问题？

Answer 1

我认为你的主要问题是:

    for(int i=0;i<2;i++)
    {
        list.add(new SingleProcess.MyThread(erastotenes,numbers.subList((numbers.size()/2)*i,(numbers.size()/2)*i+numbers.size()/2)));
        list.get(list.size()-1).start();
        list.get(list.size()-1).join();
    }

您启动一个线程，然后立即等待它完成；这完全消除了并行性。你可以开始并等待最后:

    for(int i=0;i<2;i++)
    {
        list.add(new SingleProcess.MyThread(erastotenes,numbers.subList((numbers.size()/2)*i,(numbers.size()/2)*i+numbers.size()/2)));
        list.get(list.size()-1).start();
    }
    for (Thread t : list) {
        t.join();
    }

但是，你的信号量也有问题。每个线程只要正在处理一个数字，就会阻止所有其他线程执行任何操作；这再次意味着所有并行性都消失了。

在我看来，你可以完全取消信号量；多次将相同的索引设置为 0 并没有太大的危险，这就是这个“关键部分”中发生的所有事情 - 但这根本不重要，因为在所有线程完成之前没有人读取有问题的数组值.