# Efficient computation of list mapping

I'm wondering about possible techniques to solve the following problem efficiently in Mathematica. Suppose you are given a list of integers that represent digits of a number with base 40. This list should be translated into digits with base 253, i.e., each 3 digits with base 40 should be translated into 2 digits with base 253. A simple solution is as follows.

l = RandomInteger[{0, 39}, 10000000];
Flatten@Map[IntegerDigits[#, 253] &,
Map[FromDigits[#, 40] &,
Partition[l, 3, 3, {1, 1}, {}]]]; // AbsoluteTiming
{5.16098, Null}


As an additional complication suppose the digits with base 253 should be permuted according to a given permutation f. Again this can simply be solved by

MapIndexed[(f[#2[[1]]] = #1) &, RandomSample[Range[0, 252]]];
Map[f[#] &,
Flatten@Map[IntegerDigits[#, 253] &,
Map[FromDigits[#, 40] &,
Partition[l, 3, 3, {1, 1}, {}]]]]; // AbsoluteTiming
{7.46978, Null}


How can the performance be improved in both cases?

Update 1

Minor improvement after combining the functions.

Flatten@Map[IntegerDigits[FromDigits[#, 40], 253] &,
Partition[l, 3, 3, {1, 1}, {}]]; // AbsoluteTiming
{4.32367, Null}


Update 2

Motivated by MarcoB's answer, I came up with one slight improvement by instantiating IntegerDigits, i.e.

Join @@ Map[{Quotient[#, 253], Mod[#, 253]} &,
Partition[l, 3].{1600, 40, 1}]; // AbsoluteTiming
{1.37657, Null}

• I don't know how much the following will help, but: 1) You don't need to Map twice, you can just map the combined function. 2) as far as I can see, Partition[l, 3, 3, {1, 1}, {}] is the same as Partition[l, 3]; the latter is unlikely to be faster, but it certainly is more readable. – MarcoB Apr 26 at 19:11
• Combining both functions yields a worse performance on my machine. The semantics of Partition[l, 3] is not the same as Partition[l, 3, 3, {1, 1}, {}]. Take l to be a list where the number of elements is not a multiple of 3. – Markus Apr 26 at 19:15
• Can you share the "combined function" code that yielded that worse result? – MarcoB Apr 26 at 19:17
• IntegerDigits is Listable so you do not need to map it onto a list, you can just apply it, which may be faster. See if this makes a difference then: Flatten@IntegerDigits[ FromDigits[#, 40]& /@ Partition[l, 3, 3, {1, 1}, {}], 253] – MarcoB Apr 26 at 19:51
• The consider explaining your problem in those terms, rather than asking about your intermediate solution. I am afraid that you may have generated an "XY problem". – MarcoB Apr 26 at 20:35

Let me introduce one condition, namely that the list's length be an exact multiple of 3. This means that all partitions are exactly 3-long and allows us to use Dot instead of FromDigits. It's not absolutely necessary, but it may only introduce a small preliminary step and it seems a small price to pay.

The result from your original code for comparison:

l = RandomInteger[{0, 39}, 9999999];

(original =
Flatten@
Map[IntegerDigits[#, 253] &,
Map[FromDigits[#, 40] &,
Partition[l, 3, 3, {1, 1}, {}]]]); // RepeatedTiming

(* Out: {10.5, Null} *)


Here's my best so far:

(withJoin =
Join @@ IntegerDigits[
Partition[l, 3].{1600, 40, 1},
253
]
); // RepeatedTiming

(* Out: {4.61, Null} *)


This is a better than twofold speedup.

The most significant speedup came from using Apply[Join] instead of Flatten: the latter was responsible for almost half the time it took the original to run!

Using Dot instead of FromDigits is also a significant improvement; as is using the Listable attribute of IntegerDigits, avoiding a Map operation.

Of course, the results are the same:

original == withJoin               (* Out: True *)

• Nice speedup indeed. – Markus Apr 27 at 11:34
Flatten@BlockMap[IntegerDigits[FromDigits[#, 40], 253] &, l, 3]


Not as much faster as I expected, but a bit.

• Thanks for this version. On my machine however, the code below "Update 1" performs slightly better. As you said, there is not much difference in terms of performance. – Markus Apr 26 at 23:38