太精炼了， 高手
2009/12/8 钟声 <[email protected]> > 很酷 > > 2009/12/8 Fayland Lam <[email protected]> > > http://perlchina.org/advent/2009/PrimeNumbers.html >> >> =for advent_year 2009 >> >> =for advent_day 8 >> >> =for advent_title Prime Numbers >> >> =for advent_author Joe Jiang >> >> 质数的计算是一个曾经非常有趣的话题，现在对我们来说也还是一个稍微有些难度的编程训练。下面我们就用这个话题来看看 Perl >> 和其他语言解决数学问题的能力。当然首先我们得有个基准程序： >> >> =begin pre >> >> % matho-primes 1 10 >> 2 >> 3 >> 5 >> 7 >> >> =end pre >> >> 如果你在运行类似 Debian 的系统，这个程序可以从 apt-get install mathomatic-primes 获得。它是 >> mathomatic 软件包的一个插件，恰好可以满足我们的需求。 >> >> 然后，我们可以用 Perl 来实现同样的功能，当然为了好玩，这会是一个 One-liner 脚本（其实是个 bash function）： >> >> =begin pre >> >> prime () >> { >> perl -e '@screen=(0,0,2..$ARGV[0]); map { my $p=$_; if >> ($screen[$p]) { $screen[$_ * $p]=0 for 2..$#screen/$p }} >> 2..sqrt($#screen); print qq($_\n) for grep {$_} @screen' $1 >> } >> >> % prime 10 >> 2 >> 3 >> 5 >> 7 >> >> =end pre >> >> 这个程序的原理是开个大数组（名叫 @screen ），并把其中下标为质数的元素置为下标本身。质数的定义是从 2 到 sqrt() >> 都无法整除的数字，所以一旦发现质数，就可以把他的若干倍数值下标的元素都置为 0。最后数组中剩下不为 0 的元素就是质数。 >> >> 那么这个程序的速度如何呢？用 time 来测试对比一下： >> >> =begin pre >> >> $ time matho-primes 1 1000000 > /dev/null >> >> real 0m0.151s >> user 0m0.152s >> sys 0m0.004s >> >> $ time prime 1000000 > /dev/null >> >> real 0m0.846s >> user 0m0.768s >> sys 0m0.076s >> >> =end pre >> >> 在第二次运行速度的比较来看，我们的程序大概是 C 语言程序的 1/6 速度。坦白说，自己觉得这个速度还不错。 >> >> 那么其他语言呢？在网上找来一个 Python 版本，用作对比： >> >> =begin pre >> >> $ python >> Python 2.6.2 (release26-maint, Apr 19 2009, 01:58:18) >> [GCC 4.3.3] on linux2 >> Type "help", "copyright", "credits" or "license" for more information. >> >>> aux = {}; [aux.setdefault(p, p) for p in range(2, 10) if 0 not in [p%d >> for d in aux if p>=d*d]]; >> [2, 3, 5, 7] >> >> % time python -c 'aux = {}; [aux.setdefault(p, p) for p in range(2, >> 1000000) if 0 not in [p%d for d in aux if p>=d*d]];' >> ... >> >> =end pre >> >> 应该说，Python 的 for ... if ... >> 后缀语法确实很酷。但是直到文章发表为止，脚本还没有结束。不知道为什么这个科学家发明的语言在数学上不太便捷。欢迎大家踊跃指出原因。 >> >> 另外又在网上找到一段 Haskell 程序，应该承认这是非常简短的程序： >> >> =begin pre >> >> $ ghci >> GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help >> Loading package base ... linking ... done. >> Prelude> let primes = sieve [2..] where sieve (p:xs) = p : sieve [x | >> x<-xs, x `mod` p /= 0] >> take 4 primes >> [2,3,5,7] >> Prelude> Leaving GHCi. >> >> $ cat | time ghci > /dev/null >> let primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x<-xs, x >> `mod` p /= 0] >> take 78498 primes >> ^D >> ... >> >> =end pre >> >> ghci 这个命令行程序来自于软件包 ghc6，是 Haskell 的 Runtime evaluator。安装命令是 apt-get >> install ghc6。 >> >> 注意这个程序的参数是需要输出的质数个数，而不是最大值。2 到 1000000 一共有 78498 个质数，这可以从 matho-primes >> 1 1000000 | wc -l 命令计算出来。 >> >> 直到文章发表为止，脚本还没有结束。其他更加复杂的版本应该可以运行的更快，但是估计不太用适合 One-liner 的方法来运行了。 >> >> 应该还可以找到其他语言的一些实现，不过限于个人的知识有限，就先不去尝试了。欢迎大家把更加有效的实现发在网上，自己认为有趣的语言值得花点时间证明一下。 >> >> ===================== >> Big Thanks to Joe. :) >> >> -- >> Fayland Lam // http://www.fayland.org/ >> >> >> > > > > -- Yours Sincerely Zeng Hong --~--~---------~--~----~------------~-------~--~----~ 您收到此信息是由于您订阅了 Google 论坛“PerlChina Mongers 讨论组”论坛。 要在此论坛发帖，请发电子邮件到 [email protected] 要退订此论坛，请发邮件至 [email protected] 更多选项，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问该论坛 -~----------~----~----~----~------~----~------~--~---
