|
Hi everyone,
I need some advice on a project that I am working on, here's my situation:
I have a Flat File(.txt) serves a my database, it has 3 colums Fld1,Fld2,Fld3, this Flat File contains about 10,000 Records(SORTED Ascending) My program receives a String as a parameter, I need to locate this string in the Flat File if it exist. Ex:
String1 = "MR. & MRS BUTCH"
//Extract each word in this string and search it in the Flat File
What is the fastest way to search each word of String1 in the Flat File? if I use line per line search I imagine how long it will take to move "M" to "B" right?
Please help I really need some advice on what to use and how to use it.
Thanks/Regards
Sidney
|
|
|
|
|
For such small numbers (unless you have extremely large fields) I'd almost suggest just loading the file and then strstr it. But you wanted the fastest way... 
I think the fastest solution you can find would be to use gperf to create three separate indices for your "db" loaded into memory. I think that would give you O(1) lookup, and so far no one has beaten that.
|
|
|
|
|
Maybe try this (if your fields are a fixed length):
1) Find the first name in the list
2) Seek to the end of the file and find the last name in the list
3) Guess-timate roughly where your string might be in the list
// psuedo code
StringUpper = String1.Upper();
AvgItemPerLetter = NumItems/26;
NumOfFirstLetter = (int)String1[0] - (int)'A';
StartPosition = NumOfFirstLetter * AvgItemPerLetter;
4) check the string at that position and go forward or backward from there
Like it or not, I'm right.
|
|
|
|
|
Best way I can think of (assuming the list is sorted) is a subdivision technique in which you check the middle item in the list. If the items name is further down the list than the search string we check the term one quater of the way through the file. Then if the quater marker has a "value" less than the string we check the 3/8 mark and so on. Its a trial and improvment technique. Here's some pseudocode
int Find(Array strarray, String searchstring)
{
int count = strarray.GetCount(), pos = 0;
float shiftsize = count;
while(1)
{
shiftsize /= 2;
pos += ((unsigned long)shiftsize)+1
switch(strcmp(strarray[pos], searchstring)
{
case 0: return pos;
case 1:
shiftsize = min(shiftsize, -shiftsize);
break;
case -1:
shiftsize = max(shiftsize, -shiftsize);
break;
}
}
}
So here's a demonstration of how I hope it works: (hope this comes out ok on your browser...)
18 Items
X X X X X X Y X X X X X X X X X X X
Step 1: 10
Step 2: 5
Step 3: 8
Step 4: 6
Step 5: 7 The iterator is looking for the Y among an array of Xs. Here we just keep subdividing the area in which the correct entry potentially lies, until we have the correct answer "cornered". I', not sure how well my pseudocode will work - its only a demo, but this teqnique is FAST it will be able to locate your string in a 4000 entry index in around 12 or 13 steps! A big improvment on systematic search! The efficiency of the routine all depends on how you code it however!
With time we live, with money we spend!
Joel Holdsworth
|
|
|
|
|
Thanks everyone!! I'll try each of your suggestions, I really appreciate it =) if there's somebody else who can contribute any Ideas pls feel free to post.
And yes the fields are fixed length. and yes the data are stored in a Flat File(.txt) so i'm using file manipulations like open and testing for EOF.
Thanks/Regards
Sidney
|
|
|
|
|
although this requires that you restructure your data, trees are a very fast way of searching strings.
you start out with a list of the alphabet, and you select the first letter of your alphabet from the tree. the next level has all the letters that follow that letter in your search space, and you select the one you want. There may be only one letter that ever follows 'z' in your database, and so you find your entry in two steps from any number of records (possibly millions)
it looks like:
A
-u
--t
---o
----m
-----atic -----aton
----e
----b
--d
-b
-s
-r
B
C
D
E
[...].X
Y
Z
This could also be termed 'search space constraint', since you are looking only in the part of the file you wish to see based on your search string. and that applies to the constraint itself (searching a subset of a subset of a subset of data) and in this way is similar to the 1/2, 1/4, 1/8 etc method, but keeps in mind that we can cull about 1/26th in the first step, and less in each step after.
// Rock
|
|
|
|
|
I am with CLaW.
If you can afford to restructure how the data in your file is stored you could create a tree. However instead of doing the tree that CLaw suggested, since you have fixed data sizes, I would implment a simple binary tree. You could later adapt this to a red-black tree which is a more efficient version of a binary tree.
Anyway, you will be able to implement the binary tree in a way that you do not need any extra classes hold and read the data, you will be able to store all of your data directly in the file. When you want to manipulate the data you would map it into memory with a memory mapped file and then access the information as a pointer.
When you implement the binary tree, you will simply store the elements in an array in memory. This should be a fairly simple task since all of your fields are fixed size. It would be more difficult and probably not worth while if your fields were not fixed.
Anyways, to performance:
A balanced binary tree will allow you to have O(ln(n)) lookup time.
for 10000 elements ln(10000) = 9.21 lookups
for 1000000 elements ln(1000000) = 13.82 lookups
Let me know if you are interested in this approach.
Build a man a fire, and he will be warm for a day
Light a man on fire, and he will be warm for the rest of his life!
|
|
|
|
|
Hi I am curios about this, can you give me more info about this?
Thanks/Regards
Sidney
|
|
|
|
|
I am at work right now, and I do not have much time to look for a good link for you. I will try to get some information for you tonight (about 7-8) hours.
In the mean while, try a search on google for something like:
array implementation "binary tree"
This should get you started, in the short time that I looked, I could not find a good source sample.
Also try learning a little bit about red-black trees, this is the implementation that you will want to settle on if you go this route. Heapsort is another item to look at.
Good Luck
Sorry I can't give you more information right now.
Build a man a fire, and he will be warm for a day
Light a man on fire, and he will be warm for the rest of his life!
|
|
|
|
|
If you only want to search the file and your strings are as you say fixed, then this is also a possibility:
Map your file using CreateFileMapping() and MapViewOfFile() from the Win32 API.
The filemapping lets you access your file as if it was a chunk of memory, and the OS takes care of all the IO stuff in the background.
MapViewOfFile() returns a pointer that you can pass as the basepointer to bsearch() from the C-runtime (stdlib.h).
This function does a binary search using a base pointer to an array of items, the size of each item (that's why the strings have to be fixed) and a function pointer to a function that can compare two strings (you could easily wrap strcmp() or lstrcmp() for this purpose).
This technique should be the fastest way of searching, but if insertion is an issue, then of course you should use trees.
"It could have been worse, it could have been ME!"
|
|
|
|
|
Someone once told me that using STL Map, which internally is an implementation of a binary tree, is an efficient way to solve this sort of problem.
|
|
|
|
|
The STL map does use a red-black tree (specialized version of a binary-tree).
This may be a little tricky to use though if he needs to parse through different strings in a key entry in order to perform his lookup.
Build a man a fire, and he will be warm for a day
Light a man on fire, and he will be warm for the rest of his life!
|
|
|
|
|
I want to display an icon in a dialog. I add a static control, set it to type Icon and select the Icon from my resources.
The problem is that, even though the icon I'm using is larger than the default size, the dialog insists on scaling it down to the default size.
How do I tell VC that I want to display the icon at it's actual size? I'd use a bitmap instead but I want it to have a non-rectangular shape and using an icon seemed simpler.
|
|
|
|
|
Overriding the paint handler in your dialog and using DrawIconEx will do the trick.
Dov Sherman wrote:
How do I tell VC that I want to display the icon at it's actual size?
Shout at it really loud. Use harsh language. Tell it that Microsoft Sucks™. Then try DrawIconEx.
|
|
|
|
|
Set the style to "real size image" in the resource editor or programmatically.
|
|
|
|
|
In a dialog-based MFC, i've created a mutex as a result of pressing of a button, this way:
m_hMutex=CreateMutex(NULL, FALSE, "unique name");
Later, i call:
WaitForSingleObject(m_hMutex, INFINITE);
waiting for a worker to release the mutex.
The behaviour of the stuff is very strange: the worker doesn't release the mutex, but the main-one passes the WaitForSingleObject call and returns WAIT_OBJECT_0 immediately.
If you know how could it be fixed, please kick a click to some reply.
rechi
|
|
|
|
|
Has the worker really acquired the mutex before you try to wait?
Also, if this is the only way you are using it perhaps an event is a better choice than a mutex?
|
|
|
|
|
I pass the mutex' handle by the PVOID of the worker, while the mutex is constructed with FALSE on bInitialOwner.
It has to behave like a theoretical binary semaphore.
rechi
|
|
|
|
|
Then, how do you know that the started thread has indeed started and acquired the mutex?
Perhaps an event is a better choice in this case. If you create an event in the non-signalled state, hand it over to the thread you're creating and then WaitFor... until the other thread signals the event object (SetEvent).
|
|
|
|
|
If you name the Mutex or Event the same in both threads there is no need to pass a handle to the other thread. Remember make the name unique in the system use a GUID for example. Then Create the mutex in the main thread and open it in worker threads.
John
|
|
|
|
|
Are you calling WaitForSingleObject(m_hMutex, INFINITE); in the worker. Your call to CreateMutex does not acquire the mutex.
John
|
|
|
|
|
I was told that you can perform this conversion using the transforms and widen and narrow functions. But having played with the transform function, I keep getting an error regarding not beign able to find the widen() function. Where is widen() defined?
this is what i do:
wstring wstr;
string str;
transform(str, wstr, widen());
|
|
|
|
|
Where is widen() defined?
basic_ios
If you for some reason can't read the documentation, you might try the following:
Open an explorer window and navigate down to your MSVC include directory. Press F3. Type "widen(" (without the quotes) in the "Containing text" edit box.
Once you get a sample compiled you can get there even faster by pressing F12 from within the IDE.
|
|
|
|
|
I have an XML document that includes a DTD . I need to parse this file using VC++ using the DOM .Where can I find resources for doing this . Please help
Actx
|
|
|
|
|
http://www.codeproject.com/soap/#XML
I vote pro drink ![Beer | [beer]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/beer.gif)
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
