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