首页 > 代码库 > 微博估计要火一阵的SleepSort之Shell及C实现

微博估计要火一阵的SleepSort之Shell及C实现

2024-07-10 01:58:05   225人阅读

今日在微博看到如此神奇的代码，居然还有新的sort算法，对于我这种渣渣必须研究一下，代码如下：

#!/bin.bash
function f()
{
    sleep "$1" //sleep 这么多s
    echo "$1"
}


while [ -n "$1" ] //第一个参数不为空
do
    f "$1" & //后台运行，相当于fork一个进程去执行f, 父进程同时继续下去
    shift //输入参数左移，也即覆盖掉第一个参数
done

wait//父进程等待子进程都结束了再继续往下，否则子进程成为孤立进程




SleepSort，一看代码，看到sleep大致就明白意图了，利用sleep，以及多线程并发，按照sleep大小排序，并发来print排序


这个算法本质上是并发的算法，运用了sleep函数，同时几个进程并发，并发是指几个进程同一时间段同时执行，一个时刻还是要排个序逐个执行的，而并行是需要硬件支持的，真正的同一时刻多个进程同时运行。


于是乎本菜鸟打算C语言搞一搞，因为借助linux的fork函数来模拟 shell里面 &的后台运行功能。另外上述代码接口不太好，最好是传递数组参数这种的，于是我写个接口比较general的C版
另外这里面要注意就是shell wait等前面子进程全部结束，父进程才继续。我用C总是输出第一个数父进程就返回了，差了C的文档才知道，他是任意一个child返回父进程就返回了，因此多次wait 用个loop。


代码(*nix OS only)：
#include <iostream>
#include <sys/wait.h>
using namespace std;


void f(int x)
{
        sleep(x);
        cout<<x<<" ";
}
void SleepSort(int*a, int n)
{
        int status;
        pid_t pid;
        for(int i=0;i<n;i++)
        {
                pid=fork();
                if(pid==0)//child process, return 0 pid
                {
                        f(a[i]);
                        return;
                }
                else//father process return pid>0
                {
                        ;
                }
        }
        for(int i=0;i<n;i++)
                wait(NULL);//each wait one child process, then continue
}
int main()
{
        int a[]={6,2,5,8,5,4,7,1};
        SleepSort(a,8);
}




按照这个思想，其实任何并行的技术理论都可以实现sleepsort，例如CUDA，openmp, mpi等等，我这里弄个并发版本。


另外确实要用最小单位s的sleep函数，稍微注意一下就好了~~~ 下面博客说的比较清楚~~~

http://blog.csdn.net/changingivan/article/details/6966510

收到这个启发，这个算法有个缺陷，如果排序的树interval很小，例如1.1 1.11这种，也可能有危险，最小sleep差比一次loop是关键


联系
我们