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"
<[EMAIL PROTECTED]>
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
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
