如何在Perl 6中有效地生成素数列表？

Question

在Perl 6中，使用is-prime生成素数列表非常容易。

my @primes = (^∞).grep: *.is-prime;

如果需要相对较少的素数，这就足够了，但是对于大的数字来说，效率很低，因为每个数字都是独立检查的。

是否有一种方法可以访问Perl 6内置的素数检查逻辑，从而有效地创建素数列表？否则我需要自己做个筛子。很简单，但我担心，在高级Perl 6代码中使用一个筛子，其效率几乎与我开始使用的代码一样低。

Answer 1

我为原筛编写了一些Perl 6绑定。

https://github.com/CurtTilmes/perl6-primesieve

数学：：初级筛

Answer 2

如果您使用--profile运行您的程序，您将看到超过99%的时间用于Int.is-prime。因为这实际上只是nqp::isprime_I()的一个包装器，所以我尝试在没有包装器的情况下运行类似的代码。但这并没有明显改变任何事情。因此，这项工作的首要任务是在nqp::isprime_I()完成的。

因此，您真正拥有的唯一选项是将搜索的素数并行化。在不久的将来，hyper将是你在这里的朋友。但是，这目前正处于“初始的天真实现”阶段，更健壮的实现将在：https://gist.github.com/jnthn/6a80a9712fb38b32537f9f0e46fca6d7中进行讨论。

在此之前，如果您希望更快地运行，则必须手动拆分要检查是否为初始状态的值的范围，并在start块中运行它们，并从结果的Promise中收集结果。

Answer 3

这并不是我问题的真正答案，但我列举了几种获得素数列表的方法。

结论：

1. . is -prime确实太慢了(尽管@DanaJ的分支有望对此有所改进)。
2. Perl 6代码中的筛子并不像我所担心的那么慢，只要您稍微优化一些东西(即使代码不那么漂亮Perl6ish)。
3. 本机代码(通过Perl 5模块)仍然要快得多。
4. 作弊是最快的。

编辑：添加了Curt的初级筛模块。哇，真快！它胜过欺骗(即从文件中读取素数)！好吧，这可能是因为Primesieve不支持生成器/迭代器(还没有？)，所以我只是一次返回整个列表，而所有其他版本都使用生成器/延迟列表。

编辑:基于Timbus的评论，添加了“更优化的”筛子。这个有相当不错的性能，但代码几乎不可能遵循.

编辑：添加了一个更好的纯Perl6版本，具有灵活的筛子大小。我从奇数1.99的(预初始化)筛开始，必要时将筛子大小加倍。再加上一些进一步的优化(例如，扩展筛网时，我们只需检查素数到√(筛子大小))，这是迄今为止最快的纯Perl 6版本。进一步的优势:你不必事先知道一个限制；如果你确实需要一个很高的限制，它会给小素数带来更快的速度。

编辑：数学：：现在支持迭代器，所以在脚本中包含它。

#!/usr/bin/env perl6

use v6.c;

# The easy but slow way
sub primes-is-prime
{
    (^∞).grep: *.is-prime;
}

# Use a sieve (simple Perl 6 style)
sub primes-sieve(Int $max)
{
    my @sieve;
    lazy gather for 2..$max -> $p {
        next if @sieve[$p];
        take $p;
        for 2*$p, 3*$p ... $max -> $n {
            @sieve[$n] = True;
        }
    }
}

# Use a sieve (optimized)
sub primes-sieve2(Int $max)
{
    my int @sieve;
    lazy gather {
        take 2;
        loop (my int $p = 3; $p ≤ $max; $p += 2) {
            next if @sieve[$p];
            take $p;
            loop (my int $n = 3*$p; $n ≤ $max; $n += 2*$p) {
                @sieve[$n] = 1;
            }
        }
    }
}

# Use a sieve (even more optimized)
sub primes-sieve3(Int $max)
{
    my int @sieve;
    my $max2 = ($max-1) div 2;
    lazy gather {
        take 2;
        for 1 .. $max2 -> int $i {
            next if @sieve[$i];
            take 2*$i + 1;
            my $max3 = ($max2 - $i) div (2*$i + 1);
            for 1 .. $max3 -> int $j {
                @sieve[(2*$j + 1)*$i + $j] = 1;
            }
        }
    }
}

