Skip site navigation (1) Skip section navigation (2)

Re: strpos() && KMP

From: Decibel! <decibel(at)decibel(dot)org>
To: Pavel Ajtkulov <ajtkulov(at)acm(dot)org>
Cc: pgsql-patches(at)postgresql(dot)org
Subject: Re: strpos() && KMP
Date: 2007-08-03 23:41:03
Message-ID: 20070803234102.GX25704@nasby.net (view raw or flat)
Thread:
Lists: pgsql-patches
On Thu, Aug 02, 2007 at 01:18:22AM +0500, Pavel Ajtkulov wrote:
> Hello,
> 
> this patch allow to use Knuth-Morrison-Pratt algorithm for strpos() function 
> (see Cormen et al. Introduction to Algorithms, MIT Press, 2001).
> 
> It also works with multibyte wchar.
> 
> In worst case current brute force strpos() takes O(n * m) (n && m is length of strings) 
> time (example: 'aaa...aaab' search in 'aaa...aaa').
> KMP algo always takes O(n + m) time. 
> To check this someone need to create a table with one text attribute, and insert several thousands
> record 'aa..aa'(for example, with lenght = 1000) . After execute "select count(*) from test where 
> strpos(a, 'aaa....aab') > 0;" on current and modified version.
> 
> Also, I advise to use "select .. where strpos(att, 'word') > 0;" instead "select .. where attr like '%word%'"
> (strpos must be faster than regex).
> 
> In general, this belongs to artificial expressions. In natural language KMP is equal (execution time)
> current strpos() nearly.

Do you have any performance test results for this?
-- 
Decibel!, aka Jim Nasby                        decibel(at)decibel(dot)org
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

In response to

Responses

pgsql-patches by date

Next:From: Decibel!Date: 2007-08-04 00:03:35
Subject: Re: Repair cosmetic damage (done by pg_indent?)
Previous:From: Decibel!Date: 2007-08-03 23:12:09
Subject: Re: Repair cosmetic damage (done by pg_indent?)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group