Often when writing algorithms which involve set operations on small
enumerations, I start off using Data.Set. I soon find performance requires rewriting that code to use bitwise operations. I miss the nice interface of Data.Set and the type checking of using a proper data type. So, as an exercise in writing a library, I wrote out an implementation of bitwise set operations using the interface of Data.Set with a couple of extensions. It provides an abstract interface and type checking. Using GHC -O3, code compiles right down to the primitive bit-twiddling operators. My example program (a sudoku solver) runs several times faster. I'll be grateful for any feedback on this. Perhaps something like it would be useful included in the standard libraries. Cheers, David -------------------------------- David F. Place mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe EnumSet.hs (11K) Download Attachment |
David F. Place <d <at> vidplace.com> writes:
I'm currently writing and evolution to the standard collection package that can be found here: http://darcs.haskell.org/packages/collections/ We integrate your module there. What would you say? Cheers, JP. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Apr 3, 2006, at 10:02 AM, Jean-Philippe Bernardy wrote: > I'm currently writing and evolution to the standard collection > package that can > be found here: > > http://darcs.haskell.org/packages/collections/ > > We integrate your module there. What would you say? Sure. I'd be honored. -------------------------------- David F. Place mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by David Place
On Monday 03 April 2006 14:19, David F. Place wrote:
> Often when writing algorithms which involve set operations on small > enumerations, I start off using Data.Set. I soon find performance > requires rewriting that code to use bitwise operations. I miss the > nice interface of Data.Set and the type checking of using a proper > data type. > > So, as an exercise in writing a library, I wrote out an > implementation of bitwise set operations using the interface of > Data.Set with a couple of extensions. It provides an abstract > interface and type checking. Using GHC -O3, code compiles right down > to the primitive bit-twiddling operators. My example program (a > sudoku solver) runs several times faster. > > I'll be grateful for any feedback on this. Perhaps something like it > would be useful included in the standard libraries. I wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations? Ben _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote: > wondered about the Ord instance. Wouldn't it be faster to compare > (word-) representations? I thought about that some. Since the set representation is based completely on the enumeration, it would be possible for the type being collected to have a different implementation of Ord. For instance: newtype LowerCaseAlpha = LCA Char deriving (Eq, Show) instance Enum LowerCaseAlpha where fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a') toEnum x = LCA $ toEnum $ x + (fromEnum 'a') instance Ord LowerCaseAlpha where compare (LCA a) (LCA b) | a == b = EQ | a > b = LT | a < b = GT Perverted, but possible. -------------------------------- David F. Place mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 4/3/06, David F. Place <[hidden email]> wrote:
> > On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote: > > > wondered about the Ord instance. Wouldn't it be faster to compare > > (word-) representations? > > > I thought about that some. Since the set representation is based > completely on the enumeration, it would be possible for the type > being collected to have a different implementation of Ord. For > instance: > > newtype LowerCaseAlpha = LCA Char deriving (Eq, Show) > > instance Enum LowerCaseAlpha where > fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a') > toEnum x = LCA $ toEnum $ x + (fromEnum 'a') > > instance Ord LowerCaseAlpha where > compare (LCA a) (LCA b) > | a == b = EQ > | a > b = LT > | a < b = GT > > Perverted, but possible. I don't think there is a requirement for the Ord class to be equal to "compare a b = compare (toAscList a) (toAscList b)". I'd say it's safe to simply compare the bits representation. Besides, I've integrated your module to the package I'm busy setting up. http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs (I'm accepting patches -- most notably if someone wishes to complete the haddock documentation) FWIW, it passed the standard regression testsuite for Sets flawlessly. I'm thinking of removing the UniverseSet class though. It seems to me that Bounded serves the purpose just right. Cheers, JP. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Apr 3, 2006, at 5:38 PM, Jean-Philippe Bernardy wrote: > I don't think there is a requirement for the Ord class to be equal to > "compare a b = compare (toAscList a) (toAscList b)". I'd say it's safe > to simply compare the bits representation. Hmm. OK. > > Besides, I've integrated your module to the package I'm busy > setting up. > > http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs Cool. > > (I'm accepting patches -- most notably if someone wishes to complete > the haddock documentation) I'll look into it. > > FWIW, it passed the standard regression testsuite for Sets flawlessly. I do quality work. > > I'm thinking of removing the UniverseSet class though. It seems to me > that Bounded serves the purpose just right. Does that mean we lose the unary `complement` function? I am rather fond of that. -------------------------------- David F. Place mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |