Benutzer-Werkzeuge

Webseiten-Werkzeuge


scytheman:zeugs:code:bogosort

↑ zurück

Bogosort

Beschreibung

Bogosort ist ein sehr beliebter Sortieralgorithmus. Statt die richtige Reihenfolge der Elemente aufwändig zu berechnen wird sie einfach solange geraten, bis ein Treffer erzielt wird. Einen wirklichen Zweck hat dieses Programm also nicht.

Die zu sortierende Zahlenfolge wird mit dem Parameter -s angegeben. Es wird empfohlen, bei mehr als 10 Zahlen auf ein Mehrprozessorsystem zurück zu greifen und die Anzahl der Threads mit dem Parameter -j entsprechend anzupassen.

Benötigt

  • C++-Compiler
  • Humor

Code

/*      bogo_sort.cpp
 *
 *      This is a bloated, messy, threadable implementation of bogosort for
 *      research purposes.
 *      
 *      Copyright 2009 Alexander Heinlein
 *      
 *      This program is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 3 of the License, or
 *      (at your option) any later version.
 *      
 *      This program is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *      
 *      You should have received a copy of the GNU General Public License
 *      along with this program; if not, write to the Free Software
 *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 *      MA 02110-1301, USA.
 */
 
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm> /* qsort() */
#include <cstdlib>   /* rand_r() */
#include <ctime>     /* time() */
#include <cstring>   /* memset() */
#include <pthread.h>
#include <signal.h>
#include <sys/time.h> /* gettimeofday() */
 
// each thread holds own run number, avoids the need for
// constant (un-)locking when using a global run counter
std::vector<unsigned long long> runs;
// start time of program
unsigned long start = 0;
// length of sequence, needed to calculate bogosorts/s
unsigned int seq_len;
bool finished = false;
 
pthread_mutex_t finish_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t init_mutex   = PTHREAD_MUTEX_INITIALIZER;
 
//! initialize thread by assignign distinct thread number
unsigned int init_thread()
{
 unsigned int num;
 pthread_mutex_lock(&init_mutex);
 // resize vector and initialize run
 num = runs.size();
 runs.resize(num + 1);
 runs[num] = 0;
 pthread_mutex_unlock(&init_mutex);
 
 return num;
}
 
//! notify other threads about success (threadsafe)
void finish()
{
 pthread_mutex_lock(&finish_mutex);
 finished = true;
 pthread_mutex_unlock(&finish_mutex);
}
 
//! print current progress
void print_status()
{
 struct timeval tv;
 gettimeofday(&tv, NULL);
 unsigned long now = tv.tv_sec * 1000 * 1000 + tv.tv_usec;
 
 double u_secs = (now - start);
 
 unsigned long long total_runs = 0;
 for(std::vector<unsigned long long>::iterator it = runs.begin(); it != runs.end(); it++)
 {
    total_runs += *it;
 }
 
 // million bogosorts per second
 double m_bsorts = 0;
 if(u_secs != 0)
 {
    m_bsorts = (total_runs * seq_len) / u_secs;
 }
 
 std::cout << total_runs << " runs after " << u_secs / 1000.0 / 1000.0 << " seconds (" << m_bsorts << " million bogosorts/s)." << std::endl;
}
 
class BogoSort
{
 private:
    void print(std::vector<int>& vec);
 
 public:
    void bsort(std::vector<int> vec);
};
 
//! print vector elements
void BogoSort::print(std::vector<int>& vec)
{
 for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
 {
    std::cout << *it << " ";
 }
 
 std::cout << std::endl;
}
 
