Re: Sorting problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg20156] Re: [mg20071] Sorting problem*From*: kewjoi at hixnet.co.za (Kew Joinery)*Date*: Sat, 2 Oct 1999 03:05:11 -0400*References*: <7sv0o6$244@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Hello, With all the respect to Mr. Kozlowski?s words just to add this: Sometimes even from innocent posting one could learn something new and interesting (example- Langford problem), or probably find faster algorithm from old book. Here is an example when build-in function is much slower then custom implementation using well-known formula from old book:(I took the code from the updated Combinatorica package.) *this is the build-in Stirling(2) code: In[2]:= StirlingS2[1234,100];//Timing Out[2]= {33.34 Second,Null} **this is the custom implementation: In[3]:= Stirling2[1234,100];//Timing Out[3]= {0.33 Second,Null} and the code was: In[1]:= Stirling2[n_Integer?Positive, k_Integer] := Sum [ (-1)^(k-i)*Binomial [k, i]*(i^n), {i, 1, k}]/k! Eugene. Andrzej Kozlowski wrote: > I don't want to sound rude but I do not think this problem is really so > interesting or very relevant to this group. Or rather, more precisely, this > kind of questions surface here from time to time but usually lead to > anything fruitful. The reasons are as follows. > > There is nothing at all mysterious about the theoretical question itself. It > is very well known and discussed in detail in Section 5.3.3 of Volume 3 of > Knuth's "The Art of Computer Programming" (1973 edition). The method is > described in Section 5.2.3 and called "tree selection". (the algorithm > itself is on page 142). This can be easily implemented in Mathematica but it > seems to me that is not much point doing so. The reason is that the actual > function you will get will almost certainly perform worse in real life than > something constructed using built in functions, even if it's theoretical > running time of the algorithm is worse. For example, here is one obvious > attempt: > > In[1]:= > secondlargest[l_] := Max[DeleteCases[l, Max[l]]] > > It seems to me that this should have the worst case running time of 3n-3, > but most likely will beat a user defined implementation of the best > algorithm. And if not than probably something similar will. It may be mildly > interesting to check this hypothesis but I have seen already enough evidence > that this sort of thing is true in general. Of course there is another > possible question here: would it be useful to have a built in implementation > of a (generalized) algorithm of this type? I guess it probably just wouldn't > be useful enough. > > In my opinion Mathematica has to be treated as a separate computing paradigm > and efficiency comparisons only make sense between different Mathematica > functions based on actual performance (which in any case may be platform > dependent). > > -- > Andrzej Kozlowski > Toyama International University > JAPAN > http://sigma.tuins.ac.jp > http://eri2.tuins.ac.jp > > ---------- > >From: Cheng Tsz Hei <s986001 at mailserv.cuhk.edu.hk> To: mathgroup at smc.vnet.net > >To: mathgroup at smc.vnet.net > >Subject: [mg20156] [mg20071] Sorting problem > >Date: Wed, Sep 29, 1999, 16:33 > > > > > Dear everybody, > > Here I have some interesting problem want to share with everyone. > > The problem is : > > there are n elements in the arrays and we would like to find the > > second smallest > > one in at most n + lgn - 2 comparsion in the worest case. > > anyone know the answer? > > > > Maths > > > >

**Re: greek alphabet**

**RE: creating input cell with unevaluated expression?**

**Re: Sorting problem**

**Re: Re: List-Selection**