From: Lennart Borgman <lennart.borgman@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Leo <sdl.web@gmail.com>, Drew Adams <drew.adams@oracle.com>,
emacs-devel@gnu.org
Subject: Re: `completion-in-region'
Date: Sun, 11 Apr 2010 23:06:44 +0200 [thread overview]
Message-ID: <q2ve01d8a51004111406z173c8423j4a5ae03eee524a3b@mail.gmail.com> (raw)
In-Reply-To: <jwvk4sdyarz.fsf-monnier+emacs@gnu.org>
On Sun, Apr 11, 2010 at 10:51 PM, Stefan Monnier
<monnier@iro.umontreal.ca> 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)?
next prev parent reply other threads:[~2010-04-11 21:06 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-04-06 14:37 `completion-in-region' Leo
2010-04-09 3:05 ` `completion-in-region' Stefan Monnier
2010-04-11 12:56 ` `completion-in-region' Leo
2010-04-11 15:32 ` `completion-in-region' Stefan Monnier
2010-04-11 18:05 ` `completion-in-region' Drew Adams
2010-04-11 19:44 ` `completion-in-region' Stefan Monnier
2010-04-11 19:56 ` `completion-in-region' Drew Adams
2010-04-11 20:49 ` `completion-in-region' Stefan Monnier
2010-04-11 21:13 ` `completion-in-region' Drew Adams
2010-04-11 20:08 ` `completion-in-region' Lennart Borgman
2010-04-11 20:51 ` `completion-in-region' Stefan Monnier
2010-04-11 21:06 ` Lennart Borgman [this message]
2010-04-12 2:10 ` `completion-in-region' Stefan Monnier
2010-04-12 9:46 ` `completion-in-region' Lennart Borgman
2010-04-12 13:10 ` `completion-in-region' Stefan Monnier
2010-04-12 14:50 ` `completion-in-region' Davis Herring
2010-04-11 21:12 ` `completion-in-region' Drew Adams
2010-04-12 15:36 ` `completion-in-region' Leo
2010-04-12 18:10 ` `completion-in-region' Stefan Monnier
2010-04-12 15:51 ` `completion-in-region' Leo
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=q2ve01d8a51004111406z173c8423j4a5ae03eee524a3b@mail.gmail.com \
--to=lennart.borgman@gmail.com \
--cc=drew.adams@oracle.com \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
--cc=sdl.web@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.