The Question and Answer Board

[PMS Witch]

In a previous post, I suggested that using pointers would raise the efficiency of my anagram finder. I was curious about just how much difference various alterations would bring.

I established a base value by using my watch to time the program. 10 executions appeared to take 4 seconds.

My first optimisation was to substitute the resource consuming fscanf() for the more efficient fgets(). Since fgets() includes the CR and LF, I needed extra code to strip these two unwanted characters from the string. To compensate for this additional work, I counted the characters as I searched for the end of the string, eliminating the work of calling strlen(). My dictionary contains 109,000 words and I saved this bit of work with each.

With these changes, I was no longer able to measure execution times with my watch. I changed my .BAT file to now execute the program 100 times, and as well, print the time from the system clock. My system clock updates 18 times per second, which is accurate enough for what I have in mind.

100 executions now took 17.6 seconds.

I suggested previously that using pointers instead of array indices would save time. Array indices use arithmetic to determine which array element to access. Pointers can use increments. Intel processors can increment a register in few machine cycles, while arithmetic addition requires several cycles as well as the overhead in storing intermediate values.

Using pointers, 100 executions now took 16.1 seconds.

Since I substituted fgets() for fscanf(), I then substituted puts() for printf() too. Since the results consist of only a few words at the most, improvement, if any, was undetectable.

My point is this: one must be vigilant in choosing the correct library functions because they can often impact a program’s performance profoundly. With my anagram solver, changing the code to use pointers cut execution time by one second. However, selecting different library functions to read my dictionary file cut execution time by twenty-two seconds. (Less than half.)

As well, my pointer code is less readable or understandable by humans.

Example: while(*word) ++*(wordaarray+*word++-‘a’);

Imagine debugging a few thousand lines of code that looks like this! I’ll digress here, but I once worked with a guy whose code was filled with comments like “Guess what this does.” and “I forgot how this works.”

Again, thank-you for bringing the wordfinder and anagram solver to IH. I’ve filled a few spare moments experimenting and learned a bit from the observations.

Cheers, PW.