Haskell merge sort inversions

The name of the pictureThe name of the pictureThe name of the pictureClash 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.



enter image description hereenter image description hereenter image description here



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.







share|improve this question



















  • Please don't use images of text. They're not accessible. Instead, type in the text itself.
    – dfeuer
    Feb 25 at 3:21
















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.



enter image description hereenter image description hereenter image description here



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.







share|improve this question



















  • Please don't use images of text. They're not accessible. Instead, type in the text itself.
    – dfeuer
    Feb 25 at 3:21












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.



enter image description hereenter image description hereenter image description here



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.







share|improve this question











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.



enter image description hereenter image description hereenter image description here



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.









share|improve this question










share|improve this question




share|improve this question









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
















  • 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










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 sort Ints, or make the types as generic as possible, for example



    union :: (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 and
length 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!






share|improve this answer























    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    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






























    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 sort Ints, or make the types as generic as possible, for example



      union :: (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 and
    length 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!






    share|improve this answer



























      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 sort Ints, or make the types as generic as possible, for example



        union :: (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 and
      length 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!






      share|improve this answer

























        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 sort Ints, or make the types as generic as possible, for example



          union :: (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 and
        length 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!






        share|improve this answer















        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 sort Ints, or make the types as generic as possible, for example



          union :: (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 and
        length 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!







        share|improve this answer















        share|improve this answer



        share|improve this answer








        edited Jan 14 at 18:09


























        answered Jan 14 at 17:48









        Petr Pudlák

        2,755931




        2,755931






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            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













































































            Popular posts from this blog

            Chat program with C++ and SFML

            Function to Return a JSON Like Objects Using VBA Collections and Arrays

            Will my employers contract hold up in court?