2011-05-20

C++0xによるsleep sortの実装

sleep sortの仕様:4chan BBS - Genius sorting algorithm: Sleep sort

以下、実装。コンパイルすら通していないので、正しく動くかどうかは不明。C++0x準拠のSTLが欲しい。

#include <iostream>
#include <vector>
#include <thread>
#include <chrono>

// 個々の要素のソート、というか表示遅延
void sort_element( unsigned int elem )
{
    std::this_thread::sleep_for( std::chrono::duration<unsigned int>( elem ) ) ;
    std::cout << elem << std::endl ;
}

// イテレーターの参照結果はunsigned int型に変換できる型であること
template < typename Iterator >
void sleep_sort( Iterator first, Iterator last )
{
    std::vector< std::thread > v ;
    for ( ; first != last ; ++first )
    { v.emplace_back( sort_element, static_cast<unsigned int>( *first ) ) ; }

    for ( auto & t : v )
    { t.join() ; }
}

int main()
{
    std::vector<unsigned int> v = { 5, 3, 6, 3, 6, 3, 1, 4, 7 } ;
    sleep_sort( v.begin(), v.end() ) ;
}

このプログラムの実行には、少なくとも7秒かかる。

追記:iostreamは、多分スレッドセーフじゃない。スレッドセーフにも色々な強さがあるが、どのような順番で出力されるかは、分からない。したがって、完全を目指すならば、何らかの方法で出力をシーケンスさせる必要がある。

しかし、このプログラムでは、待ち時間の最小単位が1秒である。1秒というのは、多くの実行環境で、処理が完了するのに十分な時間である。sleep sortが大抵の場合で動く理由は、そこにあるのだ。

No comments:

Post a Comment

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.