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

Question

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!

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.