Java中的Eratosthenes并行筛选 - java

我正在尝试并行实现Eratosthenes筛。我制作了一个布尔列表,其中填充了给定大小的true。每当找到素数时,该素数的所有倍数在布尔值列表中都标记为false。

我试图使该算法并行的方法是通过触发一个新线程,同时仍然过滤初始素数。例如,算法以prime = 2开始。在for过滤器的循环中,当prime * prime时,我制作了另一个for循环,其中检查了prime(2)和prime * prime(4)之间的每个数字。如果布尔值列表中的该索引仍然为true,则启动另一个线程以过滤该素数。

嵌套的for循环随着要过滤的质数的发展而产生越来越多的开销,因此我将其限制为仅当质数<100时才进行此嵌套的for循环。我假设到那时,这1亿个数字将是有点过滤。这里的问题在于,以这种方式,要过滤的素数保持在9500素数以下,而算法在10000素数处停止(素数*素数<size(100m))。我也认为这根本不是正确的解决方法。我在网上进行了大量搜索,但没有找到任何与之并行的Java实现实例。

我的代码如下所示:

主班:

public class Main {
    private static ListenableQueue<Integer> queue = new ListenableQueue<>(new LinkedList<>());
    private static ArrayList<Integer> primes = new ArrayList<>();
    private static boolean serialList[];
    private static ArrayList<Integer> serialPrimes = new ArrayList<>();
    private static ExecutorService exec = Executors.newFixedThreadPool(10);
    private static int size = 100000000;
    private static boolean list[] = new boolean[size];
    private static int lastPrime = 2;

    public static void main(String[] args) {
        Arrays.fill(list, true);

        parallel();
    }

    public static void parallel() {
        Long startTime = System.nanoTime();
        int firstPrime = 2;

        exec.submit(new Runner(size, list, firstPrime));
    }

    public static void parallelSieve(int size, boolean[] list, int prime) {
        int queuePrimes = 0;
        for (int i = prime; i * prime <= size; i++) {
            try {
                list[i * prime] = false;
                if (prime < 100) {
                    if (i == prime * prime && queuePrimes <= 1) {
                        for (int j = prime + 1; j < i; j++) {
                            if (list[j] && j % prime != 0 && j > lastPrime) {
                                lastPrime = j;
                                startNewThread(j);
                                queuePrimes++;
                            }
                        }
                    }
                }
            } catch (ArrayIndexOutOfBoundsException ignored) { }
        }
    }

    private static void startNewThread(int newPrime) {
        if ((newPrime * newPrime) < size) {
            exec.submit(new Runner(size, list, newPrime));
        }
        else {
            exec.shutdown();
            for (int i = 2; i < list.length; i++) {
                if (list[i]) {
                    primes.add(i);
                }
            }
        }
    }
}

跑步班:

public class Runner implements Runnable {
    private int arraySize;
    private boolean[] list;
    private int k;

    public Runner(int arraySize, boolean[] list, int k) {
        this.arraySize = arraySize;
        this.list = list;
        this.k = k;
    }

    @Override
    public void run() {
        Main.parallelSieve(arraySize, list, k);
    }

}

我觉得有一种解决这个问题的简单得多的方法...
你们对我如何使并行化工作甚至更简单有任何建议吗?

参考方案

创建像Eratosthenes的Sieve之类的算法的高性能并发实现比创建高性能单线程实现要困难一些。原因是您需要找到一种方法来对工作进行分区,以最大程度地减少并行工作线程之间的通信和干扰。

如果实现了完全隔离,则可以希望速度提高到接近可用逻辑处理器的数量,或者在典型的现代PC上达到一个数量级。相比之下,使用适当的筛子单线程实现将使您的速度至少提高2到3个数量级。一种简单的解决方案是在需要时简单地从文件中加载数据,或者将其封装到像Kim Walisch的PrimeSieve这样的体面的筛选程序中。

即使我们只想研究并行化问题,仍然有必要对算法本身以及运行它的机器有一些了解。

最重要的方面是,现代计算机具有较深的缓存层次结构,其中,只有L1缓存(通常为32 KB)可以全速访问,而所有其他内存访问都将受到严重影响。转换为Eratosthenes筛网后,这意味着您需要一次将目标范围筛分一个32 KB窗口,而不是将每个素数跨度超过数兆字节。在平行舞开始之前,必须筛分直至目标范围末端平方根的小素数,但随后可以分别筛分每个片段或窗口。

筛选给定的窗口或片段需要确定要筛选的小质数的起始偏移量,这意味着每个窗口和每个小质数至少有一个模除法是非常慢的操作。但是,如果筛分连续的段而不是放置在范围内任何位置的任意窗口,则可以将向量中每个质数的末端偏移保留下来,并将其用作下一个段的起始偏移,从而避免了昂贵的起始偏移计算。

因此,用于Eratosthenes筛网的一种有前途的并行化策略是为每个工作线程提供32 KB块的连续组进行筛分,因此每个工作线程仅需要进行一次起始偏移量计算。这样,工作人员之间就不会存在内存访问争用,因为每个人都有自己独立的目标范围子范围。

