Re: Fast keyword Search through CSortedArray?? anyone? - C / C++ / MFC Discussion Boards

Re: Handling Stack Overflow

Shog⁹27-Sep-06 19:03

Shog⁹

27-Sep-06 19:03

risingtechie wrote:
Is there anyway to handle stack over flow without using windows exceptions?

When you run out of stack space, you'll end up trying to write to the guard page that's set up just beyond the end of the stack. This is what triggers the Stack Overflow exception, and any chance you have of handling it is going to have to work with SEH in some way, because that's how Windows does it. (yeah, you could probably write your own stack code, and compiler to go with it... but that's getting a bit excessive)

Handling the Stack Overflow exception is tricky - there's little or no stack left, so calling any methods will likely fail (the sort of failure where it's impossible for the OS to do anything but terminate the app and move on). If you really, really need it to work, you can use SEH or XP's Vectored Exception Handler support to catch the exception, and then immediately switch to another stack.

This is... decidedly non-trivial. And as Zac mentioned, if you're overflowing the stack, you probably have other problems with your program. There will be very little you can do to salvage the situation.

If you have the need for a system tolerant of such errors, you'll probably be better off using a separate watchdog program to monitor the main app, and restart it when things go wrong.

----
Scripts i’ve known...
CPhog 1.8.2 - make CP better.
Forum Bookmark 0.2.5 - bookmark forum posts on Pensieve
Print forum 0.1.2 - printer-friendly forums
Expand all 1.0 - Expand all messages
In-place Delete 1.0 - AJAX-style post delete
Syntax 0.1 - Syntax highlighting for code blocks in the forums

Re: Handling Stack Overflow

ShilpiP27-Sep-06 20:03

ShilpiP

27-Sep-06 20:03

It is a wrong practice to implement stack with the help of array .u use linklist than ur problem will be solved

Fast keyword Search through CSortedArray?? anyone?

Greg Ellis27-Sep-06 9:50

Greg Ellis

27-Sep-06 9:50

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

Re: Fast keyword Search through CSortedArray?? anyone?

David Leyva27-Sep-06 10:06

David Leyva

27-Sep-06 10:06

Hi
You can use a Thread to process a binary search. The when search finish you can select or show the item(s)

David

Re: Fast keyword Search through CSortedArray?? anyone?

Greg Ellis27-Sep-06 10:15

Greg Ellis

27-Sep-06 10:15

ah ok thank you!

Do you know if there is any examples of where I can find how to do this?

Thanks,
Greg

Re: Fast keyword Search through CSortedArray?? anyone?

Steve S27-Sep-06 21:49

Steve S

27-Sep-06 21:49

If I understand correctly, you have a list of ordered elements, and a partial match. Binary search will help, but won't be exactly what you want.

To do something similar, I use a binary search which does a length restricted string comparison to find an element which matches, and then backs up to find the first match. For my application this approach is fine, since I only have a few items in each such grouping. Your mileage may vary.

However, a better approach, which someone has already suggested, might be to have a small array of indices into the array, keyed by first letter. Essentially something like this:

typedef struct index
{
TCHAR chr;
int start;
} INDEX;
CArray<INDEX, INDEX&>> ix;

INDEX in;
ix.RemoveAll();
in.chr = _T('\0');
in.start = -1;
for(i = 0; i < nElements; i++)
{
// get first char of this item...
chr = ....;
if (in.chr!=chr)
{
// make a new index entry
in.chr = chr;
in.start = i;
ix.Add(in);
}
}
in.chr = _T('\0');
in.start = nElements;
ix.Add(in);

To do your search, look in the ix array for a matching first character, get the start index from the matching entry, and the stop index from the next entry Smile | :)

This gives you a smaller space to do additional matching if necessary.

Steve S
Developer for hire

Re: Fast keyword Search through CSortedArray?? anyone?

Zac Howland27-Sep-06 10:20

Zac Howland

27-Sep-06 10:20

Greg Ellis wrote:
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.

