Tại sao gmtime được triển khai theo cách này?

Question

Tôi đã xảy ra trên nguồn cho chức năng gmtime của Minix. Tôi đã quan tâm đến bit tính số năm từ ngày kể từ thời đại. Dưới đây là ruột của bit:

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++; 
} 

Dường như các thuật toán là O (n), trong đó n là khoảng cách từ các thời đại. Ngoài ra, có vẻ như LEAPYEAR phải được tính riêng cho mỗi năm – hàng chục lần cho các ngày hiện tại và nhiều hơn nữa cho những ngày xa trong tương lai. Tôi đã có thuật toán sau đây để làm điều tương tự (trong trường hợp này từ thời đại theo tiêu chuẩn ISO-9601 (Năm 0 = 1 BC) chứ không phải là UNIX kỷ nguyên):

#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 

này chạy trong thời gian O (1) cho ngày bất kỳ , và có vẻ như nó sẽ nhanh hơn ngay cả đối với những ngày hợp lý gần năm 1970.

Vì vậy, giả sử các nhà phát triển Minix là những người thông minh đã làm theo cách của họ vì lý do và có thể biết nhiều hơn về C so với tôi , tại sao?

Answer 1

Đây là suy đoán, nhưng có lẽ MINIX đã yêu cầu mà là quan trọng hơn tốc độ thực thi, chẳng hạn như sự đơn giản, dễ hiểu và dễ hiểu? Một số mã được in trong một cuốn sách giáo khoa, sau khi tất cả.

Answer 2

Phương pháp của bạn có vẻ hợp lý, nhưng khó hơn một chút để có được nó hoạt động cho EPOCH_YR = 1970 vì bây giờ bạn đang ở giữa chu kỳ trên một vài chu kỳ.

Bạn có thể xem liệu mình có tương đương với trường hợp đó hay không và xem liệu nó có còn tốt hơn không?

Bạn chắc chắn phải tranh luận rằng việc triển khai gmtime() có nên được sử dụng trong bất kỳ mã hiệu suất cao nào không. Đó là rất nhiều công việc bận rộn để làm trong bất kỳ vòng chặt chẽ.

Answer 3

Ran mã của bạn như mã y2 Minix như y1 Solaris 9 v245 & có dữ liệu hồ sơ này:

%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 

Có lẽ đó là một câu trả lời

Answer 4

Cách tiếp cận đúng. Bạn chắc chắn muốn đi cho một O (1) algo. Sẽ làm việc trong lịch của người Maya mà không có quảng cáo. Kiểm tra dòng cuối cùng: dayno được giới hạn ở 0..364, mặc dù trong những năm nhuận nó cần phải nằm trong phạm vi 0..365. Dòng trước đó có một lỗ hổng tương tự.