123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118 |
- #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* countingSort(const T* in, int size, int max, int (*key)(const T&)) {
- max++;
- int* counter = new int[max];
- for(int i = 0; i < max; i++) {
- counter[i] = 0;
- }
- for(int i = 0; i < size; i++) {
- counter[key(in[i])]++;
- }
- for(int i = 1; i < max; i++) {
- counter[i] += counter[i - 1];
- }
- T* out = new T[size];
- for(int i = size - 1; i >= 0; i--) {
- out[counter[key(in[i])]-- - 1] = in[i];
- }
- delete[] counter;
- 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 = countingSort(a, size, max - 1, 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 = countingSort(a, size, max - 1, 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 = countingSort<int*>(a, size, max - 1, 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;
- }
|