Between2First Function

ButterflySoul · Post by **ButterflySoul** » 2003-03-28 18:51

I was doing some spring cleaning in a script, and put the function together anyway so I thought I'd share it, since BeforeFirst and AfterFirst seem popular in lill scripts people make =)

The idea is to avoid resorting to :
BeforeFirst(AfterFirst(sIn, sFirst), sSecond)
and to use instead :
Between2First(sIn, sFirst, sSecond)

Code: Select all

Function Between2First(sIn, sFirst, sSecond)
   Dim iStartPos : iStartPos=InStr(sIn, sFirst)+Len(sFirst)
   Between2First = Mid(sIn, iStartPos, InStr(iStartPos, sIn, sSecond)-iStartPos)
End Function

Between2First("chocochocolatpistachevanilleframboise", "chocolat", "vanille") would for example be equal to "pistache"

Yummy ! =)

TasMan · Post by **TasMan** » 2003-03-28 18:56

BeforeFirst and AfterFirst are slow.....mind you, this is coming from an optimization freak

.

ButterflySoul · Post by **ButterflySoul** » 2003-03-28 19:04

BeforeFirst and AfterFirst are slow.....mind you, this is coming from an optimization freak

I know they are =) I try to avoid them too (instead, I resort to a Split whenever possible. I'm not sure what other people do, maybe there's a better way).
For this specific case though, the function above is the best I could think of. Improvements are of course welcomed =p

TasMan · Post by **TasMan** » 2003-03-28 19:08

Slow / Originals

Code: Select all

Function BeforeFirst(sIn, sFirst) 
    BeforeFirst = Left(sIn, InStr(1, sIn, sFirst) - 1)
End Function

Function AfterFirst(sIn, sFirst)  
    AfterFirst = Right(sIn, Len(sIn) - InStr(1, sIn, sFirst) - (Len(sFirst) - 1))
End Function

Function AfterLast(sFrom, sAfterLast)
    If InStr(1, sFrom, sAfterLast) Then
        AfterLast = Right(sFrom, Len(sFrom) - InStrRev(sFrom, sAfterLast) - (Len(sAfterLast) - 1))
    Else
        AfterLast = ""
    End If
End Function

Function BeforeLast(sFrom, sBeforeLast)
    If InStr(1, sFrom, sBeforeLast) Then
        BeforeLast = Left (sFrom , InStrRev(sFrom, sBeforeLast) - Len(sBeforeLast))
    Else
        BeforeLast = ""
    End If
End Function

Function Between2First(sIn, sFirst, sSecond) 
   Dim iStartPos : iStartPos=InStr(sIn, sFirst)+Len(sFirst) 
   Between2First = Mid(sIn, iStartPos, InStr(iStartPos, sIn, sSecond)-iStartPos) 
End Function

Faster/Mine (based on byte functions)

Code: Select all

Function BeforeFirst(sIn, sFirst) 
    BeforeFirst = LeftB(sIn, InStrB(1, sIn, sFirst) - 1)
End Function

Function AfterFirst(sIn, sFirst)
  AfterFirst = RightB(sIn, LenB(sIn) - InStrB(1, sIn, sFirst) - LenB(sFirst) + 1)
End Function

Function AfterLast(sFrom, sAfterLast)
    If InStrB(1, sFrom, sAfterLast) Then
        AfterLast = Right(sFrom, Len(sFrom) - InStrRev(sFrom, sAfterLast) - (Len(sAfterLast) - 1))
    Else
        AfterLast = ""
    End If
End Function

Function BeforeLast(sFrom, sBeforeLast)
    If InStrB(1, sFrom, sBeforeLast) Then
        BeforeLast = Left(sFrom , InStrRev(sFrom, sBeforeLast) - Len(sBeforeLast))
    Else
        BeforeLast = ""
    End If
End Function

Function Between2First(sIn, sFirst, sSecond) 
   Dim iStartPos

   iStartPos = InStrB(sIn, sFirst) + LenB(sFirst)
   Between2First = MidB(sIn, iStartPos, InStrB(iStartPos, sIn, sSecond) - iStartPos) 
