egghelp/eggheads community

string match

2002-11-18T12:39:01-04:00

Using a foreach word [split $arg] to chk each word for a channel, makes the eggdrop be a little slow when it's an spam. Isn't there any other alternative, maybe a faster one to do such a chk?

Statistics: Posted by caesar — Mon Nov 18, 2002 12:39 pm

string match

2002-11-12T17:37:15-04:00

And finaly, wich is the good code? :]

It is indeed true that the conclusion was extremenly vague and poorly written:

Based on the above results both the SPDY and the SPLT are good solutions

Why don't you give the splt proc a try:

Code:

#---------------------------------------------------------------------# split lines and test by strikelight (slightly modified) #---------------------------------------------------------------------proc stringisbad { channel string } {    if {[string first {#} $string] == -1 } { return 0 }    foreach word [split $string] {       if {![string match "*#*" $word]} { continue }       if  {[string compare -nocase $word $channel] == 0 } { continue }      return 1    }    return 0 }

Statistics: Posted by egghead — Tue Nov 12, 2002 5:37 pm

string match

2002-11-12T13:54:56-04:00

And finaly, wich is the good code? :]

Statistics: Posted by caesar — Tue Nov 12, 2002 1:54 pm

string match

2002-11-01T19:14:21-04:00

After some further messing and testing around, 3 candidates remained:

BARE: a single bare line regexp, not (yet) generical for any channel (stdragon)
SPDY: a speedy string comparison proc (egghead/stdragon)
SPLT: a good old line splitting and word by word checking (strikelight, minor mod by egghead)

First some differences are highlighted in what each proc considers GOOD/BAD:

Code:

Testing: BAREBARE   GOOD     join eggheadBARE   GOOD     join #eggheadBARE   GOOD     join #egghead!BARE   GOOD     join#eggheadBARE   GOOD     join #egghead for funBARE   GOOD     #eggheadBARE   GOOD     #egghead!!!aaaaaaaBARE   BAD      #egghead2BARE   GOOD     #egghead-xxxxxTesting: SPDYSPDY   GOOD     join eggheadSPDY   GOOD     join #eggheadSPDY   BAD      join #egghead!SPDY   GOOD     join#eggheadSPDY   GOOD     join #egghead for funSPDY   GOOD     #eggheadSPDY   BAD      #egghead!!!aaaaaaaSPDY   BAD      #egghead2SPDY   BAD      #egghead-xxxxxTesting: SPLTSPLT   GOOD     join eggheadSPLT   GOOD     join #eggheadSPLT   BAD      join #egghead!SPLT   BAD      join#eggheadSPLT   GOOD     join #egghead for funSPLT   GOOD     #eggheadSPLT   BAD      #egghead!!!aaaaaaaSPLT   BAD      #egghead2SPLT   BAD      #egghead-xxxxx

Next the procs are tested against a list of 20 identical strings, each string being "hello #egghead join #xxx for great fun"

Code:

Testing 20 strings WITH channel names (10000 times)BARE:  855 microseconds per iteration (average of 42 microseconds per line)SPDY:  741 microseconds per iteration (average of 37 microseconds per line)SPLT:  807 microseconds per iteration (average of 40 microseconds per line)BARE:  919 microseconds per iteration (average of 45 microseconds per line)SPDY:  758 microseconds per iteration (average of 37 microseconds per line)SPLT:  806 microseconds per iteration (average of 40 microseconds per line)

Several tests indicated that the SPDY and SPLT are the fastest, but the differences between the 3 are minor.

Next the procs were tested against 20 identical strings without any channel name in it ("hello world, this is a line"):

Code:

Testing 20 strings WITHOUT channel names (10000 times)BARE:  364 microseconds per iteration (average of 18 microseconds per line)SPDY:  235 microseconds per iteration (average of 11 microseconds per line)SPLT:  753 microseconds per iteration (average of 37 microseconds per line)BARE:  366 microseconds per iteration (average of 18 microseconds per line)SPDY:  301 microseconds per iteration (average of 15 microseconds per line)SPLT:  750 microseconds per iteration (average of 37 microseconds per line)

In this case SPLT has some difficulties to catch up, because it has to check each word in the line up to the last one for the presence of a channel name. These differences can be amplified by adding more words to the line.

