Difference between revisions of "The Bean Counters"

From CDOT Wiki
Jump to: navigation, search
(Flat Profile)
(Blanked the page)
 
(18 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{GPU610/DPS915 Index | 20181}}
 
  
= The Bean Counters =
 
''Beans are a cheap commodity, so to count them is a rather silly thing to do. A "bean counter" is one who nitpicks over small things in order to save costs.''
 
 
== Team Members ==
 
# [mailto:ytian38@myseneca.ca?/subject=GPU610 Yankai Tian]
 
# [mailto:cansin@myseneca.ca?/subject=GPU610 Jay Ansin]
 
 
  [mailto:ytian38@myseneca.ca,cansin@myseneca.ca?/subject=GPU610 Email All]
 
 
 
== Projects ==
 
# sudoku - [http://www.andrew.cmu.edu/user/astian/ by Tian Debebe (CMU)] ''not affiliated with Yankai whatsoever''
 
# '''sorting algorithms''' - [http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html Alex Allain cprogramming.com], [https://www.toptal.com/developers/sorting-algorithms Animations]
 
 
 
 
= Progress =
 
 
== A1: Select and Assess ==
 
There wasn't a project source code for this. Everything was written by yours truly. etc. etc. etc. The 10 algorithms tested are:
 
 
=== Source Code ===
 
===== bubble sort =====
 
template<typename T>
 
inline void bubbleSort(T * array, int size) {
 
for (int i = 0; i < size; i++) {
 
for (int j = 0; j < size - 1; j++) {
 
if (array[j] > array[j + 1]) {
 
T swap = array[j + 1];
 
array[j + 1] = array[j];
 
array[j] = swap;
 
}
 
}
 
}
 
}
 
 
 
===== selection sort =====
 
template<typename T>
 
inline void selectionSort(T * array, int size) {
 
for (int i = 0; i < size; i++) {
 
int min = i;
 
for (int j = i; j < size; j++) {
 
if (array[min] > array[j])
 
min = j;
 
}
 
T temp = array[i];
 
array[i] = array[min];
 
array[min] = temp;
 
}
 
}
 
 
===== insertion sort =====
 
template<typename T>
 
inline void insertionSort(T * array, int size) {
 
T curr;
 
int j;
 
for (int i = 0; i < size; i++) {
 
curr = array[i];
 
for (j = i; j > 0 && array[j - 1] > curr; j--) {
 
array[j] = array[j - 1];
 
  }
 
array[j] = curr;
 
}
 
}
 
 
===== merge sort =====
 
template<typename T>
 
inline void mergeSort(T * array, int size) {
 
T * temp = new T[size];
 
mergeSort(array, temp, 0, size - 1);
 
delete[] temp;
 
}
 
 
template<typename T>
 
inline void mergeSort(T * array, T * temp, int start, int end) {
 
if (start < end) {
 
int mid = (start + end) / 2;
 
mergeSort(array, temp, start, mid);
 
mergeSort(array, temp, mid + 1, end);
 
merge(array, temp, start, mid + 1, end);
 
}
 
}
 
 
template<typename T>
 
inline void merge(T * array, T * temp, int startA, int startB, int endB) {
 
int aptr = startA;
 
int bptr = startB;
 
int idx = startA;
 
while (aptr < startB && bptr < endB + 1) {
 
if (array[aptr] < array[bptr]) {
 
temp[idx] = array[aptr];
 
idx++;
 
aptr++;
 
}
 
else {
 
temp[idx++] = array[bptr];
 
bptr++;
 
}
 
}
 
while (aptr<startB) {
 
temp[idx] = array[aptr];
 
idx++;
 
aptr++;
 
}
 
while (bptr < endB + 1) {
 
temp[idx++] = array[bptr];
 
bptr++;
 
}
 
 
for (int i = startA; i <= endB; i++) {
 
array[i] = temp[i];
 
}
 
}
 
 
===== heap sort =====
 
template<typename T>
 
inline void heapSort(T * array, int size) {
 
for (int i = size / 2 - 1; i >= 0; i--) {
 
heapify(array, size, i);
 
}
 
for (int i = size - 1; i >= 0; i--) {
 
std::swap(array[0], array[i]);
 
heapify(array, i, 0);
 
}
 
}
 
 
template <typename T>
 
void heapify(T * array, int size, int i) {
 
int largest = i;
 
int left = 2 * i + 1;
 
int right = 2 * i + 2;
 
if (left < size && array[left] > array[largest])
 
largest = left;
 
 
if (right < size && array[right] > array[largest])
 
largest = right;
 
 
if (largest != i) {
 
std::swap(array[i], array[largest]);
 
heapify(array, size, largest);
 
}
 
}
 
 
===== quick sort =====
 
template<typename T>
 
inline void quickSort(T * array, int size) {
 
quickSort(array, 0, size - 1);
 
}
 
 
template<typename T>
 
