2 ms·
This could be sped up significantly by implementing a fast path for ASCII strings. Most inputs would be ascii (even assuming the amount of emoji people use the
by kristianp 4y ago
This could be sped up significantly by implementing a fast path for ASCII strings. Most inputs would be ascii (even assuming the amount of emoji people use these days). You'd want to check with real-world data if its worth it though.
To conclude that the performance data shows exponential complexity is erroneous: the data sent to Wolfram Alpha doubles with each data-point because the input size is doubling, but the x-axis info isn't being supplied to Alpha. Eyeballing the data, the last 2 data points are 5.85 and 11.8, which is very close to double (11.7 vs 11.8), suggesting linear complexity.
- wofo 4y agoJust to clarify, 5.85 ms and 11.8 ms are the data points of the baseline, so complexity is indeed linear there. The Elixir implementation, though, runs in 225.4 ms (39x slower) and 664 ms (56x slower). Thanks for pointing out the mistake in the data sent to Wolfram Alpha! Still, if you look at the results table, you can see that the factor of increase is ~2x at the beginning, but is ~3x at the end. (This is why I wanted a plot instead of a table in the blog post :p, because then the curve speaks for itself)
- kristianp 4y agoOk, thanks for that. I misread that baseline was the Elixir version. I thought that usually "baseline" is the reference implementation that you start with and the slowest? Interesting topic, thanks for writing the blog post!