On Sun, Jun 17, 2012 at 2:26 AM, Tillmann Rendel <ren...@informatik.uni-marburg.de> wrote: > Hi, > > > David Menendez wrote: >> >> As you noticed, you can get somewhat better performance by using the >> combinators that convert to S.Set internally, because they eliminate >> redundant computations later on. > > "Somewhat better"? My example was three times faster, and I guess that the > fast variant is O(n) and the slow variant is O(n²). So I expect that for > some applications, the Set interface is more than fast enough and the > MonadPlus-interface is much too slow.
Yes, that should have been "significantly better". >>> (Why is unioned faster then numbers? Is union doing some rebalancing? Can >>> I >>> trigger that effect directly?) >> >> >> It's because mplus a b>>= f turns into mplus (a>>= f) (b>>= f), >> whereas unioned takes the union before calling f. > > Here, you compare mplused to unioned, but in the parentheses, I asked about > numbers and unioned (from my last email). You're right. That may have been caused by the time to compute numbers itself; I saw that numbers `times` numbers was faster than unioned `times` unioned the second time I ran it. Additionally, I haven't done any serious performance testing, but there also seems to be a speedup when the following lines are added to run: run (Bind (Plus (Prim sa) mb) f) = run (Bind (S.union sa (run mb)) f) run (Bind (Plus ma (Prim sb)) f) = run (Bind (S.union (run ma) sb) f) -- Dave Menendez <d...@zednenem.com> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
