# Can Map operations be compiled or otherwise sped up for large lists?

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]], listY[[#[], 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]], listY[[#[], 1]]} & /@ selectedIndices;


Where we #[] and #[] 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]], listY[[#[], 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]], listY[[#[], 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!

• 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

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[]) 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.

• 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