Re: Sorting problem
- To: mathgroup at smc.vnet.net
- Subject: [mg20158] Re: [mg20071] Sorting problem
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Sat, 2 Oct 1999 03:05:12 -0400
- Sender: owner-wri-mathgroup at wolfram.com
I agree. However my point was different. I meant conditions like "n + lg(n) - 2 comparisons" are not really very relevant in the case of Mathematica programming since we really can't control what goes on internally. On the other hand I now believe the author of the message was not interested in a Mathematica program, just the algorithm. The standard thing to do in such cases is first to check Knuth's book. This algorithm is in fact pretty obvious; it is the proof that there can't be a better one that is interesting. But this has even less to do with Mathematica. -- Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp http://eri2.tuins.ac.jp ---------- >From: kewjoi at hixnet.co.za (Kew Joinery) >To: Andrzej Kozlowski <andrzej at tuins.ac.jp>, "mathgroup at smc.vnet.net" <mathgroup at smc.vnet.net> >Subject: [mg20158] Re: [mg20071] Sorting problem >Date: Fri, 01 Oct 1999 01:28:43 +0200 > > 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 fr om 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: [mg20158] [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 >> > >> > > > >