Saturday, November 29, 2014

Sleep Sort

Je suis en train d’expérimenter avec les nouvelles fonctionnalités de C++11, en particulier les manières de gérer la concurrence. Dans ce post je propose une implémentation de sleep sort.

Qu’est ce que sleep sort ? Un algorithme de tri basé sur la mise en attente de thread. Cet algorithme n’a pas à ma connaissance d’application autre qu’être une plaisanterie populaire sur le board /prog/ de 4chan. L’idée de l’algorithme est de lancer en parallèle pour chaque entier x à trier sleep(x); print x;. Dans un monde parfait cet algorithme à comme complexité O(max(x)), en pratique c’est plutôt O(n^2 + max(x)) car l’ordonnanceur du noyau doit maintenir les n threads. Il y a également un point sur lequel il faut faire attention, si les éléments à trier ne sont pas garantis sans doublon si print n’est pas thread-safe il y des accès concurrents. C’est pourquoi j’utilise un mutex.

#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <thread>
#include <vector>

using namespace std;
using namespace std::chrono;

auto die = bind(uniform_int_distribution<>{1, 64}, default_random_engine{});

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& t) {
    bool first = true;
    for (auto& x : t) {
        if (!first)
            os << ' ';
        first = false;
        os << x;
    }
    return os;
}

template <typename Iterator>
void sleep_sort(Iterator first, Iterator last) {
    vector<thread> tasks;
    mutex m;
    for (auto it = first; it != last; ++it) {
        typename Iterator::value_type x = *it;
        tasks.push_back(thread{[&first, x, &m]() {
            this_thread::sleep_for(milliseconds{10 * x});
            unique_lock<mutex> lck{m};
            *first = x;
            ++first;
        }});
    }

    for (auto& th : tasks)
        th.join();
}

int main() {
    vector<int> t(128);
    for (int& x : t)
        x = die();

    cout << t << '\n';

    sleep_sort(begin(t), end(t));
    assert(is_sorted(begin(t), end(t)));
    
    cout << t << '\n';
}

No comments:

Post a Comment