RE: Appending to Lists
- To: mathgroup at smc.vnet.net
- Subject: [mg27118] RE: [mg27045] Appending to Lists
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.de>
- Date: Sun, 4 Feb 2001 02:58:53 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
-----Original Message----- From: James Jones [mailto:j.k.jones at dl.ac.uk] To: mathgroup at smc.vnet.net Subject: [mg27118] [mg27045] Appending to Lists Hi, I have a function that creates a list (a) from another list (b). The list elements are re-grouped in the new list according to a third list (c). A Position command is applied to list (c) for an element, then with this output the list (a) is created from list (b) at positions given by the element position data, list (c). This is repeated for the large number of elements in the original lists. The Position command is necessary as different elements appear in the list a different number of times. However, with the large number of elements in the lists (approx 50,000 for a simple list), this method is _very_ slow. If any one can give me help in speeding this process up I would be very grateful. The data sets would look like this b c 0.2 1 0.6 2 1.2 3 -0.2 1 0.5 2 0.3 1 0.7 2 -0.2 1 -0.6 1 A List would then be created from this data ( the list (a) ) containing vectors for 1, 2 and 3. The data in (b) is not important, and the order in which elements in (c) drop out is not set. In this case the (a) list should look like a = { { 0.2, -0.2, -0.2, -0.6} , {0.6, 0.5, 0.7} , { 1.2 } } My current function looks like this Do[AppendTo[xfinal, Flatten[Part[X, #] & /@ Position[Global`PARTICLE, i]]], {i, 1, Max[PARTICLE]}]; where xfinal is an (a) list, i.e. to be created. X is the (b) list , i.e. to be addressed, and PARTICLE is the (c) list. It is referenced by number. and it is very slow! Also, after producing this list, the different vector elements need to be made the same length, and so 0.0 are added to the ends of all vector elements shorter than the longest. My current function for doing this looks like table = Table[0.0, {Length[First[long]]}]; Print["Table Created!"]; Do[If[Length[Part[xfinal, i]] < Length[First[long]], AppendTo[Part[xfinal, i], Drop[table, (Length[Part[xfinal, i]])] ]], {i, 2, Length[xfinal]}]; where list (long) just sorts the list elements according to length. This function is also very slow, and I was wondering, again, if anyone knew a faster way of implementing this. Is the production of a table, once, and then dropping bits off and appending the fastest method? Of course this needs to be done tens of thousands of times per set of data so any small speed increase would be very helpful ;-> Again, any help much appreciated, James Jones Daresbury Laboratory Dear James, deplorably, in my last reply I left out the timingd for the sort/split version. Here are my more complete records: Prog In[1]:= b = {0.2, 0.6, 1.2, -0.2, 0.5, 0.3, 0.7, -0.2, -0.6}; In[2]:= c = {1, 2, 3, 1, 2, 1, 2, 1, 1}; In[3]:= Position[c, 1] Out[3]= {{1}, {4}, {6}, {8}, {9}} In[4]:= Part[b, #] & /@ Position[c, 1] Out[4]= {{0.2}, {-0.2}, {0.3}, {-0.2}, {-0.6}} In[5]:= Flatten[Part[b, #] & /@ Position[c, 1]] Out[5]= {0.2, -0.2, 0.3, -0.2, -0.6} In[6]:= l = Flatten[Part[b, #] & /@ Position[c, #]] & /@ Range[3] Out[6]= {{0.2, -0.2, 0.3, -0.2, -0.6}, {0.6, 0.5, 0.7}, {1.2}} In[7]:= maxlen = Max @@ Length /@ l Out[7]= 5 In[8]:= PadRight[#, maxlen, 0.] & /@ l Out[8]= {{0.2, -0.2, 0.3, -0.2, -0.6}, {0.6, 0.5, 0.7, 0., 0.}, {1.2, 0., 0., 0., 0.}} In[9]:= Transpose[{c, b}] Out[9]= {{1, 0.2}, {2, 0.6}, {3, 1.2}, {1, -0.2}, {2, 0.5}, {1, 0.3}, {2, 0.7}, {1, -0.2}, {1, -0.6}} In[10]:= Split[Sort@Transpose[{c, b}], First[#1] === First[#2] &] Out[10]= {{{1, -0.6}, {1, -0.2}, {1, -0.2}, {1, 0.2}, {1, 0.3}}, {{2, 0.5}, {2, 0.6}, {2, 0.7}}, {{3, 1.2}}} In[11]:= l = Map[Last, Split[Sort@Transpose[{c, b}], First[#1] === First[#2] &], {2}] Out[11]= {{-0.6, -0.2, -0.2, 0.2, 0.3}, {0.5, 0.6, 0.7}, {1.2}} In[12]:= PadRight[#, maxlen, 0.] & /@ l Out[12]= {{-0.6, -0.2, -0.2, 0.2, 0.3}, {0.5, 0.6, 0.7, 0., 0.}, {1.2, 0., 0., 0., 0.}} In[13]:= t = Table[0.0, {Max @@ Length /@ l}] Out[13]= {0., 0., 0., 0., 0.} In[14]:= Join[#, Drop[t, Length[#]]] & /@ l Out[14]= {{-0.6, -0.2, -0.2, 0.2, 0.3}, {0.5, 0.6, 0.7, 0., 0.}, {1.2, 0., 0., 0., 0.}} In[16]:= With[{t0 = Table[0. , {3}]}, ReplacePart[t0, #2, #1] & @@@ Transpose[{c, b}]]//Transpose Out[16]= {{0.2, 0., 0., -0.2, 0., 0.3, 0., -0.2, -0.6}, {0., 0.6, 0., 0., 0.5, 0., 0.7, 0., 0.}, {0., 0., 1.2, 0., 0., 0., 0., 0., 0.}} Tests: Test of test: In[18]:= nWhat = 3; nEvents = 10; In[19]:= btest = Table[Random[Real, {-1, 1}], {nEvents}] Out[19]= {-0.691794, 0.813392, 0.396099, 0.164031, 0.61136, 0.839132, 0.646768, \ -0.976798, -0.31982, 0.526729} In[20]:= ctest = Table[Random[Integer, {1, nWhat}], {nEvents}] Out[20]= {1, 3, 2, 3, 2, 2, 3, 2, 1, 3} In[21]:= ltest = Flatten[Part[btest, #] & /@ Position[ctest, #]] & /@ Range[nWhat] Out[21]= {{-0.691794, -0.31982}, {0.396099, 0.61136, 0.839132, -0.976798}, {0.813392, 0.164031, 0.646768, 0.526729}} In[22]:= With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest] Out[22]= {{-0.691794, -0.31982, 0., 0.}, {0.396099, 0.61136, 0.839132, -0.976798}, {0.813392, 0.164031, 0.646768, 0.526729}} In[23]:= With[{ltest = Flatten[Part[btest, #] & /@ Position[ctest, #]] & /@ Range[nWhat]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]] Out[23]= {{-0.691794, -0.31982, 0., 0.}, {0.396099, 0.61136, 0.839132, -0.976798}, {0.813392, 0.164031, 0.646768, 0.526729}} In[24]:= With[{ltest = Map[Last, Split[Sort@Transpose[{ctest, btest}], First[#1] === First[#2] &], {2}]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]] Out[24]= {{-0.691794, -0.31982, 0., 0.}, {-0.976798, 0.396099, 0.61136, 0.839132}, {0.164031, 0.526729, 0.646768, 0.813392}} In[25]:= With[{t0 = Table[0., {nWhat}]}, ReplacePart[t0, #2, #1] & @@@ Transpose[{ctest, btest}]] // Transpose Out[25]= {{-0.691794, 0., 0., 0., 0., 0., 0., 0., -0.31982, 0.}, {0., 0., 0.396099, 0., 0.61136, 0.839132, 0., -0.976798, 0., 0.}, {0., 0.813392, 0., 0.164031, 0., 0., 0.646768, 0., 0., 0.526729}} Test 3 Particles or Counters, 100,000 events: In[26]:= nWhat = 3; nEvents = 100000; In[27]:= btest = Table[Random[Real, {-1, 1}], {nEvents}]; In[28]:= ctest = Table[Random[Integer, {1, nWhat}], {nEvents}]; In[29]:= Timing[With[{ltest = Flatten[Part[btest, #] & /@ Position[ctest, #]] & /@ Range[nWhat]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[29]= 1.352 Second In[30]:= Timing[With[{ltest = Map[Last, Split[Sort@Transpose[{ctest, btest}], First[#1] === First[#2] &], {2}]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[30]= 5.207 Second In[31]:= Timing[With[{t0 = Table[0., {nWhat}]}, ReplacePart[t0, #2, #1] & @@@ Transpose[{ctest, btest}]] // Transpose][[1]] Out[31]= 2.383 Second Test 30 Particles or Counters, 100,000 events: In[32]:= nWhat = 30; nEvents = 100000; In[33]:= btest = Table[Random[Real, {-1, 1}], {nEvents}]; In[34]:= ctest = Table[Random[Integer, {1, nWhat}], {nEvents}]; In[35]:= Timing[With[{ltest = Flatten[Part[btest, #] & /@ Position[ctest, #]] & /@ Range[nWhat]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[35]= 3.585 Second In[36]:= Timing[With[{ltest = Map[Last, Split[Sort@Transpose[{ctest, btest}], First[#1] === First[#2] &], {2}]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[36]= 5.418 Second In[37]:= Timing[With[{t0 = Table[0., {nWhat}]}, ReplacePart[t0, #2, #1] & @@@ Transpose[{ctest, btest}]] // Transpose][[1]] Out[37]= 4.346 Second Test 300 Particles or Counters, 30,000 events: In[38]:= nWhat = 300; nEvents = 30000; In[39]:= btest = Table[Random[Real, {-1, 1}], {nEvents}]; In[40]:= ctest = Table[Random[Integer, {1, nWhat}], {nEvents}]; In[41]:= Timing[With[{ltest = Flatten[Part[btest, #] & /@ Position[ctest, #]] & /@ Range[nWhat]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[41]= 9.534 Second In[42]:= Timing[With[{ltest = Map[Last, Split[Sort@Transpose[{ctest, btest}], First[#1] === First[#2] &], {2}]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[42]= 1.582 Second In[43]:= Timing[With[{t0 = Table[0., {nWhat}]}, ReplacePart[t0, #2, #1] & @@@ Transpose[{ctest, btest}]] // Transpose][[1]] Out[43]= 3.866 Second Test 1000 Particles or Counters, 10,000 events: In[44]:= nWhat = 1000; nEvents = 10000; In[45]:= btest = Table[Random[Real, {-1, 1}], {nEvents}]; In[46]:= ctest = Table[Random[Integer, {1, nWhat}], {nEvents}]; In[47]:= Timing[With[{ltest = Flatten[Part[btest, #] & /@ Position[ctest, #]] & /@ Range[nWhat]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[47]= 15.853 Second In[48]:= Timing[With[{ltest = Map[Last, Split[Sort@Transpose[{ctest, btest}], First[#1] === First[#2] &], {2}]}, With[{maxlen = Max @@ Length /@ ltest}, PadRight[#, maxlen, 0.] & /@ ltest]]][[1]] Out[48]= 0.581 Second In[49]:= Timing[With[{t0 = Table[0., {nWhat}]}, ReplacePart[t0, #2, #1] & @@@ Transpose[{ctest, btest}]] // Transpose][[1]] Out[49]= 4.887 Second So we see that the sort/split version is unaffected by the no of particles (or counters?) but is not the best in any circumstances. -- Hartmut Wolf