On 14/07/07, Hugh Perkins <[EMAIL PROTECTED]> wrote:
As I say, I'm not a Haskell expert, so feel free to provide a better implementation.
It's not really about providing a "better implementation" as that would imply that the algorithms are the same, which they are not. You're comparing two quite different algorithms (see the paper to which you've already been pointed). You need to specify what you actually want to compare. Maybe you need to write a C# version of the Haskell version? using System; using System.Collections.Generic; namespace ConsoleApplication1 { class Program { static IEnumerable<int> FromTo(int from, int to) { for (int i = from; i <= to; ++i) { yield return i; } } static IEnumerable<int> Drop( int x, IEnumerable<int> list ) { IEnumerator<int> it = list.GetEnumerator(); for (int i = 0; i < x; ++i) { if (!it.MoveNext()) { yield break; } } while ( it.MoveNext() ) { yield return it.Current; } } static IEnumerable<int> FilterDivisible(int x, IEnumerable<int> list) { foreach (int i in list) { if (i % x != 0) { yield return i; } } } static IEnumerable<int> Sieve(IEnumerable<int> list) { IEnumerator<int> it = list.GetEnumerator(); if (!it.MoveNext()) { yield break; } int p = it.Current; yield return p; foreach (int i in Sieve( FilterDivisible( p, Drop( 1, list ) ) ) ) { yield return i; } } static IEnumerable<int> Primes( int max ) { return Sieve( FromTo(2, max) ); } static int MaxPrime( int max ) { int count = 0; foreach (int i in Primes(max)) { ++count; } return count; } static void Main(string[] args) { Console.WriteLine("Count {0}", MaxPrime(17984)); Console.ReadLine(); } } } And yes, this one uses lazy streams just like the Haskell version, and it also uses the same algorithm so it should be a much more fair comparison. I gave up waiting for this one to terminate on large inputs, btw. :-) So yeah, apples to apples, the difference is hardly ordes of magnitude. But when you construct a micro-benchmark where you write one of the version in a way which essentially maps directly to hardware, you're going to see that version be a lot faster. If you actually *use* the languages a bit more fairly (e.g. use lazy streams in C#, since you used them in Haskell -- or by all means, write a Haskell version using unboxed ST arrays) you'll see something a bit more useful. And that's if you manage to use the same algorithm for both languages, of course. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe