[RESOLVED] Need advice - what to use CStringArray or CStringList

[Philip Nicoletti]

What happens is that first it goes really fast but then it literally slows down to a crawl (probably due to constant memory reallocations of the dynamic array.) The file search, I believe is cached by the OS so the second pass runs very fast.

CArray can have that problem (altough 1000 seems very small for that
to happen). a std::vector will not run in to that difficulty nearly as much.
To prevent re-allocations, a CList or std:: list or std:eque could be
used.

When I asked : for each tag ... a list of files that have that tag ?

you answered : If I find that the tag matches I'm updating the file that this tag is in and save it back to disc.


So does this mean at some point, you are given a tag ... you need to
find ALL files that have that tag ? If so, then the following should work:

std::map< CString , list<CString> > (or similar MFC)
where the key is the tag , and the value is a list of files
having that tag.

[Paul McKenzie]

So what would you use in this case? (I can't go with std::vector since I've never used it before and I need to go with something that I already know.)

What if what you already know is less efficient than something you don't know? Are you willing to learn the thing that you don't know?

It has been reported (and I tend to agree), that the STL containers are more efficient and robust than the MFC containers. All it takes is an example or two from a book as to how to use them correctly. Unless you really have a huge stake in the serialization methods used in the MFC container classes, or you're maintaining a legacy MFC only app, IMO there is little, if any reason to be using the MFC container classes. I've seem rumors where the Microsoft engineers do not even use the MFC containers, but use the STL containers, but those are just rumors and I can't really substantiate them (but it wouldn't surprise me).

To be honest, I'm kind of surprised the MFC containers haven't been deprecated -- they have been around since 1990, before the STL containers made their way into the C++ standard library, and IMO been superseded by the standard components. There was nothing wrong with the MFC containers back in the early days of Visual C++ 1.0 or 1.5, but the standard C++ library container classes has surpassed those old MFC container classes (but again, only if you really and truly need the MFC serialization stuff in the MFC container classes, and even then, you can write your own serialization for the STL containers).

Now CString, that is a different story -- the CString class (which is now templated) is a very good implementation that has advantages over std::string.

Regards,

Paul McKenzie

[ahmd]

OK, guys, I see your point and I'm ready to do a comparative analysis, but I need your help to substitute my existing methods with the "better ones". So I'm currently using the following technique.

1. I have a global variable for the array that contains all paths:

CStringArray* pArrConvFiles;

2. During the first pass I collect file paths into that array like this:

pArrConvFiles->Add(strFilePath);

3. Then when I need to find if a certain file is in the array during the second pass I do the following:

	for(int i = 0; i < pArrConvFiles->GetCount(); i++)
	{
		if(strFile.CompareNoCase(pArrConvFiles->GetAt(i)) == 0)
		{
			//Found it
			return TRUE;
		}
	}

	return FALSE;

[Paul McKenzie]

OK, guys, I see your point and I'm ready to do a comparative analysis, but I need your help to substitute my existing methods with the "better ones". So I'm currently using the following technique.

1. I have a global variable for the array that contains all paths:

CStringArray* pArrConvFiles;

Why does pArrConvFiles need to be a pointer?

Regards,

Paul McKenzie

[ahmd]

Why does pArrConvFiles need to be a pointer?

OK, I'll change it to:

CStringArray ArrConvFiles;

but it has to be a pointer in #2 & 3. Does it make that much slower if it's a pointer?

[Paul McKenzie]

3. Then when I need to find if a certain file is in the array during the second pass I do the following:

	for(int i = 0; i < pArrConvFiles->GetCount(); i++)
	{
		if(strFile.CompareNoCase(pArrConvFiles->GetAt(i)) == 0)
		{
			//Found it
			return TRUE;
		}
	}

	return FALSE;

If you sorted the array of names first, then you could use a binary search instead of looping through each element. Or maybe you should use a different container, one that has fast lookups (map, for example).

Regards,

Paul McKenzie

[ahmd]

If you sorted the array of names first, then you could use a binary search instead of looping through each element. Or maybe you should use a different container, one that has fast lookups (map, for example).

Paul, I really don't know what it means. If you give me a code sample I'll substitute it with what I already have and run the two for the same folder and post here the exact time that it took two methods to complete.

[Paul McKenzie]

Paul, I really don't know what it means. If you give me a code sample I'll substitute it with what I already have and run the two for the same folder and post here the exact time that it took two methods to complete.

First, the bottleneck I see is the "compareNoCase" function, on top of using a linear data structure such as an array.

Possibly, you should use a map of <CString, CString>, where the key is the lower case version of the name, and the data (the second item in the map) is the original name without any case changes.

