Welcome, guest | Sign In | My Account | Store | Cart

Sleepsort with processes and pipes (Python recipe) by Benjamin Peterson
ActiveState Code (http://code.activestate.com/recipes/577758/)

Sleepsort is a sorting algorithm that uses the system sleep syscall in a very creative fashion.

This is the same algorithm as recipe 577756 but using *nix processes instead of threads.

Python, 51 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import os
import time

def sleepsort(l):
    """Another dumb sorting algorithm."""
    pids = []
    def reap():
        while pids:
            os.waitpid(pids.pop(), 0)
    # Setup communication.
    startr, startw = os.pipe()
    resr, resw = os.pipe()
    try:
        for i, x in enumerate(l):
            pid = os.fork()
            if pid == 0:
                # Wait for parent process to signal start.
                os.read(startr, 1)
                time.sleep(x)
                # Notify the parent process.
                os.write(resw, str(i).encode("ascii") + b" ")
                # Goodbye.
                os._exit(0)
            else:
                pids.append(pid)
        # Start the sleeps.
        os.write(startw, b"x" * len(l))
        os.close(startw)
        startw = -1
        reap()
        os.close(resw)
        resw = -1
        # Read results.
        data = []
        while True:
            d = os.read(resr, 4096)
            if len(d) == 0:
                break
            data.append(d)
    finally:
        os.close(startr)
        if startw > 0:
            os.close(startw)
        os.close(resr)
        if resw > 0:
            os.close(resw)
        reap()
    return [l[int(c)] for c in b"".join(data)[:-1].split(b" ")]

if __name__ == "__main__":
    print(sleepsort([10, 9, 7.3, 7, 6, .2, .4, 3, 2, 1.5]))

Sleepsort has an interesting algorithmic complexity: O(n) where n is either the maximum value of the input or the length of the input, whichever grows faster.

The origin of this algorithm is apparently http://dis.4chan.org/read/prog/129554415

Tags: process, sorting, unix