4
$\begingroup$

I have noticed that many functions that are meant to operate on string are slower compared to similar functions that operate on lists.

One example: Counts versus LetterCounts (and notice that the version with Counts has to do two more tasks than version with LetterCounts - it has to do ToCharacterCode and then KeyMap with FromCharacterCode to transform the output to the LetterCounts version)

SeedRandom[1]
str = RandomInteger[{1, 26}, 300] /. 
    Thread[Range[26] -> CharacterRange["A", "Z"]] // StringJoin;

LetterCounts[str, 2] // RepeatedTiming

KeyMap[FromCharacterCode, 
  Sort[Counts[Partition[ToCharacterCode[str], 2, 1]], 
   Greater]] // RepeatedTiming

(*{0.00426, <|"TT" -> 3, "IF" -> 3, "EP" -> 3, ... , "HA" -> 1, "AH" -> 1, "FA" -> 1|>}*)
(*{0.000830, <|"TT" -> 3, "IF" -> 3, "EP" -> 3, ... , "HA" -> 1, "AH" -> 1, "FA" -> 1|>}*)

The speed difference is significant!

Something is rotten in the state of Denmark Wolfram.

$\endgroup$
0

2 Answers 2

4
$\begingroup$
LetterCounts[str, 2]

and

KeyMap[FromCharacterCode, 
  Sort[Counts[Partition[ToCharacterCode[str], 2, 1]], Greater]];

are not equivalent operations - just try the inputs found in the LetterCounts documentation and you'll quickly see differences. So the timing comparison is not very meaningful.

edit: To answer the question in the comments, the self-written

myCharacterCounts[str_, n_] := KeyMap[FromCharacterCode,
    Counts @ Partition[ToCharacterCode @ str, n, 1]
]

will run slightly faster than CharacterCounts[str, n], though on my machine the difference is sub-millisecond even for very large strings.

But this myCharacterCounts function still does not do everything that CharacterCounts does.

CharacterCounts takes options, as in

In[45]:= CharacterCounts["aAbBcC", IgnoreCase -> True]

Out[45]= <|"c" -> 2, "b" -> 2, "a" -> 2|>

and does argument checking, issuing a message for CharacterCounts[] or CharacterCounts[2]. Argument checking and options handling are generally required for any built-in system function, but not needed for self-written functions where you know you won't be passing bad arguments or options. This may be enough to account for the timing difference, or maybe CharacterCounts is being inefficient somewhere - I can't say.

I will say that it is often, but not always, possible to beat the timing for built-in functions if you focus on a subset of the functionality and neglect error handling. And if your application is time sensitive then it is worthwhile to use the custom function instead.

$\endgroup$
4
  • 2
    $\begingroup$ They are equivalent if you use both on strings that contain only letter characters... Further more you can replace LetterCounts with Sort[CharacterCounts[#,2],Greater]& and you get perfect equivalence for all strings inputs... and still CharacterCounts is slower the same way as LetterCount is compared to my code. Why would I ever use those functions when there is a faster method? $\endgroup$ Oct 5, 2020 at 20:00
  • 1
    $\begingroup$ @azerbajdzan I don't understand your question. Sort[CharacterCounts[#,2],Greater]& is also not equivalent to LetterCounts. If you write a more specialized function that works better and faster for your inputs, then you should by all means use it. $\endgroup$
    – Jason B.
    Oct 5, 2020 at 20:20
  • 2
    $\begingroup$ That is not what I said. I said that Sort[CharacterCounts[#,2],Greater]& is equivalent with my code that uses Counts. And though they are equivalent my code is faster than when CharacterCounts is used and for no reason. $\endgroup$ Oct 5, 2020 at 20:29
  • $\begingroup$ @azerbajdzan - had a long reply, added it to the answer instead. $\endgroup$
    – Jason B.
    Oct 5, 2020 at 23:11
4
$\begingroup$

For short strings LetterCounts is slower, not sure why, for longer strings the timings are identical. Do you see similar behavior?

randomString[n_] := 
 RandomInteger[{1, 26}, n] /. 
   Thread[Range[26] -> CharacterRange["A", "Z"]] // StringJoin

counts[str_] := 
 KeyMap[FromCharacterCode, 
  Sort[Counts[Partition[ToCharacterCode[str], 2, 1]], Greater]]

<< GeneralUtilities`

BenchmarkPlot[{LetterCounts[#, 2] &, counts[#] &},
 randomString[#] &,
 10^Range[6],
 "IncludeFits" -> True]

enter image description here

$\endgroup$
3
  • $\begingroup$ On one string of length 10^6 I get 15 seconds for LetterCounts and 0.675 seconds for my code. So I do not think your plot express reality. $\endgroup$ Oct 5, 2020 at 20:08
  • $\begingroup$ I think on your plot there is even missing red point at 10^6 for LetterCounts - probably BenchmarkPlot is not patient enough to wait 15 seconds for its evaluation so it plots it without it. When I run your code on my PC I get two almost parallel lines - red and blue if I connect those points. $\endgroup$ Oct 5, 2020 at 20:16
  • $\begingroup$ Strange. On my Mac. longString = randomString[1000000]; counts[longString]; // Timing is {1.79895, Null} and LetterCounts[longString, 2]; // Timing is {1.75694, Null}. $\endgroup$ Oct 5, 2020 at 20:50

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.