End Function

TasMan · Post by **TasMan** » 2003-03-28 19:10

Best of all, these are simple replacements. No changes need to be made to the code besides replacing the actual functions. Now I think they work....I might use the byte functions a lot, but they still confuse me sometimes

.

TasMan · Post by **TasMan** » 2003-03-28 19:13

Another monologue.....well at least it's me!

It's faster to assign vbNullString than "". Also I don't use byte functions as much in these functions because there is no InStrRevB....(I cound make one, but the performance gain would probably be lost...)

Code: Select all

Function AfterLast(sFrom, sAfterLast) 
    If InStrB(1, sFrom, sAfterLast) Then 
        AfterLast = Right(sFrom, Len(sFrom) - InStrRev(sFrom, sAfterLast) - (Len(sAfterLast) - 1)) 
    Else 
        AfterLast = vbNullString
    End If 
End Function 

Function BeforeLast(sFrom, sBeforeLast) 
    If InStrB(1, sFrom, sBeforeLast) Then 
        BeforeLast = Left(sFrom , InStrRev(sFrom, sBeforeLast) - Len(sBeforeLast)) 
    Else 
        BeforeLast = vbNullString
    End If 
End Function

ButterflySoul · Post by **ButterflySoul** » 2003-03-28 19:35

Now I think they work....I might use the byte functions a lot, but they still confuse me sometimes

That's way better than me. They confuse me all the time =p I never learned programming at school, and I pretty much gathered from the docs I read so far that byte comparison basically means "case sensitive"; but I still have no clue how byte counting works, or what the difference between Right and RightB is, for example.

That said, beforelast doesn't work. BeforeLast("chocochocolatpistachevanilleframboise", "choco") returns "c" and it should return "choco"
The other 4 work great, thx =)
-Personally, I never found a use for beforelast, but I guess someone might like it-

TasMan · Post by **TasMan** » 2003-03-28 21:00

Oops

it should be this :

Code: Select all

Function BeforeLast(sFrom, sBeforeLast) 
    If InStrB(1, sFrom, sBeforeLast) Then 
        BeforeLast = Left(sFrom , InStrRev(sFrom, sBeforeLast) - 1)
    Else 
        BeforeLast = vbNullString 
    End If 
End Function

but I still have no clue how byte counting works, or what the difference between Right and RightB is, for example.

Well look at this

Right("hello", 2) = "lo"
RightB("hello", 2) = "o"

The B means the length is in bytes. Each character is 2 bytes long.

But the main thing is that it's faster. I myself normally have to test each MidB, LeftB and RightB before putting it in my code, when using InStrB with it. (InStrB + 1 = InStr * 2 - that gets old quickly

)

TasMan · Post by **TasMan** » 2003-03-28 21:06

All that said, if you looked at the source code (VB6) for my client / script on my website, you might understand better......

One fine day I might make a little tutorial on them (so people looking at my sources might actually understand

).

But here's a general rule. If the function ends in B, double the length it normally would be.

ButterflySoul · Post by **ButterflySoul** » 2003-03-28 22:10

Each character is 2 bytes long

Oh, oki =) That's pretty simple, not sure why they didn't put a lill note in the vbs doc on msdn... According to some other code you had already posted, it seemed indeed each character was several bytes long, but I wasn't sure how many, and more importantly, if it was always the same lenght or if it depended on the character (with microsoft, you never know =p )

Thankee so much for the info !
*heads off to put lill Bs everywhere*

TasMan · Post by **TasMan** » 2003-03-29 21:11

That's pretty simple, not sure why they didn't put a lill note in the vbs doc on msdn

MSDN and almost any VB site I've ever visited never mention anything about these, or just have a passing interest in them....

I think they are mentioned once on MSDN though. A one line comment say there are alternatives to Left, blah blah.

Besides, since when did MS fully document anything

?

Just noticed a few more rules that might help you/anybody else out :

RightB(String, Length)
LeftB(String, Length)
MidB(String, Start, Length)

