Haskell merge sort inversions
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
2
down vote
favorite
I'm working on a task from the one of Coursera programming courses. The purpose is to estimate the amount of inversions that are required to sort the array of numbers.
Also I'm trying to learn some Haskell basics, here is my solution:
fsthalf :: [a] -> [a]
fsthalf xs = take (length xs `div` 2) xs
sndhalf :: [a] -> [a]
sndhalf xs = drop (length xs `div` 2) xs
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
union (a, ac) (b, bc) = (a++b, ac+bc)
merge :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
merge (, ac) (bs, bc) = (bs, ac + bc)
merge (as, ac) (, bc) = (as, ac + bc)
merge (a:as, ac) (b:bs, bc)
| a <= b = ([a], 0) `union` merge (as, ac) (b:bs, bc)
| otherwise = ([b], length(a:as)) `union` merge (a:as, ac) (bs, bc)
mergeSort :: ([Int], Int) -> ([Int], Int)
mergeSort (s, c)
| length s `elem` [0, 1] = (s, c)
| otherwise = merge (mergeSort (fsthalf s, c)) (mergeSort (sndhalf s, c))
main :: IO()
main = do
_ <- readLn :: IO Int
rawValues <- getLine
let intValues = map read $ words rawValues :: [Int]
print $ snd $ mergeSort (intValues, 0)
It seems to work properly, but exceeds time limits. It takes from 9 to 10 seconds to sort the longest possible list of integers (100000 values), while the limit is 6 seconds. Could anyone please point out some possible optimizations for this solution.
haskell sorting
add a comment |Â
up vote
2
down vote
favorite
I'm working on a task from the one of Coursera programming courses. The purpose is to estimate the amount of inversions that are required to sort the array of numbers.
Also I'm trying to learn some Haskell basics, here is my solution:
fsthalf :: [a] -> [a]
fsthalf xs = take (length xs `div` 2) xs
sndhalf :: [a] -> [a]
sndhalf xs = drop (length xs `div` 2) xs
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
union (a, ac) (b, bc) = (a++b, ac+bc)
merge :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
merge (, ac) (bs, bc) = (bs, ac + bc)
merge (as, ac) (, bc) = (as, ac + bc)
merge (a:as, ac) (b:bs, bc)
| a <= b = ([a], 0) `union` merge (as, ac) (b:bs, bc)
| otherwise = ([b], length(a:as)) `union` merge (a:as, ac) (bs, bc)
mergeSort :: ([Int], Int) -> ([Int], Int)
mergeSort (s, c)
| length s `elem` [0, 1] = (s, c)
| otherwise = merge (mergeSort (fsthalf s, c)) (mergeSort (sndhalf s, c))
main :: IO()
main = do
_ <- readLn :: IO Int
rawValues <- getLine
let intValues = map read $ words rawValues :: [Int]
print $ snd $ mergeSort (intValues, 0)
It seems to work properly, but exceeds time limits. It takes from 9 to 10 seconds to sort the longest possible list of integers (100000 values), while the limit is 6 seconds. Could anyone please point out some possible optimizations for this solution.
haskell sorting
Please don't use images of text. They're not accessible. Instead, type in the text itself.
â dfeuer
Feb 25 at 3:21
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm working on a task from the one of Coursera programming courses. The purpose is to estimate the amount of inversions that are required to sort the array of numbers.
Also I'm trying to learn some Haskell basics, here is my solution:
fsthalf :: [a] -> [a]
fsthalf xs = take (length xs `div` 2) xs
sndhalf :: [a] -> [a]
sndhalf xs = drop (length xs `div` 2) xs
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
union (a, ac) (b, bc) = (a++b, ac+bc)
merge :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
merge (, ac) (bs, bc) = (bs, ac + bc)
merge (as, ac) (, bc) = (as, ac + bc)
merge (a:as, ac) (b:bs, bc)
| a <= b = ([a], 0) `union` merge (as, ac) (b:bs, bc)
| otherwise = ([b], length(a:as)) `union` merge (a:as, ac) (bs, bc)
mergeSort :: ([Int], Int) -> ([Int], Int)
mergeSort (s, c)
| length s `elem` [0, 1] = (s, c)
| otherwise = merge (mergeSort (fsthalf s, c)) (mergeSort (sndhalf s, c))
main :: IO()
main = do
_ <- readLn :: IO Int
rawValues <- getLine
let intValues = map read $ words rawValues :: [Int]
print $ snd $ mergeSort (intValues, 0)
It seems to work properly, but exceeds time limits. It takes from 9 to 10 seconds to sort the longest possible list of integers (100000 values), while the limit is 6 seconds. Could anyone please point out some possible optimizations for this solution.
haskell sorting
I'm working on a task from the one of Coursera programming courses. The purpose is to estimate the amount of inversions that are required to sort the array of numbers.
Also I'm trying to learn some Haskell basics, here is my solution:
fsthalf :: [a] -> [a]
fsthalf xs = take (length xs `div` 2) xs
sndhalf :: [a] -> [a]
sndhalf xs = drop (length xs `div` 2) xs
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
union (a, ac) (b, bc) = (a++b, ac+bc)
merge :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
merge (, ac) (bs, bc) = (bs, ac + bc)
merge (as, ac) (, bc) = (as, ac + bc)
merge (a:as, ac) (b:bs, bc)
| a <= b = ([a], 0) `union` merge (as, ac) (b:bs, bc)
| otherwise = ([b], length(a:as)) `union` merge (a:as, ac) (bs, bc)
mergeSort :: ([Int], Int) -> ([Int], Int)
mergeSort (s, c)
| length s `elem` [0, 1] = (s, c)
| otherwise = merge (mergeSort (fsthalf s, c)) (mergeSort (sndhalf s, c))
main :: IO()
main = do
_ <- readLn :: IO Int
rawValues <- getLine
let intValues = map read $ words rawValues :: [Int]
print $ snd $ mergeSort (intValues, 0)
It seems to work properly, but exceeds time limits. It takes from 9 to 10 seconds to sort the longest possible list of integers (100000 values), while the limit is 6 seconds. Could anyone please point out some possible optimizations for this solution.
haskell sorting
asked Jan 13 at 16:38
Vitaly Isaev
1113
1113
Please don't use images of text. They're not accessible. Instead, type in the text itself.
â dfeuer
Feb 25 at 3:21
add a comment |Â
Please don't use images of text. They're not accessible. Instead, type in the text itself.
â dfeuer
Feb 25 at 3:21
Please don't use images of text. They're not accessible. Instead, type in the text itself.
â dfeuer
Feb 25 at 3:21
Please don't use images of text. They're not accessible. Instead, type in the text itself.
â dfeuer
Feb 25 at 3:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
General review tips:
It'd be better to document your code. In particular functions like
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
need documentation - it's not clear which
Int
has what purpose at all without examining the source.Some of your functions are polymorphic (
sndhalf
), others not. Why? I'd suggest to have all types consistent. Either just sortInt
s, or make the types as generic as possible, for exampleunion :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
Notice how this generality also makes the types easier to understand.
I'd suggest to wrap list + its inversion count into a
newtype
such as:newtype List a = List [a] Int
This makes the code better structured, and also allows you to use smart
constructors, if you decide
so.- Investigate Haskell's
sort
for inspiration.
Now specific to performance:
- For each pass you traverse the list several times,
which can impact the performance considerably. In particular: take
andlength
in fsthalf
, the same in sndhalf
. Also length
in mergeSort
. This
makes it 5 traversals before the merging pass. I'd try to reduce this number.
Matching on
length
is wasteful, if you need just to distinguish if it's 0 or 1, you traverse the whole list needlessly:mergeSort (s, c) | length s `elem` [0, 1] = (s, c)
Instead:
mergeSort (, _) = (, 0)
mergeSort (xs@[_], _) = (xs, 1)
...Make sure you're compiling with
-O
.
I hope this helps!
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
General review tips:
It'd be better to document your code. In particular functions like
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
need documentation - it's not clear which
Int
has what purpose at all without examining the source.Some of your functions are polymorphic (
sndhalf
), others not. Why? I'd suggest to have all types consistent. Either just sortInt
s, or make the types as generic as possible, for exampleunion :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
Notice how this generality also makes the types easier to understand.
I'd suggest to wrap list + its inversion count into a
newtype
such as:newtype List a = List [a] Int
This makes the code better structured, and also allows you to use smart
constructors, if you decide
so.- Investigate Haskell's
sort
for inspiration.
Now specific to performance:
- For each pass you traverse the list several times,
which can impact the performance considerably. In particular: take
andlength
in fsthalf
, the same in sndhalf
. Also length
in mergeSort
. This
makes it 5 traversals before the merging pass. I'd try to reduce this number.
Matching on
length
is wasteful, if you need just to distinguish if it's 0 or 1, you traverse the whole list needlessly:mergeSort (s, c) | length s `elem` [0, 1] = (s, c)
Instead:
mergeSort (, _) = (, 0)
mergeSort (xs@[_], _) = (xs, 1)
...Make sure you're compiling with
-O
.
I hope this helps!
add a comment |Â
up vote
4
down vote
General review tips:
It'd be better to document your code. In particular functions like
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
need documentation - it's not clear which
Int
has what purpose at all without examining the source.Some of your functions are polymorphic (
sndhalf
), others not. Why? I'd suggest to have all types consistent. Either just sortInt
s, or make the types as generic as possible, for exampleunion :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
Notice how this generality also makes the types easier to understand.
I'd suggest to wrap list + its inversion count into a
newtype
such as:newtype List a = List [a] Int
This makes the code better structured, and also allows you to use smart
constructors, if you decide
so.- Investigate Haskell's
sort
for inspiration.
Now specific to performance:
- For each pass you traverse the list several times,
which can impact the performance considerably. In particular: take
andlength
in fsthalf
, the same in sndhalf
. Also length
in mergeSort
. This
makes it 5 traversals before the merging pass. I'd try to reduce this number.
Matching on
length
is wasteful, if you need just to distinguish if it's 0 or 1, you traverse the whole list needlessly:mergeSort (s, c) | length s `elem` [0, 1] = (s, c)
Instead:
mergeSort (, _) = (, 0)
mergeSort (xs@[_], _) = (xs, 1)
...Make sure you're compiling with
-O
.
I hope this helps!
add a comment |Â
up vote
4
down vote
up vote
4
down vote
General review tips:
It'd be better to document your code. In particular functions like
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
need documentation - it's not clear which
Int
has what purpose at all without examining the source.Some of your functions are polymorphic (
sndhalf
), others not. Why? I'd suggest to have all types consistent. Either just sortInt
s, or make the types as generic as possible, for exampleunion :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
Notice how this generality also makes the types easier to understand.
I'd suggest to wrap list + its inversion count into a
newtype
such as:newtype List a = List [a] Int
This makes the code better structured, and also allows you to use smart
constructors, if you decide
so.- Investigate Haskell's
sort
for inspiration.
Now specific to performance:
- For each pass you traverse the list several times,
which can impact the performance considerably. In particular: take
andlength
in fsthalf
, the same in sndhalf
. Also length
in mergeSort
. This
makes it 5 traversals before the merging pass. I'd try to reduce this number.
Matching on
length
is wasteful, if you need just to distinguish if it's 0 or 1, you traverse the whole list needlessly:mergeSort (s, c) | length s `elem` [0, 1] = (s, c)
Instead:
mergeSort (, _) = (, 0)
mergeSort (xs@[_], _) = (xs, 1)
...Make sure you're compiling with
-O
.
I hope this helps!
General review tips:
It'd be better to document your code. In particular functions like
union :: ([Int], Int) -> ([Int], Int) -> ([Int], Int)
need documentation - it's not clear which
Int
has what purpose at all without examining the source.Some of your functions are polymorphic (
sndhalf
), others not. Why? I'd suggest to have all types consistent. Either just sortInt
s, or make the types as generic as possible, for exampleunion :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
Notice how this generality also makes the types easier to understand.
I'd suggest to wrap list + its inversion count into a
newtype
such as:newtype List a = List [a] Int
This makes the code better structured, and also allows you to use smart
constructors, if you decide
so.- Investigate Haskell's
sort
for inspiration.
Now specific to performance:
- For each pass you traverse the list several times,
which can impact the performance considerably. In particular: take
andlength
in fsthalf
, the same in sndhalf
. Also length
in mergeSort
. This
makes it 5 traversals before the merging pass. I'd try to reduce this number.
Matching on
length
is wasteful, if you need just to distinguish if it's 0 or 1, you traverse the whole list needlessly:mergeSort (s, c) | length s `elem` [0, 1] = (s, c)
Instead:
mergeSort (, _) = (, 0)
mergeSort (xs@[_], _) = (xs, 1)
...Make sure you're compiling with
-O
.
I hope this helps!
edited Jan 14 at 18:09
answered Jan 14 at 17:48
Petr Pudlák
2,755931
2,755931
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f185046%2fhaskell-merge-sort-inversions%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Please don't use images of text. They're not accessible. Instead, type in the text itself.
â dfeuer
Feb 25 at 3:21