I need a FAST string comparison in VB 
Author Message
 I need a FAST string comparison in VB

HELP!  I've got a program that has to look for string patterns from a
dictionary, and it is SOOOO slow!  I need a faster way to check string
equivalency than :

For I = 0 to DictCount
   If Dict(I) = CheckString Then Exit For
Next I

If anybody has any ideas for a quicker comparison, or knows it's just not
possible, any help would be greatly appreciated.
-Jeff Mitchell



Sat, 23 Dec 2000 03:00:00 GMT  
 I need a FAST string comparison in VB

Quote:

> HELP!  I've got a program that has to look for string patterns from a
> dictionary, and it is SOOOO slow!  I need a faster way to check string
> equivalency than :

> For I = 0 to DictCount
>    If Dict(I) = CheckString Then Exit For
> Next I

> If anybody has any ideas for a quicker comparison, or knows it's just not
> possible, any help would be greatly appreciated.
> -Jeff Mitchell


  There are many techniques available, none of which I have source code for
:-) If nobody does either, try:

- searching for "string comparison" on the web (about 3000 matches from
AltaVista)
- algorithms books (the one I have lists several, including Boyer-Moore,
Knuth-Morris-Pratt and Rabin-Karp)
- if you're lucky, the local university library

A quick suggestion (untested). If the dictionary is relatively static, find a
hash function which generates a unique number for each word in the dictionary
(not an easy problem for me to solve, but anyway) then call the same function
on the word you want looked up.  Check to see if that number exists (binary
search if the list of unique numbers is in memory, index the field if it's in
a database), and if it does, that the words match. I'm sure there's a name
for this method, I just don't know it.

I believe this takes the size of the problem from O n to O log n, but hey,
I'm no mathematician. Just means lots faster for large n :-)

Steve



Mon, 25 Dec 2000 03:00:00 GMT  
 I need a FAST string comparison in VB
You should find that comparing string lengths is a good first step. If the
strings are different lengths then they can't be the same.

--
 -{*filter*}ie

Richard Waters,
Sapher Servers

NJM means No Junk Mail

<<Snip>>



Sat, 06 Jan 2001 03:00:00 GMT  
 I need a FAST string comparison in VB

Quote:

> HELP!  I've got a program that has to look for string patterns from a
> dictionary, and it is SOOOO slow!  I need a faster way to check string
> equivalency than :

> For I = 0 to DictCount
>    If Dict(I) = CheckString Then Exit For
> Next I

> If anybody has any ideas for a quicker comparison, or knows it's just not
> possible, any help would be greatly appreciated.

Steve Salter suggested hashing the values, then looking up based on the
hashes, which is a good solution for a very large dictionary, but before
you start getting into that you might consider changing to a binary
search rather than going straight through the values.  

This assumes you have a sorted list, if not you have a couple of other
options.  
1) if you have lots of memory, just load the whole thing into memory and
sort it.  There are several tree variants that include actually sorting
the values as you insert them.  Alternatively, load it up and use another
sort on it.

2) If you don't have lots of memory, follow Steve's suggestion and load
hashes of the values into memory, then do basically the same thing you
would with the complete strings but compare hashes instead.

3) If you have trouble getting the program to run because the VB5 runtime
DLLs keep swapping to disk, see what you can do about getting your
initial data sorted on disk, then work from there.  This will be _much_
slower than working in memory.

Changing your string comparisons isn't going to help much - it'll
probably slow you down, in fact.  Apparently the VB developers played
some games to speed things up, so VB's string comparisons are in many
cases faster than optimized ones in VC++ because down behind the scenes
they're written in optimized assembly language (and they do string length
comparisons first, as another poster suggested).



Mon, 08 Jan 2001 03:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Need a FAST String Comparison!

2. : Need Help with Now() and String comparison

3. Comparison strings with strings?

4. Speed of string comparisons in VB 3.0 Pro

5. fast string search algo needed

6. q: Need super fast string search method...

7. Need Fast DLL/OCX for String Processing/Parsing

8. Need help which way is fastest to pick out a segment from a string

9. Speed Comparison Post #1 of 2 (Was Fast Drawing)

10. Speed Comparison Post #2 of 2 - quite large (Was Fast Drawing)

11. Wanted - Faster VB string operations

12. String comparison does not work

 

 
Powered by phpBB® Forum Software