With that many items, you are going to eat up a lot of CPU time anyway. A map or hash table would allow for more efficient searching, but with an array (even a sorted one), you are still going to be stuck with an O(n) operation. Additionally, if you have 30,000 items in the list, and your search will only find 1 entry, the list control has to do a LOT of work to remove 29,999 items. So don't be surprised to see a CPU/Memory spike for a second or two.

If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week

Zac

Re: Fast keyword Search through CSortedArray?? anyone?

Waldermort27-Sep-06 15:18

Waldermort

27-Sep-06 15:18

Instead of using a single array to hold all the data, why not break it up into say 27 arrays (one for each letter of the alphabet and numbers). You would have to create an algorithm for adding items to the correct array and choosing the correct array depending on the first character entered.

Re: Fast keyword Search through CSortedArray?? anyone?

Stephen Hewitt27-Sep-06 20:40

Stephen Hewitt

27-Sep-06 20:40

Try something like this. It uses binary searches so it will be many, many times faster then using linear searches. It’s a simple console app which reads in words from a file (each word in the file separated by any white space). It is not limited to only matching a single charcter; you can match all words which start with "act" for example.
------------------------

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>

struct PrefixMatchLess : std::binary_function<std::string, std::string, bool>
{
bool operator()(const std::string &s, const std::string &prefix) const
{
const std::string sub = s.substr(0, prefix.length());
return sub<prefix;
}
};

struct PrefixMatchGreater : std::binary_function<std::string, std::string, bool>
{
bool operator()(const std::string &prefix, const std::string &s) const
{
const std::string sub = s.substr(0, prefix.length());
return sub>prefix;
}
};

int main()
{
// For notational convenience.
using namespace std;
typedef vector<string> StringList_t;
typedef istream_iterator<string> StringInIt_t;
typedef ostream_iterator<string> StringOutIt_t;

// Open the word list.
ifstream ifs("C:\\Words.txt");
if (!ifs)
{
cerr << "Failed to open word list!" << endl;
return 1;
}

// List for words.
StringList_t words;

// Read in the word list.
copy(StringInIt_t(ifs), StringInIt_t(), back_inserter(words));

// Sort the list and remove duplicates.
sort(words.begin(), words.end());
words.erase(unique(words.begin(), words.end()), words.end());

// Output the word list (diagnostic).
cout << "Word list:" << endl;
copy(words.begin(), words.end(), StringOutIt_t(cout, "\n"));
cout << endl;

for(;;)
{
// Get the prefix to search for.
string word;
cout << "Enter search prefix (! quit): ";
cin >> word;

// Check if the user wants to quit.
if (word=="!")
{
break; // Quit.
}

cout << endl;

// Calculate range.
StringList_t::iterator b = lower_bound(words.begin(), words.end(), word, PrefixMatchLess());
StringList_t::iterator e = upper_bound(b, words.end(), word, PrefixMatchGreater());

// Output results.
cout << "Matching words:" << endl;
copy(b, e, StringOutIt_t(cout, "\n"));
cout << endl;
}

return 0;
}

Steve

Clearing the edit box in ccombobox

lctrncs27-Sep-06 9:30

lctrncs

27-Sep-06 9:30

I am a beginner trying to clear the edit box of a combobox in drop list mode after making a selection from the list.

after selecting a list box entry, the control places a copy of it in the edit box by default, apparently using the SelectString member and the message WM_SETTEXT as part of the controls windows procedure.

when the dropdown type is used, ->SetEditSel and ->Clear etc will empty the edit box, (though not very elegantly). but the dropdown type still allows users enter text in the edit box (which is confusing and non-functional)

the drop list type prevents user edits of the edit box, but ->SetEditSel and ->Clear etc no longer appears to clear the edit box to pretty things up after selection.

I have tired many things already, and am considering trying to trap WM_SETTEXT or paint over the edit box somehow

I wonder if I am not missing some ridiculously minor thing (as I was before I realized the drop list type prevented user edits to the edit box)

Any suggestions about what I can do with/to my combobox control to prevent, clear or overwrite unwanted edit box text matching my selection in the list box?

Thanks to all...

"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash