F# sequence operations majorly slow compared to List?
f#, list, sequence
Solution
Seq.skip is an anti-pattern. Use LazyList from the F# PowerPack, or use enumerators (GetEnumerator...MoveNext...Current) to efficiently traverse a Seq. See other similar Q&A.
Problem
Used F# List and Seq to merge two sorted lists/sequences. The values are obtained by reading in two files from secondary memory - the results of the file reads are stored in two sequences. Assuming integers are stored for testing purposes, now trying to merge these to print out a sorted series using this code: ``` let rec printSortedSeq l1 l2 = match ( l1, l2) with | l1,l2 when Seq.isEmpty l1 && Seq.isEmpty l2 -> printfn ""; | l1, l2 when Seq.isEmpty l1 -> printf "%d " (Seq.head l2); printSortedSeq l1 (Seq.skip 1 l2); | l1, l2 when Seq.isEmpty l2-> printf "%d " (Seq.head l1); printSortedSeq (Seq.skip 1 l1) []; | l1,l2 -> if Seq.head l1 = Seq.head l2 then printf "%d " (Seq.head l1); printSortedSeq (Seq.skip 1 l1) (Seq.skip 1 l2); elif Seq.head l1 < Seq.head l2 then printf "%d " (Seq.head l1); printSortedSeq (Seq.skip 1 l1) (Seq.skip 1 l2); else printf "%d " (Seq.head l2); printSortedSeq (Seq.skip 1 l1) (Seq.skip 1 l2); ``` The code was originally written to merge two sorted lists: ``` let rec printSortedList l1 l2 = match ( l1, l2) with | h1 :: t1 , h2 :: t2 -> if h1 = h2 then printf "%d " h1; printSortedList t1 t2; elif h1 < h2 then printf "%d " h1; printSortedList t1 l2; else printf "%d " h2; printSortedList l1 t2; | [] , h2 :: t2 -> printf "%d " h2; printSortedList [] t2; | h1 :: t1, [] -> printf "%d " h1; printSortedList t1 []; | [], [] -> printfn""; ``` The performance of using them compared hugely in favor of Lists. I'm giving the timing results after doing #time;; in the FSI on some trial inputs. ``` let x = [0..2..500]; let y = [1..2..100]; let a = {0..2..500} let b = {1..2..100} ``` printSortedList x y;; Real: 00:00:00.012, CPU: 00:00:00.015 printSortedSeq a b;; Real: 00:00:00.504, CPU: 00:00:00.515 The question is - is there any way to make things faster using sequences? Because though lists are much faster, since the files that will provide the input are very large ( > 2 GB) they won't fit in main memory and so I am reading in the values from file as a lazy sequence. Converting those to lists before merging kinda defeats the whole purpose.