Pourquoi gmtime est-il implémenté de cette façon?

Je suis arrivé à travers la source pour la fonction gmtime de Minix. Je me suis intéressé au bit qui a calculé le nombre d'année depuis des jours depuis l'époque. Voici le courage de ce petit:Pourquoi gmtime est-il implémenté de cette façon?

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

Il ressemble à l'algorithme est O (n), où n est la distance de l'époque. En outre, il semble que LEAPYEAR doit être calculé séparément pour chaque année – des dizaines de fois pour les dates actuelles et beaucoup d'autres pour les dates loin dans le futur. J'ai eu l'algorithme suivant pour faire la même chose (dans ce cas, de l'époque ISO-9601 (année 0 = 1 BC) plutôt que l'époque UNIX):

#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

Cela va dans O (1) pour toute date Donc, en supposant que les développeurs de Minix sont des gens intelligents qui ont fait leur chemin pour une raison, et en savent probablement un peu plus sur C que je ne le fais. , Pourquoi?

Source

2010-06-28 Thom Smith

Il semble que cela devrait être plus rapide. Vous devez penser à votre architecture et à la vitesse à laquelle certaines instructions comme multiplier sont et à quel point un prédicteur de branche est bon (la plupart sont très bonnes). @jim mcnamara a des résultats intéressants. – BobbyShaftoe

Ceci est pure spéculation, mais peut-être MINIX les besoins étaient plus important que la vitesse d'exécution, comme la simplicité, la facilité de compréhension et la concision? Une partie du code a été imprimée dans un manuel, après tout.

Source

2010-06-29 06:07:19 bk1e

Votre méthode semble solide, mais il est un peu plus difficile de l'utiliser pour EPOCH_YR = 1970 car vous êtes maintenant en cours de cycle sur plusieurs cycles.

Pouvez-vous voir si vous avez un équivalent pour ce cas et voir si c'est encore mieux?

Vous avez certainement raison de dire que l'implémentation de gmtime() devrait être utilisée dans n'importe quel code hautes performances. C'est beaucoup de travail occupé à faire dans les boucles serrées.

Source

2010-06-28 21:51:05

Juste en soustrayant le nombre de jours à partir des années 0..1970 fonctionnerait. Ce serait constant, pourrait être stocké comme un autre #define. –

Comme Adam l'a dit, le simple fait de soustraire le décalage le corrigerait, bien qu'il déborde d'un horodatage de 32 bits. Définir l'époque à 2000 AD réglerait les deux problèmes, nécessitant une opération supplémentaire avant et après le calcul principal. Si des horodatages 64 bits sont disponibles, l'année ISO zéro est probablement meilleure car elle a) enregistre une opération, b) est plus évidente, et c) facile jour-de-semaine calendrier-agnostique. D'autre part, si vous êtes bloqué avec un horodatage 32 bits avec une époque moderne, vous pourriez aussi bien oublier les cycles de 100 et 400 ans, puisque 2000 est une année bissextile de toute façon et 1900 et 2100 sont hors de portée. –

@Thom Smith Le nombre de jours en 2000 ans (~ 730k) est bien inférieur à 2^32. Aucun code snip ne concerne les secondes. –

Ran votre code code y2 MINIX y1 Solaris 9 V245 & a ces données profileur:

%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

Peut-être est une réponse

Source

2010-06-28 22:00:35

il semble que l'implémentation en boucle s'exécute dans 0secs où l'implémentation modulo en 0.01 sec. –

Certainement un cas pour faire l'analyse comparative. J'aurais parié que le code du demandeur serait plus rapide avant de voir ces résultats. – ryyker

Approche correcte. Vous voulez absolument opter pour un algo O (1). Travaillerait dans le calendrier Maya sans ado. Vérifiez la dernière ligne: dayno est limité à 0..364, bien que dans les années bissextiles il doit être compris entre 0..365. La ligne avant a un défaut similaire.

Source

2013-09-12 00:14:06 user696732

Pourquoi gmtime est-il implémenté de cette façon?

Répondre

Questions connexes