3
$\begingroup$

I am trying to make substitution cipher solver based on quadgram statistics. I am now in doubt about how to store ciphertext - whether in string or in list of characters. I did a little test to compare how fast is manipulation of strings versus manipulation of list of characters.

st = FromCharacterCode[RandomInteger[{65, 90}, 10000000]];
li = Characters[st];
stpa = StringPartition[st, 4, 1]; // Timing
lipa = Partition[li, 4, 1]; // Timing
StringReplace[
   stpa, {"A" -> "Z", "Z" -> "A", "B" -> "Y", "Y" -> "B"}]; // Timing
ReplaceAll[
   lipa, {"A" -> "Z", "Z" -> "A", "B" -> "Y", "Y" -> "B"}]; // Timing
Clear[st, li, stpa, lipa]

(* {3.5625, Null} *)
(* {0.515625, Null} *)
(* {3.53125, Null} *)
(* {16.9531, Null} *)

It can be seen that partitioning string is about 7 times slower than partitioning list of characters. On the other hand it can be seen that swapping characters of partitioned string is about 5 times faster than swapping characters of partitioned list of characters.

Why are there so significant differences in the speed when in principle results of both procedures are same?

What are suggestion to optimize the code?

I guess in the search for the key of substitution cipher I will use more frequently swapping of characters than partitioning so probably I will use strings and StringReplace rather than list of characters and ReplaceAll. Or is there a better solutions?

$\endgroup$
2
  • 1
    $\begingroup$ This Replace[lipa,Dispatch[{"A"->"Z","Z"->"A","B"->"Y","Y"->"B"}],{2}] is a bit faster. $\endgroup$
    – user293787
    Commented Aug 20, 2022 at 14:54
  • 1
    $\begingroup$ I did not know about Dispatch, seems to be a good thing for long replacement rules. $\endgroup$ Commented Aug 21, 2022 at 14:40

1 Answer 1

5
$\begingroup$

First create all needed data:

st = FromCharacterCode[RandomInteger[{65, 90}, 10000000]];
li = Characters[st];
stpa = StringPartition[st, 4, 1]; // Timing
lipa = Partition[li, 4, 1]; // Timing
stpa1 = StringReplace[
    stpa, {"A" -> "Z", "Z" -> "A", "B" -> "Y", 
     "Y" -> "B"}]; // Timing
lipa1 = ReplaceAll[
    lipa, {"A" -> "Z", "Z" -> "A", "B" -> "Y", "Y" -> "B"}]; // Timing

Now look at the space used:

ByteCount /@ {st, li, stpa, lipa, stpa1, lipa1}

(* {10000072, 400000080, 399999960, 2079999456, 399999960, 2079999456} *)

Note that going from st to stpa the space increases 40 times. However going from li to lipa only 5 times. This may explain the first 2 timings.

The timing for the replacements may be explained by noting that the string replacement has to search much less data than the list replacement.

$\endgroup$
1
  • $\begingroup$ I think I will rather use Python as there I have more control over speed of all procedures. I am not sure Mathematica is suitable for such a project as substitution cipher solver - that is probably why there is no public code of such solver implemented in Mathematica. At least I have not seen any, but I saw implementations in Python or even in JavaScript available as an open source. $\endgroup$ Commented Aug 21, 2022 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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