Sieve of Eratosthenes 的 Haskell/Scheme 实现

win_hate

我下个官方的 svn 版本捣鼓一下。你用的是那个版本吗？

就我现在这个版本，只要在代码的开头加入

1. 
   
2. (require (lib "lazy.ss" "lazy"))
   

复制代码

则 mzscheme 就变成 lazy 的了。

[ 本帖最后由 win_hate 于 2008-9-21 19:15 编辑 ]

MMMIX

原帖由 win_hate 于 2008-9-21 19:10 发表
我下个官方的 svn 版本捣鼓一下。你用的是那个版本吗？

我用的是正式发布的 4.1 版, http://download.plt-scheme.org/drscheme/

win_hate

没有我可用的版本(XUbuntu)，x86_64 那个是红帽的，估计不好用。

MMMIX

原帖由 win_hate 于 2008-9-21 19:26 发表
没有我可用的版本(XUbuntu)，x86_64 那个是红帽的，估计不好用。

那估计你要用的话只能自己从源码编译了。

win_hate

svn check out 的版本(11826)，4.1.0.3

现在用 lang 可以用了，谢谢！

[ 本帖最后由 win_hate 于 2008-9-21 22:25 编辑 ]

MMMIX

原帖由 win_hate 于 2008-9-21 22:17 发表
svn check out 的版本(11826)，4.1.0.3

现在用 lang 可以用了，谢谢！

不客气

MMMIX

原帖由 win_hate 于 2008-9-21 10:15 发表
一个带平方优化的版本

这个你有没有做过性能测试？反正我的改进版我测了一下，反而没有改进之前的快 当然，算法本身没有问题，是实现不当造成的。

win_hate

n 比较小的时候用这种方法可能没什么好处。但用大一点的 n，比如 1000， 在我这里测，差别很大。你看看我的截图：

win_hate

学习 Haskell，你的第一个代码我能看明白，第二个就看不懂了。帮我解释一下吧

1. 
   
2. sieve :: [Integer] -> [Integer]
   
3. sieve (x:xs) = x : sieve (xs' ++ xs''')            
   
4.              where
   
5.                 (xs', xs'') = break (>= x*x) xs      
   
6.                 xs''' = filter (\y -> y `mod` x /= 0) xs''
   
7. 
   
8. primes = 2 : sieve [3,5..]
   

复制代码

• xs'++xs'''，中的 ++ 是什么意思？
  
• (xs', xs'') = break (>= x*x) xs，这里是给 xs' 和 xs'' 绑定值吗？如果是，分别绑定了什么？
  

MMMIX

原帖由 win_hate 于 2008-9-24 16:20 发表
学习 Haskell，你的第一个代码我能看明白，第二个就看不懂了。帮我解释一下吧


xs'++xs'''，中的 ++ 是什么意思？

++ 是 list append 操作，例如 "abc" ++ "def" => "abcdef"

在 Haskell 中，"abc" 是 ['a', 'b', 'c'] 的缩写

(xs', xs'') = break (>= x*x) xs，这里是给 xs' 和 xs'' 绑定值吗？如果是，分别绑定了什么？

是给 xs' 和 xs'' 绑定值(通过 pattern matching)。break p xs 会将 xs 从不满足 p 的那一点分成两部分，分别绑定到 xs' 和 xs''，例如
> break (> 3) [1,2,4,1,5]
([1,2], [4,1,5])