http://dis.4chan.org/read/prog/1295544154
要は、配列aの各要素aに対して、a秒スリープしてから出力するというアルゴリズムです。
発想は面白いですが、実用的ではありません。
C++で実装してみました。(環境は、VC2010とboost 1.44です)
► スポイラーを表示
[tabs][tabs: sleep_sort.hpp]
[tabs: synchronized_queue.hpp]
[tabs: main.cpp]
[/tabs]
#pragma once
#include <memory>
#include <algorithm>
#include <boost/thread/thread.hpp>
#include "synchronized_queue.hpp"
// delay (ms) スリープしてから、Qにvalueをプッシュするスレッド
// start()で起動する
template <typename T>
class delayed_pusher
{
public:
delayed_pusher(const T &value, synchronized_queue<T> &Q, int delay) : value(value), Q(Q), delay(delay)
{
}
void operator()() const
{
boost::this_thread::sleep(boost::get_system_time() + boost::posix_time::milliseconds(delay));
Q.push(value);
}
void start()
{
thread.reset(new boost::thread(boost::ref(*this)));
}
private:
std::unique_ptr<boost::thread> thread;
T value;
synchronized_queue<T> &Q;
int delay;
};
// 渡された値をそのまま返す
template <typename T>
inline T return_self_value(T value)
{
return value;
}
// スリープソート
// [first, last) ソートするかもしれない
// 結果は、dest以降に格納される
// decide_delay によってスリープ時間を決定する
template <typename InIt, typename OutIt, typename Func1>
void sleep_sort_copy(InIt first, InIt last, OutIt dest, Func1 decide_delay)
{
typedef typename std::iterator_traits<InIt>::value_type V;
typedef delayed_pusher<V> pusher;
// 結果を受け取るキュー
synchronized_queue<V> Q;
// スレッドグループ
std::vector<std::unique_ptr<pusher>> v;
// 各要素に対して、スレッドを準備(まだ起動はしない)
for ( ; first != last; ++first) {
v.push_back(std::unique_ptr<pusher>(new pusher(*first, Q, decide_delay(*first))));
}
// 一斉に起動
std::for_each(v.begin(), v.end(), std::mem_fn(&pusher::start));
// 早く到着した順に結果を受け取る
for (std::size_t i = 0; i < v.size(); ++i) {
while (Q.empty()) {
// wait
}
*dest = Q.front();
Q.pop();
++dest;
}
}
// 各 *first がそのままスリープ時間になるバージョン
// 整数型を指すイテレータにしか使えない
template <typename InIt, typename OutIt>
void sleep_sort_copy(InIt first, InIt last, OutIt dest)
{
sleep_sort_copy(first, last, dest, return_self_value<typename std::iterator_traits<InIt>::value_type>);
}
// 入力と受け取り先が同じ場合
template <typename FwdIt, typename Func1>
void sleep_sort(FwdIt first, FwdIt last, Func1 decide_delay)
{
sleep_sort_copy(first, last, first, decide_delay);
}
// 入力と受け取り先が同じ場合(デフォルトバージョン)
template <typename FwdIt>
void sleep_sort(FwdIt first, FwdIt last)
{
sleep_sort(first, last, return_self_value<typename std::iterator_traits<FwdIt>::value_type>);
}
#pragma once
#include <queue>
#include <boost/thread/mutex.hpp>
// std::queue<T>の各操作に排他制御を追加したもの
template <typename T>
class synchronized_queue
{
public:
void push(const T &value)
{
boost::mutex::scoped_lock lock(guard);
impl.push(value);
}
void pop()
{
boost::mutex::scoped_lock lock(guard);
impl.pop();
}
T &front()
{
boost::mutex::scoped_lock lock(guard);
return impl.front();
}
const T &front() const
{
boost::mutex::scoped_lock lock(guard);
return impl.front();
}
bool empty() const
{
boost::mutex::scoped_lock lock(guard);
return impl.empty();
}
private:
mutable boost::mutex guard;
std::queue<T> impl;
};
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include "sleep_sort.hpp"
// 最小値と最大値をもとに、線形補間してスリープ時間を決定する
// Tは暗黙的にdoubleに変換可能でなければならない
template <typename T>
struct linear_scale_delay
{
public:
template <typename InIt>
linear_scale_delay(InIt first, InIt last, int max) : lower(0), upper(0), max(max)
{
if (first != last) {
lower = *std::min_element(first, last);
upper = *std::max_element(first, last);
}
}
int operator()(const T &arg) const
{
return (lower == upper) ? 0 : static_cast<int>((arg - lower) / (upper - lower) * max);
}
private:
double lower;
double upper;
int max;
};
void prompt()
{
std::cout << "please input." << std::endl;
}
// サンプル1
// 標準入力からの入力をスリープソートして、標準出力に直接出力
void sample1()
{
std::istream_iterator<int> input(std::cin), end;
std::ostream_iterator<int> output(std::cout, " ");
sleep_sort_copy(input, end, output);
std::cout << std::endl;
std::cin.clear();
}
// サンプル2
// 標準入力からの入力を、vectorに格納し、
// スリープソートを適用してから(vectorの中身を書き換えて)
// 標準出力に出力
void sample2()
{
std::istream_iterator<double> input(std::cin), end;
std::ostream_iterator<double> output(std::cout, " ");
std::vector<double> v(input, end);
std::cout << "-before-" << std::endl;
std::copy(v.begin(), v.end(), output);
std::cout << std::endl;
sleep_sort(v.begin(), v.end(), linear_scale_delay<double>(v.begin(), v.end(), 500));
std::cout << "-after-" << std::endl;
std::copy(v.begin(), v.end(), output);
std::cout << std::endl;
}
int main()
{
prompt();
sample1();
prompt();
sample2();
}
main.cppは使用例です。
必ずソートされるわけじゃないし、文字列とかどうやってソートしよう?