inline void quickSort(T * array, int left, int right) {
 
if (right - left <= 3) {
 
insertionSort(array, left, right);
 
}
 
else {
 
int mid = (left + right) / 2;
 
std::swap(array[right], array[mid]);
 
int pivotpt = right;
 
int i = left;
 
int j = right - 1;
 
T pivot = array[pivotpt];
 
while (i<j) {
 
while (i< right - 1 && array[i]<pivot) i++;
 
while (j > 0 && array[j]>pivot) j--;
 
  if (i<j)
 
std::swap(array[i++], array[j--]);
 
}
 
if (i == j && array[i] < array[pivotpt])
 
i++;
 
std::swap(array[i], array[pivotpt]);
 
quickSort(array, left, i - 1);
 
quickSort(array, i + 1, right);
 
}
 
}
 
 
===== counting sort =====
 
template<typename T>
 
inline void countingSort(T * array, int size, int RANGE) {
 
T output[size];
 
int count[RANGE + 1];
 
std::memset(count, 0, sizeof(count));
 
 
for (int i = 0; array[i]; ++i) {
 
++count[(int)array[i]];
 
}
 
 
for (int i = 1; i <= RANGE; ++i) {
 
count[i] += count[i-1];
 
}
 
 
for (int i = 0; array[i]; ++i) {
 
output[(int)count[(int)array[i]] - 1] = array[i];
 
--count[(int)array[i]];
 
}
 
 
for (int i = 0; i < size; i++) {
 
array[i] = output[i];
 
}
 
}
 
 
===== radix sort =====
 
template<typename T>
 
inline void radixSort(T * array, int size) {
 
T maxNumber = array[0];
 
for (int i = 1; i < size; i++) {
 
if (array[i] > maxNumber)
 
maxNumber = array[i];
 
}
 
 
T exp = 1;
 
T * temp = new T[size];
 
while (maxNumber / exp > 0) {
 
T decimalBucket[10] = { 0 };
 
 
for (int i = 0; i < size; i++)
 
decimalBucket[(int)array[i] / (int)exp % 10]++;
 
 
for (int i = 1; i < 10; i++)
 
decimalBucket[i] += decimalBucket[i - 1];
 
 
for (int i = size - 1; i >= 0; i--)
 
temp[(int)--decimalBucket[(int)array[i] / (int)exp % 10]] = array[i];
 
 
for (int i = 0; i < size; i++)
 
array[i] = temp[i];
 
 
exp *= 10;
 
}
 
}
 
 
===== bucket sort =====
 
template<typename T>
 
inline void bucketSort(T * array, int size, int bucketSize) {
 
std::vector<T> buckets[bucketSize];
 
T max = getMax(array, size);
 
int divider = std::ceil(T(max + 1) / bucketSize);
 
 
for (int i = 0; i < size; i++) {
 
int j = floor(array[i] / divider);
 
buckets[j].push_back(array[i]);
 
}
 
 
for (int i = 0; i < bucketSize; i++) {
 
sort(buckets[i].begin(), buckets[i].end());
 
}
 
 
int k = 0;
 
for (int i = 0; i < bucketSize; i++) {
 
for (int j = 0; j < buckets[i].size(); j++) {
 
array[k++] = buckets[i][j];
 
}
 
}
 
}
 
 
===== shell sort =====
 
template <typename T>
 
void shellSort(T * array, int size) {
 
T temp;
 
for (int gap = size / 2; gap > 0; gap /= 2) {
 
for (int i = gap; i < size; i += 1) {
 
temp = array[i];
 
int j;
 
for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
 
array[j] = array[j - gap];
 
}
 
array[j] = temp;
 
}
 
}
 
}
 
 
=== Results ===
 
Flat profile:
 
 
Each sample counts as 0.01 seconds.
 
  %  cumulative  self              self    total
 
  time  seconds  seconds    calls  Ts/call  Ts/call  name
 
  99.71      3.46    3.46                            void radixSort<float>(float*, int)
 
  0.29      3.47    0.01                            void quickSort<float>(float*, int, int)
 
  0.00      3.47    0.00    1091    0.00    0.00  void std::__move_median_first<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >)
 
  0.00      3.47    0.00      112    0.00    0.00  void std::vector<float, std::allocator<float> >::_M_insert_aux<float const&>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const&&&)
 
  0.00      3.47    0.00      10    0.00    0.00  void std::__insertion_sort<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >)
 
  0.00      3.47    0.00      10    0.00    0.00  void std::__introsort_loop<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, int>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, int)
 
  0.00      3.47    0.00        1    0.00    0.00  _GLOBAL__sub_I_main
 
 
==== Call Graph ====
 
==== Clustered Column Chart ====
 
 
 
== A2: Parallelize ==
 
 
=== Source Code ===
 
===== bubble sort =====
 
 
===== selection sort =====
 
===== insertion sort =====
 
 
=== Results ===
 
==== Visual Profiler ====
 
==== Parallel NSight ====
 
==== Comparison ====
 
 
 
== A3: Optimize ==
 
 
=== Source Code ===
 
===== bubble sort =====
 
===== selection sort =====
 
===== insertion sort =====
 
 
=== Results ===
 
==== Visual Profiler ====
 
==== Parallel NSight ====
 
==== Comparison ====
 

Latest revision as of 11:05, 9 April 2018