Fast keyword search through CSortedArray??? Anyone know how?

[revg75]

Hi There,

I have a virtual listview that I load up anywhere from 20,000 to 200,000 records into. The virtual listview handles this no problem at all. I am using the CSortedArray by PJ Naughter class to store a array of custom objects. I can sort the array very fast no problems.

My issue occurs when I have to do a keyword search. I have to be able to allow the user to search as they type into a text box. So the user starts off with a FULL list of ALL the items appearing in the virtual listview, as the type keys into the textbox the virtual listview starts drilling down and only showing items that have the letters being typed in the name. so simple example:

List
====
Greg
John
Steve
George

If the user types G in the text box the list will now look like below

List
====
Greg
George


I have this working using a simple for loop to loop through all the items at each keystroke and remove any items from the list that do not match the keys typed. However, when my list gets to 30,000 or higher the search begins to take up WAY too much CPU. Is there some faster way I can do search like this using the CSortedArry?

Thanks
Greg

[Vanaj]

I think the bottle neck here would be in the listing of the items in the listbox...the search should be very very fast...

[revg75]

Well it's pretty fast... doesn't take it long, but when it searches as you type keys it pauses in between keystrokes because it is taking so much cpu I think...

Is this right?

[Vanaj]

might try changing the search logic where it keeps track of the last find and then when the next key is pressed it starts searching from the last find point and not from the start.

[GCDEF]

Certainly if your array were sorted a binary search would be a lot quicker than a sequential one.

[Vanaj]

Certainly if your array were sorted a binary search would be a lot quicker than a sequential one.

I was headed there next with that suggestion...great minds.....

[revg75]

The thing is though.... That I have to check each single item no matter what anyway to see if that items name contains any of the letters typed into the text box, so would it really matter in this instance if I used a binary search or not?

Do I not have to check each and every item anyway?

Also I have not seen any binary search examples that can return multiple items.. usually they only search for one single item and bring back a single found or not found.. do you know of any exmaples where they do a binary search that brings back multiples?

Thanks,
Greg

[GCDEF]

Let me make sure I understand what you're asking.

If the list contained

Frog
go
golf

and the user typed in G, you wouldn't want frog to show up would you?

As to the binary search, it's pretty easily modified. Search until you find an item that matches your criteria, then read sequentially forward and backward from that point until your criteria is no longer met. Return everything in between.

[revg75]

Yes I would want frog to show up

[Vanaj]

Actually you would only need to start searching from your last find forward if the list is sorted, and you are searching for a word that starts with the first letter of the list and the user only adds chars to the end of the search word. If any other char is changed in the search string you would have to start from the beginning.

If you are searching for a word within a word then you only option is to start from the beginning.

[GCDEF]

Wow, then you're kind of screwed. You could use some king of hash table or multimap I suppose. It would be a little faster.

[revg75]

HAHAHA ok! Maybe I have to change my seach engine then... I might have to give the option to search within a word or from the begingin and just let my users know that when they want to search within a word, they are gonig to experience speed issues..

Incidentally, would putting the search in a seperate thread help with the search freezing up the rest of my app while typing?

Thanks,
Greg

[Vanaj]

HAHAHA ok! Maybe I have to change my seach engine then... I might have to give the option to search within a word or from the begingin and just let my users know that when they want to search within a word, they are gonig to experience speed issues..

Incidentally, would putting the search in a seperate thread help with the search freezing up the rest of my app while typing?

Thanks,
Greg

A little but not much as the thread and your main GUI will have same priority...

[GCDEF]

HAHAHA ok! Maybe I have to change my seach engine then... I might have to give the option to search within a word or from the begingin and just let my users know that when they want to search within a word, they are gonig to experience speed issues..

Incidentally, would putting the search in a seperate thread help with the search freezing up the rest of my app while typing?

Thanks,
Greg

Yeah, but what's the point. You can't start the second search until you have the results of the first I assume. You could wait until they've entered everything they're looking for before beginning your search too.

Your requirements seem a little weird though. Sounds like you're saying a user could type grof and frog would be returned. Without knowing what you're up to, that seems unusual.

[revg75]

Ya my search requirements are a bit weird, but not that weird.

If an item in the list was

iamadonkey

The user could type 'don', or 'donk', or 'key' and it would return a match. However if the user typed 'yeknod' it would NOT return a match.