Re: strtr vs. str_replace runtime

Hi! On 3 January 2013 11:40, Gustavo Lopes <glopes@nebm.ist.utl.pt> wrote: > 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. > Ok, here it goes: https://bugs.php.net/bug.php?id=63893 Greetings, Nico