Re: sorting a nested list of 4-tuples

*To*: mathgroup at smc.vnet.net*Subject*: [mg120359] Re: sorting a nested list of 4-tuples*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 20 Jul 2011 06:31:19 -0400 (EDT)*References*: <201107191055.GAA10229@smc.vnet.net>

On 07/19/2011 05:55 AM, Luis Valero wrote: > Dear Sirs, > > I want to sort a list of 4-tuples of real numbers, so that, the second 4-tuple has minimum distance to the first, the third, selected from the rest, ha minimum distance to the second, and so on. > > The distance is the euclidean distance, calculated with the first two elements of each 4-tuple. > > I have defined a function that work: > > orderedList[list_] := Module[{nearest}, > Flatten[ Nest[{ > Append[ #[[1]] , nearest = Flatten @@ Nearest[ Map[ Rule[ #[[{1, 2}]], #]&, #[[2]] ], Last[ #[[1]] ] [[{1, 2}]], 1] ], > Delete[ #[[2]], Position[ #[[2]], nearest ] ] }&, { {list[[1]] }, Delete[ list, 1 ] }, Length[ list ] - 2], 1] ]; > > > but I need to improve the temporal efficiency > > Thank you The complexity will show up either in needing to obtain a growing number of nearest items (to account for the fact that many may already ahve appeared), or removing selected items from further consideration. There may be a fancy way around these but I'm not seeing it offhand. At least not if we want to couple with a fast search for nearest items, using Nearest[]. A way to alleviate this is to gather newly selected items every so often and remove them in one shot. This adds to the coding complexity (required some debugging to get it to work, for one thing). But it does seem faster. I made no effort to tune for the removal interval (which need not be constant). There ar also some parts of the code that might be made slightly faster in other ways. n = 3000; data = RandomReal[{-100, 100}, {n, 4}]; chunksize = Ceiling[Log[n]]^2; denom = 10000.; moddata = Map[Take[#, 3] &, MapThread[Prepend, {data, Range[n]/denom}]]; nf = Nearest[moddata]; next = moddata[[1]]; taken = ConstantArray[False, n]; result = ConstantArray[{0., 0., 0., 0.}, n]; remove = ConstantArray[{0., 0., 0.}, chunksize]; result[[1]] = data[[1]]; remove[[1]] = moddata[[1]]; taken[[1]] = True; Timing[Do[ nextset = nf[next, 1 + Mod[j, chunksize, 1]]; posns = Round[denom*Map[First, nextset]]; k = 1; While[k < Length[nextset] && taken[[posns[[k]]]], k++;]; taken[[posns[[k]]]] = True; result[[j]] = data[[posns[[k]]]]; next = nextset[[k]]; remove[[Mod[j, chunksize, 1]]] = next; If[Mod[j, chunksize] == 0, done = True; posns = Apply[Alternatives, remove]; moddata = DeleteCases[moddata, posns]; nf = Nearest[moddata]; ]; , {j, 2, n}]] Out[639]= {0.57, Null} By comparison: In[640]:= Timing[result2 = orderedList[data];] Out[640]= {14.71, Null} In[641]:= result2 === result Out[641]= True Daniel Lichtblau WOlfram Research

**References**:**sorting a nested list of 4-tuples***From:*Luis Valero <luis.valero@mac.com>