Getting rid of "if condition" by some math equation.
in [Java Programming]
|
Prev: MAKE UPTO $5000 MONTHLY! $2000 INYOUR FIRST 30 DAYS!
Next: help: enum cause failure in multi thread run
From: Patricia Shanahan on 14 Jul 2010 16:36 Sanny wrote: .... > > I am thinking of using > > char mm='-'; > int mm1=Character.getNumericValue(mm); > > int mm2=Str.charAt(0); > > int mm3=mm2-mm1; Have you considered a lookup-table? It would have 65536 elements, but most of the accesses would probably be concentrated in a few areas, so it would be quite cache-friendly. You could map to e.g. 1 for "-" and 0 for anything else, then do arithmetic on the lookup result. Patricia
From: Daniel Pitts on 14 Jul 2010 17:04 On 7/14/2010 11:16 AM, Sanny wrote: > I use String comparision and if "str.charat() is not '-'" > > We add bit value to xx. > > The below code takes long time as we need to do 50 "if" comparisions > each time the function is called. > > Below is the sample Java Code: > > ================================ > > long xx=0; long bit=1; I'm going to take the liberty of replacing this with a for loop: for (int i = str.length()-1; i>=0; --i) { if (str.charAt(i) != '-') { xx += bit; } bit += bit; // equiv of bit <<= 1; } > ================================ > > Since most of the time taken is by the "if condition." What evidence do you have to support that? What is "a long time" to you? I would imagine this method executes in under a millisecond. What tools have you used to determine the speed? > > I am thinking of using > > char mm='-'; > int mm1=Character.getNumericValue(mm); > > int mm2=Str.charAt(0); > > int mm3=mm2-mm1; > > Now if I subtract mm2-mm1=mm3 Then I have to have xx+=bit; only when > mm3==0; > > I want to write an Math Equation that computes mm3 and when mm3 value > is "0" xx+=bit; is done. > > I am not getting the clue how to develop this equation to get rid of > the "If conditions" > > Please suggest some equation or any other way to do this in one > statement. > > ENUMERATION? can these be used here to solve these "if conditions" in > one step? > > Bye > Sanny You have a conditional operation, so you need to handle it. My guess is that you are barking up the wrong tree with this form of micro optimization. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Sanny on 14 Jul 2010 17:11 > Have you considered a lookup-table? It would have 65536 elements, but > most of the accesses would probably be concentrated in a few areas, so > it would be quite cache-friendly. You could map to e.g. 1 for "-" and 0 > for anything else, then do arithmetic on the lookup result. Problem Solved. I tried a lookup table and now all if conditions have been removed. Now its just a piece of addition. Which quite fast 3-4 times faster than the if conditions. Bye Sanny
From: Daniel Pitts on 14 Jul 2010 18:30 On 7/14/2010 2:11 PM, Sanny wrote: > >> Have you considered a lookup-table? It would have 65536 elements, but >> most of the accesses would probably be concentrated in a few areas, so >> it would be quite cache-friendly. You could map to e.g. 1 for "-" and 0 >> for anything else, then do arithmetic on the lookup result. > > Problem Solved. I tried a lookup table and now all if conditions have > been removed. > > Now its just a piece of addition. Which quite fast 3-4 times faster > than the if conditions. I doubt it. A lookup table requires a dereference and a multiplication. I *really* think you need to make sure you're not complicating a simple piece of code for little actual gain. Measure twice, cut once. -- Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
From: Tom Anderson on 14 Jul 2010 18:46
On Wed, 14 Jul 2010, Sanny wrote: > I use String comparision and if "str.charat() is not '-'" > > We add bit value to xx. > > The below code takes long time as we need to do 50 "if" comparisions > each time the function is called. > > Below is the sample Java Code: > > ================================ > > long xx=0; long bit=1; > > if (Str.charAt(50)!='-') xx+=bit;bit++; > if (Str.charAt(49)!='-') xx+=bit;bit++; > if (Str.charAt(48)!='-') xx+=bit;bit++; > if (Str.charAt(47)!='-') xx+=bit;bit++; > if (Str.charAt(46)!='-') xx+=bit;bit++; > if (Str.charAt(45)!='-') xx+=bit;bit++; > if (Str.charAt(44)!='-') xx+=bit;bit++; > if (Str.charAt(43)!='-') xx+=bit;bit++; > if (Str.charAt(42)!='-') xx+=bit;bit++; > if (Str.charAt(41)!='-') xx+=bit;bit++; > if (Str.charAt(40)!='-') xx+=bit;bit++; > if (Str.charAt(39)!='-') xx+=bit;bit++; > if (Str.charAt(38)!='-') xx+=bit;bit++; > if (Str.charAt(37)!='-') xx+=bit;bit++; > if (Str.charAt(36)!='-') xx+=bit;bit++; > if (Str.charAt(35)!='-') xx+=bit;bit++; > if (Str.charAt(34)!='-') xx+=bit;bit++; > if (Str.charAt(33)!='-') xx+=bit;bit++; > if (Str.charAt(32)!='-') xx+=bit;bit++; > if (Str.charAt(31)!='-') xx+=bit;bit++; > if (Str.charAt(30)!='-') xx+=bit;bit++; > if (Str.charAt(29)!='-') xx+=bit;bit++; > if (Str.charAt(28)!='-') xx+=bit;bit++; > if (Str.charAt(27)!='-') xx+=bit;bit++; > if (Str.charAt(26)!='-') xx+=bit;bit++; > if (Str.charAt(25)!='-') xx+=bit;bit++; > if (Str.charAt(24)!='-') xx+=bit;bit++; > if (Str.charAt(23)!='-') xx+=bit;bit++; > if (Str.charAt(22)!='-') xx+=bit;bit++; > if (Str.charAt(21)!='-') xx+=bit;bit++; > if (Str.charAt(20)!='-') xx+=bit;bit++; > if (Str.charAt(19)!='-') xx+=bit;bit++; > if (Str.charAt(18)!='-') xx+=bit;bit++; > if (Str.charAt(17)!='-') xx+=bit;bit++; > if (Str.charAt(16)!='-') xx+=bit;bit++; > if (Str.charAt(15)!='-') xx+=bit;bit++; > if (Str.charAt(14)!='-') xx+=bit;bit++; > if (Str.charAt(13)!='-') xx+=bit;bit++; > if (Str.charAt(12)!='-') xx+=bit;bit++; > if (Str.charAt(11)!='-') xx+=bit;bit++; > if (Str.charAt(10)!='-') xx+=bit;bit++; > if (Str.charAt(9)!='-') xx+=bit;bit++; > if (Str.charAt(8)!='-') xx+=bit;bit++; > if (Str.charAt(7)!='-') xx+=bit;bit++; > if (Str.charAt(6)!='-') xx+=bit;bit++; > if (Str.charAt(5)!='-') xx+=bit;bit++; > if (Str.charAt(4)!='-') xx+=bit;bit++; > if (Str.charAt(3)!='-') xx+=bit;bit++; > if (Str.charAt(2)!='-') xx+=bit;bit++; > if (Str.charAt(1)!='-') xx+=bit;bit++; > if (Str.charAt(0)!='-') xx+=bit;bit++; > > ================================ > > Since most of the time taken is by the "if condition." So, the fundamental problem is that you are insane. But you could do something like this: long xx = 0; for (int i = 0; i < 50; ++i) { int d = Str.charAt(i) ^ '-'; d = d | (d >> 8); d = d | (d >> 4); d = d | (d >> 2); d = d | (d >> 1); xx = (xx << 1) | (d & 1); } I don't think there's any other way to do this without a formal conditional. However, on some architectures, those can be compiled to predicate instructions. I assume the root of this is that you're worried about pipeline bubbles. Also, the insanity, of course. > I want to write an Math Equation that computes mm3 and when mm3 value is > "0" xx+=bit; is done. > > I am not getting the clue how to develop this equation to get rid of the > "If conditions" The Math Equation you need is built on an understanding that an integer is a vector of bits, and that you can use bitwise operators to carry out parallel mathematical operations on those bits. There are faster ways to do the bit-counting part than my sequence of shifts and ors, but those are in the realm of advanced binary voodoo, and i am not at liberty to reveal them to you. > Please suggest some equation or any other way to do this in one > statement. One statement? More difficult. > ENUMERATION? can these be used here to solve these "if conditions" in > one step? No. You could use a lookup table, though. tom -- I hate to advocate drugs, alcohol, violence, or insanity to anyone, but they've always worked for me. -- Hunter S. Thompson |