123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159 |
- #include <chrono>
- #include <iostream>
- long getNanos()
- {
- return 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> T *mergeSort(const T *in, int size, int (*key)(const T &))
- {
- if (size <= 1)
- {
- T *out = new T[size];
- for (int i = 0; i < size; ++i)
- {
- out[i] = in[i];
- }
- return out;
- }
- // split
- int sizeLeft = size / 2;
- int sizeRight = (size + 1) / 2;
- const T *left = in;
- const T *right = in + sizeLeft;
- left = mergeSort(left, sizeLeft, key);
- right = mergeSort(right, sizeRight, key);
- T *out = new T[size];
- // merge
- int rightCounter = 0;
- int leftCounter = 0;
- for (int i = 0; i < size; ++i)
- {
- if (leftCounter >= sizeLeft)
- {
- out[i] = right[rightCounter];
- ++rightCounter;
- }
- else if (rightCounter >= sizeRight)
- {
- out[i] = left[leftCounter];
- ++leftCounter;
- }
- else if (key(left[leftCounter]) < key(right[rightCounter]))
- {
- out[i] = left[leftCounter];
- ++leftCounter;
- }
- else
- {
- out[i] = right[rightCounter];
- ++rightCounter;
- }
- }
- delete[] right;
- delete[] left;
- return out;
- }
- void cacheTest()
- {
- for (int size = 512; size < 100'000'000; 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();
- int *b = mergeSort(a, size, intKey);
- time += getNanos();
- printf("%10ld ns | %7.2lf ns / entry \n", time,
- (static_cast<double>(time) / size));
- delete[] a;
- delete[] b;
- }
- }
- struct A
- {
- int key;
- char filler[32];
- };
- int aKey(const A &a) { return a.key; }
- void structTest()
- {
- for (int size = 512; size < 100'000'000; 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();
- A *b = mergeSort(a, size, aKey);
- time += getNanos();
- printf("%10ld ns | %7.2lf ns / entry \n", time,
- (static_cast<double>(time) / size));
- delete[] a;
- delete[] b;
- }
- }
- int pointerKey(int *const &a) { return *a; }
- void pointerTest()
- {
- for (int size = 512; size < 100'000'000; 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();
- int **b = mergeSort<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;
- delete[] b;
- }
- }
- int main()
- {
- cacheTest();
- structTest();
- pointerTest();
- return 0;
- }
|