|
Are you always looking for these three digits, or was that just an example?
|
|
|
|
|
The three digits were an example, but the same digits all the time. So yes and no.
|
|
|
|
|
A state machine uses a single int to mark where you are in your search. E.g.:
int state = 0;
foreach (char c in nextString)
switch (state)
{
case (0): if (c == '6') state = 1;
break;
case (1): if (c == '2') state = 2;
break;
case (2): if (c == '4') state = 3;
break;
}
if (state == 3)
return (FOUND);
else
return (NOT_FOUND);
This is way faster than using regular expressions, which must handle much more complex cases.
|
|
|
|
|
Groovy (not the language)! I'll try it out. Thanks!
|
|
|
|
|
I'm afraid the switch will turn out to be expensive, and it really is unnecessary. How about:
int len=s.Length;
int i=0;
while(i<len) {
char c=s[i++];
if (c=='6') {
while(i<len) {
c=s[i++];
if (c=='2') {
while(i<len) {
c=s[i++];
if (c=='4') return true;
}
}
}
}
}
return false;
or the more structured:
string search="624x";
int iSearch=0;
char cSearch=search[iSearch];
foreach(char c in s) {
if(c==cSearch) {
cSearch=search[++iSearch];
if (cSearch=='x') return true;
}
}
return false;
BTW: none if these fulfill the requirement, as they would accept 6424 whereas the OP wants to reject that; so the state machine needs to be a tiny bit more complex.
|
|
|
|
|
Yes, your first example is a more efficient implementation of the state machine, but I was trying to illustrate the concept with the most clarity.
My example also could be optimized by immediately returning when the third digit was found, but I wanted to show a pure example of a state machine.
|
|
|
|
|
|
Luc Pattyn wrote: BTW: none if these fulfill the requirement, as they would accept 6424 whereas the OP wants to reject that; so the state machine needs to be a tiny bit more complex.
No, I wouldn't. When I said as long as 6-2-4 appear in that order, I meant 6[0-9]*2[0-9]*4.
|
|
|
|
|
The first example you provided is quite clear, although you had a len missing in the third while loop. I'm not so sure about the second one(since I don't have a compiler at work - not my thing anymore). Never mind. I got it. Except the 'x' confused the hell out of me.
I think I like the second one better, but I need to use the one that's faster.
Thanks!
|
|
|
|
|
sorry. I fixed both mistakes now.
I don't expect you would notice a significant performance difference between both approaches.
|
|
|
|
|
No, but I am wondering between your first method and PIEBALDconsult's use of IndexOf above. Your second method actually has a more dynamic use for me which I may or may not need. Either way, it helped me learn what I've forgotten.
Thanks!
|
|
|
|
|
IndexOf is fine for short strings; it is also fine for long strings if you know the character is present. It is a waste if you need several of them and most of those return nothing.
BTW: there also is a LastIndexOf which actually scans from right to left. So looking for 2...4 could be achieved like this:
int i2=s.IndexOf('2');
if (i2>=0 && i2<s.LastIndexOf('4')) return true;
|
|
|
|
|
Thanks, I saw that. Actually, the string I'm searching for will only appear roughly one third of the time. Why would it be a problem if the character is not present? It should basically scan the entire string just like your method does. However, I'm inclined to believe that Microsoft must have optimized the IndexOf and LastIndexOf to work just as well as your first search method. It's your second method that I'm still deciding on.
|
|
|
|
|
an IndexOf-based approach, when using several calls to such methods, has the disadvantage of scanning the string several times; a state-machine based approach typically scans just once.
I'm not sure what you mean by my first and second approach; the one with cSearch is a bit neater than the nested while loops, as it takes less code and scales better when more than a few items need to be present in a specific order. As I said, the speed difference would be minimal, the only overhead it adds is advancing one position in "search" each time the state-machine's state changes (as opposed to entering another nested while loop). When in doubt, just give it a try.
|
|
|
|
|
Luc Pattyn wrote: an IndexOf-based approach, when using several calls to such methods, has the disadvantage of scanning the string several times;
PIEBALDconsult's example shows the IndexOf(Char, Int32) or LastIndexOf(Char, Int32) searching from the last known position. That's identical to what you're doing, but I would think Microsoft has it optimized.
Luc Pattyn wrote: I'm not sure what you mean by my first and second approach;
Your cSearch (while) was the first one. That one is somewhat self-explanatory, but the second one allows me to create more dynamic searches in case the values that I'm searching for change. It also means I am not fixed at N amount of while loops.
Luc Pattyn wrote: When in doubt, just give it a try.
Yeah, I intend to. I just don't have Visual Studio here and no admin rights to install the Express version. We need a Portable Visual Studio Microsoft.
|
|
|
|
|
Bassam Abdul-Baki wrote: but I would think Microsoft has it optimized
I went to look, but found out that it's implemented as a call to "somewhere" (0xFFFFFFFFFF47A100, any clues?)
So I still know nothing. It could be optimized.. but knowing MS it is likely to be a highly generic "good for all CPU's" routine and therefore rather slow. That's what they usually do.
|
|
|
|
|
Luc Pattyn wrote: IndexOf is fine for short strings; it is also fine for long strings if you know the character is present. It is a waste if you need several of them and most of those return nothing.
Huh? You do know there are overloads for IndexOf that take the starting position to scan from, right? Scan for first character, then scan for the second character starting from the position that follows the first, then scan for the third character starting from the position that follows the second character, and so on. I figure that would be very clear code that would be very performant as well.
int index = str.IndexOf(char3, str.IndexOf(char2, str.IndexOf(char1) + 1) + 1);
|
|
|
|
|
I like that. Short and succinct. However, Luc's second method is still more dynamic. I guess we could always put this one in a loop as well.
|
|
|
|
|
aspdotnetdev wrote: You do know there are overloads for IndexOf ...
yes I do. 
However some people feel tempted by this style:
int pos1=s.IndexOf(char1);
int pos2=s.IndexOf(char2);
int pos3=s.IndexOf(char3);
.. and then a lot of decisions based on the value of pos1/2/3.
And that could be very bad on long strings.
|
|
|
|
|
Luc Pattyn wrote: And that could be very bad on long strings.
And it may also fail sometimes, such as if you are looking for a 2 then a 4 in the string "6424". That string should pass, but would fail given your sample code. IndexOf (using the start index) and a for loop is probably the best way to go, as Piebald suggested.
|
|
|
|
|
aspdotnetdev wrote: IndexOf (using the start index) and a for loop is probably the best way to go, as Piebald suggested.
Actually, I like the regular expression approach more.
|
|
|
|
|
the specs started and ended as: matching 6[0-9]*2[0-9]*4
somewhere along the thread I got confused; my BTW was wrong, 6424 has to be accepted.
So, yes PIEBALD's approach is a correct one and possibly the best.
It might be improved by looking for the last subitem using LastIndexOf (taking great care about the parameters that beast requires!).
|
|
|
|
|
Luc Pattyn wrote: It might be improved by looking for the last subitem using LastIndexOf
Not if the string is "62420000000000000000000000000000000000000000000000000".
|
|
|
|
|
It gets to be that on occasion.
|
|
|
|
|
Hence "might", it depends on the probability distribution of the patterns.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
