Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:64495
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain nebm.ist.utl.pt from 193.136.128.22 cause and error)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8;
 format=flowed
Content-Transfer-Encoding: 7bit
Date: Thu, 03 Jan 2013 11:40:31 +0100
To: <internals@lists.php.net>
Organization: =?UTF-8?Q?N=C3=BAcleo_de_Engenharia_Biom=C3=A9dica_do_Insti?=
 =?UTF-8?Q?tuto_Superior_T=C3=A9cnico?=
In-Reply-To: <CAOg_pRTSGouOVYzorTH1WDYvKqtKdJkJVHxVddO4u=TGNkSs8A@mail.gmail.com>
References: <CAOg_pRTSGouOVYzorTH1WDYvKqtKdJkJVHxVddO4u=TGNkSs8A@mail.gmail.com>
Message-ID: <ce9075c17cad65fcdd350a1f243e6ea1@nebm.ist.utl.pt>
User-Agent: RoundCube Webmail/0.8-rc
Subject: Re: [PHP-DEV] strtr vs. =?UTF-8?Q?str=5Freplace=20runtime?=
From: glopes@nebm.ist.utl.pt (Gustavo Lopes)

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