Why is my Implementation of Sorted Trees So Slow?
- To: mathgroup at smc.vnet.net
- Subject: [mg36485] Why is my Implementation of Sorted Trees So Slow?
- From: Husain Ali Al-Mohssen <husain at MIT.EDU>
- Date: Sun, 8 Sep 2002 03:31:37 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Hi all,
I am trying to implement a very simple sorted tree to quickly store some
real numbers I need. I have written an add, delete, minimum, and pop
(delete the lowest value) function and they seem to work ok but are very
slow. Let's just look @ my implementation of the add part:
nums=Null;(*my initial blank Tree)
In[326]:=
Clear[add]
In[327]:=
add[Null,x_Real]:=node[x,Null,Null]
add[Null,node[x_Real,lower_,higher_]]=node[x,lower,higher]
In[328]:=
add[node[x_Real,lower_,higher_],y_Real]:=
If[x>y,node[x,add[lower,y],higher],node[x,lower,add[higher,y]]]
In[288]:=
add[node[x_Real,lowerx_,higherx_],node[y_Real,lowery_,highery_]]:=If[x>y,
node[x,add[lowerx,node[y,lowery,highery]],higherx],
node[x,lowerx,add[higherx,node[y,lowery,highery]]]
]
Now this is my attempt to test how fast my add works:
SeedRandom[5];
Do[nums=add[nums,Random[]],{5000}];//Timing
Out[333]=
{13.279 Second,Null}
(running on Mathematica 4.1 on a win2k VMWare machine running on Linux RH7.3
running on an 1.4GHz Athlon with 1GB of ram).
Questions:
1. Is this as fast as I can get my code to run?
2. Am I doing something obviously stupid?
3. would Compiling things help?
Thanks,
Husain