kazuhoのメモ置き場

■nicesort ってのを書いてみた

sleep sort とか環境にやさしすぎて21世紀には不向きだと思うの。なので nicesort なるものを作ってみた。

#! /bin/bash

function f() {
  nice -n "$1" perl -we 'for (1..1000000) {}'
  echo "$1"
}
while [ -n "$1" ] ; do
  f "$1" &
  shift
done
wait

こんな感じで動きます。注意点としては、マルチコアだとうまく動かないので taskset 使いましょう (linux の場合) ってのと、0-20の範囲でしかそーとできないよってあたりかしら.

$ taskset 1 ./nicesort.sh 1 9 6 4
1
4
6
9

ちなみに、nice 値が１増えると実行時間は1.25倍になる。これは試験に出るよ！

参考: 革命の日々！ CFSのnice値について

Permalink | コメント(2) | トラックバック(0) | 12:59

■Cによるsleep sortの実装がないのもどうかと思ったので書いてみた

Yuyak を見て、Cによるsleep sortの実装がないのもどうかと思ったので書いてみた。シンプルですな。

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char** argv)
{
  int values[] = { 1, 9, 5, 3 };
  int i;
  
  for (i = 0; i < sizeof(values) / sizeof(values[0]); i++)
    switch (fork()) {
    case -1:
      assert(0);
      break;
    case 0:
      /* child process */
      sleep(values[i]);
      printf("%d\n", values[i]);
      exit(0);
      break;
    default:
      break;
    }
  
  for (i = 0; i < sizeof(values) / sizeof(values[0]); i++)
    while (wait(NULL) <= 0)
      assert(errno == EINTR);
  
  return 0;
}

Permalink | コメント(0) | トラックバック(0) | 12:34

■C++0x で sleep sort 書いてみた (was そういえば C++0x での sleep sort ってこんな感じでいいのかな)

GCC 4.6.0 をがんばって OSX に入れたのに std::thread 使えなくて泣きながら修正。こんな感じすね。

#include <cstdio>
#include <vector>
extern "C" {
#include <pthread.h>
#include <unistd.h>
}

int main(int, char**)
{
  int values[] = { 1, 9, 3, 6 };
  std::vector<pthread_t> threads;
  
  for (auto& v : values) {
    pthread_t tid;
    pthread_create(&tid, NULL, 
		   [](void* _v) -> void* {
		     int v = *reinterpret_cast<int*>(_v);
		     sleep(v);
		     printf("%d\n", v);
		     return NULL;
		   },
		   &v);
    threads.push_back(tid);
  }
  for (auto tid : threads)
    pthread_join(tid, NULL);
  
  return 0;
}

std::thread が使えればこうなる。

int main(int, char**)
{
  int values[] = { 1, 9, 3, 6 };
  std::vector<std::thread> threads;
  
  for (auto v : values)
    threads.emplace_back([v]() {
                           sleep(v);
                           printf("%d\n", v);
	                 });
  for (auto& thread : threads)
    thread.join();
  
  return 0;
}

コンパイラないので試せないわ。

Permalink | コメント(2) | トラックバック(0) | 09:32

■Re 常識を覆すソートアルゴリズム！その名も"sleep sort"！

常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte streamを読んで、自分が書くとしたらこんな感じかなーと思った。多重化して select 使う必要ないよねということで。

use Time::HiRes qw(sleep);

sub sleep_sort {
    # create pipe
    pipe(my $rfh, my $wfh)
        or die "pipe failed: $!";
    # spawn the processes
    my @pids;
    while (@_) {
        my $value = shift;
        my $pid = fork;
        die "fork failed: $!"
            unless defined $pid;
        if ($pid == 0) {
            # child process
            $| = 1;
            sleep $value / 10;
            print $wfh "$value\n";
            exit 0;
        }
        push @pids, $pid;
    }
    # close write handle and swallow all input
    close $wfh;
    my @values = <$rfh>;
    # get rid of the zombie processes
    for my $pid (@pids) {
        while (waitpid($pid, 0) != $pid) {
            if ($! == Errno::EINTR) {
                # continue
            } elsif ($! == Errno::ECHILD) {
                # somehow got reaped (maybe $SIG{CHLD} is 'IGNORE')
                last;
            } else {
                die "unexpected response from waitpid: $!";
            }
        }
    }
    # remove \n and return the result
    chomp @values;
    @values;
}

まあ、wait するくらいなら print する必要もないと思うけどw

sub sleep_sort {
    my %pid_value = map {
        +(fork || do {
            sleep $_ / 10;
            exit;
        }) => $_
    } @_;
    my @values;
    while (%pid_value) {
        if ((my $pid = wait) != -1) {
            push @values, delete $pid_value{$pid};
        }
    }
    @values;
}

Permalink | コメント(0) | トラックバック(0) | 05:56