//! bogosort vector
void BogoSort::bsort(std::vector<int> vec)
{
 // get distinct thread id
 unsigned int num = init_thread();
 // distinct random seed for every thread
 unsigned int seed = time(0) + num;
 
 // create sorted sequence for easy comparison
 std::vector<int> sorted = vec;
 sort(sorted.begin(), sorted.end());
 
 std::vector<int> bogosorted;
 unsigned int size = vec.size();
 unsigned int pos;
 
 // randomly sort until success
 while(bogosorted != sorted)
 {
    if(finished) return; // another thread finished successfully, let's stop
 
    runs[num]++;
    bogosorted.clear();
    vec = sorted;
 
    for(unsigned int i = 0; i < size; i++)
    {
        pos = rand_r(&seed) % vec.size(); // choose random element
        bogosorted.push_back(vec[pos]);// add to bogosort vector
        vec.erase(vec.begin() + pos);  // remove from available elements
    }
 }
 
 finish();
 
 print(bogosorted);
 print_status();
}
 
//! let thread perform bogosort
void* thread_routine(void* arg)
{
 std::vector<int>* vec = static_cast<std::vector<int>*>(arg);
 
 BogoSort bsort;
 bsort.bsort(*vec);
 
 pthread_exit(NULL);
}
 
//! signal handler
void signal_handler(int signal)
{
 switch(signal)
 {
     case SIGUSR1:
         // just print progress, but keep running
         print_status();
         break;
     case SIGINT:
     case SIGTERM:
         print_status();
         exit(0);
         break;
     default:
         std::cerr << "Received unknown signal" << std::endl;
         print_status();
         exit(1);
         break;
 }
}
 
void usage(const std::string& cmd)
{
 std::cout << "Usage: " << cmd << " [OPTION]" << std::endl << std::endl
           << "-s, --sequence SEQUENCE  sequence of numbers to sort" << std::endl
           << "-j, --jobs     NUM       number of jobs to run in parallel"  << std::endl
           << "-h, --help               print this help and exit" << std::endl
           << std::endl
           << "Example: " << cmd << " -s 75 3 84 2" << std::endl
           << "Hint: for optimum results, make sure the sequence consists of distinct numbers" << std::endl;
}
 
int main(int argc, char *argv[])
{
 if (argc < 2)
 {
    std::cerr << "You don't like arguments? So i don't like you :(" << std::endl;
    usage(argv[0]);
    return 0;
 }
 
 // parse command line arguments
 std::vector<std::string> args(argv, argv + argc);
 std::vector<int> sequence;
 int jobs = 1;
 for (std::vector<std::string>::iterator it = args.begin() + 1; it < args.end(); it++)
 {
    if (*it == "-s" || *it == "--sequence")
    {
         while (++it != args.end())
         {
             // end of sequence / next argument?
             if(it->at(0) == '-')
             {
                 --it;
                 break;
             }
 
             std::stringstream strstr(*it);
             int num;
             strstr >> num;
             sequence.push_back(num);
         }
    }
    else if (*it == "-j" || *it == "--jobs")
    {
        if(++it < args.end())
        {
            std::stringstream strstr(*it);
            strstr >> jobs;
            if(jobs < 1)
            {
                std::cerr << "Number of jobs must be at least one" << std::endl;
                return 0;
            }
        }
        else
        {
            std::cerr << "Invalid number of arguments for jobs" << std::endl;
            usage(argv[0]);
            return 0;
        }
    }
    else if (*it == "-h" || *it == "--help")
    {
        usage(argv[0]);
        return 0;      
    }
    else
    {
        std::cerr << "Invalid argument: " << *it << std::endl;
        usage(argv[0]);
        return -1;     
    }
 }
 
 if(sequence.size() <= 1)
 {
    std::cerr << "Input sequence too short" << std::endl;
    usage(argv[0]);
    return -1;
 }
 
 // register signal handler
 struct sigaction action;
 memset(&action, 0, sizeof(action));
 action.sa_handler = signal_handler;
 action.sa_flags = 0;
 sigemptyset(&action.sa_mask);
 sigaction(SIGUSR1, &action, NULL);
 sigaction(SIGINT, &action, NULL);
 sigaction(SIGTERM, &action, NULL);
 
 seq_len = sequence.size(); 
 std::cout << "Using " << jobs << " thread(s) to sort " << seq_len << " elements." << std::endl;
 
 // set start time 
 struct timeval tv;
 gettimeofday(&tv, NULL);
 start = tv.tv_sec * 1000 * 1000 + tv.tv_usec;
 
 // create threads 
 std::vector<pthread_t> threads;
 threads.reserve(jobs);
 runs.reserve(jobs);
 for(int i = 0; i < jobs; i++)
 {
     pthread_t thread;
 
     pthread_attr_t attr; 
     pthread_attr_init(&attr); 
     pthread_attr_setstacksize(&attr, 512 * 1024); // reduce default thread stack size
 
     pthread_create(&thread, &attr, &thread_routine, &sequence);
     threads.push_back(thread);
 }
 
 // we have to wait for every thread to terminate, otherwise
 // sequence may get freed to early (or some other crap happens)
 for(int i = 0; i < jobs; i++)
 {
     pthread_join(threads.at(i), NULL);
 }
 
 pthread_exit(NULL);
 
 return 0;
}

