Drawing Blanks

Premature Optimization is a Prerequisite for Success

Generating powerset: beauty vs. speed

leave a comment »

Consider the following “beautiful” implementation:

        public IEnumerable<IEnumerable<T>> GetPowerset<T>(IEnumerable<T> set)
        {
            if (!set.Any())
                yield break;
            T head = set.First();
            var tail = set.Skip(1);
            bool isTailEmpty = !tail.Any();
            yield return Singlet(head);
            if (!isTailEmpty)
            {
                var ps = GetPowerset(tail);
                foreach (var subset in ps)
                {
                    yield return subset;
                    yield return subset.Concat(Singlet(head));
                }
            }
        }

        IEnumerable<T> Singlet<T>(T x)
        {
            yield return x;
        }

(BTW, I know that my Singlet can be written as Enumerable.Repeat(x, 1), but I think the word “singlet” loks more beautiful 😉

Okay, this algorithm has a problem: it is slow.  The “binary counter” algorithm below works much, much faster:

        public IEnumerable<IEnumerable<T>> GetPowerset<T>(List<T> set)
        {           
            byte[] counter = new byte[set.Count];

            for (int count = 0; count < (1 << set.Count) - 1; count++)
            {
                bool carry = true;
                int digit = 0;
                while (carry)
                {
                    if (counter[digit] == 0)
                    {
                        counter[digit] = 1;
                        carry = false;
                    }
                    else
                    {
                        counter[digit] = 0;
                        carry = true;
                    }
                    digit++;
                }
                var q = from i in Enumerable.Range(0, set.Count) where counter[i] == 1 select set[i];
                yield return q;               
            }
        }

(See, it still uses Linq, so it’s not completely ugly 😉

What’s funny is that I ended up throwing away both of these algorithms. I initially attempted to implement subanagram generation by using powersets, but the speed was unacceptable regardless of the implementation, and I soon discovered that there is a much faster approach. So what I described above was real Premature Optimization. But was it Evil? Not at all. First of all, it could have potentially solved the problem. And even though it didn’t, it indicated that some other optimizations needed to be done

Advertisements

Written by bbzippo

11/10/2009 at 8:20 am

Posted in programming

Tagged with

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: