Re: Again, How to speed up this calculation? and more

*To*: mathgroup at smc.vnet.net*Subject*: [mg37262] Re: [mg37246] Again, How to speed up this calculation? and more*From*: Sseziwa Mukasa <mukasa at jeol.com>*Date*: Mon, 21 Oct 2002 02:29:24 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

On Friday, October 18, 2002, at 05:17 AM, Cheng Liu wrote: > Dear group, > > Thank you all for the responses. I might not make my question > very clear. Suppose that I have a list of points {p1,p2, ..., pn}, I > try > to find all possible pairs of them. The pairs may include {pi,pi}, but > {pi,pj} and {pj,pi} are considered the same and only one is counted. > > That said. After some try and error, I came to the following > way: > > h=4;w=5; > points=Flatten[Outer[List,Range[w],Range[h]],1]; > > pairs=Flatten[Map[Outer[List,{#},Drop[points,Position[points,#][[1,1]]- > 1],1][[1]]&,points],1]; > > The speed of the above calculation is reasonably fast. But I run into > the > memory problem. For example, for h=64 and w=64, the length of the list > pairs will be w*h (w*h+1)/2 = 8,390,656. In my case, The numbers for > h and > w will be a lot larger than 64. How can I get around this memory > problem > or that's the dead end for my calculation (I do have 1 GB physical mem > in > my machine)? Thanks a lot. > > The only way to get around the memory limitation is not to compute all the pairs at once. As you have already pointed out the size of the resulting list is of order (w*h)^2 which will quickly exhaust the physical memory (and for 32 bit systems the virtual memory) before w and h get very large. If you only need to operate on one pair at a time use NextKSubset to generate the distinct pairs (A,B) where A ¡Á B one at a time and then loop over each point to operate on the pairs of form (A,A). Of course whatever you do with this set will take a long time to compute simply because of the size of the data. If you need to operate on more than one pair at a time: nthpair[lst_,n_]:=With[{k=PadLeft[IntegerDigits[n- 1,Length[lst]],2]+1},{lst[[k[[1]]]],lst[[k[[2]]]]}] will return the nth element in the list of pairs in lexicographic order. Regards, Sseziwa