Benutzung

  • Kompilieren: g++ -march=native -Os -o bogo_sort bogo_sort.cpp -lpthread && strip bogo_sort
  • Starten: ./bogo_sort -j 2 -s 19563 56345 2423 4534 3543 (Sortieren von fünf Zahlen unter Benutzung von zwei Threads)
  • Status abfragen: pkill -USR1 bogo_sort (Schreibt Anzahl bisheriger Sortierversuche auf die Standardausgabe, ohne das Programm zu beenden)

Hinweis: Die Statusabfrage und auch das Ausgeben des aktuellen Fortschritts bei Beendigung durch Senden eines Interrupts erlauben es, das Programm zu beenden und zu einem späteren Zeitpunkt erneut zu starten. Dadurch lassen sich die Anzahl der Versuche mehrerer Läufe addieren, bis schließlich einer zum Erfolg führt. Wie statistisch relevant dieses Ergebnis dadurch ist, sei dahingestellt.

Messergebnisse

Sortierversuche

Anzahl der Sortierversuche bei je 10 Durchläufen (statistisch nicht relevant).

Anzahl Elemente Mögliche Kombinationen Mittelwert Minimum Maximum
3 6 12.4 2 29
5 120 98.2 2 293
8 40 320 33 240.3 2 198 67 859
10 3 628 800 3 042 537.3 1 368 590 5 850 993
12 479 001 600 124 231 721.3 2 823 229 532 764 830
13 6 227 020 800 ?? ?? ??
14 87 178 291 200 ?? ?? ??
15 1 307 674 368 000 ?? ?? ??

Millionen Bogosorts pro Sekunde (MBpS)

Zusätzlich zur Anzahl der Sortierversuche gibt das Programm auch die imaginäre Metrik der Anzahl der Bogosorts pro Sekunde aus. Dieser Wert ist natürlich unabhängig von der Länge der zu sortierenden Folge, solange sie hinreichend lang ist. Die folgende Tabelle liefert einige Aufschlüsse darüber, mit welcher Prozessorleistung welche MBpS erreichbar sind.

Hinweis: Dieses Programm ist für Benchmarks natürlich ungeeignet, da die zu erreichenden MBpS von vielen Einflüssen abhängen.

