123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118 |
- #include <chrono>
- #include <iostream>
- #define MAX_SIZE 200000
- long getNanos() {
- return std::chrono::high_resolution_clock::now().time_since_epoch().count();
- }
- long getMillis() {
- return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
- }
- int intKey(const int& i) {
- return i;
- }
- static unsigned long seed = 0;
- int randomInt() {
- seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFF;
- return static_cast<int>(seed >> 17);
- }
- template<typename T>
- void bubbleSort(T* in, int size, int (*key)(const T&)) {
- bool madeSwap; // flag to know if we are done
- // make the bubble sort
- do {
- madeSwap = false;
- for (int i = 0; i < size - 1; i++) {
- // if this element is bigger that the next one swap places
- if (key(in[i]) > key(in[i + 1])) {
- madeSwap = true;
- T val = in[i + 1];
- in[i + 1] = in[i];
- in[i] = val;
- }
- }
- } while (madeSwap);
- }
- void cacheTest() {
- for (int size = 512; size < MAX_SIZE; size *= 2) {
- printf("Cache Test with size = %9d | ", size);
- constexpr int max = 500;
- int* a = new int[size];
- seed = 0;
- for (int i = 0; i < size; i++) {
- a[i] = randomInt() % max;
- }
- long time = -getNanos();
- bubbleSort(a, size, intKey);
- time += getNanos();
- printf("%10ld ns | %7.2lf ns / entry \n", time,
- (static_cast<double>(time) / size));
- delete[] a;
- }
- }
- struct A {
- int key;
- char filler[32];
- };
- int aKey(const A& a) {
- return a.key;
- }
- void structTest() {
- for (int size = 512; size < MAX_SIZE; size *= 2) {
- printf("Struct Test with size = %9d | ", size);
- constexpr int max = 500;
- A* a = new A[size];
- seed = 0;
- for (int i = 0; i < size; i++) {
- a[i].key = randomInt() % max;
- }
- long time = -getNanos();
- bubbleSort(a, size, aKey);
- time += getNanos();
- printf("%10ld ns | %7.2lf ns / entry \n", time,
- (static_cast<double>(time) / size));
- delete[] a;
- }
- }
- int pointerKey(int* const& a) {
- return *a;
- }
- void pointerTest() {
- for (int size = 512; size < MAX_SIZE; size *= 2) {
- printf("Pointer Test with size = %9d | ", size);
- constexpr int max = 500;
- int** a = new int* [size];
- seed = 0;
- for (int i = 0; i < size; i++) {
- a[i] = new int(randomInt() % max);
- }
- long time = -getNanos();
- bubbleSort<int*>(a, size, pointerKey);
- time += getNanos();
- printf("%10ld ns | %7.2lf ns / entry \n", time,
- (static_cast<double>(time) / size));
- for (int i = 0; i < size; i++) {
- delete a[i];
- }
- delete[] a;
- }
- }
- int main() {
- cacheTest();
- structTest();
- pointerTest();
- return 0;
- }
|