1
$\begingroup$

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}
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – MarcoB Apr 26 at 19:11
  • $\begingroup$ 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. $\endgroup$ – Markus Apr 26 at 19:15
  • $\begingroup$ Can you share the "combined function" code that yielded that worse result? $\endgroup$ – MarcoB Apr 26 at 19:17
  • 2
    $\begingroup$ 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] $\endgroup$ – MarcoB Apr 26 at 19:51
  • 1
    $\begingroup$ 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". $\endgroup$ – MarcoB Apr 26 at 20:35
4
$\begingroup$

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 *)
| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice speedup indeed. $\endgroup$ – Markus Apr 27 at 11:34
0
$\begingroup$
Flatten@BlockMap[IntegerDigits[FromDigits[#, 40], 253] &, l, 3]

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Markus Apr 26 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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