Arthur David Olson <olsona@elsie.nci.nih.gov> writes:
...for a virtual tie between the cache and search approaches.
But that is for zdump. Binary search has a better worst-case behavior in general, no? If the table has N entries, binary search is O(log N) time whereas the cache approach is O(N). So if it's a virtual tie in the zdump case, then binary search is the way to go. Another possibility is to combine the ideas, and to use a cache if the cache works in O(1) time, falling back on binary search otherwise. To cater to zdump we can also search the cache + 1 and the cache - 1. The following approach uses that approach and benchmarks slightly better than the cache approach. But really, it's quite a bit of complexity for not much benefit, and think I'd prefer the simple binary search. =================================================================== RCS file: RCS/localtime.c,v retrieving revision 2006.2.0.2 retrieving revision 2006.2.0.6 diff -pc -r2006.2.0.2 -r2006.2.0.6 *** localtime.c 2006/02/22 00:24:05 2006.2.0.2 --- localtime.c 2006/03/09 07:02:09 2006.2.0.6 *************** struct tm * const tmp; *** 1266,1274 **** break; } } else { ! for (i = 1; i < sp->timecnt; ++i) if (t < sp->ats[i]) ! break; i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i]; --- 1266,1311 ---- break; } } else { ! static int guess; ! int lo = 1; ! int hi = sp->timecnt; ! ! /* ! ** If the previous guess is in range, try it again, ! ** and if that doesn't work try guess - 1 and guess + 1. ! */ ! i = guess; ! if (lo <= i && i < hi) { ! if (t < sp->ats[i]) { ! if (sp->ats[i - 1] <= t) ! goto found; ! i--; ! if (sp->ats[i - 1] <= t) ! goto found; ! hi = i - 1; ! } else { ! i++; ! if (i == hi || t < sp->ats[i]) ! goto found; ! lo = i + 1; ! } ! } ! ! /* ! ** The new value is far from the old, so use a binary ! ** search to find it. ! */ ! while (lo < hi) { ! i = (lo + hi) >> 1; if (t < sp->ats[i]) ! hi = i; ! else ! lo = i + 1; ! } ! i = lo; ! ! found: ! guess = i; i = (int) sp->types[i - 1]; } ttisp = &sp->ttis[i];