How can I optimize a functional mergesort for large lists

user_12868928 0
Viewed 162

I am trying to learn functional programming and algorithms at the same time, and Ive implemented a merge sort in Haskell. Then I converted the style into python and run a test on a learning platform, but I get return that it takes too long time to sort a list on a 1000 integers.

Is there a way i can optimize my python code and still keep my functional style or do I have to solve the problem iteratively?

Thanks in advance.

So here is the code I made in Haskell first.

merge :: Ord a => [a] -> [a] -> [a]
merge [] xs = xs
merge ys [] = ys
merge (x:xs) (y:ys)
  | (x <= y) = x : (merge xs (y:ys))
  | otherwise = y : (merge (x:xs) ys)

halve :: [a] -> ([a] , [a])
halve [x] = ([x], [])
halve xs = (take n xs , drop n xs)
        where n = length xs `div` 2

msort :: Ord a => [a] -> [a]
msort [x] = [x]
msort [] = []
msort xs = merge (msort n) (msort m)
    where (n,m) = halve xs

Then I made this code in python based on the Haskell style.

import sys
sys.setrecursionlimit(1002) #This is because the recursion will go 1002 times deep when I have a list on 1000 numbers.
    
def merge(xs,ys):
    if len(xs) == 0:
        return ys
    elif len(ys) == 0:
        return xs
    else:
        if xs[0] <= ys[0]:
            return [xs[0]] + merge(xs[1:], ys)
        else:
            return [ys[0]] + merge(xs, ys[1:])

def halve(xs):
    return (xs[:len(xs)//2],xs[len(xs)//2:])

def msort(xss):
    if len(xss) <= 1:
        return xss
    else:
        xs,ys = halve(xss)
        return merge(msort(xs), msort(ys))

Is there a smarter way I can optimize the python version and still have a functional style?

mergesort recursion python haskell performance
2 Answers

I am no Haskell expert, so I might be missing something. Here's my best gamble:

Haskell list's are not state-aware. One implication of that is that lists can be shared. That make the action of halving leaner on memory allocations - To produce a 'drop n xs' you only have to allocate one list node (or whatever they are called in Haskell) and point it to the list element in the (n 'div' 2) + 1 node on the pre-halved list. Note that 'take' is not able to do this little trick - it is not allowed to change a state of any node in the list, and hence it has to allocate new node object with equal values to the first n div 2 elements in the pre-halved list.

Now look at the python equivalent of that function - to halve the list, you use the list slicing:

def halve(xs):
    return (xs[:len(xs)//2],xs[len(xs)//2:])

Here you allocate two lists instead of one - in every level of the recursion tree! (I am also pretty sure that a list is a much more complex thing in python than the Haskell list, so probably allocation is slower, too)

What I would do:

  1. Check my gamble - use the time module to see if your code spends too long allocating those lists, compared to the overall running time.

  2. In case my gamble proved correct - avoid those allocations. A (Not very elegant, but probably fast) way to work around it - Pass a list, alongside with indices that indicate where each halve begin and where it ends. Work with offsets instead of allocating a new list each time. (EDIT:) You can avoid similar allocations as well - whenever you want to slice, pass an index to the begin\end of the new list.

  3. And a last word - one of the requirements you've mentioned is keeping the functional approach. One can interpret that as keeping your code side-effect free. To do so, I'd define an output list, and store the elements you merge in it. Combined with the index approach, that will not change the state of the input list, and will produce a new sorted output list.

EDIT: Another thing worth mentioning here: python lists are not singly linked-list, like Haskell lists. They are a data structure more commonly called Dynamic Arrays. This means that stuff like slicing, deleting an object from the middle of the list, etc. is expensive, since it has implication on ALL objects in the array. On the other hand, you are allowed to access an object at the i-th index in O(1). You should keep that in mind, it is closely related to the problem you came Up with.

user_119261700

Haskell lists are lazy. [x] ++ xs first produces the x, and then it produces all the elements in xs.

In e.g. Lisp the lists are singly-linked lists and appending them copies the first list, so prepending a singleton is an O(1) operation.

In Python though the appending copies the second list (as confirmed by @chepner in the comments), i.e. [x] + xs will copy the whole list xs and thus is an O(n) operation (where n is the length of xs).

This means that both your [xs[0]] + merge(xs[1:], ys) and [ys[0]] + merge(xs, ys[1:]) lead to quadratic behavior which you observe as the dramatic slowdown you describe.

Python's equivalent to Haskell's lazy lists is not lists, it's generators, which produce their elements one by one on each yield. Thus the rewrite could look something like

def merge(xs,ys):
    if len(xs) == 0:
        return ys
    elif len(ys) == 0:
        return xs
    else:
        a = (x for x in xs)     # or maybe iter(xs)
        b = (y for y in ys)     # or maybe iter(ys)
        list( merge_gen(a,b))

Now what's left is to re-implement your merge logic as merge_gen which expects two generators (or should that be iterators? do find out) as its input and generates the ordered stream of elements which it gets by pulling them one by one from the two sources as needed. The resulting stream of elements is converted back to list, as expected by the function's caller. No redundant copying will be performed.

If I've made some obvious Python errors, please treat the above as a pseudocode.

Your other option is to pre-allocate a second list of the same length and copy the elements between the two lists back and forth while merging, using indices to reference the elements of the arrays and mutating the contents to store the results.

user_8498910
Related