I don't know....(2)
- To: mathgroup at smc.vnet.net
- Subject: [mg2431] I don't know....(2)
- From: bientin at cli.di.unipi.it (Paolo Bientinesi)
- Date: Wed, 8 Nov 1995 23:42:03 -0500
- Organization: Dipartimento di Informatica, Universita' di Pisa
Hi all,
I received in my own folder several suggestions for this problem:
having a list whose generic entry is {a,b} where "a" is a list
and "b" is an integer,
take the list entry corresponding to the biggest integer.
I would like to summarize the ideas:
Bert Van der Zwet, Paul Rubin and Eberhard Lange propose similar
procedures, always using the Sort function applyed to the integer
part of the list, then in the first pair there is what we need.
Will Self and his teacher on the contrary propose to use the Max
function with Position: after having calculated the biggest integer
they find the position or positions of this in the list.
It's easy to image that for short lists the first kind of algorithms
is faster, but speaking about complexity they cost O(n log n), where
"n" is the length of the list, while the second ones cost O(n),
so even if they uses more functions, they will be faster for big lists.
It's possible to improve the second kind of algorithms too:
they need two scans of the list, so the real computational cost
is O(2 n), I thought that rewriting the function Max keeping track
of the position of the Max, a single scan O(n) of the list suffices:
MaxPos[list_] :=
Module[{aux, pos, i},
aux = list[[1]]; pos = {}; i = 1;
Map[
(Which[# > aux, aux = #; pos = List[i],
# == aux, pos = Join[pos, List[i]];
i = i + 1)&,
list];
{aux, pos}
]
(this algorithm is sligthly better than the usual "while" one, too)
Probably the betterments of this algorithms are difficult to see
in reality because it needs a lot of istructions.
I made some experiments with 15000 and 50000 entries and the Self
algorithm was the fastest.
Thank to all the suggestors
Paul