[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: `completion-in-region'
From: |
Lennart Borgman |
Subject: |
Re: `completion-in-region' |
Date: |
Sun, 11 Apr 2010 23:06:44 +0200 |
On Sun, Apr 11, 2010 at 10:51 PM, Stefan Monnier
<address@hidden> wrote:
>>> I see that ido implements it by turning "abc" into the regexp
>>> ".*a.*b.*c". But matching this regexp against a string like
>>> "abababababab" takes time O(N^3) where N is the length of the completion
>>> candidate, which makes me a bit uneasy
>> Does not "^a.*?b.*?c" give the same matches?
>
> No because of the ^.
Eh, sorry.
> If you use ".*?a.*?b.*?c", then yes it gives the
> same matches but it also has the same O(N^3) worst case.
This is not the right place perhaps to educate me on this, but to me
it looks like just three linear searches with the summed length for
the searches equal to that of the candidate strings. Is not that O(N)?
- Re: `completion-in-region', (continued)
- Re: `completion-in-region', Stefan Monnier, 2010/04/08
- Re: `completion-in-region', Leo, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Lennart Borgman, 2010/04/11
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- Re: `completion-in-region',
Lennart Borgman <=
- Re: `completion-in-region', Stefan Monnier, 2010/04/11
- Re: `completion-in-region', Lennart Borgman, 2010/04/12
- Re: `completion-in-region', Stefan Monnier, 2010/04/12
- Re: `completion-in-region', Davis Herring, 2010/04/12
- RE: `completion-in-region', Drew Adams, 2010/04/11
- Re: `completion-in-region', Leo, 2010/04/12
- Re: `completion-in-region', Stefan Monnier, 2010/04/12
- Re: `completion-in-region', Leo, 2010/04/12