search

dschrempf / elynx

Analyze, modify and simulate molecular sequence data and phylogenetic trees in a reproducible way.
GNU General Public License v3.0
9 stars 0 forks source link

Avoid O(n^2) case in horizontalConcat #1

Closed penteract closed 4 years ago

penteract commented 4 years ago

Using foldl' here (or foldl) can result in a computation of (((a ++ b)++c)++...) which is quadratically slower than (a++(b++(c++...))). Using foldr rather than foldl' fixes this. length (head (horizontalConcat (replicate 10000 ["hi"]))) takes 0.0 seconds to run with this change rather than 2.6 seconds under the previous version.

I don't know anything about this project, but came across it while searching for a function that does exactly this using Hoogle. If you only use very small lists, feel free to ignore this suggestion.

penteract commented 4 years ago

Since my first 2 attempts to fix it had bugs, I made a proof that the optimised version gives the same result as the unoptimised one, provided that you don't pass it infinite lists (or lists that involve bottom) https://gist.github.com/penteract/ba0057b16d15d3590e6808e7dcb44a6c.

dschrempf commented 4 years ago

Thank you for your contribution! It was fun reading your commit messages :)!