Archived

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

Bigshot

Optimize this function

Recommended Posts

Bigshot    122

  
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 this post


Link to post
Share on other sites
dorix    484
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 this post


Link to post
Share on other sites
Bigshot    122
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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
I thought everything was passed by reference in Java.

Share this post


Link to post
Share on other sites
Bigshot    122
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 this post


Link to post
Share on other sites
DrPizza    160
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 this post


Link to post
Share on other sites
Stoffel    250

  
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 this post


Link to post
Share on other sites
Kern    124
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 this post


Link to post
Share on other sites
Stoffel    250
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;
}

Share this post


Link to post
Share on other sites
SabreMan    504
quote:
Original post by Anonymous Poster
I thought everything was passed by reference in Java.

Sorry, I didn't read the entire question and my "C++ cultural assumption" kicked in.
quote:
Original post by DrPizza
Nothing is pass by reference in Java. Java has no references.

Rubbish. Any Java program has references all over the place (whether you call them references or pointers is a different question, albeit a silly one in Java).
quote:

Everything is pass by value

Semantic trickery. If a value is passed into a function, it is passed by copying a reference to a stack-allocated variable (which are nearly always references). Or, if you prefer a different terminology, a new variable is bound to the same value. This has always been known as pass-by-reference.

[edited by - SabreMan on October 22, 2002 5:07:32 AM]

Share this post


Link to post
Share on other sites
OrangyTang    1298
quote:
"(whether you call them references or pointers is a different question, albeit a silly one in Java)."


Pointers you can do pointer arithmatic on, references you can''t.

Share this post


Link to post
Share on other sites
SabreMan    504
quote:
Original post by OrangyTang
Pointers you can do pointer arithmatic on, references you can''t.


Please explain how to perform pointer arithmetic in Java.

Share this post


Link to post
Share on other sites
OrangyTang    1298
You can''t, thats my point: Java replaces pointers by references and forbids you from doing pointer arithmatic. Hence the difference between pointers and references being more than just personal naming preference as you suggest.

Share this post


Link to post
Share on other sites
SabreMan    504
quote:
Original post by OrangyTang
You can''t, thats my point

That''s funny, "Pointers you can do pointer arithmatic on" sounds like the exact opposite of that.
quote:

Java replaces pointers by references and forbids you from doing pointer arithmatic.

Not quite. In Java terminology, there is a single concept which gets called both pointers and references by different people. I''m saying that the argument of what the concept should be called isn''t very useful.
quote:

Hence the difference between pointers and references being more than just personal naming preference as you suggest.

There is little semantic difference between pointer and reference - pointers are used to implement references. C++ is an curiosity in having separate syntactic constructs for pointer and reference. It''s a distinction which doesn''t exist in Java, and therefore the construct can equally be called either "pointer" or "reference". Which one to use has been the source of much boring debate.

Share this post


Link to post
Share on other sites