From: Robert Klemme <shortcutter@...>
Date: 2009-10-29T23:15:57+09:00
Subject: Re: String Matching Problem

2009/10/29 Matt Brooks <mattbrooks@gatech.edu>:
> I appreciate everyone's input, It seems like they should all work, and
> do, initially, but for my application each one seems to stop working for
> another reason.... I am checking tons of messages, actually I am
> searching a buffer of messages, about 600 messages, every time a message
> is received, so if it takes to long to search the buffer, the new
> received messages start piling up I guess and don't ever get in the
> buffer to be searched, and so on, it is a vicious cycle I guess.

What does "received" mean?  Is this some kind of network interface?
Why are you searching all the messages again as soon as a new message
arrives?  Can you describe the real problem that you are trying to
solve?

>   I
> think each of these ways takes too many resources, compared to
> line[cmd], where line is my line received and cmd is the initial match I
> am looking for.  I suppose line[cmd] is really optimized for quick
> checking.
>
> I tried every way you all listed, and it works for a few messages, then
> it seems to get bogged down and miss messages or something as the buffer
> fills up and gets larger and larger to check each one in the buffer.
>
> Even the one liner, line[/\A#{cmd}(\z|,)/], stops working pretty quick.

That is a too foggy formulation for me.  What does that mean?  Any
errors, exceptions?

> Odd problem, because when I throw my regular line[cmd] code in there, it
> works like a charm continuously, except at the corner cases that
> provoked this thread to start with, "the unavoidable partial match".
>
> Hate to ask again, any more less intensive ways to do it?  It will be
> ran up to 600 times every tenth of a second probably.  Keep in mind
> sometimes, it only has to search the buffer for the first 10 or so
> messages before it finds a match, but sometimes it must go all the way
> deep into the buffer 500 or so to get a match, then it starts on the
> next one... etc..

This sounds as having a linear list of entries is not an appropriate
data structure for the problem at hand.  With the partial matching
needed terms "tree" and "trie" come to mind.

Please give more information about the problem you are trying to solve.

Cheers

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/