オープンアドレス法を使ったハッシュ表作成の際に生じる衝突に関しての問題

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
焼きそば
記事: 1
登録日時: 7年前

オープンアドレス法を使ったハッシュ表作成の際に生じる衝突に関しての問題

#1

投稿記事 by 焼きそば » 7年前

整数が100万個格納されているファイルを読み込み、オープンアドレス法と線形探索法を使用してハッシュ表を作成する際に、「衝突がおきた番地の総数」「衝突したキーの総数」「最大同族数、最小同族数、平均同族数」の値を調べるという課題に取り組んでいます。
上記の値はハッシュ表作成時に測定して、整数を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)

Math

Re: オープンアドレス法を使ったハッシュ表作成の際に生じる衝突に関しての問題

#2

投稿記事 by Math » 7年前

75行プレースホルダーとそのパラメーターには 6 の可変個引数が必要ですが、7個が指定されているようですが?

返信

“C言語何でも質問掲示板” へ戻る