但是,在开始并行化(即,使代码更复杂)之前,您应该首先精简它,并将要做的工作减少到绝对必要的程度。例如,从代码中查看以下片段:

for (int i = prime; i * prime <= size; i++)
   list[i * prime] = false;

无需在每次迭代中重新计算循环边界并使用乘法索引,请针对预先计算的,循环不变的值检查循环变量,并将乘法减少为迭代加法:

for (int o = prime * prime; o <= size; o += prime)
   list[o] = false;

有两个简单的针对特定筛子的优化方法,它们可以提供显着的速度提升。

1)将偶数从筛子中取出,并在需要时将素数2从稀薄的空气中拉出。宾果游戏,您的表现翻了一番。

2)而不是用小的奇数质数3、5、7等筛选每个片段,而是在片段(甚至整个范围)上展开预先计算的图案。这节省了时间,因为这些小的素数在每个段中进行了很多很多步骤,并且占据了筛分时间的绝大部分。

还有更多的可能的优化方法,包括增加一些悬而未决的成果,但要么收益递减,要么努力曲线急剧上升。尝试在Code Review中搜索“筛子”。另外,别忘了除了算法问题和机器架构之外,您还在与Java编译器进行对抗,例如,数组边界检查之类的编译器可能会或可能无法退出循环。

为您提供一个大概的数字:在C#中,带有预计算模式的单线程分段仅占优势的筛子可以在2到4秒内筛分整个32位范围,这取决于您除了上述内容外还应用了多少TLC。在我老化的笔记本电脑上,不到100毫秒就解决了高达100000000(1e8)的素数问题。

这是一些显示窗口筛分工作原理的代码。为了清楚起见,我在读取素数时放弃了所有优化,例如仅赔率表示或wheel-3步进。它是C#,但是应该与Java足够相似,以便可读。

注意:我称筛子数组eliminated是因为true值表示一个交叉的数字(省去了在数组开头填充全true的问题,无论如何它都更合逻辑)。

static List<uint> small_primes_between (uint m, uint n)
{
    m = Math.Max(m, 2);

    if (m > n)
        return new List<uint>();

    Trace.Assert(n - m < int.MaxValue);

    uint sieve_bits = n - m + 1;
    var eliminated = new bool[sieve_bits];

    foreach (uint prime in small_primes_up_to((uint)Math.Sqrt(n)))
    {
        uint start = prime * prime, stride = prime;

        if (start >= m)
            start -= m;
        else
            start = (stride - 1) - (m - start - 1) % stride;

        for (uint j = start; j < sieve_bits; j += stride)
            eliminated[j] = true;
    }

    return remaining_numbers(eliminated, m);
}

//---------------------------------------------------------------------------------------------

static List<uint> remaining_numbers (bool[] eliminated, uint sieve_base)
{
    var result = new List<uint>();

    for (uint i = 0, e = (uint)eliminated.Length; i < e; ++i)
        if (!eliminated[i])
            result.Add(sieve_base + i);

    return result;
}

//---------------------------------------------------------------------------------------------

static List<uint> small_primes_up_to (uint n)
{
    Trace.Assert(n < int.MaxValue);    // size_t is int32_t in .Net (!)

    var eliminated = new bool[n + 1];  // +1 because indexed by numbers

    eliminated[0] = true;
    eliminated[1] = true;

    for (uint i = 2, sqrt_n = (uint)Math.Sqrt(n); i <= sqrt_n; ++i)
        if (!eliminated[i])
            for (uint j = i * i; j <= n; j += i)
                eliminated[j] = true;

    return remaining_numbers(eliminated, 0);
}

Java中的“ <<”运算符 - java

最喜欢的语句来自Java的Character类:(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节,type是整数。这句话中的操作员,他们做什么?如何以及在哪里可以使用这些运算符?这是oracles java.lang.Character文档。该类中…

Java-固定大小的列表与指定初始容量的列表之间的差异 - java

我在理解这一点上遇到了问题。当我们做 List<Integer> list = Arrays.asList(array); 我们不能在该列表上使用添加,删除之类的方法。我知道Arrays.asList()返回固定大小的列表。我不明白的是,如果我们创建一个具有指定初始容量的列表,例如List<Integer> list2 = new A…

从方法参数或引用创建新对象 - java

public setArrayList(List<Integer> list) { this.list = list; //OR this.list = new ArrayList<Integer>(list); } 我看到不同的人可以交替使用此代码。这两种实现之间有区别吗? 参考方案 是的-这两个示例在功能上有所不同。public …

如何确保列表中的项目是连续的? - java

美好的一天 !我想问一下我是否有清单1,2,3,4,5 ..然后我将替换值“ 3”插入到“ 7”,这将提示我错误原因是列表不连续。List<Domain> items = new ArrayList<Domain>(); 参考方案 您可以重写ArrayList,设置和添加方法以检查设置/添加的项是否有效,如果无效,则抛出Illegal…

JAVA:字节码和二进制有什么区别? - java

java字节代码(已编译的语言,也称为目标代码)与机器代码(当前计算机的本机代码)之间有什么区别?我读过一些书,他们将字节码称为二进制指令,但我不知道为什么。 参考方案 字节码是独立于平台的,在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的,如果在Windows x86中编译,则它将仅在Win…