MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

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





  • Prev by Date: PDE & Complex solving problem
  • Next by Date: 2 gifs side by side -- with hyperlinks
  • Previous by thread: Re: PDE & Complex solving problem
  • Next by thread: RE: Why is my Implementation of Sorted Trees So Slow?