(^178) 97 Things Every Programmer Should Know
Use the Right
Algorithm and
Data Structure
Jan Christiaan “JC” van Winkel
A big bank with many branch offices complained that the new computers it
had bought for the tellers were too slow. This was in the time before everyone
used electronic banking, and ATMs were not as widespread as they are now.
People would visit the bank far more often, and the slow computers were
making the people queue up. Consequently, the bank threatened to break its
contract with the vendor.
The vendor sent a performance analysis and tuning specialist to determine
the cause of the delays. He soon found one specific program running on the
terminal that consumed almost all the CPU capacity. Using a profiling tool, he
zoomed in on the program and he could see the function that was the culprit.
The source code read:
for (i=0; i<strlen(s); ++i) {
if (... s[i] ...) ...
}
And string s was, on average, thousands of characters long. The code (writ-
ten by the bank) was quickly changed, and the bank tellers lived happily ever
after....SOULDNH ’T THE PROGRAMMER have done better than to use code that
needlessly scaled quadratically?
Each call to strlen traversed every one of the many thousand characters in
the string to find its terminating null character. The string, however, never
changed. By determining its length in advance, the programmer could have
saved thousands of calls to strlen (and millions of loop executions):
n=strlen(s);
for (i=0; i<n; ++i) {
if (... s[i] ...) ...
}