Sleep Sort：多线程排序

发表于

排序算法很多，不过下面这个不太一样，看好了~这是以时间控制的正儿八经的多线程排序~~

输入一个数组：A1,A2,A3,…Ai…,An，然后新建n个线程，每个线程Sleep(Ai)，然后输出Ai，排序就完成了。(感觉比 猴子排序 还NB~笑)

废话少说，先上代码：(Python实现)

from time import sleep
from threading import Timer

def sleepsort(values):
    sleepsort.result = []
    def add1(x):
        sleepsort.result.append(x)
    mx = values[0]
    for v in values:
        if mx < v: mx = v
        Timer(v, add1, [v]).start()
    sleep(mx+1)
    return sleepsort.result

if __name__ == '__main__':
    x = [3,2,4,7,3,6,9,1]
    if sleepsort(x) == sorted(x):
        print('sleep sort worked for:',x)
    else:
        print('sleep sort FAILED)

(Java实现)

import java.util.concurrent.CountDownLatch;

public class SleepSort {

    public static void sleepSortAndPrint(int[] nums) {
        final CountDownLatch doneSignal = new CountDownLatch(nums.length);
        for (final int num : nums) {
            new Thread(new Runnable() {
                public void run() {
                    doneSignal.countDown();
                    try {
                        doneSignal.await();
                        Thread.sleep(num);
                        System.out.print(num+"    ");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }).start();
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[args.length];
        for (int i = 0; i < args.length; i++)
            nums[i] = Integer.parseInt(args[i]);
        //int[] nums = new int[]{1,33,34,12,45,78};
        sleepSortAndPrint(nums);
    }
}

解释一下Java实现的部分内容。这里用到了CountDownLatch。

官方(JDK 6)的解释是“一个同步辅助类，在完成一组正在其他线程中执行的操作之前，它允许一个或多个线程一直等待。”简单理解，它是一个倒计时的锁。

使用给定的数字初始化 CountDownLatch。

主要方法有2个：countDown() & await()。

由于调用了 countDown() 方法，所以在当前计数到达零之前，await 方法会一直受阻塞。之后，会释放所有等待的线程，await 的所有后续调用都将立即返回。这种现象只出现一次——计数无法被重置。如果需要重置计数，需要使用CyclicBarrier。

CountDownLatch 是一个通用同步工具，它有很多用途。将计数 1 初始化的 CountDownLatch 用作一个简单的开/关锁存器，或入口：在通过调用countDown() 的线程打开入口前，所有调用 await 的线程都一直在入口处等待。用 N 初始化的 CountDownLatch 可以使一个线程在 N 个线程完成某项操作之前一直等待，或者使其在某项操作完成 N 次之前一直等待。

CountDownLatch 的一个有用特性是，它不要求调用 countDown 方法的线程等到计数到达零时才继续，而在所有线程都能通过之前，它只是阻止任何线程继续通过一个 await。

Sleep Sort思路很简单，但这里有几个问题：

  1. Python的Sleep函数精度是秒为单位的，那么如果我输入一个100000，这个排序就不得了了……可以想象会运行很久。同样在其他语言运行的情况下，数据与睡眠时间需要做平衡，否则算法失去意义。

  2. 还是输入的问题，如果是负数呢？或者是 浮点数呢？如果是更高精度的话就需要做特殊的处理。

  3. 另外，多线程算法还跟处理器的具体情况有关系。简单说，如果两个数非常接近的话(e.g. 1.0000000001 & 1.0000000002)，那么在多处理器环境下有不准确的可能。这里可以考虑OpenMPI的实现。

改进的话，Java会比较简单，其实就是对输出的数据做处理，对负数做偏移量的加法，对浮点数做乘数因子的扩大就可以了，当然这样做势必导致算法效率的下降，所以这个算法~不是任何时候都好用，算是提供一种思路吧。

算法最早出自4Chan BBS。

这个BBS现在恐怕是很出名了吧～

October 28, 2014 updated