PDA

View Full Version : Efficiency drain



ygfperson
07-12-2003, 03:10 PM
So I'm making changes to my Expression Manipulator program to allow more operators than the basic 4 and exponentiation. It basically uses a function that does a search and replace. ie:
3+4^5
becomes
add(3,expt(4,5))

The problem is that when deleting things in parentheses, after 5 of them, the program becomes horribly slow:
(((x/y)/z)/a)/b -- around 2 seconds. another layer of parentheses makes it 6 seconds

Is string manipulation really that time consuming? Or is it probably another piece of my program?

Zach L.
07-12-2003, 03:37 PM
String manipulation can be fairly expensive, depending on the string implementation. If you are using substring operations alot, you might want to try SGI's STL (www.sgi.com/tech/stl) implementation, and the "rope" class. Its faster with substring operations, but slower on some more traditional ones.

ygfperson
07-15-2003, 02:00 PM
hehe... found out the reason...

my test expression looks like this:
( ( ( 3 / 4 ) / 5 ) / 6 ) / 7

Everything in parentheses is ignored, then parsed recursively. Everything seperated by a '/' sign is a Term.

So I created a static int for the class Term and incremented it everytime a constructor was created. End result:
54149

With an extra layer of parentheses it became 415929. Add another layer:
(((((3/4)/5)/6)/7)/8)/9

2866334.

Obviously 2.8 million Term objects where 20 would suffice is a problem...

JaWiB
07-15-2003, 02:11 PM
Lol I guess that would drain efficiency just a bit

Zach L.
07-15-2003, 03:26 PM
Just a couple orders of magnitude. ;)

Barjor
07-15-2003, 03:33 PM
Do you want to work for Microsofts XP team?

Zach L.
07-15-2003, 03:52 PM
Originally posted by Barjor
Do you want to work for Microsofts XP team?

Haha! Great one.


Hang on a second though... There should only be (by my reckoning) twice the number of terms as delimiters... so 8, and 10... where are the other 3.2x10^93 coming from?

ygfperson
07-15-2003, 05:31 PM
There's some overlap... for instance there are four terms in ((x / y) / z): x, y, (x / y), and z

But you're right, I have way too many objects... and I gotta search through code to find out why.