Finally, the procs are tested against 20 identical lines containing 8 times the valid channelname as words in it ("#egghead #egghead etc...):

Code:

Testing 20 strings WITH channel names (1000 times)BARE: 2221 microseconds per iteration (average of 111 microseconds per line)SPDY: 2283 microseconds per iteration (average of 114 microseconds per line)SPLT: 1250 microseconds per iteration (average of 62 microseconds per line)BARE: 2646 microseconds per iteration (average of 132 microseconds per line)SPDY: 2275 microseconds per iteration (average of 113 microseconds per line)SPLT: 1230 microseconds per iteration (average of 61 microseconds per line)

In this extreme case the SPLT proc clearly is the fastest. These results can be further amplified by adding the channel name a couple of times more. In such case the SPLT will remain the fastest, followed by BARE and SPDY as last one.

Based on the above results both the SPDY and the SPLT are good solutions. If the proc has to be used to check general IRC conversation, then the SPDY proc is preferred over the SPLT proc. In that case the SPLT proc can be upgraded, by adding the line "if {[string first {#} $string] == -1 } { return 0 }" as the first line in the proc.

It will be very interesting to see how the results compare with a proc using an [lsearch -all -inline] (available in Tcl 8.4) followed by a channelname check.

Finally, as mentioned by stdragon, note that there are no checks for valid word separators in the SPDY and LIST proc, there is some in the BARE proc.
Adding such check, which is left as a trivial exercise for the interested reader, will raise the timing results of the SPDY and the LIST procs in an identical way, since they perform the channel name checks in the same way.

The procs:

Code:

#--------------------------------------------------------------------- # one line regexp by stdragon#--------------------------------------------------------------------- proc stringisbadBARE { channel string } {   if { [regexp -nocase {#(?!egghead(\W|$))} $string] } { return 1 }   return 0}#--------------------------------------------------------------------- # split lines and test by strikelight (slightly modified)#--------------------------------------------------------------------- proc stringisbadSPLT { channel string } {#   if {[string first {#} $string] == -1 } { return 0 }   foreach word [split $string] {       if {![string match "*#*" $word]} { continue }      if  {[string compare -nocase $word $channel] == 0 } { continue }      return 1   }    return 0}#--------------------------------------------------------------------- # review occurances of # in string (egghead/stdragon)#--------------------------------------------------------------------- proc stringisbadSPDY {channel string } {    set idx 0    while {[set idx [string first {#} $string $idx]] != -1} {      set space [string first { } $string $idx]       if {$space == -1} {set space end} {incr space -1}       set word [string range $string $idx $space]       if {[string compare -nocase $channel $word ]} {return 1}       set idx $space    }    return 0}

Statistics: Posted by egghead — Fri Nov 01, 2002 7:14 pm

string match

2002-11-01T12:44:04-04:00

I think I can improve on that :)

Code:

# based on egghead's codeproc string2isbad {chan line} {  set idx 0  while {[set idx [string first {#} $line $idx]] != -1} {    set space [string first { } $line $idx]    if {$space == -1} {set space end} {incr space -1}    set word [string range $line $idx $space]    if {[string compare -nocase $chan $word ]} {return 1}    set idx $space  }  return 0}

Of course, both of these don't check for valid word separators like commas, periods, exclamation points, question marks.

Statistics: Posted by stdragon — Fri Nov 01, 2002 12:44 pm

string match

2002-11-01T09:38:01-04:00

Call me a freak, but the following snippet is also submitted for competition

Code:

