合計 昨日 今日

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

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: 焼きそば
[URL]
ぴよぴよ(353 ポイント)
Date: 2017年10月07日(土) 23:17
No: 1
(OFFLINE)

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

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

今回お聞ききしたいことは「衝突したキーの総数」の値の測定方法についてです。
コンパイルも通り、他の値は正しく計測できているのですが、「衝突したキーの総数」だけが正しく計測できません。
自分は「衝突がおきた番地の総数」の値に「格納しようとしたキーが衝突した回数」を足せばいいのかと考えていましたが、うまくいきませんでした。
どのようにすれば正しい結果を計測できるのでしょうか。
初投稿なので拙い文章なのですが、お許しください。どなたかご協力お願い致します。

使用しているOSはLinux、使用しているコンパイラはgccです。
ソースコードは以下に記して置きます。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#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)

Name: Math
[URL]
Date: 2017年10月14日(土) 21:11
No: 2
(OFFLINE)

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

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


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[19人]