c - timeval_subtract の説明

Question

「timeval_subtract」関数を使用して、2 つの構造体 timeval 型の間の経過時間を見つけるために、誰かが「y を更新して後の減算のためにキャリーを実行する」ために使用される数学の目的と段階を追って説明できますか? 関数の目的とプログラム内での実装方法は理解していますが、内部でどのように機能するかを理解したいのですが、これについての説明がどこにも見つからず、頭を包むことができないようですそれに。

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

経過時間を求めるGNU Cライブラリに関連して記述された関数ですhttps://ftp.gnu.org/old-gnu/Manuals/glibc-2.2.5/html_node/Elapsed-Time.html したがって、私は改善を求めているのではなく、その中で除算、加算、減算、乗算を行う理由の説明を求めています。これらの特定の算術演算は何を達成しますか?/なぜ行われるのか、行われないのか? 私はステップスルーを行いましたが、それでも頭を悩ませることはできません。私はそうするまで（そして誰かが私にそれを説明した後でも）そうし続けますが、すでにそれを理解している誰かから洞察を得たいと思っていました. プラットフォームは UNIX で、初めて使用しますが、関数内で行われている操作が変わるとは思いません。使用されているアルゴリズムよりも、実行されている演算に関する問題です。

score 15 · Accepted Answer

一見すると、struct timeval2 つの部分に分割された時間が含まれているように見えます。

tv_usec-マイクロ秒、理想的には常に1000000未満である必要がありますが、コードで示唆されているように、より大きな値が許可されているようです
tv_sec- 秒 (1000000 の倍数)

マイクロ秒単位の時間はtv_usec+ tv_sec* 1000000 です。

逆に、これが真であると予想されます。

tv_sec= マイクロ秒単位の時間 / 1000000
tv_usec= マイクロ秒単位の時間 % 1000000.

*xこの関数は、と*y(論理的には*x- )の間の時間差を計算し、それを別の, に*y格納するように見えます。struct timeval*result

簡単なテストプログラムからいくつかのヒントが得られます。

#include <stdio.h>

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

出力 ( ideone ):

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

最後のテスト結果から、関数は -(0:1) ではなく (-1):999999 を返すようです。両方の値は、マイクロ秒単位で同じ負の時間 (または時間差) を表します。

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

それで、それは実際にどのように機能しますか？

x->tv_usec>=の場合、おそらくy->tv_usec2 番目のみが実行され^ます:if

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

これifは、マイクロ秒部分だけの差が 1 秒より大きいかどうかをチェックします。そうである場合、この差の秒全体をy->tv_usec(マイクロ秒として) から差し引き、(秒として) に加算しy->tv_secます。*yこれは、時間を実際に変更することなく、単純に再分配します。ifより明確に見るために、これを次のように同等に書き直すことができます。

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

ここで注意すべき重要な点の 1 つは、入力*xが*y0からtv_usec999999 までの範囲内にある場合、この本体は実行さifれないことです (したがって、おそらく^*は実際には実行されません。 999999)。x->tv_usecy->tv_usectv_usecs

これの正味の効果は、今ifでは容易には明らかではありません。

ただし、ここで興味深いことが 1 つあります。この関数を*x= 0:1000001 および*y= 0:0 で呼び出すと、結果が間違ったものになります: difference = (-1):2000001 (代わりに 1:1) および関数の戻り値 = 1 (代わりに)の 0)。これは、関数が実際には適していないことを示唆していtv_usec > 1000000ますtv_usec > 999999。そして、この動作のために、関数は入力の負にも適していないと主張しtv_usecます。この振る舞いに直面して、これらのケースを無視するつもりです。すでに十分に間違っているように見えます。

最初に見てみましょう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;  
  }

コメントとコードが示唆するように、x->tv_usec<y->tv_usecの場合、「数字」の間の「桁上げ」を、足し算ではなく足し算であるかのように処理する必要があります。でも大丈夫です、見てみましょう。

ちょっと学校に戻りましょう。

37 - 12 はどうですか?

次のようにします。

7 - 2 = 5
3 - 1 = 2

したがって、37 - 12 = 25 です。

では、57 - 38 をどうするか。

次のようにします。

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

つまり、57 - 38 = 19 です。

そしてチェック：

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

この借用を処理する必要があるかどうかを確認します。

それで、ここで何が起こっているのですか？もう一度見てみましょう：

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

y->tv_usec>の場合x->tv_usec、2 つの差を秒単位で計算し、他の場合と同様に、ifこれらの秒単位をy->tv_secに加算してから減算しy->tv_usec、単純にの時間*yを変更せずに再配分します。

ここに追加される余分な 1 ( + 1)は、関数 ( ) の最後y->tv_secから減算されるため、この 1 は、57 - 38 = 19 の例で思い出した借用として機能します。x->tv_secresult->tv_sec = x->tv_sec - y->tv_sec;

借用自体と時間の再分配以外に、ここで何が起こっているのでしょうか?

前に言ったように、負の値tv_usecsと 999999 より大きい値は無視することにします。

これ(y->tv_usec - x->tv_usec) / 1000000で私は 0 になり、真に意味のある値tv_usecs(0 から 999999 を含む) だけが残されます。

したがって、if's条件が真の場合、基本的にから 1000000 を引き、y->tv_usecに 1 (借用) を追加しy->tv_secます。

これは 57 - 38 = 19 と同じです:

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

この 10 と同様に、1000000 が後でここに追加されます。result->tv_usec = x->tv_usec - y->tv_usec;

そして、これifが関数の要です。

同様の動作をする関数を作成する必要がある場合、入力時間が負でなく、マイクロ秒の部分が 999999 を超えないようにする必要があり、次のように記述します。

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

なんらかの奇妙な理由tv_usecで入力で > 999999 をサポートしたい場合は、最初に超過分をからtv_usecに移動してからtv_sec、次のように上記を実行します。

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

ここでは、意図が明確で、コードが理解しやすいです。

c - timeval_subtract の説明

1 に答える 1

Related

Reference