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.
/* 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; }
g++ -march=native -Os -o bogo_sort bogo_sort.cpp -lpthread && strip bogo_sort
./bogo_sort -j 2 -s 19563 56345 2423 4534 3543
(Sortieren von fünf Zahlen unter Benutzung von zwei Threads)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.
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 | ?? | ?? | ?? |
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 |