I think the best way to test the performance is to use a benchmarking library such as criterion (http://www.serpentine.com/criterion/) import Criterion.Main import Data.List (inits,tails) splits1, splits2, splits3 :: [a] -> [([a],[a])] splits1 xs = zip (inits xs) (tails xs) splits2 [] = [([],[])] splits2 xs@(x:xs') = ([],xs) : [(x:as,bs) | (as,bs) <- splits2 xs'] splits3 = go id where go prefix xs = (prefix [],xs) : case xs of x:xs -> go (prefix . (x :)) xs [] -> [] main = defaultMain [ bench "splits1" $ nf splits1 input , bench "splits2" $ nf splits2 input , bench "splits3" $ nf splits3 input ] where input :: [Int] input = [1..1000] It gives the following results on my computer: benchmarking splits1 time 4.693 ms (4.625 ms .. 4.752 ms) 0.999 R² (0.998 R² .. 0.999 R²) mean 4.725 ms (4.694 ms .. 4.758 ms) std dev 97.37 μs (77.95 μs .. 123.3 μs) benchmarking splits2 time 12.10 ms (11.96 ms .. 12.25 ms) 0.999 R² (0.999 R² .. 1.000 R²) mean 12.08 ms (12.03 ms .. 12.14 ms) std dev 149.7 μs (110.0 μs .. 199.1 μs) benchmarking splits3 time 4.110 ms (4.025 ms .. 4.187 ms) 0.997 R² (0.996 R² .. 0.999 R²) mean 4.124 ms (4.081 ms .. 4.177 ms) std dev 147.6 μs (115.6 μs .. 238.5 μs) variance introduced by outliers: 17% (moderately inflated) On 01-08-2019 04:45, Todd Wilson wrote:
Dear Cafe:
I'm getting to the point in my Haskell learning curve where I'm getting more interested in the fine points of programming for performance and would be grateful for some ideas of the tools and options available for exploring this. To make this concrete, let me give a simple example. Here are two different ways of coding the same list-splitting function:
import Data.List (inits,tails) splits1, splits2 :: [a] -> [([a],[a])] splits1 xs = zip (inits xs) (tails xs) splits2 [] = [([],[])] splits2 xs@(x:xs') = ([],xs) : [(x:as,bs) | (as,bs) <- splits2 xs']
For example, splits1 [1,2,3] is [([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])].
How do these functions compare in their actual time and space usage? It seems that, asymptotically, tails is O(n) while inits is O(n^2) in both time and space (when fully evaluated), and splits2 is also O(n^2), but how would I go about comparing them in actual usage to get a more precise comparison? What profiling or run-time statistics could I gather to make a decision about which one to use in a situation where performance mattered (assuming for the sake of discussion that such a situation existed for this simple example)? And, out of curiosity, is there an even more efficient way to code this function? Thanks,
Todd Wilson _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.