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. Commented Apr 26, 2020 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. Commented Apr 26, 2020 at 19:15
• Can you share the "combined function" code that yielded that worse result? Commented Apr 26, 2020 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] Commented Apr 26, 2020 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". Commented Apr 26, 2020 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. Commented Apr 27, 2020 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. Commented Apr 26, 2020 at 23:38