探索の実行時間の計測

Question

配列と二分探索木によって，記号表の実装をしました．
これを改変して，項目の挿入個所や、探索箇所の実行時間を計測するプログラムを作りたいと考えています．
以下に二つのコードを乗せるのですが，前者は変更せずに，後者のみを改良して実装したいです，
後者のSTsearchを改変して，以下のようにしたのですが．実行してもなにも変化がありませんでした．
include<stdio.h>やinclude<time.h>は後者のファイルに書いてあります．
なぜ計測できないのか．どこにいれれば計測できるようになるのかを教えていただきたいです．
よろしくお願いします．

Item STsearch(Key v) 
{ start=clock();
  return searchR(head, v);
  end=clock();
  printf("%fsec\n",(double)(end-start)/CLOCKS_PER_SEC);

} 

##以下，ファイル

#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "ST.h"

int main(int argc, char *argv[])
{  int N, M, maxN = atoi(argv[1]), sw = atoi(argv[2]);
  Key v; Item item;
  STinit(maxN); srand(1);
  for (M = 0, N = 0; N < maxN; N++)
    {
      if (sw == 1) v = ITEMrand();
      else if (sw == 2) v = N+1;
      else if (ITEMscan(&v) == EOF) break;
      item = STsearch(v); if (item.key != NULLitem.key) continue;
      key(item) = v;
      STinsert(item); M++;
    }
  STsort(ITEMshow); 
  printf("\n");
  printf("%d keys ", N);
  printf("%d distinct keys\n", STcount());
  return 0;
}

#include <stdlib.h>
#include "Item.h"
typedef struct STnode* link;
struct STnode { Item item; link l, r; int N; };
static link head, z;
link NEW(Item item, link l, link r, int N)
{ link x = malloc(sizeof *x); 
  x->item = item; x->l = l; x->r = r; x->N = N;
  return x;
}
void STinit()
{ head = (z = NEW(NULLitem, 0, 0, 0)); }
int STcount(void) { return head->N; }
Item searchR(link h, Key v)
{ Key t = key(h->item);
  if (h == z) return NULLitem;
  if eq(v, t) return h->item;
  if less(v, t) return searchR(h->l, v);
  else return searchR(h->r, v);
}
Item STsearch(Key v) 
{ return searchR(head, v); } 
link insertR(link h, Item item)
{ Key v = key(item), t = key(h->item);
  if (h == z) return NEW(item, z, z, 1);
  if less(v, t) 
	   h->l = insertR(h->l, item);
  else h->r = insertR(h->r, item);
  (h->N)++; return h;
}

void STinsert(Item item)
{ head = insertR(head, item); }
void sortR(link h, void (*visit)(Item))
{ 
  if (h == z) return;
  sortR(h->l, visit);
  visit(h->item); 
  sortR(h->r, visit);
}
void STsort(void (*visit)(Item))
{ sortR(head, visit); } 

Comments

[kuma_kuma_]

> 二分探索木によって，記号表
ごめん二分木と記号表が結びつかない。どんな配列データから記号表を作ったの？
あと二分木の場合、再帰呼び出し？(何て呼べばよいのだろう？)になるから
全体的な速さを測るなら判るけど単体で測っても判別できるほどの秒数でる？
CPUクロックで限界に測れるミリ秒以下にならない？

[grape_ll]

自分の知識のなさから適切な表現が出来ていないのかもしれません．
確かにそれぞれで測定すると0.000secのようになってしまいそうです．ご指摘ありがとうございます．
全体の計測を目標にしたいと思います．

Answer 1

Item STsearch(Key v) 
{ start=clock();
  return searchR(head, v); ←ココでreturnしたら後続する2行が意味ないんだが
  end=clock();
  printf("%fsec\n",(double)(end-start)/CLOCKS_PER_SEC);
} 

Comments

[grape_ll]

確かにそうですね．見落としていました．
また，それぞれについての時間計測では下限を下回ってしまうというご指摘を受けたのですが，どこにこれらを挟むのが最適なのでしょうか．
initialでスタートしてsortの最初でend，標準出力という形でただしい動作となりますでしょうか．

[episteme]

僕の環境では CLOCKS_PER_SEC = 1000 でした。
つまり 1ms に満たない時間は計測不能となります。

start=clock();
searchR(head, v); を数万回繰り返す
end=clock();

とかやるっきゃないと思います(ちゃんと測りたいなら)

[grape_ll]

そうなのですね，ご回答ありがとうございました．