Re: strtr vs. str_replace runtime
Em 2013-01-02 16:53, Nicolai Scheer escreveu:
I might have chosen the wrong tool for what I'm trying to achieve in the
first place, but can anyone comment on the algorithmic complexity of strtr?
This is definitely not the expected behaviour for such small inputs. Since
the inputs varied and the keys where determined automatically in my
original script, I was confronted with runtimes of several hours compared
to just a few seconds with str_replace.
If this is the expected behaviour, at least the documentation should be
adjusted to state that this function is very inefficient with keylengths
that are very distant from each other...
Please open a bug to track this.
The algorithm behaves very poorly in this case because at each position of the text, all the substrings starting there and with size between m and n (where m is the size of the smallest pattern and n is the largest) are checked, even if there are only two patterns with size m and n. We could fix this easily by building a set of the pattern sizes found and try only with those. The hashing of the substrings could also be improved; we don't have to recalculate everything when we advance in the text.
--
Gustavo Lopes
Thread (11 messages)