proc stringisbad { channel string } {   # find first occurance of #, abort if none   # dont like while loops, but competition is fierce :)   while { [set index [string first "#" $string]] != -1 } {      # strip first part from string      set string [string range $string $index end]      # find occurance of space and set index accordingly      set indsp [string first { } $string]      # if space not found set to string end, else set to word end      if { $indsp == -1 } { set indsp end } else { incr indsp -1 }      # retrieve channel name      set channame [string range $string 0 $indsp]      # compare channel names      if { ![string equal -nocase $channame $channel] } { return 1 }       # update the string      set string [string range $string $indsp end]   }   # iterated on all words, but nothing bad found :)   return 0}

Statistics: Posted by egghead — Fri Nov 01, 2002 9:38 am

string match

2002-11-01T05:35:51-04:00

Have you tried a single regexp?

% set line "hello #egghead everybody come to #egghead2"
hello #egghead everybody come to #egghead2
% time {regexp -nocase {#(?!egghead(\W|$))} $line} 1000
9 microseconds per iteration

The code seems a bit simpler

The single line regexp works fine with the functionality of the snippets I produced. But before comparing it to the other candidates, I need it in a form where the channel name can be set separately, including the # character. This will mimic the practical situation where a proc is called with 2 arguments: a channel name and a string.
Naturally, I can produce these "preprocessing" lines myself, but they are not necessarily the best ones
Once I have these preprocessing lines, I'll put it in a proc form and compare it to the other procs.

Code:

proc stringisbad { channel string } {   # some preprocessing to strip the # from the    # channel name and build the regexp...   # regexp test returning either 0 or 1...}

Statistics: Posted by egghead — Fri Nov 01, 2002 5:35 am

string match

2002-10-31T21:09:11-04:00

Have you tried a single regexp?

% set line "hello #egghead everybody come to #egghead2"
hello #egghead everybody come to #egghead2
% time {regexp -nocase {#(?!egghead(\W|$))} $line} 1000
9 microseconds per iteration

The code seems a bit simpler :)

Statistics: Posted by stdragon — Thu Oct 31, 2002 9:09 pm

string match

2002-10-31T19:22:21-04:00

If you intend to use snippets of this thread produced by myself, they are free to use (if of any use). A "bind pubm - {* *#*} proc" defiantly will come handy

Statistics: Posted by egghead — Thu Oct 31, 2002 7:22 pm

string match

2002-10-31T18:20:40-04:00

May I include this in no-spam?

This is somthing people have been crying out for, Bu ti have been unable to generate somthing small and fast enough to deal with large load channels - nospam is packed as it is.

Statistics: Posted by ppslim — Thu Oct 31, 2002 6:20 pm

full

2002-10-31T17:47:28-04:00

so, wich is the final full script? Can u paste or send to me?

Statistics: Posted by stere0 — Thu Oct 31, 2002 5:47 pm

Mudding

2002-10-31T05:29:21-04:00

After some further mudding around, four solutions were tested:

1. REXP: solution using regexp, first script egghead
2. SPLT: iterate on each word in a string, first script strikelight
3. MODF: iterate on each word, modified version strikelight
4. FAST: iterate on each word using string functions only (code given below)

Running the full set of lines given previously containing channel names, produced the following results on the shell (averaged over 10000 iterations).

REXP: 1611 microseconds per iteration
SPLT: 740 microseconds per iteration
MODF: 970 microseconds per iteration
FAST: 639 microseconds per iteration

Clearly the REXP solution is the most expensive one, about twice the other 3 solutions. Another observation is that the modified script does not perform better compared to the script that splits the string in words and checks on each word.

Next a set of 20 strings NOT containing a #channel name , each line having 6 words ("hello world, this is a line") was tested.

The timing results:
REXP: 150 microseconds per iteration
SPLT: 991 microseconds per iteration
MODF: 781 microseconds per iteration
FAST: 164 microseconds per iteration

In this case the REXP is dead cheap as it directly detects that there are no "#" characters in the line.

To mimic behaviour with a "bind PUBM - {* *#*} " by putting the line "if {[string first "#" $string] == -1 } { return 0 }" right at the start of the SPLT and MODF scripts (i.e. first checking for the presence of a # character in the string), the following results are obtained.

REXP: 150 microseconds per iteration
SPLT: 153 microseconds per iteration
MODF: 157 microseconds per iteration
FAST: 156 microseconds per iteration

As stated somewhere else in this thread, the option of using a

has not been tested.

All in all, the idea of splitting the line and checking each word resulted in another piece, shown below. This script produced the results under FAST. Note that this script will consider "join#egghead" as good and "join#xxx" as bad.

Code:

proc stringisbad { string } {   # omit sentences without # in it   if {[set index [string first "#" $string]] == -1 } { return 0 }   # remove first part of the string   set string [string range $string $index end]   # allowed channel   set channel #egghead   # split the line into a list of words   set list [split $string]   # iterate on the words   foreach word $list {      # if word does not contain a "#" then continue ...      if { [set index [string first "#" $word]] == -1 } { continue }      # ... else retrieve channel name      set channame [string range $word $index end]      # if found name is not allowed name then string is bad      if { $channame != $channel } { return 1 }   }   # iterated on all words, but nothing bad found :)   return 0}

Statistics: Posted by egghead — Thu Oct 31, 2002 5:29 am

Re: string match

2002-10-30T21:28:36-04:00

Actually, Tcl8.4 has an [lsearch -all -inline] option which in principle should be able to produce immediately a list of matches. Unfortunately
I'm still on Tcl8.3, so I couldn't test that idea

Same here...

Statistics: Posted by strikelight — Wed Oct 30, 2002 9:28 pm

Re: string match

2002-10-30T21:27:12-04:00

Another drawback of doing a word by word check, is that it's not cheap on the average say 5 to 10 word sentences not containing any "#" char. Maybe doing a check for the presence of a # char in the string before going to a word by word check can solve this.

Already addressed this in my modification on my post containing the example, with the lsort, lrange, etc...

Statistics: Posted by strikelight — Wed Oct 30, 2002 9:27 pm

Re: string match

2002-10-30T21:26:35-04:00

or to cut down on iterations while still actually verifying each channel name..

Code:

set bad 0set mylist [lsort [split [string tolower $arg]]]set aloc [lsearch $mylist #*]if {$aloc == -1} { return }set mylist [lrange $mylist $aloc end]foreach word $mylist {  if {![string match "#*" $word]} { break }  if {$word != [string tolower $chan]} { set bad 1 }}if {!$bad} { return }

Actually, Tcl8.4 has an [lsearch -all -inline] option which in principle should be able to produce immediately a list of matches. Unfortunately I'm still on Tcl8.3, so I couldn't test that idea

Statistics: Posted by egghead — Wed Oct 30, 2002 9:26 pm