Reduce runtime for manipulating string multiple times using Hashmap / other methods
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?
java c++ performance c pthreads
New contributor
add a comment |
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?
java c++ performance c pthreads
New contributor
add a comment |
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?
java c++ performance c pthreads
New contributor
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?
java c++ performance c pthreads
java c++ performance c pthreads
New contributor
New contributor
edited 11 mins ago
New contributor
asked 50 mins ago
Amarjit Singh
992
992
New contributor
New contributor
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Amarjit Singh is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210794%2freduce-runtime-for-manipulating-string-multiple-times-using-hashmap-other-meth%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Amarjit Singh is a new contributor. Be nice, and check out our Code of Conduct.
Amarjit Singh is a new contributor. Be nice, and check out our Code of Conduct.
Amarjit Singh is a new contributor. Be nice, and check out our Code of Conduct.
Amarjit Singh is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f210794%2freduce-runtime-for-manipulating-string-multiple-times-using-hashmap-other-meth%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown