sleep sort

4chan BBS 上一个排序的程序火了,它叫休眠排序,很有意思。
PLAIN TEXT
BASH:
  1. #!/bin/bash
  2. function f() {
  3. sleep “$1”
  4. echo “$1”
  5. }
  6. while [ -n “$1” ]
  7. do
  8. f “$1” &
  9. shift
  10. done
  11. wait
其实它的原理很简单,就是,要对N个整数进行排序的话,启动N个进程(线程),每个进程休眠对应的整数指定的秒数,然后再打印该数,最后你在终端上看到的肯定是排序之后的结果了……看了之后你会不会也觉得这太坑爹了?!可是,它就是能工作,而且占用CPU很少!
值得一提的是底下回复中给出的OpenMP版本(如果要尝试的话需要openmp支持)和Perl版本。
PLAIN TEXT
C:
  1. /*
  2. * @file sleepsort.c
  3. * @brief sorts numbers
  4. *
  5. * @compile gcc sleepsort.c -fopenmp -o sleepsort
  6. *
  7. * @author Gerald Jay Sussman (Massachvsetts Institvte of Technology)
  8. */
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <omp.h>
  12. int main(int argc, char **argv) {
  13. int i;
  14. omp_set_num_threads(argc);
  15. #pragma omp parallel for
  16. for (i = 0; i <argc – 1; i++) {
  17. long int this = atol(argv[i+1]);
  18. sleep(this);
  19. printf(“%ld\n”, this);
  20. fflush(stdout);
  21. }
  22. return 0;
  23. }
PLAIN TEXT
PERL:
  1. fork and sleep $_, say, last for @ARGV; 1 while 1 <=> –wait
除了不能对浮点数和负数进行排序,它还有一个缺点,那就是其中某个进程需要睡眠最大的那个数指定的时间,然后才能得出最后结果。下面有人提出了改 进,我试了试,没有一个完美的。理想的情况下它应该能够对正负整数、浮点数进行排序,而且最坏也不要花太多时间,感兴趣的同学可以自己改进一下。
此条目发表在Linux分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。

验证图片

*