Scoring is horribly slowed down by this entry. Why?

Scoring is horribly slowed down by this entry. Why?

[Rui Zhu]

("\\([-_0-9A-Za-z]+\.\\)+\\(com\\|net\\) *$" -1000 nil r)

Today I just added this entry in my all.SCORE file to (subject with
only domain name, advertising?), but scoring process is becoming
terribly slow.  `C-u 50 RET' on several groups let me waiting more
than 10 minutes.  Does this just happen to me?

[Emacs 20.3.2 on x86 Linux with Pgnus 0.95]

Regards,
        Rui

Re: Scoring is horribly slowed down by this entry. Why?

[Felix Lee]

Rui Zhu <sprache@iname.com>:
> ("\\([-_0-9A-Za-z]+\.\\)+\\(com\\|net\\) *$" -1000 nil r)

1. there are N possible starting points for the [...]+
pattern, and greedy-match semantics will have it doing N
attempts for each possible starting point.  the (...)+
pattern around it forces each of these N attempts to be done
N times, so the best case performance is something like
O(N**3).  this is going to be terrible, because N is pretty
large, since alphanumeric characters are common.

2. "\." should be "\\.".  "\." == ".", which makes the
regexp behavior worse, since it will need to try matching
any character, not just alphanumerics, which makes N bigger,
sort of.

try using this instead:
  "[-_0-9A-Za-z.]+\.\\(com\\|net\\) *$"
--

Re: Scoring is horribly slowed down by this entry. Why?

[Felix Lee]

Felix Lee <flee@teleport.com>:
> try using this instead:
>   "[-_0-9A-Za-z.]+\.\\(com\\|net\\) *$"

urr, I mean:
    "[-_0-9A-Za-z.]+\\.\\(com\\|net\\) *$"

Re: Scoring is horribly slowed down by this entry. Why?

[Rui Zhu]

Felix Lee <flee@teleport.com> writes:

> Rui Zhu <sprache@iname.com>:
> > ("\\([-_0-9A-Za-z]+\.\\)+\\(com\\|net\\) *$" -1000 nil r)
> 
> 1. there are N possible starting points for the [...]+
> pattern, and greedy-match semantics will have it doing N
> attempts for each possible starting point.  the (...)+
> pattern around it forces each of these N attempts to be done
> N times, so the best case performance is something like
> O(N**3).  this is going to be terrible, because N is pretty
> large, since alphanumeric characters are common.
> 
> 2. "\." should be "\\.".  "\." == ".", which makes the
> regexp behavior worse, since it will need to try matching
> any character, not just alphanumerics, which makes N bigger,
> sort of.

Oops, how silly am I.  I really want `\\.', it is this forgotten
backslash that causes almost the whole trouble.

Thanks,
        Rui