Tally---challenge

[Ronald]

Hi there,

I would like to challenge you all to make the fastest tally-function
possible. The function should count the number of times a
specified string is present within another string. As I'm a Visual Basic
programmer I think i've reached the limits of performance from VB. In VB the
fastest (until now) function looks like this:

----------------------------------------------------------------------------
Function Tally(ByVal sString As String, ByVal sQuery As String) As Long
Dim ctr As Long
Dim pos As Long
sString = UCase(sString)
sQuery = UCase(sQuery)
Do
pos = InStr(pos + 1, sString, sQuery)
If pos Then ctr = ctr + 1
Loop Until pos = 0
Tally = ctr
End Function
----------------------------------------------------------------------------

Though, as this function is still not as fast as I think it can be I
would challenge everyone to write a faster one. As C++ is a better
performing language I think you all can help me.

Regards,

Ronald

[Nils Petter Vaskinn]

On Tue, 25 Nov 2003 11:13:44 +0000, Ronald wrote:

The function should count the number of times a
specified string is present within another string. As I'm a Visual Basic
programmer I think i've reached the limits of performance from VB. In VB the
fastest (until now) function looks like this: sString = UCase(sString)
sQuery = UCase(sQuery)

Your function does not match your specification. Your function performs a
case insensitive match the specification states nothing of the sort.

Also the specification in itself is lacking. suppose you have a string
"aaaa" and you search for "aa" how many matches should there be?
Should the first match "use up" the first two characters resulting in a
count of 3 or should the second character be reused so the count is 4?

--
NPV

"the large print giveth, and the small print taketh away"
Tom Waits - Step right up

[Ronald]

> > The function should count the number of times a

specified string is present within another string. As I'm a Visual Basic
programmer I think i've reached the limits of performance from VB. In VB the fastest (until now) function looks like this:

sString = UCase(sString)
sQuery = UCase(sQuery)

Your function does not match your specification. Your function performs a
case insensitive match the specification states nothing of the sort.

It should indeed be a case insensitive match.

Also the specification in itself is lacking. suppose you have a string
"aaaa" and you search for "aa" how many matches should there be?
Should the first match "use up" the first two characters resulting in a
count of 3 or should the second character be reused so the count is 4?

In the example above the Tally function should return 3.

[Karl Heinz Buchegger]

Ronald wrote:

In the example above the Tally function should return 3.

Not tested:

int Tally1( const std::string& sString, const std::string& sQuery )
{
int QueryLen = sQuery.length();
int Len = sString.length() - QueryLen + 1;
int Count = 0;
const char* spString = sString.c_str();
const char* spQuery = sString.c_str();

for( int i = 0; i < Len; ++i ) {
if( strncmp( spString, spQuery, QueryLen ) == 0 )
Count++;
spString++;
}

return Count;
}
or:

int Tally2( const std::string& sString, const std::string& sQuery )
{
std::string::size_type Offset = 0;
int Count = 0;

while( ( Offset = sString.find( sQuery, Offset ) ) != std::string::npos ) {
Offset++;
Count++;
}

return Count;
}
Oops. Forgot about the uppercase. But that should be trivial.

--
Karl Heinz Buchegger
kb******@gascad.at

[Ronald]

Karl,

Thanx for your help. But, as I do not have C++ to compile the code I would
like to ask you if you can compile it in a way I can use it within Visual
Basic.

Regards,

Ronald

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

Ronald wrote:

In the example above the Tally function should return 3.
Not tested:

int Tally1( const std::string& sString, const std::string& sQuery )
{
int QueryLen = sQuery.length();
int Len = sString.length() - QueryLen + 1;
int Count = 0;
const char* spString = sString.c_str();
const char* spQuery = sString.c_str();

for( int i = 0; i < Len; ++i ) {
if( strncmp( spString, spQuery, QueryLen ) == 0 )
Count++;
spString++;
}

return Count;
}
or:

int Tally2( const std::string& sString, const std::string& sQuery )
{
std::string::size_type Offset = 0;
int Count = 0;

while( ( Offset = sString.find( sQuery, Offset ) ) !=

std::string::npos ) { Offset++;
Count++;
}

return Count;
}
Oops. Forgot about the uppercase. But that should be trivial.

--
Karl Heinz Buchegger
kb******@gascad.at

[Karl Heinz Buchegger]

Ronald wrote:

Karl,

Thanx for your help. But, as I do not have C++ to compile the code I would
like to ask you if you can compile it in a way I can use it within Visual
Basic.

The only way I know about would be an Active X control.
But I doubt that that would be usefull. The speed improvement
of C++ would be eaten by the VB-C++ tying code required to
cross the bridge.

--
Karl Heinz Buchegger
kb******@gascad.at

[lilburne]

Karl Heinz Buchegger wrote:

The only way I know about would be an Active X control.
But I doubt that that would be usefull. The speed improvement
of C++ would be eaten by the VB-C++ tying code required to
cross the bridge.

I suspect that VB string handling is highly optimized
anyway. All you're likely to be timing is the loop control.