#include <map>
//...
typedef std::map<CString, CString> MapCStringToCString;
//...
MapCStringToCString myData;
//...
CString strFilePath;  // your original data you want to "add"
CString strFilePathLower;  // lower case version of the above 
//...
//.. This is how you add a name to the map
myData.insert( std::make_pair( strFilePathLower, strFilePath) );
//...

Now that the map is built, it is easy (and faster) to do lookups.

CString strToSearch;
// make sure that strToSearch has been converted to lower case first
//..
MapCStringToCString::iterator itFound = myData.find( strToSearch );
if ( itFound != myMap.end() ) 
{
   // we've found the name.  
   itFound->first // is the lower case version of the found name
   itFound->second //  this is the original case version of the name
}

If you have thousands of strings, this should be faster. Sorry, but I didn't use MFC map, only STL map. The possible slow part is the initial building of the map, but that should only be done once. If you're doing thousands of lookups, this is definitely faster. Note that there are absolutely no loops in the code. Since a map uses a tree structure, if you have 1,000 strings, you have a maximum of 10 comparisons. For 100,000 strings, the maximum number of comparisons is 16. Compare that with your loop --what if the item you want to find is at postion 99,999 of an array of 100,000? I think you would want to take a nap before you get a response back from the app if you used the array.

Whether this is the best way, container to use, etc. I don't think so, since I just came up with it out of the top of my head as a quick "solution" to what you posted. Others will mull over the advantages and disadvantages of what I posted.

Regards,

Paul McKenzie

[Philip Nicoletti]

You can also sort your CStringArray and do a binary search directly on it:

#include <algorithm>  // for sort and binary search

struct NoCaseLess
{
    bool operator() (const CString & lhs , const CString & rhs)
    {
        return lhs.CompareNoCase(rhs)==-1;
    }
};



    // after first pass and you have all the files
    const int n = pArrConvFiles->GetSize();

    std::sort(&pArrConvFiles->operator[](0),&pArrConvFiles->operator[](n),NoCaseLess());

    // and then when you want to search for a file

    if (std::binary_search(&pArrConvFiles->operator[](0),&pArrConvFiles->operator[](n),strFile,NoCaseLess()))
    {
        // found
    }

Question: How many times do you search thru the array ?

[autostrad]

How can I post a new thread?

[ahmd]

Thank you! Now I have two methods to try. Let me go with one at a time and I'll report which method is faster.

Possibly, you should use a map of <CString, CString>

Paul, since I'm using this on Windows OS (with a possible use of UNC network file names), it won't matter if a path is converted to all-lower letters, will it? If so, it will make it even faster if I eliminate your strFilePath member and keep strFilePathLower only.

You can also sort your CStringArray and do a binary search directly on it:

Very good too. Philip, I'll try it as soon as I'm done with Paul's code.

Question: How many times do you search thru the array ?

I can't really tell. It depends on the contents of files the function works with. It may be 1 through 10 per file on average.

How can I post a new thread?

Go to this link:
http://www.codeguru.com/forum/forumdisplay.php?f=7
and click "New thread" on the top left side.

[ahmd]

OK. A follow-up to what I posted above. I did the test and my results are inconclusive. I tested it on 862 files (not much, but I can't afford more time for it at this moment). During the operation the search was performed 646 times during the second pass. I also tested it with a release build of the project.

My unaltered method:
00:46 sec

Philip Nicoletti's code:
00:46 sec

Paul McKenzie's code:
00:45 sec

[bhushan1980]

Huh! just trying to catch up...

I have the code that's already tested and working, rewriting it completely is not what I'm looking for at this point. (Again my goal is to speed it up/optimize it.) But thanks for offering. Truly I didn't think about such approach. Although, wouldn't it be much slower if I propagate the whole class instead of just a CString object?

Well, I understand that and in such a case, what I suggested might be trivial. I just got it at the back of my mind, when I did a code in C++ to store information on a tree structure with parent and child nodes and hence used a collection of a class with Names, Parents and level members...The information was finally stored in SQL server database. I just remember the main skeleton; hardly remember the code.
Regards,
Bhushan

[ahmd]

One more interesting result, so I don't really know what to think.

128,079 files, ran only the first pass.

In case of CStringArray ---- 00:40 sec
In case of std::map<CString, CString> ---- 00:45 sec

[Paul McKenzie]

One more interesting result, so I don't really know what to think.

128,079 files, ran only the first pass.

In case of CStringArray ---- 00:40 sec
In case of std::map<CString, CString> ---- 00:45 sec

We have to see exactly what you timed and your code.

There is no way a loop that calls CompareNoCase on each iteration, and the number of iterations can be over 100,000 is faster than a map or a binary search that makes at a maximum, 15 or 16 comparisons to find an item. Maybe there is something buggy in your application.

If it were the case where an array is as fast as a map for lookups, why use a map at all in any application, and not just use arrays? Of course that doesn't make sense, so we need to see what you've coded.

Regards,

Paul McKenzie