i practising c & c++ skills , decided string reverse problem in using method used in both languages. wrote recursive solution , and indexing method. there 4 reverse functions here; 2 use strictly c methods compute, , other 2 use c++ (stl, string, algorithm) calls.
- is comparison see speed of each method or missing something?
- also want find out how memory each method uses have not figured out how that.
// c++ reverse string #include <string> // string #include <algorithm> // reverse #include <iostream> // cout #include <cstring> // std::strcpy #include <stdio.h> // printf #include <sys/time.h> // gettimeofday inline void swap_characters(char* left, char* right) { char temp = *left; *left = *right; *right = temp; } void c_index_reverse(char* input, size_t inputsize) { const size_t strsize = inputsize - 1; char temp; for(int i=0 ; < inputsize / 2 ; i++) { swap_characters(&input[i], &input[strsize - i]); } } void c_recursive_reverse(char str[], int index, int size) { swap_characters(&str[index], &str[size - index]); if (index == size / 2) return; c_recursive_reverse(str, index + 1, size); } void c_plusplus_index_reverse(std::string& input) { const size_t strsize = input.length(); for(int i=0 ; < strsize / 2 ; i++) std::swap(input[i], input[strsize - - 1]); } std::string c_plusplus_recursive_reverse(std::string& input) { if(input.length() <= 1) { return input; } std::string tmp = std::string(input.begin() + 1, input.end()); return c_plusplus_recursive_reverse(tmp) + input[0]; } double timeit(struct timeval &start, struct timeval &end){ double delta = ((end.tv_sec - start.tv_sec) * 1000000u + end.tv_usec - start.tv_usec) / 1.e6; return delta; } int main() { struct timeval start,end; // using c++ stl std::string temp = "something weird word includes longer text see delay" \ "something weird word includes longer text see delay" \ "something weird word includes longer text see delay" \ "something weird word includes longer text see delay" \ "something weird word includes longer text see delay" \ "something weird word includes longer text see delay" \ "something weird word includes longer text see delay"; std::cout << temp << std::endl; // using c++ recursive reverse function - 4 gettimeofday(&start, null); std::reverse(temp.begin(), temp.end()); gettimeofday(&end, null); std::cout << temp << std::endl; printf("%lf \n",timeit(start, end)); // use c++ style functions // using recersive - 5 gettimeofday(&start, null); temp = c_plusplus_recursive_reverse(temp); gettimeofday(&end, null); std::cout << temp << std::endl; printf("%lf \n",timeit(start, end)); // using index reverse - 3 gettimeofday(&start, null); c_plusplus_index_reverse(temp); gettimeofday(&end, null); std::cout << temp << std::endl; printf("%lf \n",timeit(start, end)); // c style char *cstr = new char[temp.length() + 1]; std::strcpy(cstr, temp.c_str()); // using index - 1 gettimeofday(&start, null); c_index_reverse(cstr, temp.length()); gettimeofday(&end, null); printf("%s \n", cstr); printf("%lf \n",timeit(start, end)); // using recersive - 2 gettimeofday(&start, null); c_recursive_reverse(cstr, 0, temp.length() - 1); gettimeofday(&end, null); printf("%s \n", cstr); printf("%lf \n",timeit(start, end)); return 0; }
having inline function swap_characters() making big job 3 lines of code, creating more pointers when have them (although compiler might optimise). using indexing var, j, decremented until meets i more efficient.
void c_index_reverse(char* input, size_t inputsize) { int j = inputsize - 1; char temp; for(int i=0; i<j; i++) { temp = input[i]; input[i] = input[j]; input[j--] = temp; } } "also want find out how memory each method uses". non-recursive method uses minimal memory, since uses pointers , indexers. recursive method uses lot more memory, since every string character (up half string length) invokes recursion, more stack usage. string "something weird ..." has 600 chars, lot of stack usage, , of execution time spent calling, manipulating stack frames, , returning, little time spent swapping chars.
recursion here "hiding nowhere".
Comments
Post a Comment