Re: Algorithm Optimizations - string search

Hello On 2008-06-09, at 14:58, Scott MacVicar wrote:

There is rabin-karp too but its worse case is O(nm) so that might not be ideal, perhaps we should try to compare all of them.

OK. I think RK will not be much better than original piece of code which runs in time o(n + m) i most cases (but has worst time o(nm))

Scott Nuno Lopes wrote:

Hi, So some comments: - you have some problems with the indentation. We only use tabs, so please stick to that. Also, there are some lines that are not indented correctly - Have you considered the Boyer-Moore algorithm? I think it's a little faster than KMP (take a look at e.g. http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/)

Yes, but it requires additional space (size of alphabet) and average running time is 3n = o(n), while KMP runs in o(n+m) that makes them actually the same on average (BM is faster in some cases of course). As Scott asked if I can make it running on UNICODE it seems to be quite important (the additional space I mean).

- please remove the //TUTAJ SKONCZYLEM comment

of course

- revert this change (as well as a few other that are similar):

       - for (r_end = r + Z_STRLEN_P(return_value) - 1; r < r_end; ) {
      + for ( r_end = r + Z_STRLEN_P( return_value ) - 1; r < r_end; ){
(we like small diffs, not long diffs with changes that also break our coding standards. e.g. we don't use space after the '(' char. Philip wrote a nice article about diffs at http://wiki.php.net/doc/articles/whitespace)

that was not intentional i think

- in strrpos_reverse_kmp() I think you allocate 4 bytes less that you want

actually the reverse - in zend_memnstr I allocate 4 bytes too much;)

- I think you've too many comments.. We don't need 1 comment per line :) After fixing all these points and after running the test suite (with valgrind) and make sure there are no regressions, I think it's safe for you to commit. Still, I would like to see some performance figures comparing the KMP and the Boyer-Moore (or point me some papers about the subject).

Will do

Thanks for your work and good luck for the rest of the SoC project :)

Thanks, Michal

Nuno ----- Original Message ----- From: "Michal Dziemianko" <michal.dziemianko@gmail.com> To: <internals@lists.php.net> Sent: Monday, June 09, 2008 12:39 PM Subject: [PHP-DEV] Algorithm Optimizations - string search

Hello, Here: http://212.85.117.53/DIFF.txt is small patch that will speed up following functions: strpos, stripos, strrpos strripos, and probably some others (all that use zend_memnstr/php_memnstr function) The speedup of zend_memnstr is about 8% on average (about 30% in case of artificial strings). Functions strrpos and strripos are about 25% faster on average. The only drawback - it needs some additional space (size of the needle). All functions pass all the tests. If it looks fine than I will apply for cvs account. Cheers, Michal