Thanks for this too :) 2009/12/7 Fayland Lam <[email protected]>
> and hey, we still haven't do day 8 yet. :) > > Regards, > > 2009/12/7 Fayland Lam <[email protected]> > > hey, I'll put it into web. >> >> Thanks. >> >> 2009/12/7 joe jiang <[email protected]> >> >> =for advent_year 2009 >>> >>> =for advent_day 9 >>> >>> =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 的方法来运行了。 >>> >>> >>> 应该还可以找到其他语言的一些实现，不过限于个人的知识有限，就先不去尝试了。欢迎大家把更加有效的实现发在网上，自己认为有趣的语言值得花点时间证明一下。 >>> >>> >>> >>> Chat Skype: joejiang799 MSN: [email protected] >>> Contact Me [image: >>> Linkedin]<http://cn.linkedin.com/pub/joe-jiang/12/552/940> [image: >>> Flickr] <http://www.flickr.com/photos/40820...@n04> >>> blog managed to setup the plone login with >>> SQLPASPlugin<http://lamppurl.blogspot.com/2009/11/managed-to-setup-plone-login-with.html> >>> >>> >>> --- @ WiseStamp Signature <http://www.wisestamp.com/email-install>. Get >>> it now <http://www.wisestamp.com/email-install> >>> >>> >>> >>> >> >> >> -- >> Fayland Lam // http://www.fayland.org/ >> > > > > -- > Fayland Lam // http://www.fayland.org/ > > > > --~--~---------~--~----~------------~-------~--~----~ 您收到此信息是由于您订阅了 Google 论坛“PerlChina Mongers 讨论组”论坛。 要在此论坛发帖，请发电子邮件到 [email protected] 要退订此论坛，请发邮件至 [email protected] 更多选项，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问该论坛 -~----------~----~----~----~------~----~------~--~---
