Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:64502 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 32993 invoked from network); 3 Jan 2013 14:37:52 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 3 Jan 2013 14:37:52 -0000 Authentication-Results: pb1.pair.com smtp.mail=scope@planetavent.de; spf=permerror; sender-id=unknown Authentication-Results: pb1.pair.com header.from=scope@planetavent.de; sender-id=unknown Received-SPF: error (pb1.pair.com: domain planetavent.de from 89.107.189.172 cause and error) X-PHP-List-Original-Sender: scope@planetavent.de X-Host-Fingerprint: 89.107.189.172 mail.xa8.serverdomain.org Linux 2.6 Received: from [89.107.189.172] ([89.107.189.172:58930] helo=mail.xa8.serverdomain.org) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id FE/38-35624-EB795E05 for ; Thu, 03 Jan 2013 09:37:51 -0500 Received: from mail-we0-f179.google.com (mail-we0-f179.google.com [74.125.82.179]) (Authenticated sender: xa8190p1) by mail.xa8.serverdomain.org (mail.xa8.serverdomain.org) with ESMTPSA id 78A92282A5CDB for ; Thu, 3 Jan 2013 15:37:45 +0100 (CET) Received: by mail-we0-f179.google.com with SMTP id r6so7383027wey.10 for ; Thu, 03 Jan 2013 06:37:45 -0800 (PST) MIME-Version: 1.0 Received: by 10.194.79.34 with SMTP id g2mr79065740wjx.17.1357223865522; Thu, 03 Jan 2013 06:37:45 -0800 (PST) Received: by 10.227.170.206 with HTTP; Thu, 3 Jan 2013 06:37:45 -0800 (PST) In-Reply-To: References: Date: Thu, 3 Jan 2013 15:37:45 +0100 Message-ID: To: internals@lists.php.net Content-Type: multipart/alternative; boundary=047d7bb03ecc62991104d2634e3b Subject: Re: [PHP-DEV] strtr vs. str_replace runtime From: scope@planetavent.de (Nicolai Scheer) --047d7bb03ecc62991104d2634e3b Content-Type: text/plain; charset=UTF-8 Hi! On 3 January 2013 11:40, Gustavo Lopes 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 --047d7bb03ecc62991104d2634e3b--