How do you search down a row of strings comparing first letter ONLY than start scanning or comparing the whole string from the point where the letter is founded:

Could someone post an example . I want to get HelloWorld for starter.... with the letter H

Apple
Andy
Bear
Baby
Bark
Candy
CanNot
CanDo
Dog
Eat
Found
Gather
HelloMother
HelloFather
HelloWorld
HelloYouGuys
HelloZerox

I don't want it compare the whole word.....THAT IS WHAT I AM TRYING TO GET AWAY FROM....

Just compare first letter if not found move down to next line and see if it is there..(and so on)

THAN START COMPARING ALL WORD beginning with the letter (H) until you find HelloWorld

Thanks in Advance
Posted on 2002-02-06 00:55:47 by cmax
As its too late, and im too tired/lazy :grin: , i will outline pseudo asm:



-Load "Hello World" in a global cmp buffer (call it Q)

LOCAL buffer called Z
currentline = 1

::HERE::
copy CurLine text into Spare Buffer (Z)

mov esi, addr Q
mov edi, addr Z
mov ecx, stringlenth of Q
rep cmpsb
if( ecx == 0)
{ Sting Found! Break out!}
else
{ currentline++
if currline != END { goto ::HERE:: }
else { String Not in list! Break Out! }
}


its a wicked hybrid of C and ASM, i hope you can follow ok... too tired to clean it up better :P

Good Luck
NaN
Posted on 2002-02-06 02:10:27 by NaN
I will wait until you are back in shape. I don't want to rush this because we need the Fastest and Flawless possible way of doing this and I'm wondering if the if's statement may be to slow for something like this.... But looking at it it seems to be a great way of doing it....But i better wait...

Thank you
Posted on 2002-02-06 03:31:25 by cmax
"if currline != END { goto ::HERE::"

"The goto HERE" .... can you just go to the first letter in a (LINE) since you know which letter that you want to goto All Ready........ and begin from there?

If so you would not even have to start comparing until you get to that line? But i guest you still have to compare just to get there. Take your time...I wait...
Posted on 2002-02-06 03:39:52 by cmax
cmax,

it will have a bit to do with how you are loading the individual strings to test them but if its a buffer that each string is loaded into one after another, just store the sample string in one buffer and the loaded word in the other and do a string compare. Exit on first mismatch while scanning the string. A match occurs if the loaded string scans to the end.

Lets see what NaN brings up when he has had some sleep.

Regards,

hutch@movsd.com
Posted on 2002-02-06 05:35:14 by hutch--
Ok, will do, but it was more or less a game plan for you to work with :)

I cant do anything from here in the school lab, but tonight i will code something up...

If you want speed however, you may want to abandon your need to compare letter by letter, and use hutch's BM algorithm.. I've use it in the past for a "RAD" autocomplete engine. Where if i type "i - n - v " the search parses a list of 10000 + words and comes up with "invoke" to finish the thought. (worked surprisingly fast).

But if you only have a hundred or so strings to search this either will do. What i posted was only one solution, bounded by your constraints.

Anywho, just some thoughts..
NaN
Posted on 2002-02-06 11:11:26 by NaN
"if you only have a hundred or so strings to search this either will do"

No more than that for me...

I hate to be a baby about it, and i don't want to guest thinking that i figured it all out properly...so I had to wait for your bottom line...That always did it for me...

Thanks again NaN
Posted on 2002-02-06 13:13:22 by cmax
i coded this just to see if i could do it. i couldnt think of a faster way and if there is one i would like to see it.
Posted on 2002-02-06 17:27:22 by smurf
BM isn't the answer to everything ;). It's a search, not a compare...
it also has setup overheard which means it works best for searching
through a long block.

hutch: there can be quite some speed gains from manually testing the
first char of the strings you're comparing before CALLing the comparison
routine, even though the comparison routine bails out on first mismatch.
This was done (mostly for fun) in the Quake1 QC compiler, and it sped
up the code by between 10-30%... so in some cases, the overhead of
call can mean a *lot*.

