5
edits
Changes
→Idea 3 - Merge Sort
The compress() function performs similar operations on a collection of text, however it relies on a dictionary and an expanding string to be tokenized in a dictrionary. This could potentially be paralellized through a divide and conquer strategy where gpu blocks with shared caches share their own dictionary and iterate over their own block of text.
==== Idea 3 - MergeSort ==== Based on assignment topic suggestions. Code for logic is based on BTP500 course note by Catherine Leung - https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/sorting/merge_sort_code.html It has been adjust to work only with int arrays and perform operation on worst case scenario for merge sort, which is something similar to this array - [0, 2, 4, 6, 1, 3, 5, 7]. *********************<b>CODE</b>*********************To compile on matrix - <b>g++ -O2 -g -pg -oa1 a1.cpp</b> It performs merge sort on array with 100000000 which has worst case scenario positioning of elements for sorting. <source>#include<iostream> int SIZE = 100000000;/*This function merges the two halves of the array arr into tmp and then copies it back into arr*/void merge(int arr[], int tmp[], int startA, int startB, int end) { int aptr = startA; int bptr = startB; int i = startA; while (aptr<startB && bptr <= end) { if (arr[aptr]<arr[bptr]) tmp[i++] = arr[aptr++]; else tmp[i++] = arr[bptr++]; } while (aptr<startB) { tmp[i++] = arr[aptr++]; } while (bptr <= end) { tmp[i++] = arr[bptr++]; } for (i = startA; i <= end; i++) { arr[i] = tmp[i]; }} //this function sorts arr from index start to endvoid mSort(int* arr, int* tmp, int start, int end) { if (start<end) { int mid = (start + end) / 2; mSort(insert topicarr, tmp, start, mid); mSort(arr, tmp, mid + 1, end); merge(arr, tmp, start, mid + 1, end); }} void mergeSort(int* arr, int size) { int* tmp = new int[size]; mSort(arr, tmp, 0, size - 1); delete[] tmp;} void printArr(int* arr) { for (int i = 0; i < SIZE; i++) { std::cout << arr[i] << std::endl; }}int main(){ int* sampleArr = new int[SIZE]; bool worstCaseFlag = false; int j = 1; for (int i = 0; i < SIZE; i++) { if (worstCaseFlag == false) { sampleArr[i] = i; worstCaseFlag =true; } else { sampleArr[i] =j; j +=2; worstCaseFlag =false; } } mergeSort(sampleArr, SIZE); //printArr(sampleArr); std::cin.get(); return 0;}</source> ******************<b>Profiling</b>****************** <source>Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 90.40 13.85 13.85 99999999 0.00 0.00 merge(int*, int*, int, int, int) 9.60 15.32 1.47 1 1.47 15.32 mSort(int*, int*, int, int) 0.00 15.32 0.00 1 0.00 0.00 _GLOBAL__sub_I_SIZE </source>******************Analysing****************** The most time consuming part is merging, which can be at least partially paralleled. The Big(O) of this case is O(n).
=== Assignment 2 ===
=== Assignment 3 ===
