[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: speed up u8_strstr
From: |
Pádraig Brady |
Subject: |
Re: speed up u8_strstr |
Date: |
Thu, 20 Jan 2011 20:16:42 +0000 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.8) Gecko/20100227 Thunderbird/3.0.3 |
On 31/07/10 20:48, Bruno Haible wrote:
> Hi Pádraig,
>
>>> the u8_strstr function.
>>
>> I wonder could we speed that up for UTF-8
>> by just deferring to strstr() ?
>
> This is a good idea, because the naïve implementation of u8_strstr is
> quadratic (O(n²)), whereas for strstr we now have an O(n) algorithm.
>
> But at the same time, can you also try to apply the O(n) algorithm to
> u16_strstr and u32_strstr?
>
> Bruno
>
Attached is a first attempt at this.
Questions I have are:
Is it OK to include str-mp.h and malloca
in unistr/ modules like I do?
I'm thinking of adding an alarm(5) to the test
to enforce the performance check.
cheers,
Pádraig.
fast-u-strstr.diff
Description: Text Data
- Re: speed up u8_strstr,
Pádraig Brady <=