Length for all of them is ALWAYS an even number. Start for MidB is ALWAYS an odd number. If they aren't, you'll get a string full of question marks.

TasMan · Post by **TasMan** » 2003-04-11 17:57

Sorry to bring a dead post back from the grave but.....

http://sourceforge.net/tracker/index.ph ... tid=548851

I've speeded up one of the functions, etc. These are faster than the alternatives, and work properly (no side effects by replacing your old functions with these). I've even got it properly organized now

.

Hopefully somebody finds it useful.

ButterflySoul · Post by **ButterflySoul** » 2003-04-23 17:45

I've run a test on the bytes version, in VB. Here are the results for 1 000 000 loops :

BigString = BeforeFirst(AfterFirst("chocochocolatpistachevanilleframboise", "chocolat"), "vanille") took 5.4922 seconds to assign
BigString = Between2First("chocochocolatpistachevanilleframboise", "chocolat", "vanille") took 4.2891 seconds to assign

The difference should be even more noticeable in VBS, since VBS works with variants, not real strings. In case you were still suspicious about the performance gain, you can now update your code safely =)

FRANKE · Post by **FRANKE** » 2003-04-24 06:41

ButterflySoul wrote:I've run a test on the bytes version, in VB. Here are the results for 1 000 000 loops :

BigString = BeforeFirst(AfterFirst("chocochocolatpistachevanilleframboise", "chocolat"), "vanille") took 5.4922 seconds to assign
BigString = Between2First("chocochocolatpistachevanilleframboise", "chocolat", "vanille") took 4.2891 seconds to assign

This is a wrong way to analyse a algorithm (in windows and other multi processes OS's) it might give you a hint on with one is faster then the other, but you can't realy be sure

TasMan · Post by **TasMan** » 2003-04-24 06:46

What is the right way then? I've never had any problems with slowing down my programs testing this way...(it's better than guessing!)

TasMan · Post by **TasMan** » 2003-04-24 07:43

