explicación de timeval_subtract

Con la función “timeval_subtract” para encontrar el tiempo transcurrido entre dos tipos de estructura de timeval, ¿puede alguien explicar el propósito y las matemáticas paso a paso utilizadas para “Realizar el acarreo para la última resta actualizando y” y otras secciones? Entiendo el propósito de la función y cómo implementarla dentro de un progtwig, pero me gustaría entender cómo funciona dentro y no puedo encontrar ninguna explicación de esto en ningún lugar, y parece que no puedo entenderlo.

int timeval_subtract (struct timeval *result, struct timeval *x,struct timeval *y) { /* Perform the carry for the later subtraction by updating y. */ if (x->tv_usec tv_usec) { int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } if (x->tv_usec - y->tv_usec > 1000000) { int nsec = (y->tv_usec - x->tv_usec) / 1000000; y->tv_usec += 1000000 * nsec; y->tv_sec -= nsec; } /* Compute the time remaining to wait. tv_usec is certainly positive. */ result->tv_sec = x->tv_sec - y->tv_sec; result->tv_usec = x->tv_usec - y->tv_usec; /* Return 1 if result is negative. */ return x->tv_sec tv_sec; } 

Es una función descrita en relación con la biblioteca GNU C para determinar el tiempo transcurrido http://www.gnu.org/software/libc/manual/html_node/Elapsed-Time.html, por lo que no estoy buscando mejoras, sino simplemente una Explicación de por qué dividir y sumr y restar y multiplicar dentro de ella. ¿Qué logran estas operaciones aritméticas específicas? / ¿Por qué se realizan / no se realizan? He dado el paso pero todavía no puedo entenderlo. Continuaré haciéndolo hasta que lo haga (e incluso después de que alguien me lo explique), pero esperaba obtener una idea de alguien que ya lo comprende. La plataforma es UNIX, que soy nuevo en el uso, pero no creo que cambie las operaciones que tienen lugar dentro de la función. Es más una pregunta acerca de la aritmética que se realiza que el algoritmo que se utiliza.

A primera vista, parece que struct timeval contiene un tiempo dividido en dos partes:

  • tv_usec : microsegundos, lo ideal es que siempre estén por debajo de 1000000, pero parece que se permiten valores mayores, como lo sugiere el código
  • tv_sec – segundos (el número de múltiplos de 1000000)

y el tiempo en microsegundos es tv_usec + tv_sec * 1000000.

A la inversa, uno esperaría que esto fuera cierto:

  • tv_sec = tiempo en microsegundos / 1000000
  • tv_usec = tiempo en microsegundos% 1000000.

La función parece calcular la diferencia de tiempo entre *x y *y (lógicamente, *x*y ) y almacenarla en otra struct timeval , *result .

Un progtwig de prueba simple nos da algunos consejos:

 #include  struct timeval { long tv_sec; long tv_usec; }; int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y) { // preserve *y struct timeval yy = *y; y = &yy; /* Perform the carry for the later subtraction by updating y. */ if (x->tv_usec < y->tv_usec) { int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } if (x->tv_usec - y->tv_usec > 1000000) { int nsec = (y->tv_usec - x->tv_usec) / 1000000; y->tv_usec += 1000000 * nsec; y->tv_sec -= nsec; } /* Compute the time remaining to wait. tv_usec is certainly positive. */ result->tv_sec = x->tv_sec - y->tv_sec; result->tv_usec = x->tv_usec - y->tv_usec; /* Return 1 if result is negative. */ return x->tv_sec < y->tv_sec; } struct timeval testData00 = { 0, 0 }; struct timeval testData01 = { 0, 1 }; int main(void) { struct timeval diff; int res; res = timeval_subtract(&diff, &testData00, &testData00); printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec); res = timeval_subtract(&diff, &testData01, &testData01); printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec); res = timeval_subtract(&diff, &testData01, &testData00); printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec); res = timeval_subtract(&diff, &testData00, &testData01); printf("%d %ld:%ld\n", res, diff.tv_sec, diff.tv_usec); return 0; } 

Salida ( ideone ):

 0 0:0 0 0:0 0 0:1 1 -1:999999 

Del último resultado de la prueba, parece que la función devuelve (-1): 999999 en lugar de – (0: 1). Ambos valores representan el mismo tiempo negativo (o diferencia de tiempo) en microsegundos:

  • -1 * 1000000 + 999999 = -1
  • – (0 * 1000000 + 1) = -1

Entonces, ¿cómo funciona realmente?

Si x->tv_usec > = y->tv_usec entonces solo el segundo if probable que * se ejecute:

  if (x->tv_usec - y->tv_usec > 1000000) { int nsec = (y->tv_usec - x->tv_usec) / 1000000; y->tv_usec += 1000000 * nsec; y->tv_sec -= nsec; } 

Esto if comprueba si la diferencia en las partes de microsegundos solo es mayor que 1 segundo. Si es así, resta todos los segundos de esta diferencia de y->tv_usec (como microsegundos) y lo agrega a y->tv_sec (como segundos). Esto simplemente redistribuye el tiempo en *y sin cambiarlo realmente. Podrías reescribir esto if gusta esto para verlo más claramente:

  if (x->tv_usec - y->tv_usec > 1000000) { int nsec = (x->tv_usec - y->tv_usec) / 1000000; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } 

