Archived

This topic is now archived and is closed to further replies.

processing time ...

This topic is 5805 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is totaly non game related, but ... I wrote a program in C++ to process a certain text file. When I only had 200 records it took 12 seconds. Not bad i thought, but then i tried 400 records... 96 seconds. 800 records took over 400 seconds and 1600 records was well in the thousands. I narrowed the code down to the point where I was just opening the file and dumping the whole thing onto the heap and then looping through it with a very simple "for" loop. In otherwords, i stripped out all processing code. The results where about the same. So my question is then, why does the computer need an exponentialy longer time to deal with larger memory allocations? Could it be that my "for" loop used strlen?
    
for(unsigned long i = 0; i <= std::strlen(fileBuffer); i++){
}  
Does strlen take much longer to return the length of a buffer that is a quite large? Some of these records where hundreds of bytes so the allocated memory was pretty big. As i'm writing this i'm starting to think that it would have been much better to write...
  
unsigned long bufferSize = std::strlen(fileBuffer);
for(unsigned long i = 0; i <= bufferSize; i++){
}    
~ChaosBob (who probably just answered his own question) Edited by - chaosbob on February 24, 2002 8:03:53 AM

Share this post


Link to post
Share on other sites
yep, you just answered your own question.

The reason being, is that the program calls ''strlen'' on every loop of the array, and strlen is an O(n) algorithm. It essentially loops through the array on every pass.

So, putting that into a for loop causes your simple loop to become a double-nested loop, with a complexity of O(n^2), which makes your algorithm exponentially slower.

Caching the size of the loop is definitely the right choice.

Share this post


Link to post
Share on other sites
Thanks for that explanation. I was thinking more about strlen and how it works. I''m curious, what would be the behaviour resulting from calling strlen on an array of char''s in which no null terminator exists? Would strlen continue reading past the end of the array until it came across the next null byte in memory?

Just curious

~ ChaosBob

Share this post


Link to post
Share on other sites