CPU Vendor CPU Typ GHz Threads MBpS
AMD A4-3400 2.85 1 19.49
AMD A4-3400 2.85 2 36.84
AMD A8-6600K 3.90 1 38.64
AMD A8-6600K 3.90 2 51.09
AMD A8-6600K 3.90 4 116.71
AMD A8-6600K 3.90 8 121.84
AMD E-450 1.65 1 8.89
AMD E-450 1.65 2 16.91
AMD FX-4100 3.60 2 50.43
AMD FX-4100 3.60 4 88.51
AMD FX-4100 3.60 8 100.32
AMD FX-8350 4.00 1 37.94
AMD FX-8350 4.00 2 63.19
AMD FX-8350 4.00 4 119.40
AMD FX-8350 4.00 8 185.33
AMD FX-8350 4.00 16 239.08
AMD Geode LX800 0.50 1 1.77
AMD Opteron 4180 2.60 1 18.80
AMD Opteron 4180 2.60 2 28.98
AMD Opteron 4180 2.60 4 55.18
AMD Opteron 4180 2.60 8 123.75
AMD Opteron 4180 2.60 16 176.88
AMD Opteron 4180 2.60 32 188.73
Broadcom ARM1176JZF-S 0.70 1 2.87
Intel Core2 Duo E8400 3.20 1 29.97
Intel Core2 Duo E8400 3.20 2 56.29
Intel Core2 Duo U7600 1.20 1 7.32
Intel Core2 Duo U7600 1.20 2 13.04
Intel Core2 Quad Q8300 2.50 1 18.99
Intel Core2 Quad Q8300 2.50 2 32.05
Intel Core2 Quad Q8300 2.50 4 64.42
Intel Core2 Quad Q9400 2.66 1 24.27
Intel Core2 Quad Q9400 2.66 2 44.35
Intel Core i3-2120 3.30 1 24.68
Intel Core i3-2120 3.30 2 37.78
Intel Core i3-2120 3.30 4 62.94
Intel Core i7-2600K 3.40 1 38.02
Intel Core i7-2600K 3.40 2 61.37
Intel Core i7-2600K 3.40 4 129.74
Intel Core i7-2600K 3.40 8 192.04
Intel Dual-Core T4500 2.30 1 19.46
Intel Dual-Core T4500 2.30 2 39.05
Intel Dual-Core E5200 2.50 1 22.90
Intel Dual-Core E5200 2.50 2 43.28
Intel Dual-Core E5400 2.70 1 11.56
Intel Dual-Core E5400 2.70 2 22.36
Intel Pentium 4 3.00 1 11.85
Intel Pentium 4 3.00 2 15.97
Intel Pentium M 750 1.86 1 8.68
Intel Xeon ?? 3.20 1 9.16
Intel Xeon ?? 3.20 2 14.23
Intel Xeon ?? 3.20 4 20.39
Intel Xeon E5-4650 2.70 1024 953.57
Intel Xeon E5-4650 2.70 1 27.58
Intel Xeon E5-4650 2.70 128 407.08
Intel Xeon E5-4650 2.70 16 82.10
Intel Xeon E5-4650 2.70 2048 1029.59
Intel Xeon E5-4650 2.70 2 31.39
Intel Xeon E5-4650 2.70 256 560.65
Intel Xeon E5-4650 2.70 32 168.85
Intel Xeon E5-4650 2.70 4 33.72
Intel Xeon E5-4650 2.70 512 777.56
Intel Xeon E5-4650 2.70 64 252.12
Intel Xeon E5-4650 2.70 8 59.46
Intel Xeon E5410 2.33 1 13.93
Intel Xeon E5410 2.33 2 22.77
Intel Xeon E5410 2.33 4 39.77
Intel Xeon E5410 2.33 8 79.28
Intel Xeon E5420 2.50 1 18.98
Intel Xeon E5420 2.50 2 23.46
Intel Xeon E5420 2.50 4 47.12
Intel Xeon E5420 2.50 8 93.10
Intel Xeon E5420 2.50 16 101.24
Intel Xeon E5450 3.00 1 22.75
Intel Xeon E5450 3.00 2 32.44
Intel Xeon E5450 3.00 4 53.78
Intel Xeon E5450 3.00 8 108.25
Intel Xeon E5504 2.00 1 14.67
Intel Xeon E5504 2.00 2 16.92
Intel Xeon E5504 2.00 4 35.85
Intel Xeon E5504 2.00 8 80.44
Intel Xeon E5504 2.00 16 92.50
Intel Xeon E5530 2.40 1 19.43
Intel Xeon E5530 2.40 2 36.50
Intel Xeon E5530 2.40 4 59.25
Intel Xeon E5530 2.40 8 109.73
Intel Xeon E5530 2.40 16 155.24
Intel Xeon E5530 2.40 32 171.39
Intel Xeon E5530 2.40 64 191.94
scytheman/zeugs/code/bogosort.txt · Zuletzt geändert: 2016/11/15 19:22 von scytheman