# Use a flexible sieve size (and further optimized)
sub primes-sieve4
{
    # Pre-initialize our sieve with the odd numbers from 1 to 99
    my $max = 100;
    my int @sieve = 1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,
                    1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,0,1,1,1,0,1;

    lazy gather {
        # Don't forget our single even prime number
        take 2;

        my int $min-i = 1;
        loop {
            # Take all primes in the new part of the sieve 
            my int $max-i = ($max-1) div 2;
            for $min-i .. $max-i -> int $i {
                take 2*$i + 1 unless @sieve[$i];
            }

            # Extend sieve by factor 2
            # We must check the primes from 3 to √(2*max) in the sieve
            # for max to 2*max
            for 1 .. ((2*$max).sqrt.floor-1) div 2 -> int $i {
                next if @sieve[$i];
                my int $p = 2*$i + 1;
                my int $min-j = max(($max-i - $i) div $p, $i);
                my int $max-j = (2*$max-i + 1 - $i) div $p;
                for $min-j .. $max-j -> int $j {
                    @sieve[$i + $p*$j] = 1;
                }
            }

            # Double the sieve size, and start the next iteration
            # in the second half of the sieve
            $max *= 2;
            $min-i = $max-i+1;
        }
    }
}

# Use a Perl 5 module
sub primes-perl5
{
    use Math::Prime::Util:from<Perl5> <prime_iterator>;

    my $it = prime_iterator;
    lazy gather {
        loop {
            take $it.();
        }
    }
}

# Use Primesieve module
sub primes-primesieve($max)
{
    # See:
    #  - http://primesieve.org/
    #  - https://github.com/CurtTilmes/perl6-primesieve
    use Math::Primesieve;

    # No iterator support (yet?), so just return the whole list
    return Math::Primesieve.new.primes($max);
}

# Use Primesieve module (iterator)
sub primes-primesieve-iterator
{
    # See:
    #  - http://primesieve.org/
    #  - https://github.com/CurtTilmes/perl6-primesieve
    use Math::Primesieve;
    my $iterator = Math::Primesieve::iterator.new;
    lazy gather {
        loop {
            take $iterator.next;
        }
    }
}

# Cheat
# Source: https://primes.utm.edu/lists/small/millions/ - first million
# (Unzip and remove the first few lines from the file.)
sub primes-cheat
{
    lazy $*PROGRAM.sibling('primes1.txt').words.map(+*);
}

sub timer(&code)
{
    my $start = now;
    &code();
    my $elapsed = now - $start;
    say "Elapsed: $elapsed.fmt('%.3f')s";
}

sub MAIN
{
    #my $nth = 1_000;
    #my $max = 8_000;

    #my $nth = 10_000;
    #my $max = 105_000;

    my $nth = 50_000;
    my $max = 612_000;

    timer {
        my @primes = primes-is-prime;
        say "Using .is-prime: @primes[$nth]";
    }
    timer {
        my @primes = primes-sieve($max);
        say "Using a sieve (simple Perl 6 style): @primes[$nth]";
    }
    timer {
        my @primes = primes-sieve2($max);
        say "Using a sieve (optimized): @primes[$nth]";
    }
    timer {
        my @primes = primes-sieve3($max);
        say "Using a sieve (even more optimized): @primes[$nth]";
    }
    timer {
        my @primes = primes-sieve4;
        say "Using a flexible sieve size (further optimized): @primes[$nth]";
    }
    timer {
        my @primes = primes-perl5;
        say "Using a Perl 5 module: @primes[$nth]";
    }
    timer {
        my @primes = primes-primesieve($max);
        say "Using Primesieve module: @primes[$nth]";
    }
    timer {
        my @primes = primes-primesieve-iterator;
        say "Using Primesieve module (iterator): @primes[$nth]";
    }
    timer {
        my @primes = primes-cheat;
        say "Cheating: @primes[$nth]";
    }
}

# 4 year old Linux server, running Rakudo Star 2017.04:
#
# Using .is-prime: 611957
# Elapsed: 216.134s
# Using a sieve (simple Perl 6 style): 611957
# Elapsed: 124.087s
# Using a sieve (optimized): 611957
# Elapsed: 41.129s
# Using a sieve (even more optimized): 611957
# Elapsed: 7.285s
# Using a flexible sieve size (further optimized): 611957
# Elapsed: 3.897s
# Using a Perl 5 module: 611957
# Elapsed: 10.031s
# Using Primesieve module: 611957
# Elapsed: 0.312s
# Using Primesieve module (iterator): 611957
# Elapsed: 1.460s
# Cheating: 611957
# Elapsed: 2.017s