Hi!
On 9 January 2013 23:45, Gustavo Lopes <glo...@nebm.ist.utl.pt> wrote: > On Thu, 03 Jan 2013 11:40:31 +0100, Gustavo Lopes <glo...@nebm.ist.utl.pt> > wrote: > > 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. >> >> > Both optimizations (the hash rolling and limiting the substrings hashed on > each iteration) worked quite well. > > But I got much better results with another algorithm [1], so I'm going to > merge the branch with it [2] instead. I get these results with a 1.7 MB > string and 13 replacement strings, the smallest with 6 characters and 30 > iterations (x86-64, gcc -O3): > > strtr: 0.1387 > str_replace: 0.4471 > Nice :) > > The algorithm doesn't perform as well when the replacement strings are > small. Adding a replacement for the pattern '_' (1 character) yields: > > strtr: 0.6157 > str_replace: 0.6230 > Even that is way better than before :) > > But even in this case, it works better than my optimized version of the > current algorithm. > > I plan on merging to 5.4 and 5.5; you may want to review it as introducing > completely new code carries some risk. > > [1] > http://citeseerx.ist.psu.edu/**viewdoc/summary?doi=10.1.1.13.**2927<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.2927> > [2] https://github.com/cataphract/php-src/compare/strtr_wu94 Does "merging to 5.4" mean I can grab the head of the 5.4 branch afterwards and try it myself? Thanks! Greetings Nico
