Re: Re[4]: [Haskell-cafe] In-place modification

14 Jul 2007

      On 14/07/07, Hugh Perkins  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