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
> >
> >