The FASTEST subsets function [Was: Subsets of a list] - comp.lang.scheme

Message from discussion The FASTEST subsets function [Was: Subsets of a list]

Eli Barzilay

View profile

More options Jan 16 2002, 6:05 am

Newsgroups: comp.lang.scheme

From: Eli Barzilay <e...@barzilay.org>

Date: 16 Jan 2002 06:05:48 -0500

Local: Wed, Jan 16 2002 6:05 am

Subject: Re: The FASTEST subsets function [Was: Subsets of a list]

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

Doug Quale <qua...@charter.net> writes:
> [...] The lazy streams approach will give many the benefits of
> memoization while avoiding most of the disadvantages.

> Memoization pros

> - can be applied automatically without changing the naive
> implementation

> - memoized results can be saved across top level invocations of the
> function

Well, your implementation fails *both* of these, the second one is not
important, but I consider the first one very important.

> Memoization cons

> - not always faster

Of course you should know when to use it, but when you *do*, it's
better than changing the function with an explicit matrix or whatever.

> - doesn't work well if function arguments are complex (the required
> hash compare might be too slow)

Same as above -- the basic assumption is that an argument hash lookup
is much faster than the computation for that argument, so you should
know when to use it. (Also, know what hash to use, the subsets was
particularly easy since an eq? test is enough.)

> - usually implemented using imperative machinery under the hood
> (although the resulting memoized function has functional
> behavior)

Ah, but that's not a bad thing -- it's a good thing that you can throw
efficiency machinery on the underlying implementation and keep your
code functional -- this is exactly the advantage of memoization over
standard dynamic programming techniques. (The implementation of
Haskell is imperative too...)

> - can lead to horrendous space leaks in the memo tables; recovering
> this space might require manual control partly negating the first
> pro listed above

Either you know what you're doing (for example, have a wrapper that
uses a fresh table for every top level call), or you can simply use
weak pointers.

> In a lazy stream formulation, the nth element of the lazy stream
> will be a list of the subsets of cardinality n. [...]

That's one formulation, but it points to one thing which is nice when
you're lazy -- you never care to generalize your code making it do
more than you really need since redundant computations will not be
done... (My standard example is instead of finding *a* solution for
the n-queen problem, you find all of them and pull out the first.)

> As a small bonus We can easily use subsets_stream to implement the
> powerset function:

> powerset s = concat (takeWhile (not . null) (subsets s))

The funny thing is that this powerset is much simpler in any case...
(Probably one line in Haskell)

> (define (subsets s n)
> (stream-ref (subsets-stream s) n))
> [...]

I've added this to my thing, called `ssubsets' (the last one).

http://sardine.cs.columbia.edu:8080/subsets/

--
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:
http://www.barzilay.org/ Maze is Life!

Reply to author Forward