I've gone ahead and made a patch, which is attached. I don't have
access to the full test suite, but it passes the QuickCheck test for
just the prop_Ordered property, which is no longer a tautology. Who
wrote that test anyway? :)
Scott
On Mon, May 19, 2008 at 5:43 PM, Scott Dillard
Hi,
It's always bugged me that IntSet.fromAscList is an alias for fromList, which is basically (foldr insert), even though a sorted list is (almost) already in tree order. Is there a reason for this? Or was it just that fromList is good enough? (which it is.)
Assuming the latter, and somewhat bored, I wrote a function to build an IntSet from sorted input in linear time. This goes in Data.IntSet.hs :
data Stack = Push {-# UNPACK #-} !Prefix !IntSet !Stack | Nada
fromAsc xs = make Nada xs where make stk [] = finish stk make Nada (z:zs) = make (Push z (Tip z) Nada) zs make stk@(Push _ y Nada) (z:zs) = make (Push z (Tip z) stk) zs make stk@(Push py y stk') zs@(z:zs') = make (Push z (Tip z) (reduce (branchMask py z) stk)) zs'
reduce _ stk@(Push _ x Nada) = stk reduce m stk@((Push px x (Push py y stk'))) = let !mxy = branchMask px py !pxy = mask px mxy in if shorter m mxy then reduce m (Push pxy (Bin pxy mxy y x) stk') else stk
finish Nada = Nil finish (Push _ x Nada) = x finish (Push px x (Push py y stk)) = finish (Push p (join px x py y) stk) where m = branchMask px py p = mask px m
Every trie node is allocated exactly once, and so the burden on the heap is significantly less, even if its only a little bit faster. I tested it by building a list from -n to n for big n, and computing the sum. It alloc's 50% less and the MUT time is like 40% less, but the GC time is more (why would that be?) so it runs in maybe 7/8ths the time, versus fromList.
I have another, prettier version that uses [] instead of this hacky Stack type, but its slower, breaking even with fromList on speed, still allocating much less.
Is this something you guys feel would be worth including? Should I make a proper patch? One could even use this to write an O(n) mapKeysMonotonic, bringing the IntMap and Map APIs further into alignment. Or is 8/7x speedup not worth the extra code weight?
Scott