The problem statement is that we have a string and we want to rotate each character to its next character i.e a to b, b to c and z to a. Also, the conversion is based on the number x ( x is <= size of string). The number represents the length of the characters to be converted. Let's say the number is 3 and string is stack which means only first 3 characters need to be converted, so output will be tubck. if the number is 5 then the output will be tubdl.
I am running the solution for 100000000 times and generating the variable number randomly. I have solved this problem using 3 approaches mentioned below:
- Convert from character to integer, then increment the integer by 1, then convert the integer back to character.
- Using the hashmap to get the updated character value in O(1) time.
- Using C, but the approach followed is same as of step # 1
The runtime of the hashmap technique (approach 2) is coming to be more. I don't know why?
Approach #1 is
public static void main(String[] args) {
Long startTime = System.currentTimeMillis();
String name = "abcdefghijklmnopqrstuvwxyz";
char[] stringCharArray = name.toCharArray();
Random random = new Random();
for (Integer i = 0; i <100000000; i++) {
{
for (int j = 0; j < random.nextInt(26) + 1; j++) {
if (stringCharArray[j] == 'z') {
stringCharArray[j] = 'a';
} else {
stringCharArray[j] = (char) (((int) (stringCharArray[j])) + 1);
}
}
}
}
Long endtime = System.currentTimeMillis();
System.out.println(endtime-startTime+" ms");
}
Approach # 2 using hashmap is
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put('a', 'b');
hashMap.put('b', 'c');
hashMap.put('c', 'd');
hashMap.put('d', 'e');
hashMap.put('e', 'f');
hashMap.put('f', 'g');
hashMap.put('g', 'h');
hashMap.put('h', 'i');
hashMap.put('i', 'j');
hashMap.put('j', 'k');
hashMap.put('k', 'l');
hashMap.put('l', 'm');
hashMap.put('m', 'n');
hashMap.put('n', 'o');
hashMap.put('o', 'p');
hashMap.put('p', 'q');
hashMap.put('q', 'r');
hashMap.put('r', 's');
hashMap.put('s', 't');
hashMap.put('t', 'u');
hashMap.put('u', 'v');
hashMap.put('v', 'w');
hashMap.put('w', 'x');
hashMap.put('x', 'y');
hashMap.put('y', 'z');
hashMap.put('z', 'a');
Long startTime = System.currentTimeMillis();
String name = "abcdefghijklmnopqrstuvwxyz";
char[] stringCharArray = name.toCharArray();
Random random = new Random();
for (Integer i = 0; i <100000000; i++) {
{
for (Integer j = 0; j < random.nextInt(26) + 1; j++) {
stringCharArray[j] = (char) hashMap.get(stringCharArray[j]);
}
}
}
Long endtime = System.currentTimeMillis();
System.out.println(endtime-startTime+" ms");
}
Approach #3
#include <stdio.h>
#include <time.h>
#include <zconf.h>
#include <stdlib.h>
int main() {
long start = clock();
char name[] = "abcdefghijklmnopqrstuvwxyz";
for (int i = 0; i <100000000; i++) {
{
for (int j = 0; j < rand() % 25; j++) {
if (name[j] == 'z') {
name[j] = 'a';
} else {
name[j] = (char) (((int) (name[j])) + 1);
}
}
}
}
long stop = clock();
printf("time taken = %ld sec \n",( stop-start)/1000);
}
The runtime of approach 1 is ~ 8150 m, approach 2 is ~ 9700 ms and approach 3 is ~ 5400 ms. I am using MacBook Pro 2.3 GHz Intel Core i5 with 8 GB 2133 MHz LPDDR3.
How do I reduce this runtime, I used stream.parallelize() in java for apprach#2 to make the changes but the runtime was increasing. What am I doing wrong?
The goal is to get the runtime less than approach #3. Is there a way in C to parallelize this and solve in lesser time using pthreads?
