HiveBrain v1.2.0
Get Started
← Back to all entries
snippetpythonMinor

Parallel quicksort algorithm taking way too long

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
waylongtooquicksortalgorithmparalleltaking

Problem

Below is a Python implementation of the quicksort algorithm using parallelism. It takes about 1 second per every 10 items in the list, which is hilariously unacceptable. Why is it so slow?

from multiprocessing import *

def quicksort(lyst, connection=None):
    if len(lyst) > 1:
        pivot = lyst.pop(len(lyst)-1)
        wall = 0
        for i in range(len(lyst)):
            if lyst[i] <= pivot:
                lyst[wall], lyst[i] = lyst[i], lyst[wall]
                wall += 1
        receiveLeft, sendLeft = Pipe()
        receiveRight, sendRight = Pipe()
        Process(target=quicksort, args=(lyst[:wall], sendLeft)).start()
        Process(target=quicksort, args=(lyst[wall:], sendRight)).start()
        lyst = receiveLeft.recv() + [pivot] + receiveRight.recv()
    if connection:
        connection.send(lyst)
        connection.close()
    return lyst

if __name__ == '__main__':
    quicksort([8,4,6,9,1,3,10,2,7,5])


EDIT
Thanks for the responses. As it turns out, switching to Threads and limiting the number of them I was spawning sped things up. However, my linear version of the algorithm still performed better.

Solution

The problem seems to be the fact that you are not dealing with threads (as you should), but rather entire processes (which is more computationally demanding). Refer to this page for details on how to spawn threads.

Also, as a side node, it makes no sense to keep spawning new threads over and over again, since spawning a thread can take easily a couple of milliseconds, which would obliterate all performance gain. Instead, ask the user to pass the maximum amount of threads allowed, and do not spawn any more than that. Furthermore, it would be reasonable to cancel spawning a new thread in case the range to sort it receives is too small.

Hope that helps.

Context

StackExchange Code Review Q#141078, answer score: 2

Revisions (0)

No revisions yet.