holy frijoles: constant factors matter.
Cale Gibbard
cgibbard at gmail.com
Thu Oct 13 05:28:05 EDT 2005
On 13/10/05, Ross Paterson <ross at soi.city.ac.uk> wrote:
> On Wed, Oct 12, 2005 at 07:22:07PM -0700, John Meacham wrote:
> > these differences in jhc runtimes were the result of a single line change.
> >
> > < total time = 44.32 secs (2216 ticks @ 20 ms)
> > < total alloc = 9,372,965,276 bytes (excludes profiling overheads)
> > ---
> > > total time = 36.74 secs (1837 ticks @ 20 ms)
> > > total alloc = 6,621,233,076 bytes (excludes profiling overheads)
> >
> > the odd thing is, the change should not have changed the order of the
> > algorithm at all. the change was (effectivly)
> >
> > Map.fromAscList . map f . Map.toAscList
> > being changed to
> > Map.map f
>
> Note that fromAscList is misnamed: it actually assumes a non-descending
> list and checks for duplicates. It's fromDistinctAscList that assumes
> an ascending list.
>
> > in any case, the reason I mention it is because if there were routines
> > for converting between Set and Map that preserved the binary tree
> > structure, I think their use could dramatically speed up many routines.
>
> The old Data.Set was a wrapper around the finite map type, which made
> that sort of thing easy to do. The new one is a specialized copy
> for efficiency, at the cost of extra code. It's possible, but messy.
> Will keysSet and setToMap be enough, or will we want intersection and
> two versions each of difference and isSubmapOf too?
>
> > Map already has a keysSet, but it does the same inefficient thing
> > building an intermediate list. all that is needed is a
> >
> > setToMap :: (a -> b) -> Set a -> Map a b
>
> This would be a useful abstraction even with the simplistic definition
>
> setToMap :: (a -> b) -> Set a -> Map a b
> setToMap f s =
> Data.Map.fromDistinctAscList [(k, f k) | k <- Data.Set.toAscList s]
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
I'd just like to mention that I proposed these a while back :)
(The post was titled "Data.Map, Data.Set working together")
Here are some things which I'd like to see:
Restrict a function to a finite map: restrict :: (Ord a) => (a -> b)
-> (Set a) -> (Map a b)
Restrict one map to another: restrictMap :: (Ord a) => (Map a b) ->
(Set a) -> (Map a b)
(maybe a typeclass for the above two?)
Domain of a map: domain :: (Ord a) => (Map a b) -> (Set a)
Range of a map: range :: (Ord a, Ord b) => (Map a b) -> (Set b)
It would also be nice to have things like
join :: (Ord a) => Set (Set a) -> Set a
(this is union, will correspond to monadic join once that's possible :)
and powerSet :: Set a -> Set (Set a).
- Cale
More information about the Libraries
mailing list