Smurf, "rep cmpsb" is slow. The only string instructions you want to
use are "rep movsd" and "rep stosd", and only with dwords, and dword
aligned source and destination. Except of course if you're coding for
size, where all string instructions can be used with good results.
Posted on 2002-02-06 18:21:09 by f0dder
MMX can be used for multi-byte comparisions
with great speed and little to no set-up. I'll
leave the algorithm to the reader.

Hint: There is one example on this board. ;)
Posted on 2002-02-06 18:26:03 by bitRAKE
Basic linear search of a string table. This algorithm does not require a sorted table. Keep in mind that repe cmpsb has an early out -- it stops comparing when it detects different characters.
.data ; NOTE: [b]offset[/b] is implied in DD instructions


; Here is the table of string [b]pointers[/b]
table dd string01, string02, ...
dd string11, string12, ...
last_entry dd searchkey ; ensure search key will always be found

; Here are the predefined strings
string01 db "A1",0
string02 db "A2",0
;...
string11 db "Hall",0
string12 db "Help",0
;...

; This is the string we are searching for (the search key) in the table
searchkey db "Help",0

.code
mov ebx, offset table ; get address of 1st string ptr entry
sloop:
mov edi, [ebx] ; get string ptr stored in table
mov esi, offset searchkey ; get ptr to the search key
; ... insert string compare (edi, esi) code here
; ... if success, JMP to sfound
match_failed:
add ebx,4 ; match failed, point to next string ptr entry
jmp sloop
sfound:
; search failed if EBX == offset last_entry
; otherwise, EBX points to string ptr entry
Posted on 2002-02-06 18:49:38 by tank
Cmax, give it a whirl... post your results if your concerned... I just got in (late) from the lab.. (Friggn robot P**S'n me off)... So Im burnt and going to bed... If your still stumped tomorrow, i will try and get it for you then...

Best of luck..
NaN
Posted on 2002-02-06 22:47:53 by NaN
NaN, im in no rush.

After seeing all the things that you Aministator do, I know sometime you just have to wait or even miss. That's why I Posts with a main key word . I just hope for an refrerece to go to when i come back to the subject and that the info would be easy to find for me and anybody else.

This board just keep you PoP-InG. One new subject after another...

I'm on my way to strutures now...BIG TIME....
Frist i want to Break-em All Down.... Than learn how to use them...

Thats the way a little boy do when he get a new train set...They tear them up a few days after Xmas than in march or April you come home and he got it running again...

Dame...

Do we ever get a mental break...

I saw all of the Robots on a BitMap post by ....
Who was that ...
Was that you ...

Kool

By the way... All of the ideas here is ready to be put to work, any more would only be a PLUS pretaining to this subject... Hope most answers can be founded here...

Thanks
Posted on 2002-02-07 01:23:19 by cmax
Interestingly enough a linear search is probably the fastest way to do it IF the data is sequential. The advantage of doing it this way is that you save the load THEN compare time by sequentially reading it in memory.

===================
BM isn't the answer to everything . It's a search, not a compare...
===================

Any search algo does comparison, they will not work if you don't. If the byte data is only short, a linear scan is faster but a BM catches it up REAL fast. :)

cmax,

let us know how you store the different strings as this will effect how you can find the text you are after the fastest.

Regards,

hutch@movsd.com
Posted on 2002-02-07 05:49:41 by hutch--
I just had a quick play and here is the result. It assumes that you store the data in a linear fashion so I used your string samples and put them in the .DATA section.

Regards,

hutch@movsd.com
Posted on 2002-02-07 06:20:56 by hutch--
I'm probably wrong but isnt this type of
problem best solved by a hash table? I'm going
to write some code to test this, will post as
soon as its done.

take care
prs
Posted on 2002-02-08 01:13:10 by prs
Maybe it don't make no since!

I'll just remove this...

Thanks anyway everybody....
Posted on 2002-02-08 02:56:40 by cmax
Originally posted by cmax
In real time running the program of course we could never tell because its still lighting fast TO THE USER.
But as programmers we are suppose to take care of these things even thought the users will never tell the difference....



Just a question, are you on drugs or somethings? ;-)


Random
Posted on 2002-02-08 03:38:56 by random
Forget the question if it was that bad...

Sorry
Posted on 2002-02-08 05:32:09 by cmax
LSD?
Posted on 2002-02-08 06:03:51 by random