Last active
January 28, 2017 10:47
-
-
Save squirrel532/d42cc1b1cfbc694ecc4dcc1fa17c091d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <string.h> | |
#include <stdint.h> | |
#include <time.h> | |
#include <assert.h> | |
inline void swap_char(char *a, char *b) { | |
*a ^= *b; *b ^= *a; *a ^= *b; | |
} | |
// super slow recursion O(n^2) | |
char *rev_a(char *s) { | |
char head = *s; | |
if (head == '\0'){ | |
return s; | |
} | |
rev_a(s+1); | |
// copy substring | |
char *current = s; | |
while(1) { | |
if (*(current+1) == '\0') { | |
*current = head; | |
break; | |
} else { | |
*current = *(current+1); | |
} | |
++current; | |
} | |
return s; | |
} | |
// maximum stack depth is the length of s. | |
// O(n) | |
char *rev_s(char *s) { | |
int len = strlen(s); | |
if (len > 1) { | |
char head = *s; | |
char *tail_ptr = s+len-1; | |
*s = *(tail_ptr); | |
*(tail_ptr) = '\0'; | |
rev_s(s+1); | |
*(tail_ptr) = head; | |
} | |
return s; | |
} | |
// binary swap, inspired by merge sort | |
char *rev_b(char *s) { | |
int len = strlen(s); | |
if (len > 1) { | |
// int mid = len / 2 + (len & 1); // ignore privot | |
int mid = (len + 1) / 2; // ignore privot | |
rev_b(s+mid); | |
// TODO: swap s, s+mid, strlen(s+mid) | |
for (int i = 0; i < mid; i++) { | |
char tmp = s[i]; | |
s[i] = s[i+mid]; | |
s[i+mid] = tmp; | |
} | |
rev_b(s+mid); | |
} | |
return s; | |
} | |
// depth O(n) | |
int _helper_c(char *s, char *current) { | |
if (*current == '\0') { | |
return 0; | |
} else { | |
int co_idx = _helper_c(s, current+1); | |
if (co_idx < current-s) { | |
/* | |
char tmp = s[co_idx]; | |
s[co_idx] = *current; | |
*current = tmp; | |
*/ | |
swap_char(s+co_idx, current); | |
} | |
return co_idx + 1; | |
} | |
} | |
char *rev_c(char *s) { | |
_helper_c(s, s); | |
return s; | |
} | |
// depth O(n) | |
/* | |
int _helper_d(void *s, void *current) { | |
if (*((char*)current) == '\0') { | |
return 0; | |
} else { | |
uint64_t *str = s, *cur = current; | |
// const int step = sizeof(uint64_t) / sizeof(char); | |
int co_idx = _helper_c(s, (void *)(cur+1)); | |
if (co_idx < current-s) { | |
uint64_t tmp = str[co_idx]; | |
str[co_idx] = *cur; | |
*cur = tmp; | |
// remember the inter reverse of each uint64_t | |
_swap_char_(s , s+7); | |
_swap_char_(s+1, s+6); | |
_swap_char_(s+2, s+5); | |
_swap_char_(s+3, s+4); | |
_swap_char_(current , current+7); | |
_swap_char_(current+1, current+6); | |
_swap_char_(current+2, current+5); | |
_swap_char_(current+3, current+4); | |
} | |
return co_idx + 1; | |
} | |
} | |
char *rev_d(char *s) { | |
_helper_d((void*)s, (void*)s); | |
return s; | |
} | |
*/ | |
char *rev_for(char *str) { | |
int len = strlen(str); | |
for (int i = 0; i < len/2; i++) { | |
char c = str[i]; | |
str[i] = str[len - i - 1]; | |
str[len - i - 1] = c; | |
} | |
return str; | |
} | |
int main(int argc, char const* argv[]) | |
{ | |
char str[1050000], backup[1050000], reversed[1050000]; | |
FILE *FD = fopen(argv[1], "r"); | |
if (FD != NULL) { | |
fscanf(FD, "%s", str); | |
fclose(FD); | |
} else { | |
strcmp(str, "hello world"); | |
} | |
int len = strlen(str); | |
for (int i = 0; i < len; i++) { | |
reversed[i] = str[len - i - 1]; | |
} | |
reversed[len] = '\0'; | |
strcpy(backup, str); | |
char *(*reverse_fuctions[])(char *) = {rev_for, rev_a, rev_b, rev_s, rev_c}; | |
int n_reverse_function = sizeof(reverse_functions) / sizeof(reverse_functions[0]); | |
puts("absc"); | |
for (int i = 0; i < n_reverse_functions; i++) { | |
clock_t begin = clock(); | |
reverse_fuctions[i](str); | |
assert(strcmp(str, reversed) == 0); | |
reverse_fuctions[i](str); | |
assert(strcmp(str, backup) == 0); | |
clock_t end = clock(); | |
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC; | |
printf("Case %d# %lfs\n", i+1, time_spent); | |
} | |
/* | |
printf("%s\n", rev(str)); | |
printf("%s\n", rev(str)); | |
printf("%s", rev(rev(str))); | |
*/ | |
return 0; | |
} |
$ ./a.out case1k
absc
Case 1# 0.000010s
Case 2# 0.000959s
Case 3# 0.000186s
Case 4# 0.000892s
Case 5# 0.000014s
$ ./a.out case4k
absc
Case 1# 0.000033s
Case 2# 0.013263s
Case 3# 0.000650s
Case 4# 0.006442s
Case 5# 0.000047s
$ ./a.out case8k
absc
Case 1# 0.000058s
Case 2# 0.033567s
Case 3# 0.001025s
Case 4# 0.029117s
Case 5# 0.000089s
$ ./a.out case1M
absc
Case 1# 0.004937s
[1] 10302 segmentation fault ./a.out case1M
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Needs compile options -O, or remove inline from the declaration of swap_char manually.