上記の値はハッシュ表作成時に測定して、整数を10万個格納するたびに結果を出力していくといった感じです。
今回お聞ききしたいことは「衝突したキーの総数」の値の測定方法についてです。
コンパイルも通り、他の値は正しく計測できているのですが、「衝突したキーの総数」だけが正しく計測できません。
自分は「衝突がおきた番地の総数」の値に「格納しようとしたキーが衝突した回数」を足せばいいのかと考えていましたが、うまくいきませんでした。
どのようにすれば正しい結果を計測できるのでしょうか。
初投稿なので拙い文章なのですが、お許しください。どなたかご協力お願い致します。
使用しているOSはLinux、使用しているコンパイラはgccです。
ソースコードは以下に記して置きます。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef struct cell{ // バケットの構造体
int key ; // キー(整数値)
} CELL ;
CELL *Htable ; // ハッシュ表(開放番地法、連鎖法)
#define INTV -1 // 初期化定数
#define FLS -1 // 関数戻り値(エラー値)
#define FILENAME "/home/algorithm_data/integer1MS.dat"
#define HSIZE 1000000 // ハッシュ表の大きさ(100万)
#define DVS 999983 // 除数(HSIZEを超えない最大の素数)
#define CONSL 19 // 線形探査法の定数(開放番地法、連鎖法)
void init_tbl(CELL *, int); // ハッシュ表を初期化
int store(CELL *, int, int, int); //ハッシュ表に入力値を格納
int hash(int, int); //: ハッシュ関数(キー: 整数値)
int prob_lin(int, int, int); //: 線形探査法
CELL *allocate_Htable(int); //: ハッシュ表を主記憶に割付ける
int Table[HSIZE]={0}; //衝突番地総数を計測するための配列
int countkey=0; // 衝突キー総数のカウント用変数
int total[HSIZE]={}; // 衝突キー総数を計測するための配列
int main(void)
{
FILE *fin;
int i=0,j=0,n=0,data,rc,countadr=0;
int oun=HSIZE/10,max=0,min=0,average=0,average1=0;
CELL *Htable;
if((fin=fopen(FILENAME,"r"))==0)
{
printf("%s がオープンできません\n", FILENAME);
exit(0);
}
Htable = allocate_Htable(HSIZE) ;
init_tbl(Htable, HSIZE) ;
printf("\t要素数 \t 衝突番地総数 \t 衝突キー総数 \t 最大同族数 \t 最小同族数 \t 平均同族数\n");
while(fscanf(fin, "%d", &data)!=EOF)
{
rc=store(Htable,HSIZE,DVS,data);
if(rc==FLS)
printf("%dは格納できません\n",data);
if(++i%oun==0)
{
for(j=0;j<HSIZE;j++)
{
if(max<Table[j])//
max=Table[j];
if((min>Table[j])&&(Table[j]>1))//
min=Table[j];
if(Table[j]>1)//
{
countadr++;
average+=Table[j];
}
}
if(countadr!=0)//
average=average/countadr;
n++;
printf("%dU \t %d \t %d \t %d \t %d \t %d\n",n,countadr,countadr,countkey,max,min,average);
min=HSIZE;
countadr=0;
}
}
fclose(fin) ;
return 0;
}
CELL *allocate_Htable(int hsize)
{
CELL *Htable ;
Htable = (CELL *)malloc(sizeof(CELL) * hsize) ;
if (Htable == NULL) {
printf("空き記憶域がありません\n") ;
exit(1) ;
}
return Htable ;
}
void init_tbl(CELL *Htable, int hsize)
{
int i ;
for(i = 0; i < hsize; i++)
{
Htable[i].key = INTV ;
}
return ;
}
int store(CELL *table, int size, int cons, int inv)
{
unsigned int adr, count=1;
adr = hash(inv, cons) ;
while(count <= size)
{
if (table[adr].key == INTV)//格納されていない
{
table[adr].key = inv ;
return adr;
}
else if (table[adr].key != INTV)//格納済み
{
if(count==1)//初回の衝突のみカウント
countkey++;
if (table[adr].key == inv)
return FLS;
adr = prob_lin(size, CONSL, adr) ;
count++;
}
}
return FLS;
}
int hash(int key, int mod)
{
int hv ;
hv = key % mod;
Table[hv]++;
return hv ;
}
int prob_lin(int size, int cons, int adrs)
{
adrs += cons ;
if (size <= adrs)
adrs -= size ;
return adrs ;
}
番号:0 除数:999983 CONSL:19
要素数 衝突番地総数 衝突キー総数 最大同族数 最小同族数 平均同族数
1U 0 (+ 1) 0 (+ 1) 0 (+ 1) 0 (+ 1) 0 (+ 1)
2U 10107 (± 1) 20214 (± 1) 2 (± 1) 2 (± 1) 2 (± 1)
3U 28248 (± 1) 57559 (± 1) 3 (± 1) 2 (± 1) 2 (± 1)
4U 52317 (± 1) 108529 (± 1) 4 (± 1) 2 (± 1) 2 (± 1)
5U 81603 (± 1) 172295 (± 1) 5 (± 1) 2 (± 1) 2 (± 1)
6U 114436 (± 1) 246079 (± 1) 5 (± 1) 2 (± 1) 2 (± 1)
7U 149796 (± 1) 328202 (± 1) 6 (± 1) 2 (± 1) 2 (± 1)
8U 186856 (± 1) 417457 (± 1) 6 (± 1) 2 (± 1) 2 (± 1)
9U 224992 (± 1) 512505 (± 1) 7 (± 1) 2 (± 1) 2 (± 1)
10U 263720 (± 1) 612350 (± 1) 7 (± 1) 2 (± 1) 2 (± 1)