代码之家 › 专栏 › 技术社区 › Thom Smith

为什么GMTime是这样实现的?

time c

Thom Smith · 技术社区 · 16 年前

我在minix的gmtime函数的源代码中遇到过。我对从新纪元开始计算年数的那一点很感兴趣。下面是这一点的要点:

http://www.raspberryginger.com/jbailey/minix/html/gmtime_8c-source.html

http://www.raspberryginger.com/jbailey/minix/html/loc__time_8h-source.html

#define EPOCH_YR 1970
#define LEAPYEAR(year) (!((year) % 4) && (((year) % 100) || !((year) % 400)))
#define YEARSIZE(year) (LEAPYEAR(year) ? 366 : 365)

int year = EPOCH_YR;

while (dayno >= YEARSIZE(year)) {
    dayno -= YEARSIZE(year);
    year++;
}

它看起来像是算法是O(n),其中n是距纪元的距离。此外,似乎每年都必须单独计算闰年——当前日期有几十次,未来日期有更多次。我有下面的算法来做同样的事情(在本例中是从ISO-9601 epoch(0年=1 bc)开始的,而不是从Unix epoch开始的):

#define CYCLE_1   365
#define CYCLE_4   (CYCLE_1   *  4 + 1)
#define CYCLE_100 (CYCLE_4   * 25 - 1)
#define CYCLE_400 (CYCLE_100 *  4 + 1)

year += 400 * (dayno / CYCLE_400)
dayno = dayno % CYCLE_400

year += 100 * (dayno / CYCLE_100)
dayno = dayno % CYCLE_100

year +=   4 * (dayno / CYCLE_4)
dayno = dayno % CYCLE_4

year +=   1 * (dayno / CYCLE_1)
dayno = dayno % CYCLE_1

这在O(1)中适用于任何日期,并且看起来应该更快,即使对于接近1970年的日期也是如此。

所以,假设minix开发人员是聪明人,他们这样做是有原因的,而且可能比我对c了解得更多,为什么?

4 回复 | 直到 16 年前

bk1e 16 年前

这纯粹是猜测,但也许Minix的需求比执行速度更重要,比如简单、易于理解和简洁?毕竟,有些密码是印在教科书上的。

jim mcnamara 16 年前

运行代码为y2 minix代码为y1 solaris 9 v245&获取此探查器数据:

 %Time Seconds Cumsecs  #Calls   msec/call  Name
  79.1    0.34    0.34   36966      0.0092  _write
   7.0    0.03    0.37 1125566      0.0000  .rem
   7.0    0.03    0.40   36966      0.0008  _doprnt
   4.7    0.02    0.42 1817938      0.0000  _mcount
   2.3    0.01    0.43   36966      0.0003  y2
   0.0    0.00    0.43       4      0.      atexit
   0.0    0.00    0.43       1      0.      _exithandle
   0.0    0.00    0.43       1      0.      main
   0.0    0.00    0.43       1      0.      _fpsetsticky
   0.0    0.00    0.43       1      0.      _profil
   0.0    0.00    0.43   36966      0.0000  printf
   0.0    0.00    0.43  147864      0.0000  .div
   0.0    0.00    0.43   73932      0.0000  _ferror_unlocked
   0.0    0.00    0.43   36966      0.0000  memchr
   0.0    0.00    0.43       1      0.      _findbuf
   0.0    0.00    0.43       1      0.      _ioctl
   0.0    0.00    0.43       1      0.      _isatty
   0.0    0.00    0.43   73932      0.0000  _realbufend
   0.0    0.00    0.43   36966      0.0000  _xflsbuf
   0.0    0.00    0.43       1      0.      _setbufend
   0.0    0.00    0.43       1      0.      _setorientation
   0.0    0.00    0.43  137864      0.0000  _memcpy
   0.0    0.00    0.43       3      0.      ___errno
   0.0    0.00    0.43       1      0.      _fstat64
   0.0    0.00    0.43       1      0.      exit
   0.0    0.00    0.43   36966      0.0000  y1

也许这就是答案

Cade Roux 16 年前

Your method seems sound, but it's a little more difficult to get it to work for EPOCH_YR = 1970 because you are now mid-cycle on several cycles.

对于gmtime()实现是否应该在任何高性能代码中使用这一点,您肯定是对的。在任何一个紧凑的循环中都要做大量的工作。

user696732 12 年前

Correct approach. You definitely want to go for an O(1) algo. Would work in Mayan calendar without ado. Check the last line: dayno is limited to 0..364, although in leap years it needs to range 0..365 . The line before has a similar flaw.