Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'm performing a series of Map operations in the following script:

inputList = Table[RandomReal[100, {60, 2}], {i, 1, 10^3}];
scalingFactor = 10;
i = 1;
listX = Round[scalingFactor*Table[{inputList[[i, k]], # - inputList[[i, k]] & /@ inputList[[i]]}, {k, 1, Length[inputList[[i]]]}]];
i = 2;
listY = Round[scalingFactor*Table[{inputList[[i, k]], # - inputList[[i, k]] & /@ inputList[[i]]}, {k, 1, Length[inputList[[i]]]}]];

selectedIndices = RandomInteger[{1, 30}, {10^3, 2}];
pairList = {listX[[#[[1]], 1]], listY[[#[[2]], 1]]} & /@ selectedIndices;

The above code is mostly meant to illustrate the kind of Map operations I'm doing, however, a description of what's going on would be as follows:

(1) We first generate inputList, which, at the outermost level, contains $10^3$ lists, each with $60$ pairs of real numbers (the pairs are of the form: {RandomReal[{0,100}],RandomReal[{0,100}]}).

(2) listX and listY, computed in precisely the same way but for different lists in inputList (with indices $i = 1$ and $2$, respectively), generate $60$ two-element lists (one for each point in inputList[[i]]) that look like this:

listXexample = {{{440, 663}, {{0, 0}, {467, 333}, {376, -548}, {-178, -128}, {-254, -560}, {262, -533}, {-203, 202}, {63, -68}, {160, -604}, {382, -187}, {471, -162}, {-292, 336}, {-317, -196}, {-75, 253}, {-199, -125}, {-214, -543}, {246, -456}, {363, -455}, {-366, 235}, {-178, 309}, {211, 255}, {27, -360}, {495, -458}, {-34, -452}, <<12>>, {-259, -133}, {-232, 103}, {-375, -387}, {-98, -455}, {253, -548}, {233, -418}, {207, 245}, {367, -100}, {107, 19}, {419, -85}, {324, -526}, {465, -434}, {-342, -506}, {216, 35}, {452, 254}, {-252, 215}, {307, -110}, {-344, 277}, {387, -449}, {-62, -542}, {140, -78}, {-249, -49}, {-66, -425}, {-251, 175}}}, <<58>>, {<<1>>, {<<1>>}}};   

The first element in each list, e.g. {440, 663} as above, represents a chosen element, and the second element represents a list of the differences between this chosen element and all other elements in inputList[[i]], e.g. # - {440, 663} in the above example. All values in these lists are then rounded, as shown.

(3) pairList is computed by taking a (here random) set of integer indices of the form {{20,40},{40,15},...}, and then performing the mapping operation:

pairList = {listX[[#[[1]], 1]], listY[[#[[2]], 1]]} & /@ selectedIndices;

Where we #[[1]] and #[[2]] represents the first and second element, respectively, in a particular integer pair in selectedIndices.

To simulate the script inputs, we're using the following randomly generated test values:

scalingFactor = 10;
inputList = Table[RandomReal[100, {60, 2}], {i, 1, 10^3}];
selectedIndices = RandomInteger[{1, 30}, {10^3, 2}];

As well as the $i = (1,2)$ values.




Is there a way to compile and speed up the sort of Map operations above?


Also, can anyone replicate my finding that changing:

inputList = Table[RandomReal[100, {50, 2}], {i, 1, 10^3}];

To:

inputList = Table[RandomReal[100, {100, 2}], {i, 1, 10^3}];

Counterintuitively halves the effective time to compute:

pairList = {listX[[#[[1]], 1]], listY[[#[[2]], 1]]} & /@ selectedIndices

Why would this happen?




Update: Running Mr. Wizard's reformulated code:

inputList = RandomReal[100, {1000, 60, 2}];
selectedIndices = RandomInteger[{1, 30}, {10^3, 2}];
scalingFactor = 10;

t1 = AbsoluteTime[];

i = 1;
listX = Round[scalingFactor*Table[{inputList[[i, k]], # - inputList[[i, k]] & /@ inputList[[i]]}, {k, 1, Length[inputList[[i]]]}]];
i = 2;
listY = Round[scalingFactor*Table[{inputList[[i, k]], # - inputList[[i, k]] & /@ inputList[[i]]}, {k, 1, Length[inputList[[i]]]}]];

myPairList = {listX[[#[[1]], 1]], listY[[#[[2]], 1]]} & /@ selectedIndices;



t2 = AbsoluteTime[];

f1[m_] := With[{t = m\[Transpose]}, {m, Subtract[t, #]\[Transpose] & /@ m}\[Transpose]]

{listX, listY} = Round[scalingFactor * f1 /@ inputList[[{1, 2}]]];

pairList = {listX[[#, 1]], listY[[#2, 1]]}\[Transpose] & @@ (selectedIndices\[Transpose])


t3 = AbsoluteTime[];


myPairList == pairList

Outputs True.

We can also note that the timing for my code vs. Mr. Wizard's

myTiming = t2 - t1
mrWizardTiming = t3 - t2

Is about $\approx 65$ milliseconds (me) and $\approx 3$ milliseconds (Mr. Wizard), respectively. Nicely done Mr. Wizard!

share|improve this question
    
It would be helpful to provide a written description of your operation in addition to the code. –  Mr.Wizard Sep 22 '13 at 8:06
    
@Mr.Wizard Absolutely Mr. Wizard. –  RM1618 Sep 22 '13 at 8:10
    
You are using only the first part of each sublist in listX or listY, meaning that none of the difference data ends up in pairList. Shall I assume this is correct, and that listX and listY must be generated as shown for use elsewhere? –  Mr.Wizard Sep 22 '13 at 8:42
    
@Mr.Wizard That's correct - this is a representative snippet from a larger piece of code, I just wanted to accurately portray the data structures I'm using. –  RM1618 Sep 22 '13 at 8:45
    
Please see my answer and try it on your larger data set. I could not replicate the final example in your question, but I am using version 7 and things may have changed. –  Mr.Wizard Sep 22 '13 at 8:47
show 2 more comments

1 Answer 1

Here is my refactoring of your code:

inputList       = RandomReal[100, {1000, 60, 2}];
selectedIndices = RandomInteger[{1, 30}, {10^3, 2}];
scalingFactor   = 10;

f1[m_] := With[{t = m\[Transpose]}, {#, Subtract[t, #]\[Transpose]} & /@ m]

{listX, listY} = Round[scalingFactor * f1 /@ inputList[[{1, 2}]]];

pairList = {listX[[#, 1]], listY[[#2, 1]]}\[Transpose] & @@ (selectedIndices\[Transpose])

My basic approach was to shift processing into vector/array operations on larger chunks of data. To that end I used Transpose to allow pairwise subtraction from the entire block (i.e. inputList[[1]]) at once. This means that there is essentially one loop in place of two at least in terms of high level constructs. Here is a self-contained example:

s1 = Partition[CharacterRange["a", "z"], 2] ~Take~ 6;

Table[j - i, {i, s1}, {j, s1}]

Table[(s1\[Transpose] - i)\[Transpose], {i, s1}]

I used Table instead of Map for both to emphasize the difference. Note that this is somewhat wasteful as s1 is repeatedly transposed; I used With in my f1 function to prevent this.

Likewise for pairList I transposed selectedIndices to get two vectors, positions to extract from each listX and listY and passed them using Apply and Function. This removes a top-level loop (Map) completely and lets vector-optimized Part work efficiently. I then use a second Transpose to reshape the data as desired.

share|improve this answer
    
I updated my question comparing the result of my code with yours and I noticed a discrepancy? I apologize - it was a bit too long to do that in comment form. Let me know if I'm messing something up on my end. –  RM1618 Sep 22 '13 at 8:55
    
@RM1618 Adding such things to the question is the correct way. Let me take a look at it. –  Mr.Wizard Sep 22 '13 at 8:57
    
@RM1618 You somehow lost both \[Transpose] symbols in my pairList line, but correctly preserved them in the f1 definition. If you add those two the results should match. –  Mr.Wizard Sep 22 '13 at 9:01
    
Got it, and you achieved a speedup of over an order of magnitude! If you feel like it, could you offer some pointers about why this is so much faster? –  RM1618 Sep 22 '13 at 9:11
    
@RM1618 Thanks for the vote, but you might wait longer to Accept; someone else may give you a better solution if you do not discourage looking at the question. I'll add a few comments to my answer for explanation. –  Mr.Wizard Sep 22 '13 at 9:12
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.