Archived

This topic is now archived and is closed to further replies.

Optimize this function

This topic is 5753 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts


int WordToInteger(Word w)
{
// convert w into an integer based on the values of letters

int intnumber = 0;

for (int i = 0; i < w.numletters; ++i)
{
intnumber += Math.pow(10, w.numletters-i-1) * elementAt(w.letters[i].id);
}

return intnumber;
}

This function is used in solving cryptarithmetic problems to convert a word into an integer, so in most cases it''s called at least several thousand times. Needs to be a lot faster. It''s in java..converting to C would probably help, lol. The function elementAt runs constant and is basically just one line, but to keep abstraction i''m using a function call. I guess I''m looking for a way to speed up the 10^i call which is used to create a number one digit at a time. i.e. (10^0 * 5) + (10^1 * 2) = 25 I thought about doing bit-shifting instead of calling the power function, but then realized it only works in base 2. Any suggestions?

Share on other sites
Do it in reverse and keep a digit factor:

  int WordToInteger(Word w){    // convert w into an integer based on the values of letters    int intnumber = 0;    int digitfactor = 1;    for (int i = w.numletters-1; i >= 0; i--)    {        intnumber += digitfactor * elementAt(w.letters[i].id);        digitfactor *= 10;    }    return intnumber;}

No more pow(...) call. You probably want to make sure that the input passed in is valid too.

Cheers, dorix

Share on other sites
Thanks! Simple and effective. I just tried it... in a program that called that function over 150,000 times it reduced the running time from 1600 milliseconds to 300

Share on other sites
And pass by const-reference rather than value.

Share on other sites
I thought everything was passed by reference in Java.

Share on other sites
Yeah all non-primitive types are like pointers or references.. you don''t even have a choice. When you create a new instance of anything you have to call new.

Well that definitely helped... now i need to optimize other things and try to reduce the number of times i have to call that function.

Share on other sites
Nothing is pass by reference in Java. Java has no references. Everything is pass by value; it just happens that object variables are pointers to objects on the garbage collected heap, so are passed by pointer value.

Share on other sites

  int WordToInteger(Word w){  int intnumber = 0;  for (int i = 0; i < w.numletters; ++i)  {    intnumber = intnumber * 10 + elementAt (w.letters[i].id);  }  return intnumber;}

http 500 strike 1..

Share on other sites
Stoffel: Your version will not give the same result, you push all digits left then add the new one at the end(right).
Bigshot and dorix add new digits left of all the others.

Share on other sites
Ah, you are correct. When I''ve worked with hashing strings before, the first letter is the most significant so my method is the one I use. This will give the same output:

  int WordToInteger(Word w){  int intnumber = 0;  for (int i = w.numletters-1; i >= 0; i--)  {    intnumber = 10 * intnumber + elementAt(w.letters[i].id);  }return intnumber;}

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• Forum Statistics

• Total Topics
631782
• Total Posts
3002331
×