external-sort 0.1 → 0.2

raw patch · 3 files changed

+71/−12 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• demo.hs +66/−9
• external-sort.cabal +4/−3
• src/Algorithms/ExternalSort.lhs +1/−0

@@ -1,17 +1,74 @@ {-# LANGUAGE PatternSignatures #-} import Algorithms.ExternalSort import Data.List--- fast +import System.IO+import System.Environment (getArgs)+import System.Time+import HSH --- this will take a while but should eventurally return the right answer-main  = do-  (res :: Int) <- return . last =<< externalSort bigList-  putStrLn . show $ res +-- to do: compare speed against unix sort util on a 10 million line file. --- pure, in-memory prelude sort will crash your computer-mainBadIdea  = putStrLn . show $ last $ sort bigList+-- pure in-memory prelude sort will crash your computer when the list gets over a million elements or so+-- externalsort caches the sublists used in the sort algorithm on your hard drive, so you can sort a much larger list. +{- +The behavior below was on a demo executable, compiled. (In ghci, even last on a 10 million element list+caused an out of memory error.) The test computer had 256M physical ram and was ulimited to 256M cache. -bigList :: [Int]-bigList = reverse [1..10^8]+*Main>:! ulimit -v+262144++For 10 million element list:+*Main> :! time ./demo preludesort 7+demo: out of memory (requested 1048576 bytes)+Command exited with non-zero status 1+4.88user 0.68system 0:21.11elapsed 26%CPU (0avgtext+0avgdata 0maxresident)k+0inputs+0outputs (0major+64817minor)pagefaults 0swaps+*Main> :! time ./demo externalsort 7+10000000+73.87user 1.96system 1:24.25elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k+792inputs+156280outputs (6major+16739minor)pagefaults 0swaps+./demo unixsort 7+wrote bigfile, time: Mon Oct 20 15:25:26 CEST 2008+demo: out of memory (requested 1048576 bytes)++For 100 million element list, external sort failed.+time ./demo externalsort 8+demo: out of memory (requested 1048576 bytes)++real	10m14.061s+user	8m26.712s+sys	0m11.793s+thartman@thartman-laptop:~/external-sort>ls -lh ExternalSort.bin+-rw-r--r-- 1 thartman thartman 764M Oct 20 15:50 ExternalSort.bin++The problem is not fitting a 10^8 element list in memory, the following works fine+ (when compiled, though not in ghci):+t = putStrLn . show . last $ [1..10^8::Int]++Maybe think about this more later.++-}++main = do+  [s,e] <- getArgs+  let exp = read e+  case s of+    "preludesort" -> sortwith exp $ return . sort+    "externalsort" -> sortwith exp externalSort+    "unixsort" -> unixsort exp+    _ -> let msg = "usage: ./demo preludesort 7 or ./demo externalsort 7 or ./demo unixsort 7 \+                    \(sort 10 million element list)" +         in  fail msg++sortwith exp s = putStrLn =<< return . show . last =<< s ([1..10^exp ::Int]) ++unixsort exp = do+  let fn = "bigfile"+  withFile fn AppendMode (\h -> (mapM_ (hPutStrLn h . show) ([1..10^exp::Int]) ) ) +  putStrLn . ( ("wrote " ++ fn ++ ", time: ") ++ ) . show =<< getClockTime+  run $ "time tail -n1 | sort " ++fn :: IO String+  return ()++t = putStrLn . show . last $ [1..10^8::Int]

@@ -1,14 +1,15 @@ Name:                external-sort-Version:             0.1+Version:             0.2 Synopsis:            Sort large arrays on your hard drive. Kind of like the unix util sort. Description:         Sort arrays too large to fit in ram, by using your hard drive. Category:            Algorithms License:             BSD3-Author:              Ben Midfield+Author:              Ben "Midfield" Lee  Maintainer:          thomashartman1 at gmail dot com -Stability:           ExperimentalCategory:            Other+Stability:           Experimental+Category:            Other Build-type:          Simple Cabal-version: >=1.2 

@@ -85,6 +85,7 @@ list of sorted blocks, and spool to disk, keeping track of offsets. We then read back the blocks (lazily!), and merge them. +> externalSort :: (Ord a, Bin.Binary a) => [a] -> IO [a] > externalSort [] = do return [] > externalSort l = do >   h <- openFile "ExternalSort.bin" WriteMode