Besides if you keep your system conditions fairly constant (i.e I run most tests on a comp running nothing Win98 - it's the only that thing running). Assuming you don't run anything like music or games, etc, the tests should remain fairly constant.

FRANKE · Post by **FRANKE** » 2003-04-24 07:58

TasMan wrote:What is the right way then?

from "Data Structures and Algorithms in Java":

Code up the algorithm in some high-level computer language (like java)
Compile the program into some low-level executable language (like the bytecode language of the Java Virtuel Machine)
Determine, for each instruction i of the low-level language, the time ti needed to execute the instruction.
Determine, for each instruction i of the low-level language, the number of times ni that instruction i gets executed when the algorithm is run.
Sum up the products ni * ti over all the instructions, which yields the running time of the algorithm.

This approach can often give us an accurate estimate of the running time, but it is very complicated to pursue since it requires a detailed understanding of the low-level language generated by a program's compilation and the environment in which it is to run.
So, instead, we perform our analysis directly on the high-level code or pseudocode. We define a set of high-level primitive operations that are largely independent from the programming language used and can be identified also in the pseudocode. Primitive operations include the following:

Assigning a value to a variable
Calling a method
Performing an arithmectic operation (for example, adding two numbers)
Comparing two numbers
indexing into an array
Following an object reference
Returning from a method

FRANKE · Post by **FRANKE** » 2003-04-24 08:00

TasMan wrote:Besides if you keep your system conditions fairly constant (i.e I run most tests on a comp running nothing Win98 - it's the only that thing running). Assuming you don't run anything like music or games, etc, the tests should remain fairly constant.

This is also the method I normally uses

TasMan · Post by **TasMan** » 2003-04-24 08:08

I'm still learning my C++ and now to to test things in VB I should go with Java?

*dripping with sarcasm*

ButterflySoul · Post by **ButterflySoul** » 2003-04-24 11:29

This is a wrong way to analyse a algorithm (in windows and other multi processes OS's)

I absolutely agree with you, it is a wrong way, this is why I ran the test several times for each function before posting =)
The 3 last decimals were different on each test, but both results stayed proportional one to another after each test "batch".

Also, the variation from one test to another (after my successive tests) suggests that the other processes running on the machine can make the execution time vary by about 1/10th of a second between 2 runs for the same function. However, the difference between the running time of the 2 functions is over a second, so it's significant enough to consider the difference due to "background load" as irrelevant; as the background load can only explain for -at most- 2/10th of a second worth of variation between the 2 functions (the rest of the difference, which is still over a second, has to come from the code difference itself, unless I'm missing something).

So indeed, it's not the best and most accurate way to test them, but since background processes can only explain for about 5-10% of the difference, the remaining difference is large enough to make the test valid.
(I originally included all the decimals because they're part of the same test batch, so the proportion from one to another is right, eventhough each value taken individually doesn't mean anything).

It's faster I tell you... Upgrade your Stimbots, UserIp, and other scripts already... geeze =p lol

FRANKE · Post by **FRANKE** » 2003-04-24 12:27

I am not sure but I have read that

Code: Select all

if 1 = 2 then 
  statement1
end if
if 1 <> 2 then
  statement2
end if

is faster then

Code: Select all

if 1 = 2 then 
  statement1
else
  statement2
end if

Is there anybody there can validate that ?

Moch · Post by **Moch** » 2003-04-24 12:36

Argh!! Makes me want to learn VB Scripting just so I can put in some fancy code too

*L*

You have a good test there really ONLY if the runtime growth of the algorithims are equal. Thus you are only finding the x constant of xO(*). Also if they have diffrent growth rates (IE: depends on the string size in this case?) You should run the tests on first a small string and then a really big string. If they are they same growth then you should get about the same proportion for each test... However if it is diffrent growths, then it is likely you will see a big diffrence if your string length becomes long enough. In this case... you find out who has the better run time on small strings vs long strings. Then you can save some major time by making sure you are using the right algorithim for the really long strings

However, in this case.. it looks like that both of these functions should run in O(NlnN) time so there should be hardly any porpotionality change with really long strings (not to mention the string size of what you are searching for)... Soo.. that being that and me saying, ahh yeah you are prob right because they both prob have the same runtime growth.. I have to ask... why the heck did I post this in the first place? *L* Keep up the optimizations! I personally think that you could prob right a 'faster' algorithim then the ones provided in stock VBS. Faster.. meaning smaller x *L*

~Moch

ButterflySoul · Post by **ButterflySoul** » 2003-04-24 14:25

You have a good test there really ONLY if the runtime growth of the algorithims are equal.

Actually, they are not. My algo has a fixed cost which is diming a variable, then a proportional growth depending on the string lenght. The other algo (which is essentially a combination of 2 other algos) has a proportional growth all along.
Also, mine seeks a position first to "limit the damage", while the other algo hacks a bit away then passes a huge chunck of string to the second algo to play with. Since the methods are so different, there's no way they'll have the same growth...

In other words, the longer the string, the faster my single algo will be compared to the classic combination of 2 algos; eventhough it already performs faster on relatively short strings.

I get your point... I should have made the test by passing the bible as an argument and ask both functions to return the stuff in between chapter 5 and chapter 7 =p

Moch · Post by **Moch** » 2003-04-24 21:06

ButterflySoul wrote: Actually, they are not. My algo has a fixed cost which is diming a variable, then a proportional growth depending on the string lenght. The other algo (which is essentially a combination of 2 other algos) has a proportional growth all along.
Also, mine seeks a position first to "limit the damage", while the other algo hacks a bit away then passes a huge chunck of string to the second algo to play with. Since the methods are so different, there's no way they'll have the same growth...

*L* Perhaps we shouldn't get in a analaysis of algorithims debate, but the growth of any comparison based function can be at the very least O(NlnN). Two comparison functions can have the same growth but oen could be x1O(NlnN) and the other x2O(NlnN)... where their growth is identical but it just takes |x1 - x2| times more instructions to excute one more than the other at any length N. Hehe . Usually with string comparisons N is a combo of the length of the string being searched and the substring being looked for. It doesn't matter if you are Diming one variable or two, it isn't going to change the growth.. and the only the growth can be diffrent is that one (or both) methods can have a worst growth.. like O(n^2) or some much worst polynomial run time growth *blech*

Lets just say, its not so easy as saying what growth is better.. just attempt to get at the the proven lowest level of growth at NlnN and thats practically good enough! *L* It is also harder than just looking at the code and giving it an assement like you did... Analysis takes a bit more work than that... sad but true, but hey, that's computer science for you!

Keep on working at getting that X1 down! Now... if you want to have a non-comparison algo then you can get it down to linear time.. and they haven't proven that you can't even get it down to less than linear, so that is even a possibility. However, inpratical for a VBScript *L*

Forgive me... but I just had to get that crap out of my system (flash back of Analysis Of Algorithims in College)

Oh yeah, that was my point, to get a more accurate runtime.. take the bible, do a search, blah blah.. so ignore everything I just said.

~Moch

ButterflySoul · Post by **ButterflySoul** » 2003-04-25 00:43

ok, I didn't have a text version of the bible, so I did with the Egytian Book of the Dead, saved to a nice txt file of 241KB. It's not as long as the bible, but it make a reasonably long string nonetheless
I also checked, re-checked, double checked and triple checked (and re-rechecked once more to really be sure) the code.. There is no 0 missing or extra 0 in either loop...

I assigned the variable with a seperate button, because the first time you open the file system object to read stuff, there's a small delay that you don't have the next time you read stuff. So the book was already loaded and assigned to sText before either function started looping. Considering the size of string, I only looped 10000 times instead of a milion, because I didn't want to sit there all night.

To assign 10000 times : BigString = BeforeFirst(AfterFirst(sText, "The Fifth Arit"), "The Seventh Arit") : 35.8750 seconds
To assign 10000 times : BigString = Between2First(sText, "The Fifth Arit", "The Seventh Arit") : 2.2969 seconds

Here are the values of a few extra runs, so you can see the variation due to the background load :
36.2969 / 2.3594
36.1406 / 2.3125
35.9219 / 2.3047

Comments ?

Moch · Post by **Moch** » 2003-04-26 01:50

Hey me again *s* Sorry to be such an annoyance... I do have a comment. Yeah those comparisons are DRASTIC... makes you think there is something funky going on... Well there is.

I went back and looked at the BeforeFirst and AfterLast functions and this is why I think the runtimes were so drastic......

BeforeFirst uses the Left function. Your functions just use the InStr function... so.. It appears to me (even though I don't have the text) that the first accurance of this inBetween is fairly close to the beganing of the loaded string (book). At least a great deal closer to the beganning the end. Since BeforeFirst is: (using your sped up version) :

Code: Select all

Function BeforeFirst(sIn, sFirst)
    BeforeFirst = LeftB(sIn, InStrB(1, sIn, sFirst) - 1)
End Function

What happens here is that, yes it first searches forward in the string, but then its like ok...Lets use LeftB and lets start at InStrB(blah) - 1.... Well, the problem with this one big strings is that VB is iterating througgh the string BACKWARDS to get to the Position variable. So in this case since the string is very long it takes a while to do that. Yes, very ineffecient compared to yours which uses just the InStr function... which parses FORWARD through the string. In this case it would of been a better solution to do

Code: Select all

BeforeFirst = Mid(sIn, 1, InStrB(1, sIn, sFirst) )

Forgive me if I have any slight syntax errors as I don't really know ifthere is a MidB or even use VB.. (I'm a C man *L*).

Anyway, my point here? That if the first accurance in your test happened near the END of the string data (book) then the outcome of your tests most likely would of been reversed, your's being the slower one by 20+ seconds. (I am giving you credit that your implementation is faster anyway, but I really don't know).

Probably an even better implentation of a faster algo would get the Length of the string to be searched, and compared the position to .5*fullStringLength and if its lower use the implentation you have now, but if it is higher to use the one that incorporates LeftB. Yes, thats a tad (just a smidgeon) more overhead... but doing it that way would speed up your implentation when strings are near the end.

Ok.. I'll be quiet now