Una cosa importante a tener en cuenta aquí es que cuando la entrada *x y *y tienen su tv_usec en el rango de 0 a 999999 inclusive, el cuerpo de este if no se ejecuta (por lo tanto, probablemente * nunca sea ​​en realidad cuando x->tv_usec > = y->tv_usec y cuando tv_usecs están en el rango de 0 a 999999).

El efecto neto de esto if no está claro ahora.

Sin embargo, una cosa interesante se puede ver aquí. Si llamamos a esta función con *x = 0: 1000001 y *y = 0: 0, el resultado será incorrecto: diferencia = (-1): 2000001 (en lugar de 1: 1) y el valor de retorno de la función = 1 (en lugar de 0) . Esto sugiere que la función no es realmente adecuada para tv_usec > 1000000 e incluso para tv_usec > 999999 . Y debido a este comportamiento, voy a afirmar que la función tampoco es adecuada para tv_usec negativo en las entradas. Solo voy a ignorar esos casos frente a este comportamiento. Ya se ve lo suficientemente mal.

Echemos un vistazo a la primera if .

  /* Perform the carry for the later subtraction by updating y. */ if (x->tv_usec < y->tv_usec) { int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } 

Como lo sugieren el comentario y el código, cuando x->tv_usec < y->tv_usec necesitamos cuidar el “carry” entre los “dígitos” como si estuviéramos sumndo y no restando. Pero está bien, ya lo veremos.

Volvamos a la escuela por un momento.

¿Cómo haces 37 – 12?

Lo haces así:

 7 - 2 = 5 3 - 1 = 2 

Y así 37 – 12 = 25.

Ahora, ¿cómo estás 57 – 38?

Lo haces así:

 10/*because 7 < 8*/ + 7 - 8 = 9 5 - 3 - 1/*borrow, because of the above*/ = 1 

Y así 57 - 38 = 19. ¿Ves?

Y el cheque:

  if (x->tv_usec < y->tv_usec) { 

verifica si necesitamos o no cuidar este préstamo.

Entonces, ¿qué está pasando aquí? Miremos de nuevo:

  if (x->tv_usec < y->tv_usec) { int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; y->tv_usec -= 1000000 * nsec; y->tv_sec += nsec; } 

Si y->tv_usec > x->tv_usec , calcula la diferencia entre los dos en segundos completos y al igual que el otro if agrega estos segundos completos a y->tv_sec y los resta de y->tv_usec , simplemente redistribuyendo el tiempo en *y , sin cambiarlo.

El extra ( + 1 ) que se agrega a y->tv_sec aquí se restará de x->tv_sec al final de la función ( result->tv_sec = x->tv_sec - y->tv_sec; ) y por lo tanto Este 1 funciona como el préstamo que acabo de recordarles en el ejemplo 57 - 38 = 19.

¿Qué más está sucediendo aquí además del préstamo en sí y en algún momento la redistribución?

Como dije antes, solo ignoraré tv_usecs negativos y más de 999999, ya que es probable que se manejen incorrectamente.

Con esto tomo (y->tv_usec - x->tv_usec) / 1000000 para ser 0 y solo me quedan valores verdaderamente significativos de tv_usecs (0 a 999999 inclusive).

Entonces, si la condición if's es verdadera, básicamente y->tv_usec 1000000 de y->tv_usec y agrego 1 (el préstamo) a y->tv_sec .

Esto es lo mismo que teníamos en 57 - 38 = 19:

 10/*because 7 < 8*/ + 7 - 8 = 9 5 - 3 - 1/*borrow, because of the above*/ = 1 

De manera similar a este 10, 1000000 se agregarán más adelante aquí: result->tv_usec = x->tv_usec - y->tv_usec;

Y esta primera if es la carne de la función.

Si tuviera que escribir una función con un comportamiento similar, requeriría que los tiempos de entrada no fueran negativos y que las partes de microsegundos no fueran superiores a 999999 y escribiría esto:

 int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y) { result->tv_sec = x->tv_sec - y->tv_sec; if ((result->tv_usec = x->tv_usec - y->tv_usec) < 0) { result->tv_usec += 1000000; result->tv_sec--; // borrow } return result->tv_sec < 0; } 

Si por alguna extraña razón quisiera apoyar tv_usec > 999999 en las entradas, primero movería el exceso de tv_usec a tv_sec y luego haría lo anterior, algo como esto:

 int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y) { struct timeval xx = *x; struct timeval yy = *y; x = &xx; y = &yy; if (x->tv_usec > 999999) { x->tv_sec += x->tv_usec / 1000000; x->tv_usec %= 1000000; } if (y->tv_usec > 999999) { y->tv_sec += y->tv_usec / 1000000; y->tv_usec %= 1000000; } result->tv_sec = x->tv_sec - y->tv_sec; if ((result->tv_usec = x->tv_usec - y->tv_usec) < 0) { result->tv_usec += 1000000; result->tv_sec--; // borrow } return result->tv_sec < 0; } 

Aquí, la intención es clara y el código es fácil de entender.